BGP: What Is It And How Does It Work

If you are following the news on the Internet, you might have seen that in late February the FCC (Federal Communications Commission) launched an inquiry into BGP. The introduction of the Notice of Inquiry document mentions that:

The Commission, in tandem with its federal partners, has urged the communications sector to defend against cyber threats, while also taking measures to reinforce our Nation’s readiness and to strengthen the cybersecurity of vital communications services and infrastructure, especially in light of Russia’s escalating actions inside of Ukraine. [...] We seek comment on vulnerabilities threatening the security and integrity of the Border Gateway Protocol (BGP), which is central to the Internet

You might have heard of BGP as the thing used to route the Internet, or as the thing that broke Facebook last year. But do you really know what it is, how it works, and what are its potential flaws? Let's find out.

Packets Routing and BGP

If one wants to define the Internet, he may say that the Internet is a set of interconnected networks. According to Cisco, there will be 5.3 Billion users by 2023, and according to siteefy, there are currently 1.17 Billion websites. This is great, but with these numbers, you can imagine that a sort of map is needed for a packet to go from a machine A to a machine B. That is what BGP is for.

To give a more technical definition, BGP (Border Gateway Protocol - using port 179 on TCP) allows to route packets between Autonomous Systems. Autonomous Systems use BGP to broadcast the IP addresses they manage, and what other Autonomous Systems they are connected to. Before going more into the details, let's take a moment to define some terminology.

Terminology

Autonomous System (AS)

An autonomous system is a group of one or more IP prefixes (e.g. 8.8.0.0/24 which represents all of the IP addresses between 8.8.0.1 and 8.8.0.254) that have a single clearly defined routing policy. They are usually managed by a single organization, for example, a company (e.g. Google, Amazon), a Government Agency, or an ISP (e.g. Verizon). It is possible for an organization to manage multiple Autonomous Systems.

Autonomous System Number (ASN)

Each Autonomous System is identified by an Autonomous System Number (ASN), which is assigned by a Regional Internet Registry (RIR). It is used by network operators to exchange routing information.

It is possible to know more about the owner of an ASN by using the whois command (like you would do for a domain name.) For example, whois AS15169 (the output is kind of big, so I will not paste it here.)

You can also know to which AS and IP prefix an IP address belongs. For example, cymru.com provides an API queryable using whois

> whois -h whois.cymru.com -- '-v 8.8.8.8'
AS      | IP               | BGP Prefix          | CC | Registry | Allocated  | AS Name
15169   | 8.8.8.8          | 8.8.8.0/24          | US | arin     | 1992-12-01 | GOOGLE, US

Various services on the Internet also allow you to know more about an ASN. For example, AS15169 on ipinfo.io, where you can see all the IP ranges attributed to the AS, and to how it is connected to other autonomous systems.

Regional Internet Registry (RIR) and Internet Assigned Number Authority (IANA)

There are five Regional Internet Registries, and each one is assigned to a particular geographical zone. For example, the American Registry for Internet Numbers (ARIN) is in charge of assigning ASNs to American entities. The five RIRs are themselves managed by the Internet Assigned Number Authority (IANA). RIRs are also in charge of assigning IP ranges.

High-Level Example

All these definitions are good, but let's look at something concrete, and say that you want to send a request to Google's DNS 8.8.8.8. For your computer it will be pretty simple: the only network connection it has is your router, so it sends the request there. Then, your router also has the single choice of sending your request to your ISP. Then what?

The following figure is a simplified map of the Internet. On the top right, is your ISP (let's say AS0), and on the bottom left Google (let's say AS15169.) From your computer, your request is routed through various parts of your ISP network (possibly using Internal BGP, iBGP,) and eventually reaches your ISP's edge router. From there, your ISP decides (thanks to BGP and internal policies) that the best path is AS0 -> AS1 -> AS2 -> AS10 -> AS15169, so it will send your request to AS1, which will route your request through its internal network and send it to AS2, and so on until it reaches the right place.

BGP Simple Schema
Figure 1: Internet Decentralized Connections

Note that for simplification's sake, Figure 1 shows a single BGP router for each ISP, but they will actually be multiple of them (in addition to internal BGP ones.)

How are Autonomous Systems Connected Together

One thing that you might have wondered by looking at the previous Figure 1 is how are the various ASs actually connected together. Let's define a couple of extra terms, and see how they fit in the big picture.

Upstream and Downstream Autonomous Systems

If you look at the ipinfo.io page for AS15169, you will notice that there is a list of Upstream ASNs and a list of Downstream ASNs. Long story short, Downstreams ASNs represent ASs using Google to access the wider network, and Upstream ASNs represent ASs used by Google to access the wider network.

Internet (IP) Transit and Peering

IP Transit is a service where an ISP (upstream provider) will sell the right to use their network to connect to the wider Internet (i.e. to use the BGP connections that the ISP has with other ISPs.)

There are cases where two ISPs may allow each other to access their networks for free. This is called peering. This will usually happen when ISPs have business interests to access each other networks for free.

Tier 1, 2, and 3 Networks

We mentioned two types of connections between ISPs: IP Transit and Peering. How ISPs use them will mostly depend on what Tier they are.

Tier 1 Networks

Tier 1 ISPs are the biggest ones. They are typically defined as being able to access every other network on the Internet without having to pay for Internet transit or peering.

Some examples of Tier 1 ISPs are AT&T, NTT, and Orange.

Tier 2 Networks

Tier 2 ISPs are peering with other (mostly Tier 2) networks, but also purchase IP transit from Tier 1 providers to gain access to the entire Internet.

Tier 2 ISPs usually have a national or regional reach, and only a few of them are capable of serving customers across multiple continents through their own infrastructure.

Some examples of Tier 2 ISPs are Korea Telecom, British Telecom, and Comcast.

