How does BGP routing work? – Kadiska

BGP stands for Border Gateway Protocol. Refers to the routing protocol used to ensure proper interconnection between autonomous systems (AS). eBGP (external BGP) is used between AS, while iBGP (internal BGP) is used within AS (Autonomous System).

These basics are explained in our article “What is BGP?”.

Now let’s dig a little deeper into how BGP actually works.

eBPG vs iBPG routing protocols

BGP is the protocol used in the backbone of the Internet. It allows organizations that have their own AS (usually Internet Service Providers and large organizations) to interconnect with others. This type of interconnection between AS is called peering.

The

basics of BGP interconnection

The Level 1 club

When an AS is configured, it is paired with other AS to declare its IP prefixes (prefixes refer to the IP subnets it owns), which are then declared to other AS, and so on. In this way, when new prefixes are announced, they spread over the Internet.

If you own an AS, it doesn’t mean you can automatically make it available worldwide! Among the 100,000 AS, only about twenty of them can reach all Internet destinations without buying transit from any other AS, forming the so-called Tier-1 club.

The routes

BGP Unlike other routing

protocols, there is no peer discovery process

.

Each BGP speaker, which is called a “peer,” exchanges routing information with its neighboring peers in the form

of network prefix announcements.

With prefix ads, the information is enough to build an AS connectivity graph, as illustrated below.

As you can see, communication between two prefixes can often occur through different paths.

The J prefix of AS 1559 can, for

example, reach the G prefix from AS 257 via AS 20 or AS 13936

.

So how do routers choose between different possible routes?

The BGP

AS BGP route

does not work like any other traditional routing protocol that uses metrics such as distance or costs (e.g., bandwidth) to make

routing

decisions

. Instead, BGP uses several attributes to route traffic.

The main attribute of BGP is called “AS path”. This is a list of AS numbers that describe the inter-AS route to a destination. The AS route is so critical to BGP function that the protocol is often referred to as a route vector routing protocol.

The figure above shows how the AS path is propagated

. The AS 1 pair sends its prefix to the AS 6 and AS 5 pairs (AS route [1]

), which in turn send the list of prefixes respectively to the AS 3 (AS route [6, 1]) and AS 2 (AS route [5, 1]) pairs. AS 2 peer propagates this list of prefixes to AS 4 peer (AS Path [2, 5, 1]). Finally, AS 4 peer propagates the prefix AS 1 peer to AS 3 peer (AS Path [4, 2, 5, 1]).

As a result, AS 3 is accessible from AS 1 via route AS [6, 1] as well as route AS [4, 2, 5, 1].

The BGP routing decision process

From the example above, you may think that the route chosen between the AS 1 and AS 3 pairs will be through the AS 6 because this is the shortest route.

Well, it

may be the case, but this is not the strict rule! In fact, the best route is chosen based on policies, which are configured through various prefix filters, announcing specific routes, or manipulating BGP attributes.

When a destination can be reached from two different routes, BGP selects the best route by sequentially evaluating the route attributes:

  • Weight
  • Local preference
  • Originate
  • route

  • length
  • AS MED (Multi Exit Discriminator)
  • source code
  • eBGP route over iBGP
  • route

  • Shortest IGP route to next BGP hop Oldest route
  • Router ID
  • Neighboring IP address

.

The main point here is not to go into all the details of these attributes, but to understand the basic principle of the routing decision process.

Returning to the previous example, if the attribute “weight” of the path AS [4, 2, 5, 1

] from AS 1 to AS 3 is greater than the attribute of the path AS [6, 1], then this path is chosen. If the “weight” attribute is the same for both paths, the next attribute (local preference) is evaluated, and so on.

So, in

short, by using BGP attributes, you can ensure that your traffic will transit through your preferred AS, based, for example, on non-technical parameters such as financial agreements you may have with other AS owners

.

How and when is BGP routing protocol data exchanged?

BGP uses the TCP transport protocol to transfer data. This provides reliable delivery of BGP updates. BGP uses TCP port 179 for this.

It uses the Finite State Machine (FSM) model to maintain a table of all BGP pairs and their operational status.

Compared to other routing protocols, BGP does not send periodic updates of routing data. Instead, it sends updates only when network changes occur. For example, these changes can be caused by session resets, link errors, and policy changes.

Finally, BGP periodically sends keep-alive messages to verify the TCP connection.

What can go wrong with BGP?

First of all, we have seen that BGP pairing is configured manually. Human setup is prone to errors. Or worse, this is prone to malicious attacks.

As an example, remember IBM’s cloud outage in June 2020? This was due to a BGP

hijacking!

Another recent example from December 2020 is the outage of Google Euro-Cloud due to incorrect access control list settings, which led the BGP routing protocol to remove the europe-west2-a Availability Zone from the rest of Google’s backbone.

Secondly, and this is undoubtedly one of the main challenges for BGP, processing updates from large routing tables can be a problem for some routers.

Each router needs to store a local database of all prefixes advertised by each routing pair. A router has a finite capacity to process updates and once the update rate exceeds its local processing capacity, the router will start queuing unprocessed updates. In the worst-case scenario, the router will start lagging in real time, so that the information a BGP speaker is propagating reflects a past local topology, not necessarily the current local topology. In its most benign form, the router will announce “ghost” routes where the prefix is no longer accessible, however, the unsynchronized router will continue to advertise accessibility.

The following

graph shows the evolution of the

size of the IPv4 BGP routing table since the beginning of BGP:

As you can see, even with the exhaustion of available IPv4 addresses, the size of routing tables continues to increase dramatically!

The APNIC organization has published the following detailed article on this topic.

Not only does the average size of the BGP routing table increase, but the frequency of BGP updates also follows the same route. In another article, APNIC takes into account a specific AS (AS 131072) to measure the evolution of routing table updates per year. From 300,000 updates in 2009 (about 30 updates per hour), it exceeded 800,000 updates in 2020 (about 90 updates per hour).

Takeaway

BGP is

an important part

of the fundamentals of the Internet.

As it must be configured manually, it is prone to human error and security attacks

.

In addition, the evolution of networks makes them increasingly susceptible to instabilities and service interruptions.

In a global context of digital services, monitoring BGP behavior in terms of route discovery, performance monitoring, as well as route changes, become critical!

If you want to learn more about how you can monitor network performance from the internet to your AS (or your cloud provider’s AS) or from your AS to different digital assets, I recommend you read this article.