Routers and Routing Routing Tables and Route Summarisation Nick Urbanik Copyright Conditions: Open Publication License (see http://www.opencontent.org/openpub/) Department of Information and Communications Technology Routing Modern Routing Tables . . . . . . . . . The Routing Algorithm . . . . . . . . . Longest Prefix . . . . . . . . . . . . . . . . Example: . . . . . . . . . . . . . . . . . . . CIDR The Big Emergency . . . . . . . . . . . . The Solution: CIDR and NAT . . . . Address Depletion . . . . . . . . . . . . . Router Table Explosion . . . . . . . . . How does CIDR solve them? . . . . . Aggregating Routes Aggregating routes. . . . . . . . . . . . . Without Route Summarisation . . . . With Route Summarisation . . . . . . Explanation . . . . . . . . . . . . . . . . . How the Routes were Summarised. . Route Aggregation: NetAddr::IP . . route-aggregate . . . . . . . . . . . . . Addressing Scheme Designing an Addressing Scheme. . . Example Problem . . . . . . . . . . . . . Example Problem . . . . . . . . . . . . . Solution — Links. . . . . . . . . . . . . . Solution — Larger Subnets — 1 . . . Solution — Larger Subnets — 2 . . . Gateway Protocols Classes of Routing Protocols. . . . . . Gateway Protocols. . . . . . . . . . . . . BGP: AS Types Border Gateway Protocol BGP . . . . Single-homed Autonomous Systems. Single-homed Autonomous Systems. Multi-homed Non-transit AS . . . . . Multi-homed Transit AS. . . . . . . . . Multi-homed Transit AS. . . . . . . . . BGP: to use or not to use. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide 2 3 4 5 slide 6 slide 7 slide 8 slide 9 slide 10 slide slide slide slide slide slide slide slide slide slide slide slide slide 11 12 13 14 15 16 17 18 19 20 21 22 23 . . . . . . . . . . . . . . . . . slide 25 . . . . . . . . . . . . . . . . . slide 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide slide slide slide 27 28 29 30 31 32 33 BGP Attributes BGP. . . . . . . . . . . . . . . . . . . . . BGP Attributes. . . . . . . . . . . . . BGP Weight Attribute . . . . . . . . Preferring One Link BGP Local Preference Attribute . BGP LOCAL PREF. . . . . . . . . . . . BGP MED Attribute . . . . . . . . . BGP MULTI EXIT DISC. . . . . . . . BGP: Selecting one Link . . . . . . BGP AS path Attribute . . . . . . . BGP Messages BGP Message Types . . . . . . . . . BGP Packet Formats . . . . . . . . . Open Message . . . . . . . . . . . . . . Update Message . . . . . . . . . . . . Notification Message . . . . . . . . . Modern Routing Tables . . . . . . . . . . . . . . . . . . . slide 35 . . . . . . . . . . . . . . . . . . . slide 36 . . . . . . . . . . . . . . . . . . . slide 37 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide slide slide slide slide slide slide slide 38 39 40 41 42 43 44 45 46 47 48 Each entry in a routing table has 3 main items: A network address (the destination) A netmask length A next hop address $ Kernel IP routing table Destination Gateway 172.19.64.0 0.0.0.0 127.0.0.0 0.0.0.0 0.0.0.0 172.19.127.254 ¡¢ £ ¤¥ ¦ §         Genmask 255.255.192.0 255.0.0.0 0.0.0.0 Flags U U UG Iface eth0 lo eth0 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 2 The Routing Algorithm For a given destination IP address Search the routing table for the longest prefix match for the address Extract the next hop address from the routing table entry Send the packet to the next hop address If no match found, report that the destination is unreachable. Routing Tables and Route Summarisation — slide 3               SNM — ver. 1.3 Longest Prefix So what does “longest prefix match” mean? To see if the prefix matches, ◦ Bitwise AND netmask with destination ◦ Bitwise AND netmask with network from routing table entry ◦ If the two results are equal, then the prefix matches If we do the same for all entries in the routing table, the match with the longest netmask wins. Routing Tables and Route Summarisation — slide 4   SNM — ver. 1.3 Example: Given this routing table, where does the packet with destination 192.168.0.3 go to? 192.168.0.0 192.168.25.0 192.168.0.0 0.0.0.0 0.0.0.0 0.0.0.0 172.19.35.254 202.180.160.251 255.255.255.0 255.255.255.0 255.255.0.0 0.0.0.0 U U UG UG eth0 vmnet1 ppp1 ppp0   The Solution: CIDR and NAT Two solutions were developed: cidr (Classless Internet Domain Routing), and nat (Network Address Translation). ◦ nat allows a firewall or router to present one address to the outside world, but many to the inside. ◦ In Linux, use iptables. ◦ Use private addresses: Routing Tables and Route Summarisation — slide 5       How about 192.168.128.48? 192.168.25.10? 192.169.0.1?     SNM — ver. 1.3 ◦ 192.168.0.0/16 ◦ 172.12.0.0/12 ◦ 10.0.0.0/8 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 7   Address Depletion Class C was too small for medium sized enterprises Class B was too big Many organisations asked for (and received) class B networks when they needed only a /22 or /21 network This used up the available 232 addresses too fast Later there was a need for small Internet allocations of 1 or 2 addresses. ◦ Class C was too wasteful for this. Routing Tables and Route Summarisation — slide 8   The Big Emergency In the early 90s, it became apparent that two problems were quickly going to become overwhelming: ◦ Address depletion — we were running out of IP addresses ◦ Router table explosion — the routing tables were growing too fast for the router hardware to cope SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 6       SNM — ver. 1.3     Router Table Explosion As class B addresses became scarce, smes were given a number of class C network allocations   Without Route Summarisation B’s routing table advertised to C 200.200.24/24 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 ..... V Router B W 200.200.24/24 But each class C needed a separate routing table advertisement Local information about the internal network structure of a company needed to be advertised world wide This did not scale By now routing would need much more cpu and ram than is currently used, and the Internet would have slowed further. Routing Tables and Route Summarisation — slide 9 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 Router A Router C Y     A’s routing table advertised to B 200.200.24/24 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 X Router D B’s routing table advertised to D 200.200.24/24 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 ..... Z     SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 12 SNM — ver. 1.3 With Route Summarisation How does CIDR solve them? New address allocations can be sized accurately to the need ◦ When requesting addresses, the authority (http://www.apnic.net/) will reserve some addresses for future growth if you specify you will need them New address allocations are made taking into account neighbouring networks Aim is to summarise many routes into as few routes as possible. Routing Tables and Route Summarisation — slide 10     Routing table advertised by A is much smaller after summarisation 200.200.24/24 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 Router A V B’s routing table advertised to C 200.200.24/22 200.200.28/24 ..... W Router B X Router C Y A’s routing table advertised to B 200.200.24/22 200.200.28/24 Router D B’s routing table advertised to D 200.200.24/22 200.200.28/24 ..... Z SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 13 SNM — ver. 1.3   Explanation The first diagram shows all subnets behind router A advertised everywhere ◦ This is because the routers are unable to summarise the routes The second diagram shows the subnets behind A summarised into two routes instead of 5 ◦ The routers must be running a classless routing protocol such as ospf or rip2.     Aggregating routes Routers summarise routes themselves when they use classless routing protocols such as: ◦ rip2 ◦ ospf SNM — ver. 1.3   ◦ bgp Routing Tables and Route Summarisation — slide 11 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 14 How the Routes were Summarised 200.200.24.0/24: 2410 = 000110002 200.200.25.0/24: 2510 = 000110012 200.200.26.0/24: 2610 = 000110102 200.200.27.0/24: 2710 = 000110112 ◦ So these can be summarised into: ◦ 200.200.24.0/22 200.200.28.0/24: 2810 = 000111002 ◦ This cannot be summarised with the other routes, so it must be advertised separately. SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 15     © #! /usr/bin/perl -w use NetAddr::IP; $| = 1; our ( @ips, @ip ); if ( @ARGV ) { @ips = @ARGV } else { @ips = ; } foreach my $ip ( @ips ) { push @ip, NetAddr::IP->new( $ip ); } my @aggregated = NetAddr::IP::compact( @ip ); print "@aggregated\n"; SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 17 Route Aggregation:         © ¨     There is a Perl module for working with IP addresses (of course): NetAddr::IP Includes the method compact(), which takes a list of networks and returns a list of summarised address blocks. The next slide shows a little program that will aggregate address blocks given on the command line or on standard input. Routing Tables and Route Summarisation — slide 16   Designing an Addressing Scheme Given one (or two) blocks of addresses, how do we allocate addresses to a network involving routers? Need also to allocate addresses to links between routers—these need their own little subnet Routing Tables and Route Summarisation — slide 18         SNM — ver. 1.3 SNM — ver. 1.3   © !" " © " !   Example Problem Given a physical network layout as shown in the figure below Has 10 subnets (excluding the link Z) All three routers support cidr addressing subnet 1 subnet 2 subnet 3 subnet 4 subnet 5 Router B Y Router A X Router C Z   Solution — Links General strategy: determine the lower and upper limits on each subnet. Allocate networks in the order of smallest to largest. The smallest block of addresses is only suitable for allocating to the links, so allocate them first. Minimum size of each serial link is 4, as 2 prefix size of 32 − 2 = 30, i.e., /30. log2 (2+2)         = 22 , giving a     Allocate adjacent subnets to links X and Y, so that router C can aggregate routes to them. subnet network subnet 6 subnet 7 subnet 8 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 19 subnet X 172.19.128.0/30 subnet Y 172.19.128.4/30 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 21 Example Problem You are given: ◦ The information on previous slide ◦ Two address blocks: – 172.19.0/20 – 172.19.128/28 Requirements are: ◦ Subnets 1 to 8 must each support up to 140 computers ◦ Subnets must be assigned to allow maximum route aggregation ◦ Any unused addresses must be kept in single blocks so that they can be used elsewhere or for future expansion SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 20       Solution — Larger Subnets — 1 For each of the larger subnets, minimum size is 256, i.e., a /24 subnet 28 is the lowest power of 2 that contains 140+2. (2 so prefix length = 32 − 8 = 24). log2 (140+2)   = 28 ; SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 22 Solution — Larger Subnets — 2 Let us allocate the lowest 8 /24 blocks from 172.19.0/20: subnet subnet subnet subnet subnet subnet subnet subnet subnet     Border Gateway Protocol — BGP network 1 2 3 4 5 6 7 8 172.19.0.0/24 172.19.1.0/24 172.19.2.0/24 172.19.3.0/24 172.19.4.0/24 172.19.5.0/24 172.19.6.0/24 172.19.7.0/24 In a tutorial exercise, you will determine what routes each router advertises. Routing Tables and Route Summarisation — slide 23 SNM — ver. 1.3 Classes of Routing Protocols Distance Vector or Link-State are two types of routing protocols. Another way to classify routing protocols is as follows: Intra-Domain routing: ◦ routing of packets within the same Autonomous System (AS) ◦ Interior Gateway Protocol igp, rip 2, ospf, . . . Inter-Domain routing: ◦ Inter-Domain routing is between multiple Autonomous Systems. ◦ Exterior Gateway Protocol egp, Border Gateway Protocol bgp Autonomous System (as) refers to a group of routers (i.e. networks) administered by the same organization. Each as is assigned a number. as numbers range from 1 to 65,535, with 64512 to 65535 reserved for private (internal networks) use. Routing Tables and Route Summarisation — slide 25       Gateway Protocols SNM — ver. 1.3       Gateway Protocols Inter-domain and Intra-domain routing protocols are also referred as Exterior and Interior routing protocols respectively. The first widely used exterior gateway protocol is called Exterior Gateway Protocol (egp), it was designed to communicate reachability among the core routers of arpanet. egp is more a reachability protocol than a routing protocol, it only tests reachability but not makes intelligent routing decisions. egp is replaced by the Border Gateway Protocol (bgp). The current version of bgp is version 4 ◦ earlier versions don’t support cidr, so are obsolete SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 26   Single-homed Autonomous Systems Single homed as, or stub as ◦ An as has only one exit point to outside networks. Quite often, a single-homed as is referred as a stub network. An isp can use three different methods to advertise a customer’s network, a single-homed as, so that the Internet community can learn about such a network. ◦ Using static/default routes ◦ Using igp, such as ospf and rip ◦ Using egp, such as bgp In most cases, simple static routes are used. bgp is not commonly used due to the difficulty stub networks have with getting a registered as number. Routing Tables and Route Summarisation — slide 29               Border Gateway Protocol BGP bgp is an inter-domain (inter-as) routing protocol. However, bgp can also be used within an as. When used between as, bgp is referred as Exterior bgp (ebgp). When used within an as, bgp is referred as Interior bgp (ibgp). bgp is mainly used in core routers in the Internet, for connections between Internet Service Providers. Large networks (universities and big enterprises) also use bgp to connect to isps. Within these networks, however, other Interior Gateway Protocols (such as rip or ospf) are used rather than ibgp. Routing Tables and Route Summarisation — slide 27         SNM — ver. 1.3     Multi-homed Non-transit AS An as is a multi-homed system if it has more than one exit point to the outside networks. An as connected to the Internet can be multi-homed to a single isp or multiple isps. Non-transit refers to the fact that transit traffic does not pass through the as. A non-transit as would advertise only its own routes to the isps to which it connects, it would not advertise routes that it learned from one isp to another. A multi-homed Non-transit as does not really need to run bgp with their isps. Other routing methods can be used instead. However, some isps may prefer the customers to use bgp. Routing Tables and Route Summarisation — slide 30 SNM — ver. 1.3 Single-homed Autonomous Systems Only one connection between stub network and a single ISP Stub Network ISP SNM — ver. 1.3   Routing Tables and Route Summarisation — slide 28 SNM — ver. 1.3 Multi-homed Transit AS Source BGP: to use or not to use If the routing policy of an as is consistent with the isp’s policy, it is not necessary to use bgp to exchange routing information with the isp. If the as and isp’s policy are different, bgp is preferred. If the as uses different isps for redundancy, (or load sharing) a combination of static and default routes could be used instead of bgp. If the as uses multiple connections to isps that are active at the same time, bgp is preferred. Routing Tables and Route Summarisation — slide 33   BGP   BGP Destination SNM — ver. 1.3 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 31 BGP Attributes BGP BPG is designed to be used on the Internet. Many route parameters, called attributes, can be used with bgp so that better routing policies are provided. bgp supports cidr which helps reduce the routing table size. bgp packets are carried through tcp connection. When two neighbor routers wish to exchange bgp route information, a tcp connection is established first. bgp routers do not send periodic updates. Full routing information are exchanged when the tcp connection is first established, afterward, only changed routes will be advertised. Also, only the optimal path (i.e. there are alternate paths) to a destination network is advertised through routing updates. Routing Tables and Route Summarisation — slide 35   Multi-homed Transit AS A multi-homed transit as can be used for transit traffic of other autonomous systems. bgp can be used internally so that multiple border routers in the same as can share bgp information. ibgp is run inside the as. Routers that route ibgp traffic are transit routers. ebgp is run between the local and the external ass. Routers on the boundary of an as that use ebgp to exchange information with the isp are border (or edge) routers. Routing Tables and Route Summarisation — slide 32         SNM — ver. 1.3     SNM — ver. 1.3   BGP Attributes Routes learned via bgp have associated properties that are used to determine the best route to a destination when multiple paths exist. These properties are referred to as bgp attributes. The following bgp attributes can be used to determine the best path: ◦ Weight (Cisco proprietary, highest priority) ◦ Local Preference ◦ as Path ◦ Origin ◦ Multi-Exit Discriminator (lowest priority) SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 36   BGP Local Preference Attribute The local preference attribute is used to prefer an exit point from the local autonomous system as. If there are multiple exit points from the as, the local preference attribute is used to select the exit point for a specific route. For example, two routers (A & B) connect a local as100 to another as200, and both routers receive route advertisement for a particular network 10.0.0.0/8. If router A is set a local preference value of 50 while router B is set a value of 55, the route through router B will be used to forward traffic from local as to the particular network 10.0.0.0/8. Weight attribute is similar to the local preference attribute in that they are used to set an outgoing path. Their difference is that weight attribute is local to a router while local preference attribute is propagated throughout the local as. Routing Tables and Route Summarisation — slide 38         SNM — ver. 1.3 BGP Weight Attribute Weight is a Cisco-defined attribute that is local to a router. The weight attribute is not advertised to neighboring routers. If the router learns about more than one route to the same destination, the route with the highest weight will be preferred. When there are two routes/paths to a destination, both will be maintained in the bgp routing table. However, only the route with the highest weight will be installed in the ip routing table. That is, when forwarding ip packets, the route with the highest weight is used. Routing Tables and Route Summarisation — slide 37   BGP #$ %  #  &' local pref = 100 Router A preferred route to 172.16.1/24 ( Router C   172.17.2/24 172.16.1/24   Router B local pref = 50 AS100 Router D AS200 SNM — ver. 1.3 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 39 BGP MED Attribute The multi-exit discriminator (med) is used to suggest an external as regarding the preferred route into the local as that is advertising the route. The external as, which receive the meds, may not take the “suggestion” and may use other bgp attributes for route selection. meds are advertised throughout the local as. Routing Tables and Route Summarisation — slide 40  ' 2 1 3 4 % )0 #1   BGP AS path Attribute When a route advertisement passes through an autonomous system, the as number is added to an ordered list of as numbers that the route advertisement has traversed. The AS path attribute can be used to detect routing loops. ◦ If a router receives a route advertisement with an ordered list containing an as number the same as the as that the router belongs to, it ignores the route advertisement. The AS path attribute can be used to select the better path. ◦ The route that contains the shortest AS path (i.e. the order list that contains the shortest list of as numbers) is selected. SNM — ver. 1.3 172.16.1/24       SNM — ver. 1.3 BGP     Router A 172.17.2/24 MED=5 preferred route Router C Routing Tables and Route Summarisation — slide 43 172.17.2/24 172.17.2/24 MED=10 Router B AS100 Router D AS200 BGP Message Types Four bgp message types are specified in RFC 1771 (i.e. bgp version 4). The Open Message opens a bgp communication session between peers and is the first message sent by each side after a tcp connection is established. The Update Message is used to provide routing updates to other bgp systems, allowing routers to construct a consistent view of the network topology. Update messages can withdraw one or more unfeasible routes from the routing table and simultaneously can advertise a route. The Notification Message is sent when error condition is detected. Notifications are used to close an active session. The Keep-alive Message notifies bgp peers that a device is active. Routing Tables and Route Summarisation — slide 44   SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 41   BGP: Selecting one Link Local Pref = 100 Router A preferred route to 172.16.1/24 Router C 172.17.2/24 MED=5 172.17.2/24 preferred route to 172.17.2/24 172.16.1/24 172.17.2/24 MED=10 Router B Local Pref = 50 AS100 Router D AS200 SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 42 SNM — ver. 1.3       BGP Packet Formats All bgp message types use the basic packet header Field length in bytes   BGP Additional Fields: Update Message Additional fields of Update Message contains: ◦ Withdrawn routes: a list of IP address prefixes for the routes being withdrawn ◦ Network layer reachability information: a list of ip address prefixes (e.g. 10.1.1.0/24) for the advertised routes ◦ Path attributes (such as origin, as path, med, LOCAL PREF, . . . ) that describe the characteristics of the advertised path. ◦ Unfeasible routes length, i.e., length of withdrawn routes field ◦ Total path attribute length, i.e., length of the path attributes field Field length in bytes 2 unfeasible routes length   16 Marker 2 Length 1 Type variable Data The basic packet header contains: ◦ a 16-byte marker field which contains authentication value ◦ a 2-byte length field which contains the total length of the message ◦ a 1-byte type field which specifies the message type ◦ data of variable length, this field carry the upper-layer information SNM — ver. 1.3   Routing Tables and Route Summarisation — slide 45 variable withdrawn routes 2 path attributes length variable path attributes variable network layer reachability info SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 47 Additional Fields: Open Message Open, update and notification messages have additional fields, but keep-alive messages use only the basic packet header. Additional fields of the Open Message contains: ◦ bgp version number (i.e., 4) ◦ AS number of sender ◦ hold-time ◦ bgp identifier of the sender (ip address) ◦ optional parameters such as authentication data. Field length in bytes 1 BGP Additional Fields: Notification Message Additional fields of Notification Message contains: ◦ Error code that indicates the type of error that occurred. ◦ Error sub code ◦ error data. Field length in bytes 1 error code       1 error subcode variable error data SNM — ver. 1.3 2 2 4 BGP ID 1 Length of optional param 4 Optional parameters Routing Tables and Route Summarisation — slide 48 version AS number hold time SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 46