BGP: The Three-Napkin Protocol

Abstract

In January 1989, at the twelfth meeting of the Internet Engineering Task Force in Austin, Texas, Kirk Lougheed of Cisco and Yakov Rekhter of IBM sat down at lunch with Cisco co-founder Len Bosack and sketched a routing protocol on napkins, two or three of them; nobody kept the originals. The Border Gateway Protocol was published as RFC 1105 that June. It was meant to rescue the NSFNET from a protocol that could not keep up, and it became the protocol by which tens of thousands of independent networks tell each other which addresses they can reach, which is to say the protocol that makes the internet one network. It was built on trust. Any network can announce any route, and from the AS 7007 leak of 1997 to Pakistan Telecom’s capture of YouTube in 2008 and Facebook’s disappearance in 2021, that trust has been the source of its failures. Cryptographic route validation was standardised in 2012 and still covers only part of the internet.

The BGP finite state machine, the six session states defined in the protocol specification. Image: Lukeritchie, CC BY-SA 3.0, via Wikimedia Commons.

The Problem with EGP

The internet of the late 1980s connected separate networks, each run by its own organisation and each called an autonomous system (AS). Inside an AS, routers could use whatever protocol they liked. Between them, the protocol was the Exterior Gateway Protocol, EGP, specified by David Mills in RFC 904 in April 1984.

EGP had been designed for a tree, with the ARPANET at the root, and the National Science Foundation’s NSFNET was turning the tree into a mesh of regional networks. Guy Almes, who ran one of the NSFNET regional networks, recalled two problems. EGP sent its complete set of routes directly over IP in a single message, which could not grow as the number of networks grew, and it assumed a flat topology of autonomous systems. The IETF’s Interconnectivity Working Group had been told not to invent a new protocol and was working on a third version of EGP. Craig Partridge, a networking researcher at BBN, later summarised the story as “a couple of very frustrated engineers,” frustrated “because the IETF was flailing around looking at alternatives.”

Lunch in Austin

At the Austin meeting, Lougheed and Rekhter took a break. “They sat down in the cafeteria,” in one later account, looking for a short-term fix for an internet that then connected about 100,000 computers. Bosack, by Cisco’s account, suggested running the protocol over TCP, which Lougheed said “was considered heresy at the time.”

Almes, who was in the working group, listed the three ideas on the napkins. TCP carried the routing messages, so their length was no longer a problem. Routers exchanged their full tables once and then only incremental updates. And every route carried its AS path, the full list of autonomous systems the announcement had passed through, which Almes considered the most important: a router could see whether a route would loop back through itself, and operators could write policies about which networks they would send traffic through. The engineers later disagreed on whether there had been two napkins or three; Rekhter said three, and the Internet Hall of Fame agreed, but the originals were not kept.

Lougheed and Rekhter published the specification as RFC 1105 in June 1989. By the October 1989 IETF meeting in Hawaii work on a version 2 had begun (RFC 1163, June 1990), and BGP-3 followed in October 1991 (RFC 1267). BGP-4, edited by Rekhter and Li, was published as RFC 1654 in July 1994 and RFC 1771 in March 1995. It added support for classless addressing (CIDR, RFC 1519, September 1993), which let providers aggregate many small address blocks into one announcement and slowed the growth of the global routing table. BGP-4 is still the version in use, revised as RFC 4271 in January 2006 and extended to IPv6 and 32-bit AS numbers. Rekhter’s own summary of the lessons, in a talk at Google in 2007, began: “Short-term solution tend to stay for a long time; long-term solutions tend to never happen.”

Announcing What You Do Not Own

BGP routers believe what their neighbours tell them. A network announces that it can reach a block of addresses, its neighbours pass the announcement on, and routers everywhere choose among the routes they hear, preferring the most specific prefix and then, broadly, the shortest AS path. Nothing in the original protocol checks that the network announcing a prefix is entitled to it. Routing security depended on providers filtering what their customers announced, and on their care.

