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 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 1/48 Modern Routing Tables I I I I $ route -n 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 Each entry in a routing table has 3 main items: A network address (the destination) A netmask length A next hop address Genmask 255.255.192.0 255.0.0.0 0.0.0.0 Flags U U UG Iface eth0 lo eth0 Routing Modern Routing Tables The Routing Algorithm Longest Prefix Example: CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 2/48 The Routing Algorithm I I I I I 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 Modern Routing Tables The Routing Algorithm Longest Prefix Example: CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 3/48 Longest Prefix I I I So what does “longest prefix match” mean? To see if the prefix matches, N Bitwise AND netmask with destination N Bitwise AND netmask with network from routing table entry N 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 Modern Routing Tables The Routing Algorithm Longest Prefix Example: CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 4/48 Example: I 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 Routing Modern Routing Tables The Routing Algorithm Longest Prefix Example: CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages I I I How about 192.168.128.48? 192.168.25.10? 192.169.0.1? SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 5/48 The Big Emergency I In the early 90s, it became apparent that two problems were quickly going to become overwhelming: N Address depletion — we were running out of IP addresses N Router table explosion — the routing tables were growing too fast for the router hardware to cope Routing CIDR The Big Emergency The Solution: CIDR and NAT Address Depletion Router Table Explosion How does CIDR solve them? Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 6/48 The Solution: CIDR and NAT I I I Two solutions were developed: CIDR (Classless Internet Domain Routing), and NAT (Network Address Translation). N NAT allows a firewall or router to present one address to the outside world, but many to the inside. N In Linux, use iptables. N Use private addresses: N 192.168.0.0/16 N 172.12.0.0/12 N 10.0.0.0/8 Routing CIDR The Big Emergency The Solution: CIDR and NAT Address Depletion Router Table Explosion How does CIDR solve them? Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 7/48 Address Depletion I I I I I 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. N Class C was too wasteful for this. Routing CIDR The Big Emergency The Solution: CIDR and NAT Address Depletion Router Table Explosion How does CIDR solve them? Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 8/48 Router Table Explosion I I I I I As class B addresses became scarce, SMEs were given a number of class C network allocations 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 CIDR The Big Emergency The Solution: CIDR and NAT Address Depletion Router Table Explosion How does CIDR solve them? Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 9/48 How does CIDR solve them? I I I New address allocations can be sized accurately to the need N 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 CIDR The Big Emergency The Solution: CIDR and NAT Address Depletion Router Table Explosion How does CIDR solve them? Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 10/48 Aggregating routes I Routers summarise routes themselves when they use classless routing protocols such as: N RIP2 N OSPF N BGP Routing CIDR Aggregating Routes Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 11/48 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 Routing CIDR Aggregating Routes 200.200.24/24 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 Router A Router C Y Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate 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 Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 12/48 With Route Summarisation 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 D B’s routing table advertised to D 200.200.24/22 200.200.28/24 ..... Z Routing CIDR Router C Y Aggregating Routes Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate A’s routing table advertised to B 200.200.24/22 200.200.28/24 Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 13/48 Explanation I I The first diagram shows all subnets behind router A advertised everywhere N 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 N The routers must be running a classless routing protocol such as OSPF or RIP2. Routing CIDR Aggregating Routes Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 14/48 How the Routes were Summarised I I I I I 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 N So these can be summarised into: N 200.200.24.0/22 200.200.28.0/24: 2810 = 000111002 N This cannot be summarised with the other routes, so it must be advertised separately. Routing CIDR Aggregating Routes Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 15/48 Route Aggregation: NetAddr::IP I I I I 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 CIDR Aggregating Routes Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 16/48 route-aggregate #! /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"; Routing CIDR Aggregating Routes Aggregating routes Without Route Summarisation With Route Summarisation Explanation How the Routes were Summarised Route Aggregation: NetAddr::IP route-aggregate Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 17/48 Designing an Addressing Scheme I I 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 CIDR Aggregating Routes Addressing Scheme Designing an Addressing Scheme Example Problem Example Problem Solution — Links Solution — Larger Subnets — 1 Solution — Larger Subnets — 2 Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 18/48 Example Problem I I I Given a physical network layout as shown in the figure below Has 10 subnets (excluding the link Z) All three routers support CIDR addressing Router A X Router C Z Router B Y Routing CIDR Aggregating Routes Addressing Scheme Designing an Addressing Scheme Example Problem Example Problem Solution — Links Solution — Larger Subnets — 1 Solution — Larger Subnets — 2 Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages subnet 1 subnet 2 subnet 3 subnet 4 subnet 5 subnet 6 subnet 7 subnet 8 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 19/48 Example Problem I I You are given: N The information on previous slide N Two address blocks: I 172.19.0/20 I 172.19.128/28 Requirements are: N Subnets 1 to 8 must each support up to 140 computers N Subnets must be assigned to allow maximum route aggregation N Any unused addresses must be kept in single blocks so that they can be used elsewhere or for future expansion Routing CIDR Aggregating Routes Addressing Scheme Designing an Addressing Scheme Example Problem Example Problem Solution — Links Solution — Larger Subnets — 1 Solution — Larger Subnets — 2 Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 20/48 Solution — Links I I 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 log2 (2+2) = 22 , giving a prefix size of 32 − 2 = 30, i.e., /30. Allocate adjacent subnets to links X and Y, so that router C can aggregate routes to them. subnet subnet X subnet Y network 172.19.128.0/30 172.19.128.4/30 Routing CIDR Aggregating Routes Addressing Scheme Designing an Addressing Scheme Example Problem Example Problem Solution — Links Solution — Larger Subnets — 1 Solution — Larger Subnets — 2 Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages I I SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 21/48 Solution — Larger Subnets — 1 I I 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 log2 (140+2) = 28 ; so prefix length = 32 − 8 = 24). Routing CIDR Aggregating Routes Addressing Scheme Designing an Addressing Scheme Example Problem Example Problem Solution — Links Solution — Larger Subnets — 1 Solution — Larger Subnets — 2 Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 22/48 Solution — Larger Subnets — 2 I Let us allocate the lowest 8 /24 blocks from 172.19.0/20: subnet subnet 1 subnet 2 subnet 3 subnet 4 subnet 5 subnet 6 subnet 7 subnet 8 network 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 Routing CIDR Aggregating Routes Addressing Scheme Designing an Addressing Scheme Example Problem Example Problem Solution — Links Solution — Larger Subnets — 1 Solution — Larger Subnets — 2 Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages I In a tutorial exercise, you will determine what routes each router advertises. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 23/48 order Gateway Protocol — BGP]Gateway Protocols 23-1 Routing CIDR Aggregating Routes Gateway Protocols Border Gateway Protocol — BGP Addressing Scheme Gateway Protocols Classes of Routing Protocols Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 24/48 Classes of Routing Protocols I I I I I I Distance Vector or Link-State are two types of routing protocols. Another way to classify routing protocols is as follows: Intra-Domain routing: N routing of packets within the same Autonomous System (AS) N Interior Gateway Protocol IGP, RIP 2, OSPF, . . . Inter-Domain routing: N Inter-Domain routing is between multiple Autonomous Systems. N 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 CIDR Aggregating Routes Addressing Scheme Gateway Protocols Classes of Routing Protocols Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 25/48 Gateway Protocols I I 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. Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols Classes of Routing Protocols Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages I EGP I 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 N earlier versions don’t support CIDR, so are obsolete SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 26/48 Border Gateway Protocol BGP I BGP I I I 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 CIDR Aggregating Routes Addressing Scheme 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 BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 27/48 Single-homed Autonomous Systems Only one connection between stub network and a single ISP Stub Network ISP Routing CIDR Aggregating Routes Addressing Scheme 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 BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 28/48 Single-homed Autonomous Systems I I I I Single homed AS, or stub AS N 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. N Using static/default routes N Using IGP, such as OSPF and RIP N 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 CIDR Aggregating Routes Addressing Scheme 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 BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 29/48 Multi-homed Non-transit AS I 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. Routing CIDR Aggregating Routes Addressing Scheme 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 BGP Attributes Preferring One Link BGP Messages I I 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. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 30/48 Multi-homed Transit AS Routing Source CIDR Aggregating Routes Addressing Scheme 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 BGP BGP Destination BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 31/48 Multi-homed Transit AS I I I 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 CIDR Aggregating Routes Addressing Scheme 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 BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 32/48 BGP: to use or not to use I I I 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 CIDR Aggregating Routes Addressing Scheme 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 BGP Attributes Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 33/48 Routing CIDR Aggregating Routes BGP Attributes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes BGP BGP Attributes BGP Weight Attribute Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 34/48 BGP I I I I 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 CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes BGP BGP Attributes BGP Weight Attribute Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 35/48 BGP Attributes I I 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: N Weight (Cisco proprietary, highest priority) N Local Preference N AS Path N Origin N Multi-Exit Discriminator (lowest priority) Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes BGP BGP Attributes BGP Weight Attribute Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 36/48 BGP Weight Attribute I I I 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 CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes BGP BGP Attributes BGP Weight Attribute Preferring One Link BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 37/48 BGP Local Preference Attribute I I I 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 CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes 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 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 38/48 BGP LOCAL_PREF local pref = 100 Router A preferred route to 172.16.1/24 Routing Router C CIDR Aggregating Routes Addressing Scheme Gateway Protocols 172.17.2/24 172.16.1/24 BGP: AS Types BGP Attributes Preferring One Link BGP Local Preference Attribute BGP LOCAL_PREF BGP MED Attribute BGP MULTI_EXIT_DISC Router B local pref = 50 AS100 Router D AS200 BGP: Selecting one Link BGP AS_path Attribute BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 39/48 BGP MED Attribute I I I 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 CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes 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 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 40/48 BGP MULTI_EXIT_DISC Routing Router A 172.17.2/24 MED=5 preferred route Router C CIDR Aggregating Routes Addressing Scheme Gateway Protocols 172.17.2/24 172.16.1/24 BGP: AS Types BGP Attributes Preferring One Link 172.17.2/24 MED=10 Router B AS100 Router D AS200 BGP Local Preference Attribute BGP LOCAL_PREF BGP MED Attribute BGP MULTI_EXIT_DISC BGP: Selecting one Link BGP AS_path Attribute BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 41/48 BGP: Selecting one Link Local Pref = 100 Router A preferred route to 172.16.1/24 Routing CIDR Router C Aggregating Routes Addressing Scheme Gateway Protocols 172.17.2/24 MED=5 172.17.2/24 preferred route to 172.17.2/24 172.16.1/24 BGP: AS Types BGP Attributes Preferring One Link BGP Local Preference Attribute BGP LOCAL_PREF 172.17.2/24 MED=10 Router B Local Pref = 50 AS100 Router D AS200 BGP MED Attribute BGP MULTI_EXIT_DISC BGP: Selecting one Link BGP AS_path Attribute BGP Messages SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 42/48 BGP AS_path Attribute I I I 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. N 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. N The route that contains the shortest AS_path (i.e. the order list that contains the shortest list of AS numbers) is selected. Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes 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 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 43/48 BGP Message Types I I I I I 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. BGP Four Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages BGP Message Types BGP Packet Formats Open Message Update Message Notification Message SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 44/48 BGP Packet Formats I All BGP message types use the basic packet header 16 Marker 2 Length 1 Type variable Data Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages BGP Message Types BGP Packet Formats Open Message Update Message Notification Message Field length in bytes I The basic packet header contains: N a 16-byte marker field which contains authentication value N a 2-byte length field which contains the total length of the message N a 1-byte type field which specifies the message type N data of variable length, this field carry the upper-layer information SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 45/48 Additional Fields: Open Message I I 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: N BGP version number (i.e., 4) N AS number of sender N hold-time N BGP identifier of the sender (IP address) N optional parameters such as authentication data. 2 2 4 BGP ID 1 Length of optional param 4 Optional parameters Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages BGP Message Types BGP Packet Formats Open Message Update Message Notification Message Field length in bytes 1 version AS number hold time SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 46/48 BGP Additional Fields: Update Message I Additional fields of Update Message contains: N Withdrawn routes: a list of IP address prefixes for the routes being withdrawn N Network layer reachability information: a list of IP address prefixes (e.g. 10.1.1.0/24) for the advertised routes N Path attributes (such as origin, AS_path, MED, LOCAL_PREF, . . . ) that describe the characteristics of the advertised path. N Unfeasible routes length, i.e., length of withdrawn routes field N Total path attribute length, i.e., length of the path attributes field variable withdrawn routes 2 path attributes length variable path attributes variable network layer reachability info Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages BGP Message Types BGP Packet Formats Open Message Update Message Notification Message Field length in bytes 2 unfeasible routes length SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 47/48 BGP Additional Fields: Notification Message I Additional fields of Notification Message contains: N Error code that indicates the type of error that occurred. N Error sub code N error data. 1 error code 1 error subcode variable error data Routing CIDR Aggregating Routes Addressing Scheme Gateway Protocols BGP: AS Types BGP Attributes Preferring One Link BGP Messages BGP Message Types BGP Packet Formats Open Message Update Message Notification Message Field length in bytes SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 48/48