How BGP works

What is BGP?

Border Gateway Protocol (BGP) is an Exterior Gateway Protocol (EGP) that makes the Internet work by enabling data routing between autonomous systems (AS). BGP can be seen as the postal service for the Internet. When someone submits data via the Internet, BGP is responsible for looking at all of the available paths that data could travel and picking the best route. 

BGP is generally considered a path-vector routing protocol, which sends peers information on which path traffic on a network will go. This includes which ASes that traffic will travel through. Distance-vector protocols like the IGP RIPv2 only counts hops, and is unable to know which exact path traffic will take. 

BGP relies on path-vector route discovery due to the visibility it provides. This is also the reason why it's not a link-state routing protocol, since link-states do not have complete visibility and may introduce unwanted traffic via its LSU (link state update) packets, and so on. The IGP OSPF uses link-state routing.

Because BGP uses path-vector discovery, convergence times for BGP is the slowest among the routing protocols used today. 

The Internet is a network of networks. It is broken up into hundreds of thousands of smaller networks known as autonomous systems (AS). Each of these networks is essentially a large pool of routers run by a single organization. If we see BGP as the postal service of the Internet, ASes are like individual post office branches. A town may have hundreds of mailboxes. They forward outbound transmissions to the AS, which then uses BGP routing to get these transmissions to their destinations.

The above example illustrates a simplified version of BGP where there are only six ASes on the Internet. If AS1 needs to reach AS3, it has two different options:

1. Hopping from AS2 and then to AS3.
2. Or hopping to AS6, then to AS5, AS4, and finally to AS3.

This simplified version makes the decision seem straightforward. The first option has fewer hops then the second and thus is the quickest, most efficient route. Now, imagine that there are hundreds of thousands of ASes and that hop count is only one part of a complex selection algorithm. That is the reality of BGP routing on the Internet.

The Internet is constantly changing, with new systems popping up left and right, or existing systems becoming unavailable. Because of this, every AS must be kept up to date with information regarding new routes as well as obsolete routes. This is done through peering sessions where each AS connects to neighboring ASes with a TCP/IP connection for the purpose of sharing routing information. Using this information, each AS is equipped to properly route outbound data transmissions coming from within.

This is where the Post Office analogy falls apart. Unlike post office branches, autonomous systems are not all part of the same organization. In fact, they often belong to competing businesses. Because of this, BGP routes sometimes take business considerations into account. ASes often charge each other to carry traffic across their networks, and the price of access can be factored into which route is ultimately selected.

Who owns and operates autonomous systems?

Typically ASes belong to ISPs or other large organizations such as tech companies, universities, government agencies, and scientific institutions. Each AS wishing to exchange routing information must have a registered autonomous system number (ASN). Internet Assigned Numbers Authority (IANA) assigns Regional Internet Registries (RIRs), which then assigns them to ISPs and networks. ASNs are 16 bit numbers between one and 65534 and 32 bit numbers between 131072 and 4294967294. As of 2018, there are approximately 64,00 ASNs in use worldwide. These ASNs are only required for external BGP.

The differences between external BGP and internal BGP: IGP vs. EGP

Routes are exchanged over the Internet using external BGP (eBGP). Autonomous systems have the option to use an internal version of BGP to route through their internal networks, which is known as internal BGP (iBGP). It should be noted that internal BGP is NOT a requirement for using external BGP. Autonomous systems can choose from a number of internal protocols to connect the routers on their internal network.

iBGP is an example of an interior gateway protocol (IGP). ASes have the option to use iBGP, but also IS-IS and OSPF, EIGRP, etc. eBGP is the main external gateway protocol (EGP) that is used. eBGP is like international shipping. There are certain standards and guidelines that need to be followed when shipping a piece of mail internationally. Once it reaches its destination country, it has to go through the destination country's local mail service to reach its final destination. Each country has its own internal mail service that does not necessarily follow the same guidelines as those of other countries. Similarly, each autonomous system can have its own internal routing protocol for routing data within its own network. Or, one AS may use primarily IS-IS for internal routing while another uses OSPF.

 What are BGP attributes?

Attributes are additional factors BGP uses alongside hop counts when deciding the most efficient path for network traffic. This is useful when BGP needs to decide between multiple options, like administrative distances and metrics do for routers in a routing table. Many routers allow administrators to customize attributes for more granular control over how traffic flows on their networks. Some examples of BGP attributes are:

• Weight: A Cisco-proprietary attribute, this tells a router which local paths are preferred.
• Local preference: This tells a router which outbound path to select.
• Originate: This tells a router to choose routes it added to BGP itself.
• AS path length: Similar to the example diagram above, this attribute tells a router to prefer shorter paths.

There are several other BGP attributes as well. All these attributes are ordered by priority for BGP routers--for example, a BGP router first checks to see which route has the highest weight, then checks local preference, then checks to see if the router originated the route, and so on. So if all routes received have an equal weight, the router selects a path based on preference instead. This acts similarly to routing tables where if you have multiple routes to the same network with the same administrative distance, it picks the one with the lowest metric value.

BGP's flaws

BGP has flaws relating to the route-sharing function of BGP relying on trust, and autonomous systems implicitly trusting the routers that are shared with them. When peers announce incorrect route information, intentional or not, traffic goes where it is not supposed to, potentially with malicious results.

One incident involved a Turkish ISP called TTNet accidentally advertised incorrect BGP routes to its neighbors. These routes incorrectly claimed TTNet itself was the best destination for all traffic on the Internet. As these routes spread further to more autonomous systems, a massive disruption occurred, creating a one-day crisis where many people across the world were not able to access some or all of the Internet.

Another incident involved a Pakistani ISP attempting to use a BGP route to block Pakistani users from visiting YouTube. The ISP then accidentally advertised these routes with its neighboring ASes and the route quickly spread across the Internet's BGP network. This route sent users trying to access YouTube to a dead-end, which resulted in YouTube being inaccessible for several hours.

Another incident occurred in June 2019 when a small Pennsylvania company became the preferred path for routes through Verizon's network, causing much of the Internet to become unavailable to users for several hours.

These are examples of a practice called BGP hijacking, which does not always happen accidentally. In April 2018, attackers deliberately created bad BGP routes to redirect traffic that was meant for Amazon's DNS service. These attackers were able to steal over $100,000 worth of cryptocurrency by redirecting traffic to themselves.

BGP hijacking can be used for several kinds of attacks:

• Phishing and social engineering through re-routing users to fake websites
• DDoS through blackholing or redirecting
• On-path attacks to modify exchanged data, and subvert reputation-based filtering systems
• Impersonation attacks to eavesdrop on communications

How to secure BGP

Some progress has been made in securing BGP. Most notably, a security framework for routing called Resource Public Key Infrastructure (RPKI) was introduced in 2008. RPKI uses cryptographically signed records called Route Originate Authorization (ROAs) to validate which network operate is allowed to announce an organization's IP addresses using BGP. This ensures that only authorized parties are announcing an organization's prefixes. 

But RPKI alone isn't enough. Over 50% of the top ISPs support RPKI to some extent, but a larger majority is needed to fully secure BGP. Network operators can protect their networks by implementing RPKI and using network alerting technologies, which alerts customers when unauthorized parties are advertising their prefixes.