AS 7007. On 25 April 1997 a router of MAI Network Services, AS 7007, received a full routing table from a customer and, without filters, re-announced much of the internet as its own, broken into small /24 prefixes. Being more specific than the real routes, the announcements won, and much of the internet’s traffic was drawn towards a small provider. Other problems kept the bad routes in other networks’ tables even after the router was disconnected. MAI’s contact, Vincent Bono, posted an explanation and an apology to the NANOG mailing list the next day.

YouTube. On 24 February 2008 Pakistan set out to block YouTube inside the country. At 18:47 UTC Pakistan Telecom (AS 17557) announced a more specific prefix of YouTube’s addresses, 208.65.153.0/24, and its upstream provider PCCW Global passed the announcement to the world. Most of the internet’s YouTube traffic went to Pakistan. YouTube announced the same prefix at 20:07 and two even more specific /25s at 20:18, and PCCW withdrew the Pakistani routes at 21:01. The RIPE NCC’s analysis counted about two hours from start to finish.

China Telecom. On 8 April 2010, according to a report of the U.S.-China Economic and Security Review Commission, China Telecom advertised erroneous routes for about 18 minutes, and networks around the world adopted paths that sent traffic for about 15 percent of internet destinations through China, among them U.S. government and military sites. The commission said it could not determine what, if anything, was done with the traffic; China Telecom denied hijacking anything.

Theft. On 24 April 2018 the Ohio provider eNet (AS 10297) announced more specific routes for addresses of Amazon’s Route 53 DNS service for about two hours. Someone used them to answer DNS queries for the cryptocurrency site MyEtherWallet with the address of a phishing copy, and users who clicked through the browser’s certificate warning lost cryptocurrency, about $150,000 according to most reports. Amazon said none of its systems had been compromised; someone had simply announced its routes.

Withdrawal. On 4 October 2021 a command during routine maintenance at Facebook took down all connections in its backbone. Facebook’s DNS servers, programmed to stop advertising themselves if they could not reach the data centres, withdrew their BGP routes, and Facebook, Instagram and WhatsApp vanished from the internet for hours. The engineers’ own remote access depended on the same network, and teams had to be sent to the data centres in person.

Securing the Routes

Proposals to secure BGP are almost as old as the incidents. Stephen Kent and colleagues at BBN designed S-BGP, in which every router signs the announcements it passes on, and in 2004 were still writing reports on how to move it into the internet. The approach that gained ground was narrower. The Resource Public Key Infrastructure (RPKI), specified by Matt Lepinski and Kent in RFC 6480 in February 2012, lets the regional internet registries that allocate addresses certify which AS may originate which prefix, as signed Route Origin Authorizations. Route origin validation (RFC 6811, January 2013) lets a router reject announcements that contradict them. It would have stopped Pakistan Telecom’s announcement, which came from the wrong AS. It would not stop an attacker who forges the AS path to start with the right one; BGPsec, published as RFC 8205 in September 2017, signs the whole path.

Adoption of RPKI rose slowly and then faster. In June 2021 about 30 percent of routed prefixes were covered by a valid authorisation; by 2025 the NIST RPKI monitor showed more than half. In June 2024 the U.S. Federal Communications Commission proposed requiring the nine largest American broadband providers to file BGP security risk management plans, covering their creation of Route Origin Authorizations and their filtering, noting that BGP’s “initial decades-old design, which remains widely deployed today, does not include intrinsic security features.”

Dead End: The Temporary Fix

BGP was conceived as a short-term fix, by engineers frustrated with the search for a better long-term design. Nothing replaced it. BGP had the property Rekhter later valued most: it was flexible enough to extend, with new address families, new attributes and larger AS numbers, without replacing the routers’ installed base. Every attempt to change its trust model had to be deployed by thousands of independent operators, each paying the cost for a benefit that arrived only when most of the others had done the same. In 1998 Peiter Zatko told a Senate committee that his group could make the internet unusable in about half an hour by attacking BGP (see Peiter Zatko (Mudge)); the routing system he described was still running, with the same protocol at its core, twenty-five years later.