This blog is the first 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.
The Border Gateway Protocol (BGP) turned 30 years old this year, making it one of the most long-lasting, widely-used protocols ever deployed in the Internet. BGP was initially conceived in January, 1989 by Yakov Rekhter (IBM) and Kirk Lougheed (Cisco) on two napkins during the 12th IETF conference in Austin, Texas.
Curiously enough, BGP was conceived as an interim solution to overcome the infeasibility of using the existing Exterior Gateway Protocol (EGP) with the increase in complexity for connectivity between Administrative Domains. Thirty years passed, and the interim solution became one of the pillars of the Internet architecture. Version 4 (the current version) was released in 1994, and since then it gets updated sporadically with new features and capabilities.
What is BGP? Some Basics
Before we dive into the history of BGP, let’s go over some basics of what it is. The primary function of BGP is to manage how packets are routed across the internet through the exchange of routing and reachability information between edge routers. BGP directs traffic between autonomous systems (AS), which are network routers managed by a single enterprise or service provider. When an AS gets set up, it peers with other AS’s to share IP prefixes, which are then shared with other AS’s, and so on. In this way, when new prefixes are announced, they get propagated around the internet.
The biggest problem, however, is that BGP is extremely vulnerable to both malicious attacks and human error. There are roughly 65,000 AS’s that make up the global internet, and little to no oversight for how each AS peering filters must be configured. This means that if a new, bogus route (aka a bogon prefix) is announced (either through intentional hijacking or just a typo) it sends traffic to the wrong network, and can spread like wildfire across the internet.
A Little Bit of History
Some background is required to better understand the crucial role that BGP played in the history of the Internet. In 1989, the Internet as we perceive it today was just moving its first steps. The commercial use of the Internet was still forbidden (the restriction was lifted in 1995 with the decommission of NSFNET), but commercial ISPs were sprouting and offering network access to end users, and the commercial use of the Internet was no longer a taboo topic.
When BGP was firstly standardized in June, 1989, the long-running ARPANET was just being decommissioned (February 28, 1989), TCP/IP was being used to interconnect different networks from remote countries, and the Internet was about to move from its centric architecture to a more distributed architecture, without a clearly defined backbone. Curiously, the requiem to ARPANET by Vinton G. Cerf was performed in the very same IETF meeting where BGP was just being announced to the world.
Up until then, the so-called Internet gateways were exchanging net-reachability information via the Exterior Gateway Protocol (EGP). EGP was conceived for an Internet composed by a core AS and multiple other smaller AS’s directly connected to that core, and it totally relied on having a tree-structured topology of AS’s, without cycles.
Although these limitations were bearable in an early stage Internet where stub gateways were talking to each other via its ARPANET backbone, with the advent of commercial entities and multiple backbones (such as NSFNET), its inadequacies became more and more pronounced – not to mention the impossibility to create policy-based routing, which is the key of success of BGP.
BGP: The Two-Napkin Protocol
BGP is still a path vector protocol like its predecessor EGP, but it was conceived foreseeing a peer-to-peer environment where AS’s could exchange routing information without relying either on a priori topology knowledge or on a core AS. With the introduction of BGP, the concept of AS has also been changed and re-defined. In the last BGP version, an AS “is considered to be a set of routers under a single technical administration, using an interior gateway protocol (IGP) and common metrics to determine how to route packets within the AS, and using an inter-AS routing protocol to determine how to route packets to other AS’s.”
The basic piece of routing information that AS’s exchange with each other is called route. A route is composed by a set of destination IP networks paired with set path attributes, which describe the path toward the destinations. “This information is sufficient to construct a graph of AS connectivity from which routing loops may be pruned and policy decisions at an AS level may be enforced.”
To guarantee the reliability of transmission, BGP is encapsulated into a TCP connection, meaning that two routers that want to establish a BGP session must have prior IP reachability. After establishing a TCP connection, the two routers – hereafter called BGP peers – agree on the parameters to use in the BGP session via BGP open messages, and then start exchanging routes. These routes can be generated by the peer itself or they can be learned by the peer via other BGP sessions, and each of them is announced via BGP update messages.
The figure below summarizes the BGP process each AS applies when receiving a route from another peer:
Whenever a route is received from an AS, the route is subject to a filtering process where it can be discarded or accepted and, if required, its path attributes are manipulated. Then a BGP decision process is applied to select the best route for each IP destination network, since an AS may receive multiple routes toward the same IP network from different peers.
The BGP decision process is composed of a sequence of steps that allow the AS to choose the best route by analyzing the path attributes of each of the candidates, in order to apply criteria that range from pure commercial (e.g. prefer a cheaper provider over the other) to technical reasons (e.g. transit traffic to reach a destination via the smallest number of ASes). Each best route is then installed in the routing table of the router and used to forward traffic. Eventually, after a proper attribute manipulation, each best route is propagated to the all other BGP peers, or a subset of them depending upon the output filtering process applied.
Since the early days of deployment of BGP, the Internet grew widely in size and shape. Nowadays, the Internet is composed of about 65,000 AS’s that exchange routing information related to about 800,000 IPv4 networks and about 70,000 IPv6 networks. However, due to the distributed architecture of the Internet, it is impossible to determine the number of BGP sessions established among AS’s in the wild.