Routing Tables and Route Summarisation - p. 1/48 Routing Tables and Route Summarisation - p. 3/48 Solution — Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 21 Solution — Larger Subnets — 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 22 Solution — Larger Subnets — 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 23 Gateway Protocols Classes of Routing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 25 Gateway Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 26 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. Given this routing table, where does the packet with destination 192.168.0.3 go to? Routing Tables and Route Summarisation The Routing Algorithm Nick Urbanik Border Gateway Protocol BGP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 27 Single-homed Autonomous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 28 Single-homed Autonomous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 29 Multi-homed Non-transit AS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 30 Multi-homed Transit AS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 31 Multi-homed Transit AS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 32 BGP: to use or not to use. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 33 BGP Attributes BGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 35 BGP Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 36 BGP Weight Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 37 Preferring One Link BGP Local Preference Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 38 BGP LOCAL Department of Information and Communications Technology (see http://www.opencontent.org/openpub/) Routers and Routing BGP: AS Types Copyright Conditions: Open Publication License Example: 255.255.255.0 255.255.255.0 255.255.0.0 0.0.0.0 U U UG UG PREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 39 SNM — ver. 1.3 SNM — ver. 1.3 BGP: Selecting one Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 42 BGP AS path Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 43 0-1 Routing Tables and Route Summarisation - p. 2/48 192.168.0.0 192.168.25.0 192.168.0.0 0.0.0.0 BGP MULTI EXIT DISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 41 Contents Routing Modern Routing Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 2 The Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 3 Longest Prefix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 4 Example: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 5 CIDR The Big Emergency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 6 The Solution: CIDR and NAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 7 Address Depletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 8 Router Table Explosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 9 How does CIDR solve them? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 10 Aggregating Routes Aggregating routes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 11 Without Route Summarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 12 With Route Summarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 13 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 14 How the Routes were Summarised . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 15 Route Aggregation: BGP Messages BGP Message Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 44 BGP Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 45 Open Message. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 46 Update Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 47 Each entry in a routing table has 3 main items: A network address (the destination) A netmask length A next hop address Modern Routing Tables Notification Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 48 NetAddr::IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 16 route-aggregate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 17 Addressing Scheme Designing an Addressing Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 18 Example Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 19 Example Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 20 $ 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 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. Flags U U UG SNM — ver. 1.3 Longest Prefix Genmask 255.255.192.0 255.0.0.0 0.0.0.0 0-2 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 4/48 Iface eth0 lo eth0 SNM — ver. 1.3 BGP MED Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 40 How about 192.168.128.48? 192.168.25.10? 192.169.0.1? 0.0.0.0 0.0.0.0 172.19.35.254 202.180.160.251 Routing Tables and Route Summarisation - p. 5/48 eth0 vmnet1 ppp1 ppp0 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 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: 192.168.0.0/16 172.12.0.0/12 10.0.0.0/8 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 6/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 7/48 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. Router Table Explosion 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. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 8/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 9/48 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. RIP2 OSPF BGP Aggregating routes Routers summarise routes themselves when they use classless routing protocols such as: SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 10/48 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 ..... W Router B 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 With Route Summarisation Routing table advertised by A is much smaller after summarisation 200.200.24/24 Router A V B’s routing table advertised to C 200.200.24/22 200.200.28/24 ..... Router B W Router C Y 200.200.24/24 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 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 Router A V Router C Y 200.200.25/24 200.200.26/24 200.200.27/24 200.200.28/24 A’s routing table advertised to B 200.200.24/22 200.200.28/24 X 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 - p. 12/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 13/48 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. 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 - p. 14/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 15/48 Route Aggregation: NetAddr::IP 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. 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"; SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 17/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 16/48 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 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 subnet 6 subnet 7 subnet 8 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 18/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 19/48 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 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 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 network subnet X 172.19.128.0/30 subnet Y 172.19.128.4/30 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 20/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 21/48 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 log2 (140+2) = 28 ; so prefix length = 32 − 8 = 24). Solution — Larger Subnets — 2 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 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 22/48 In a tutorial exercise, you will determine what routes eachSNM — ver. 1.3 advertises. router Routing Tables and Route Summarisation - p. 23/48 order Gateway Protocol — BGP]Gateway Protocols Gateway Protocols Border Gateway Protocol — BGP 23-1 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 24/48 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. Routing Tables and Route Summarisation EachSNM — ver. 1.3 assigned a number. AS numbers range from - p. 25/48 AS is 1 to 65,535, with 64512 to 65535 reserved for private (internal networks) use. 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 - p. 26/48 Border Gateway Protocol BGP Single-homed Autonomous Systems Only one connection between stub network and a single ISP Stub Network ISP 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. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 27/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 28/48 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. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 29/48 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. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 30/48 Multi-homed Transit AS Source 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. BGP BGP Destination SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 31/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 32/48 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. BGP Attributes SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 33/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 34/48 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. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 35/48 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 - p. 36/48 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. 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 localSNM — ver. 1.3 preference attribute is propagatedRouting Tables and Route Summarisation - p. 38/48 throughout the local AS. SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 37/48 BGP LOCAL_PREF local pref = 100 Router A preferred route to 172.16.1/24 Router C BGP MED Attribute 172.17.2/24 172.16.1/24 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. Router B local pref = 50 AS100 Router D AS200 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 39/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 40/48 BGP MULTI_EXIT_DISC Router A 172.17.2/24 MED=5 preferred route 172.17.2/24 172.16.1/24 Router C 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 AS100 Router D AS200 172.17.2/24 MED=10 Router B Local Pref = 50 AS100 SNM — ver. 1.3 Router D AS200 Routing Tables and Route Summarisation - p. 42/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 41/48 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 Routing Tables and Route Summarisation - p. 43/48 BGP Message Types BGP message types are specified in RFC 1771 (i.e. 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 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 44/48 device is active. BGP Four BGP Packet Formats All BGP 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 2 2 4 BGP ID version AS number hold time 1 Length of optional param 4 Optional parameters message types use the basic packet header 16 Marker 2 Length 1 Type variable Data Field length in bytes 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 - p. 45/48 SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 46/48 BGP Additional Fields: Update Message BGP Additional Fields: Notification 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 variable 2 path attributes length variable path attributes variable network layer and Route Summarisation - p. 47/48 Routing Tables reachability info SNM — ver. 1.3 Routing Tables and Route Summarisation - p. 48/48 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 unfeasible — ver. 1.3 withdrawn SNM routes length routes