Tier 3 Networks

Tier 3 service providers are usually small and only purchases IP transit from Tier 2 and (sometimes) Tier 1 networks.

Internet eXchange Point (IXP) and Private Network Interconnect (PNI)

An IXP is a physical location where Internet infrastructure companies (e.g. ISPs and CDNs) connect to exchange traffic. It is basically a data centre containing network switches and is maintained (paid for) by the various participants.

The advantage for the participants is that they can access each-others networks without having to pay bigger providers for pairing. IXPs also help improve the latency of the requests exchanged between the participants. Note that participants do not share their upstream connections through IXPs.

You can see some examples of IXPs on this website.

Note that IXPs usually involve more than two participants. If two ISPs deem that a mutual connection is important enough, they will create a Private Network Interconnect (PNI), which is a direct fibre connection between the two of them.

A Concrete Example

Now that we defined all the actors using BGP, let's look at an example again, but this time with a deeper level of detail (note that there is a lot to say, so we will try to keep things simple and not go into every aspect.)

In the following Figure 2, we have:

  • AS1 is Tier 2 ISP, it is getting an upstream connection to AS2, a Tier 1 ISP
  • AS2 has a downstream connection to AS1 and AS4
  • AS3, AS4, and AS5 are Tier 2 ISPs
  • AS3 and AS5 are sharing a connection through an IXP
  • AS1 and AS3 exchange a lot of traffic, so they have a pairing
  • Same for AS4 and AS5
BGP Protocol example
Figure 2: Example of BGP Network

Let's say that we are AS1, a new ISP and we just got online. We first need to configure our neighbors. Since we have agreements with AS3 and AS2, we add them to our BGP neighbor configuration. Our table would then look like the following (in reality it would be more complex and contain statistics, status, ...):

Neighbour AS
1.5.0.1 3
1.2.0.1 2

From there, we will receive BGP information, and our BGP table will be filled with the following (again, simplified version):

Network Next Hop Path
1.1.0.1 0.0.0.0 i
1.5.0.0/16 1.5.0.1 AS3
1.4.0.0/16 1.5.0.1 AS3, AS5
1.3.0.0/16 1.5.0.1 AS3, AS5, AS4
1.2.0.0/16 1.5.0.1 AS3, AS5, AS4, AS2
1.2.0.0/16 1.2.0.1 AS2
1.3.0.0/16 1.2.0.1 AS2, AS4
1.4.0.0/16 1.2.0.1 AS2, AS4, AS5
1.5.0.0/16 1.2.0.1 AS2, AS4, AS5, AS3

Note that the routes can also be set manually instead of relying on messages from neighbors. Since networks are not something frozen, updates will be sent using BGP when changes are made. For example, if it became irrelevant for AS4 and AS5 to have a peering agreement, and that they ceased to have a direct connection, our local table would be updated to the following.

Network Next Hop Path
1.1.0.1 0.0.0.0 i
1.5.0.0/16 1.5.0.1 AS3
1.4.0.0/16 1.5.0.1 AS3, AS5
1.2.0.0/16 1.2.0.1 AS2
1.3.0.0/16 1.2.0.1 AS2, AS4

Back to our initial BGP table, let's say that we want to send a packet to AS5. We have two options:

  • Take the AS3 -> AS5 route
  • Take the AS2 -> AS4 -> AS5 route

Since we have multiple options, the router will look at the BGP configuration to choose which route to use. BGP policies allow basing routing decisions on multiple elements such as:

  • The path length
  • The local preference
  • How old is the route
  • If the packet can be routed through iBGP rather than eBGP
  • ... (see the references of the article for more details)

In our case, since we pay for traffic sent to AS2, we might have a local preference telling the router to put packets through AS3 in priority, since we have a free pairing agreement.

What Can Go Wrong?

BGP is a pretty old protocol (sketched in 1989,) and like most old protocols (looking at you ARP, DNS, and many others) it was not built with security in mind.

The most significant risk with BGP is the BGP hijack attack. It consists in having an AS send wrong routing information. For example, let's go back to Figure 2. We have a relationship with AS2 and AS3, so we chose to trust them to not act maliciously, but we don't have control over their neighbors, their neighbor's neighbors, and so on... It is well possible that at some point, AS5 turns malicious and advertises that it owns the network 1.3.0.0/24 (which actually belongs to AS4). Since BGP is based on trust, our BGP routes would be compromised, and some of our communications may end up in the wrong hands (note that in this example, AS5 turns malicious, but it could as well be a human error.)

There are actually several examples of BGP hijack attacks being executed. In 2018, a Russian ISP hijacked IP prefixes belonging to Amazon DNS servers and redirected users of a cryptocurrency wallet to a malicious website. The hackers stole the equivalent of about USD 152,000 in cryptocurrencies (reference)

Another recurrent issue is route leakage. This basically happens when a route happens to be (non intentionally) broadcasted beyond its intended scope. For example, in 2008, Pakistan Telecom tried to censor YouTube by null-routing the service's IP addresses. The routes were then mistakenly sent to Pakistan Telecom's upstream provider, PCCW, and from there, were spread across the Internet.

Fixing BGP

The most recent attempt to fix BGP is RPKI (Resource Public Key Infrastructure,) but is not widely deployed yet. You can read more about it here, as well as see its adoption progress. Basically, it works in the following way:

  • Prefix owners create a ROA (Route Origin Authorization) that allows associating an AS to an IP prefix
  • ROAs are signed by the appropriate Regional Internet Registry Certificate Authority (Trust Anchor) to attest that the binding is correct
  • Autonomous Systems can check that the association AS/IP prefix they have in their routes is correct by pulling the information and checking the signatures (for example by using a validator)

Sources and Extra Resources:

Image Credits: