Blog Post

How BGP Routing Really Works

Published

October 24, 2019

mins read

Alessandro Improta

Luca Sani

in this blog post

This blog is the fourth installment of a 5-part blog series about the Border Gateway Protocol (BGP). You can download the full series in The Comprehensive Guide to BGP, or view individual installments below.

Part 1: Happy Birthday to BGP, a Pillar of the Modern Internet

Part 2: X-Raying BGP

Part 3: BGP and Your Brand’s Bottom Line

Part 5: Vulnerabilities of BGP

The Internet is always in constant evolution. Nowadays there are more than 4 billion users connected to the Internet, browsing around 2 billion websites, playing games, watching videos, and doing business with each other no matter where in the world they are. This large number of users can reach their desired content via Internet routes provided by the interconnections of about 60K Autonomous Systems exchanging reachability information via BGP on about 800K different IPv4 networks and about 70K IPv6 networks. And these numbers are growing each passing minute.

The main role of BGP routing is “[…] to exchange network reachability information with other BGP systems.” Routes are announced and withdrawn constantly from various parts of the world. Whenever a new AS joins the routing game, the first things it will do is get routes from its provider(s) to reach every Internet destination and announce to its neighbors that there is a new route towards the network(s) it owns. Each neighbor will then inform its own neighbors about these new routes, and so on so forth.

On the other hand, any AS shutting down causes the withdrawal of its routes to spread all over the Internet. But there are only a few causes of route announcement/withdrawal. A few other examples of route changes include whenever a fiber cable is accidentally cut, whenever two AS’s sign a new economic agreement (or whenever that expires), and whenever there’s any kind of network failure.

BGP Route Announcements and Replacement

Once an organization gets an AS number and IPv4/IPv6 subnets from one of the five Regional Internet Registries (see the map below for the geographic distribution of RIRs) or one of the Local Internet Registries (LIRs), that organization is ready to announce its network reachability towards the global Internet.

RIR service map courtesy of RIPE NCC

First, that organization needs to settle an agreement with one or more providers to be connected to the Internet. Then it must start advertising to the Internet the subnets obtained from the RIR/LIR so that every other player in the Internet will be aware of the presence of this new network resource and forward traffic accordingly.

To better understand how the Internet will learn about the presence of the newly advertised subnets, please consider the figure below. For ease of understanding this and the following examples, we will assume that a customer will announce only its subnets to its provider, a provider will announce everything to its customers, and a peer will announce to other peers its subnets and all the subnets it received from its customers. We will also assume that the BGP routing decision process will always choose as best route the route with the shortest AS path.

AS 1 is a brand new organization that managed to get the subnet 10.10.10.0/24 from one of the available LIRs, and which contacted AS 2 and signed an agreement so that AS 2 can transit traffic for AS 1 and allow AS 1 to be connected to the Internet. As soon as the network administrator of AS 1 installs the subnet 10.10.10.0/24 in its router, it will be generated an UPDATE message for AS 2 carrying the information that a new subnet has been announced.

More importantly, this message will carry the information that this new subnet will be reached crossing only AS 1, meaning that AS1 is the origin AS of the subnet. This information is carried in the AS path, which is one of the mandatory attributes in Update messages. This attribute is manipulated by each border router crossed to keep track of the path followed by the Update message and avoid BGP routing loops. This is part of the BGP best route selection process.

Once AS 2 receives the Update message carrying 10.10.10.0/24, it will install this new route in its Adj-RIB-In, will select it as the best route for 10.10.10.0/24, and will install in the proper Adj-RIB-Out according to AS 2 outbound-filter policy. Thus, it will announce an Update message towards its peer, AS 3, and its other customer, AS 4, prepending its own AS number in the AS path.

At this point, AS 2 will be aware of the presence of this new subnet and will start to route traffic towards it whenever required. The same procedure will be followed by AS 3, which will propagate the Update message towards its customer AS 4, prepending its own AS number.

AS 4 will then receive two different Update messages to reach 10.10.10.0/24 at two different times. If the Update message coming from AS 3 will be received before the Update message of AS 2, then AS 5 will receive first an Update message with AS path 4 3 2 1, then another Update message with AS path 4 2 1. Otherwise, AS 5 will only receive one single Update message with AS path 4 2 1, since the piece of routing information carried by the packet announced by AS 3 will not be considered by AS 4 as best route.

Let’s now assume that the BGP session between AS 2 and AS 4 is torn down. In this case, both AS’s cannot reach each other anymore and the content of the related Adj-RIB-In tables will be invalidated. Consequently, the two AS’s will run again the decision process for all the best routes which were involving the other AS. In the example, this means that AS 4 will analyze every other Adj-RIB-In to find a route feasible to reach 10.10.10.0/24. This process is called Path exploration and can potentially involve many routes, affecting the performances of the router. Once found a feasible replacement, then AS 4 will inform its customer that the path has changed sending an Update message with AS path 4 3 2 1.

Route withdrawals

Let’s now assume that the organization decides to shut down its operations. In this case, the router will be shut down and most probably sold to the highest bidder. Once the router is shut down, the BGP session established will be torn down and will trigger a domino effect all over the Internet to let everybody know that the subnets owned by the organization are no longer available to receive any traffic.

Consider once again the example shown in the figure above, with all the BGP sessions up and running. Once the BGP session between AS 1 and AS 2 is shut down, then AS 2 will start its Path exploration phase, finding no feasible routes to reach 10.10.10.0/24. Then it will generate a special Update message announcing that it cannot reach subnet 10.10.10.0/24, thus informing its neighbor to stop propagating traffic towards AS 2 to reach AS 1. AS 3 will receive this piece of information and will behave like AS 2, announcing to AS 4 that 10.10.10.0/24 is no more reachable via AS 3.

As before, AS 4 will receive two different Update messages in time. If the Update message coming from AS 3 will be received before the Update message coming from AS 2, then the first message will just remove the route from the Adj-RIB-In related to AS 3, while the second message will trigger a Path exploration phase on AS 4, which will find no feasible routes to reach 10.10.10.0/24 and will propagate the Update message to AS 5, which will be the last in line to know that the subnet has been withdrawn from the Internet.

On the other hand, if the Update message from AS 2 will be received first, then AS 4 will run a Path exploration phase which will let AS 4 believe that there is still an available route towards 10.10.10.0/24, and will advertise this new reachability to AS 5 via an Update message with AS path 4 3 2 1. In this case, only the reception of the message from AS 3 carrying the withdrawal of 10.10.10.0/24 will trigger another Path exploration phase on AS 4 and let AS 4 (and AS 5, consequently) finally understand that the route is no more there.

Please note, however, that an Update message advertising the withdrawal of a subnet does not necessarily mean that the destination is no longer reachable from any AS composing the Internet. For example, such a message could be generated in a geographic area due to a temporary local network failure and/or due to BGP session misconfigurations, while the subnet is still being reachable from other AS’s.

Path exploration is a natural consequence of path vector protocols as BGP. In this family of protocols, the path information is always updated dynamically so that updates looping through the network can be discarded easily. On the other hand, the path dependencies created tend to prolong BGP protocol convergence, which can be reduced by applying special timers on the border routers.

Regional Internet Registries: