Skip to content

The history of BGP: how the internet's routing protocol was bolted on

· 25 min read
Copyright: MIT
history bgp networking
A timeline from 1989 to 2021 above the word BGP in monospace with an orange underline

There is a photocopy of three sheets of handwritten paper that, for years, hung on a wall at Cisco. It is the closest thing the internet has to a founding document for the protocol that decides where your packets go. The protocol is BGP, the Border Gateway Protocol, and the story of those sheets explains a great deal about why the internet’s routing layer behaves the way it does in 2026: trusting by default, policy-driven, and held together by social convention as much as by code.

The question worth sitting with is this. How did a protocol sketched over lunch in 1989, by two engineers solving an immediate interoperability headache, end up running every inter-network handoff on a planet-spanning system carrying trillions of dollars of traffic, with no built-in way to tell whether the routes it accepts are true? The answer is not that anyone made a bad decision. It is that BGP was always a stopgap that worked too well to replace, and security was something the internet kept promising to add later.

This post walks the timeline. EGP and the tree-shaped internet it assumed. The 1989 napkins and the path-vector idea. BGP-4 and CIDR rescuing the address space in the mid-1990s. The routing table’s growth into the millions and the day it briefly broke routers worldwide. Then the long, unfinished retrofit of security onto a protocol that shipped without any: RPKI, route origin validation, MANRS, and the BGPsec specification almost nobody runs. Along the way, the outages that taught operators what trusting your neighbors actually costs.

Before BGP: EGP and the tree

To understand why BGP looks the way it does, start with what it replaced. The early internet was small enough to route as a tree. There was a core, the ARPANET backbone, and networks hung off it. The Exterior Gateway Protocol, specified in RFC 904 in April 1984 and foreshadowed by RFC 827 before it, handled the exchange of reachability information between these autonomous systems and the core.

EGP did one job: it let a gateway tell the core network which networks it could reach. It assumed a strict hierarchy. There was no notion of choosing between competing paths because the topology did not offer competing paths. Everything flowed up to the backbone and back down. EGP carried reachability, not real routing metrics, and crucially it could not detect or break loops in a topology that contained cycles. In a tree there are no cycles, so this was fine. For a while.

The problem arrived with commercialization. By the late 1980s the NSFNET backbone had replaced the ARPANET core, multiple backbones were appearing, and networks wanted to connect to more than one provider. A single-rooted tree cannot describe an internet where Network A reaches Network C both directly and through Network B. EGP had no answer for that. It would loop, or it would simply fail to express the choice. The internet was growing a mesh, and the protocol holding its edges together assumed a tree.

1989: three sheets of paper in Austin

In January 1989, at the 12th IETF meeting in Austin, Texas, Kirk Lougheed of Cisco and Yakov Rekhter of IBM sat down and sketched a replacement. The standard telling is that the first design went onto two napkins, which is why BGP is sometimes called the “two-napkin protocol.” The napkins themselves were lost long ago. What survives is a photocopy of the three sheets of handwritten paper the napkin sketch was expanded into, preserved now in the Cisco archive at the Computer History Museum. Len Bosack, Cisco’s co-founder, is named in some accounts of the design work alongside Lougheed and Rekhter.

The result was RFC 1105, “A Border Gateway Protocol (BGP),” published in June 1989. The core idea that made BGP different from EGP is the path vector. Instead of advertising a destination with a distance metric, a BGP speaker advertises a destination along with the full list of autonomous systems a packet would cross to reach it. That list is the AS_PATH attribute, and it is the single most important design choice in the protocol.

The path vector solves the loop problem that sank EGP in a mesh. When a router receives a route, it reads the AS_PATH. If its own autonomous system number is already in that path, the route would create a loop, so the router rejects it. No counting to infinity, no distance-vector convergence pathologies, no assumption of a tree. The path itself carries the loop-prevention logic. It also carries something subtler that turned out to matter enormously: a place to attach policy. Because each AS sees the whole path, it can make acceptance and preference decisions based on who is in that path, not just on how far away the destination is.

EGP: single-rooted tree BGP: path-vector mesh core one path up, one path down A B C AS_PATH B A vs AS_PATH B C picks a path, rejects loops *EGP assumed a tree with one route up and one route down. BGP's AS_PATH lets a network see and choose between competing paths through a mesh, and reject any path that already contains its own AS number.*

BGP also made a transport decision that looks obvious now and was slightly unusual then. It runs over TCP, on port 179. EGP and the interior protocols of the day ran their own reliability logic over raw IP. BGP delegated all of that to TCP: ordered delivery, retransmission, flow control. A BGP session is just a long-lived TCP connection between two routers, over which they exchange UPDATE messages and periodic KEEPALIVEs. That choice kept the protocol simple and is part of why it has lasted. It also handed BGP a class of failure modes that come straight from TCP, which is a thread that runs through the security story later.

1991 to 1995: BGP-4 and the CIDR rescue

The first versions moved quickly. RFC 1105 was BGP-1. RFC 1163 followed with BGP-2 in 1990, and RFC 1267 brought BGP-3 in October 1991. These were refinements, not redesigns. The version that mattered, the one still in use, was BGP-4.

BGP-4 arrived because the internet was about to run out of addresses, and not the way people usually mean. The class-based addressing scheme handed out networks in three sizes. A Class A block held more than sixteen million addresses, a Class B block held 65,536, and a Class C block held 256. Most organizations were too big for a Class C and far too small for a Class B, so they took a Class B and wasted most of it. The Class B space was emptying fast. Worse, every allocated network needed its own routing table entry, and the table was growing on a curve that the routers of 1993 could not keep up with.

The fix was Classless Inter-Domain Routing, CIDR, and it required the routing protocol to stop assuming that an address’s class told you its prefix length. BGP-4, first in RFC 1654 in 1994 and then clarified in RFC 1771 in 1995, added an explicit prefix length to every advertised route. A route was no longer “this Class B.” It was now “this /17,” or “/19,” or any length you liked. That one change let providers hand out address blocks sized to need, and it let them aggregate. A provider holding a contiguous range could advertise one supernet route instead of dozens of more-specific ones.

The effect on the routing table was immediate and visible. As BGP-4 and CIDR deployment spread through 1994, the forwarding table dropped by around ten percent within about six weeks, and the exponential growth curve flattened into a roughly linear one that held for the next five years. The internet bought itself the better part of a decade of breathing room with a length field and an aggregation rule. The current BGP-4 specification, RFC 4271, was published in January 2006 and folded in fifteen years of accumulated operational experience, but it did not change the fundamentals Lougheed and Rekhter sketched. The protocol running in 2026 is recognizably the protocol from the napkins.

If you want the converging-routing-table mechanics in depth rather than the history, the companion piece BGP explained walks through how the best-path selection and convergence actually work.

The routing table that would not stop growing

CIDR slowed the growth. It did not stop it. Every multihomed network that wants its traffic to survive a provider failure announces its own address block to the world, and every such announcement is a global routing table entry that every default-free router on the internet must hold. The economics push relentlessly toward more entries. Address blocks get sliced into more-specifics for traffic engineering. Networks deaggregate to defend against hijacks. The table grows because the internet grows and because growth is messy.

The numbers tell the story plainly. The IPv4 table held roughly 20,000 entries in 1994. It crossed 100,000 around 2000, 512,000 in 2014, 768,000 in 2019, and pushed past 900,000 in the years after. IPv6, younger and less fragmented, sat in the low hundreds of thousands by the mid-2020s. Each of those round numbers is more than a curiosity, because routers do not hold the forwarding table in ordinary memory. The fast path uses TCAM, ternary content-addressable memory, which compares a destination address against every stored prefix in parallel in a single lookup. TCAM is fast and expensive and physically fixed in size. A router shipped with room for N routes cannot hold N+1.

0 512k 768k 2014: 512k day 2019: 768k 1994 2010 2024 IPv4 global routing table, prefixes held by a default-free router *The IPv4 table crossed each round number on a schedule operators could see coming. 512k day was the one where a widely shipped default caught a lot of routers at exactly the wrong size.*

On 13 August 2014, the table crossed 512,000 routes, and a lot of the internet found out the hard way that their hardware had been sized for exactly that number. Cisco’s Catalyst 6500 and 7600 platforms, certain ASR 9000 line cards, and ASR 1000s with 4 GB of RAM shipped with a default that split TCAM to hold 512,000 IPv4 routes. When the table grew past that, those routers could no longer install new prefixes in hardware. Some fell back to slow software forwarding and saw CPU spike. Some dropped routes. Traffic was lost in pockets across the internet for hours. The fix was a configuration change to reallocate the TCAM partition, available on many platforms, but it had to be applied router by router, and plenty of operators had not seen it coming. “512k day” entered the operational vocabulary. The same anxiety returned at 768,000 routes in March 2019, though by then most operators had learned to watch the CIDR Report and resize ahead of the curve.

The lesson of 512k day is not really about one vendor’s default. It is that the routing table is a shared resource that no single party controls, growing under pressure from thousands of independent decisions, and the hardware that holds it ages on a different clock than the table grows. That tension never resolves. It only gets managed.

The original sin: BGP trusts whatever it hears

Here is the thing the napkin sketch did not include, because in 1989 it did not need to. BGP has no way to verify that a route it receives is true. When a neighbor announces “I can reach 203.0.113.0/24, and the path is me,” BGP believes it. When another neighbor announces the same prefix as a more-specific “203.0.113.0/25, path me,” BGP prefers the more-specific route, because longer prefixes win, and it believes that too. There is no signature, no authority, no check that the announcer has any right to the address space it claims. The protocol assumes every speaker is honest and competent. For a network of a few hundred mutually known research institutions, that assumption was reasonable. For the commercial internet it became a standing liability.

Two failure shapes come out of this trust. A hijack is when a network announces address space it does not own, pulling traffic toward itself. A route leak is when a network announces routes it learned but should not propagate, usually re-advertising its provider’s routes to its peers or vice versa, violating the unwritten rules of who-tells-whom that hold the routing economy together. Most leaks are accidents. Some hijacks are accidents too. The protocol cannot tell the difference between an honest mistake and an attack, because it cannot tell either of them from a legitimate announcement.

The catalog of incidents is long, and reading it in order is the fastest way to understand why the security work that follows was necessary. The companion posts on BGP hijacks and route leaks and how BGP hijacking enabled crypto theft go deeper on the attack mechanics; here the point is the historical pattern.

In April 1997, a misconfigured router belonging to AS7007 re-originated a large chunk of the global table as its own, deaggregated into more-specifics, and the internet poured traffic into a network that could not carry it. This was the AS7007 incident, the first famous routing meltdown, and it was an accident caused by a software bug. In February 2008, Pakistan Telecom tried to block YouTube domestically by announcing a more-specific route for YouTube’s address space into its own network. The announcement leaked to its upstream provider and propagated worldwide, and for a couple of hours YouTube was unreachable across much of the internet because the more-specific route won everywhere. A government censorship action became a global outage through nothing more exotic than the longest-prefix-match rule.

The pattern repeats with variations. In 2010 a China Telecom leak briefly pulled a slice of the global table through its network. In 2013, researchers documented the first clear case of BGP used for man-in-the-middle interception, with traffic to financial and government targets routed on a detour through Belarus and Iceland and back, over a span of days, intact enough that the victims may never have noticed. The thread tying them together is that none of them required breaking BGP. They required only using it as designed, against a protocol that verifies nothing.

Why the more-specific route wins legitimate AS 203.0.113.0/24 hijacker AS 203.0.113.0/25 transit router longest prefix wins traffic A /25 beats a /24 on every router that hears it, no matter who is lying. *The hijacker does not need to be believed over the real owner. A more-specific prefix beats a less-specific one on longest-match alone, so announcing a /25 against a /24 quietly steals exactly that traffic.*

2018: when the trust gap turned into theft

For years BGP incidents were mostly outages and espionage. The 2018 MyEtherWallet attack showed the internet what a routing hijack looks like when the goal is money, and it stitched together routing, DNS, and TLS into one clean theft.

On 24 April 2018, for roughly two hours, a network in Columbus, Ohio, AS10297, belonging to a hosting company called eNet, announced more-specific routes covering five address blocks that belonged to Amazon’s Route 53 DNS service. Those /24 announcements pulled DNS query traffic for Route 53 toward attacker-controlled infrastructure on a compromised server in Chicago. The fake DNS service answered queries for myetherwallet.com with the IP of a phishing site hosted in Russia. Users who typed the right address, with no typo and no malware on their machines, were handed the wrong server because the route to Amazon’s nameservers had been bent. The phishing site presented a self-signed certificate, which threw a browser warning, and the users who clicked through it lost their funds. Estimates of the take ran from roughly $150,000 upward in Ethereum.

The attack is worth dwelling on because it shows how the layers depend on each other. BGP delivered the traffic to the wrong place. DNS, sitting on top, returned the wrong answer because its packets were intercepted. The only thing standing between the user and the loss was the TLS certificate warning, the one layer that did its job, and many users clicked past it. Cross-link reading on the layers underneath this stack lives in the history of DNS and the history of CDNs, both of which inherit BGP’s trust assumptions whether they want to or not.

Later attacks refined the trick. In 2022 the KLAYswap incident in South Korea hijacked the address of a server hosting a JavaScript file, served malicious script, and pulled off roughly $2 million; the attacker even obtained a valid TLS certificate by passing a certificate authority’s domain validation check, because that check itself relied on routing the CA’s validation request, which the hijack also captured. The same year, the Celer Bridge attack forged routing database entries and a fake AS path that included Amazon’s AS number to lend the hijack credibility and slip past origin checks. The crypto era gave BGP hijacking a clear price tag, and the price tag funded better tradecraft.

The retrofit, part one: RPKI and route origin validation

The security community had understood the problem for a long time. Bolting a fix onto a deployed protocol that the entire internet runs simultaneously, with no flag day and no central authority, is the hard part. The first piece to reach real deployment was RPKI, the Resource Public Key Infrastructure, specified across a family of RFCs starting with RFC 6480 in 2012.

RPKI builds a chain of cryptographic certificates that mirror the way address space is actually allocated. The five Regional Internet Registries sit at the top, each holding a certificate for the address blocks it administers. When an RIR allocates a block to a network, it issues that network a certificate for the block. The network can then create a Route Origin Authorization, a ROA, a signed statement that says “autonomous system number X is authorized to originate these prefixes.” The ROA is the cryptographic answer to the question BGP never asked: does the announcer have the right to this address space?

ROAs by themselves do nothing to traffic. They are signed records sitting in a repository. The enforcement half is Route Origin Validation, specified in RFC 6811 in 2013. A router doing ROV fetches the validated ROA data, then checks each route it receives against it. A route whose origin AS and prefix match a ROA is “valid.” A route with no covering ROA is “not found,” which is treated as neutral because most of the internet still has no ROA. A route that contradicts a ROA, wrong origin AS or a more-specific prefix the ROA does not permit, is “invalid,” and the common policy is to drop invalid routes outright.

Route origin validation, end to end RIR signs the block ROA AS + prefix, signed validator pulls + checks ROAs router (ROV) RTR feed of states valid accept not found accept invalid drop ROV checks the origin AS only. It says nothing about the rest of the path. *Origin validation answers one question: is the AS at the end of the path allowed to announce this prefix? It does not check whether the path in between is real, which is the gap BGPsec was meant to close.*

ROV deployment was slow at first and then picked up sharply in the late 2010s. A turning point was large operators committing publicly. Cloudflare turned on origin validation and started publishing measurement data showing how much of the routing table was covered by ROAs and how many networks were dropping invalids. By the mid-2020s the majority of announced address space had ROAs, and a large and growing share of the internet’s networks were rejecting RPKI-invalid routes, which is why a modern fat-finger hijack often gets contained in minutes instead of hours. ROV is real, it works, and it is the one piece of BGP security that operators genuinely run at scale.

It also has a hard limit baked into its name. Origin validation checks the origin. It confirms that the AS at the end of the path is allowed to announce the prefix. It says nothing about whether the path leading to that origin is real. An attacker who forges an AS_PATH ending in the legitimate origin’s AS number, the trick the Celer Bridge attackers used, can produce a route that passes ROV while still hijacking traffic. Closing that gap requires validating the whole path, which is a much harder problem.

The retrofit, part two: BGPsec, the fix almost nobody runs

BGPsec, specified in RFC 8205 in September 2017, is the answer to the path problem. The idea is that each AS along the way cryptographically signs the route as it forwards it, so that every hop in the AS_PATH carries proof that the previous AS authorized handing the route to it. A receiver can verify the entire chain. A forged path fails verification because the attacker cannot produce the signatures of ASes it does not control.

On paper this closes the gap ROV leaves open. In practice almost nobody runs it, and the reasons are a case study in why retrofitting security onto deployed infrastructure is brutally hard. BGPsec has to be validated and signed at every hop to mean anything, which creates a first-adopter problem with no payoff: if you deploy it and your neighbors have not, you have spent money and gained almost nothing, because an unsigned path segment breaks the chain. The cryptographic work is heavy. Routers carrying hundreds of thousands of routes would need to verify a signature chain on every update, and the current generation of forwarding hardware was not built for that. The update messages get larger. And, the detail that quietly sank a lot of enthusiasm, BGPsec does not stop route leaks at all. A network authorized to announce a prefix can still leak it to the wrong neighbor with a perfectly valid signed path. BGPsec secures the path’s authenticity, not the policy correctness of who it was handed to.

The result, nearly a decade after standardization, is that BGPsec has effectively no production deployment. It is a finished specification waiting for a hardware generation and an incentive structure that have not arrived. Origin validation got deployed because a network can turn it on unilaterally and benefit immediately. BGPsec asks everyone to move together, and on the internet, getting everyone to move together is the thing that never happens.

The retrofit, part three: MANRS and norms instead of crypto

While the cryptographic fixes ground forward slowly, a different kind of retrofit took a different bet: that a lot of the routing damage comes from sloppiness, not attackers, and that you can fix sloppiness with norms and peer pressure. This is MANRS, Mutually Agreed Norms for Routing Security, which grew out of a Routing Resilience Manifesto effort in early 2014 and launched formally that November, later backed by the Global Cyber Alliance.

MANRS does not invent new protocol mechanisms. It asks participating networks to do four unglamorous things well. Filter, so you do not accept or propagate routes your neighbors should not be sending you. Prevent spoofing, by validating source addresses so your network is not a launchpad for spoofed-source attacks. Coordinate, by keeping your contact information current so other operators can reach you when something breaks. And validate, by publishing your routing data through tools like RPKI and the internet routing registries so others can filter against it. None of these is novel. The MANRS bet is that publicly committing to them, and being seen to commit, drags the median operator’s hygiene up.

It is a sociological fix for a technical problem, and that is exactly right for a system that was always held together as much by convention as by code. The internet’s routing layer has never had an enforcement authority. It has neighbors who agree to behave, and a long memory for who does not. MANRS formalizes the agreement without pretending it can compel anyone. Whether it moves the needle is genuinely hard to measure, which is the standing critique of it, but the alternative of waiting for universal BGPsec is a longer wait.

2021: Facebook withdraws itself from the internet

The most-watched BGP event of the decade was not an attack. On 4 October 2021, Facebook disappeared for roughly six hours, and it took Instagram, WhatsApp, and Messenger with it. The cause was BGP, and the mechanism is a clean demonstration of how routing, DNS, and operational tooling interlock.

During routine maintenance, an engineer ran a command intended to assess backbone capacity that instead disconnected Facebook’s data centers from its backbone. Facebook’s authoritative DNS servers were built to do something sensible in isolation: if they lost their connection to the data centers, they would withdraw their own BGP route announcements, on the theory that a nameserver that cannot reach the services behind it should stop advertising itself. The maintenance error triggered exactly that condition fleet-wide. At 15:39 UTC, Facebook withdrew the BGP routes to the prefixes carrying its DNS servers. With those routes gone from the global table, the rest of the internet had no path to Facebook’s nameservers, so no one could resolve facebook.com, so nothing about Facebook worked. The withdrawal also locked out Facebook’s own engineers, whose internal tools and physical access systems depended on the same infrastructure. Routes came back a little before 21:00 UTC, and the domain resolved again by 21:05.

No one hijacked anything. Facebook’s routers did precisely what they were configured to do, and the configuration encoded an assumption that a single maintenance command managed to violate at global scale. It is the inverse of a hijack: instead of announcing routes it should not, a network withdrew routes it needed, and the withdrawal propagated with the same speed and obedience that makes hijacks dangerous. The episode put BGP on the front page of newspapers that had never printed the acronym, and it taught a generation of engineers that the routing layer is not someone else’s problem.

What the napkins got right, and what they could not

Step back and the shape of the history is clear. BGP is a protocol designed in an afternoon to solve a specific 1989 problem, the mesh that EGP could not describe, and the path-vector idea at its heart was good enough that it never needed replacing. BGP-4 and CIDR rescued the address space without changing the fundamentals. The routing table grew into the millions and the protocol carried it, with occasional hardware scares like 512k day that were really scaling problems wearing a BGP costume. The thing the design left out, any way to verify that a route is true, was not an oversight so much as a non-problem in 1989 that became the central problem of the next thirty years.

The retrofit is real but lopsided. Origin validation works and is widely deployed because any single network benefits the moment it turns ROV on. Path validation works on paper and is deployed essentially nowhere because it only pays off when everyone moves together. MANRS fills the gap between them with social commitment, which is fitting for a protocol that always ran on trust. The honest summary in 2026 is that BGP is partway through a security upgrade that began over a decade ago and has no scheduled completion, because there is no one who can schedule it.

That is the most BGP thing about BGP. It has no center. No one runs it, no one can flag-day it, no one can force the next fix. The three sheets of paper from Austin sketched a protocol for a network of trusting peers, and the network grew into something that should not trust anyone, and the protocol is still, structurally, the one from the paper. The internet routes packets across tens of thousands of independent networks every second, on the strength of announcements it mostly cannot verify, held together by ROAs where they exist and good manners where they do not. It works far better than it has any right to. That gap, between how fragile the trust model is and how rarely it fails, is the whole story.

Sources & further reading

Further reading