Every routing protocol on this site was written by someone, for a network that had a specific problem on a specific day. This chapter tells that story in order: four machines in 1969, a network that fell over in 1980 because of three numbers, a protocol sketched on two napkins in 1989, and the long work since of making a system built on trust a little less trusting. Every date comes from the document that made it true.
Common mix-up: link-state routing is often presented as the modern successor to distance vector, as if one replaced the other in the 1990s. In fact the ARPANET switched its routers to a link-state algorithm around 1979, about nine years before RIP, the best-known distance-vector protocol, was written down as RFC 1058 in 1988. Both families have been in continuous use ever since; neither is "the new one."
This chapter assumes you know what a routing protocol is for and the difference between distance vector and link state. If either is new, read dynamic routing on networks.jelia.nyc first; it is the on-ramp to everything here. The technical chapters of this site then explain each protocol properly. This one only tells you when, who and why.
The timeline below holds every event the chapter mentions, placed by its publication month. Each lane is a family: interior protocols that route inside one network, exterior protocols that route between networks, label switching and engineered paths, routing security, and a lane of milestones and incidents. Switch families on and off, then click or tap a dot (or focus the timeline and use the arrow keys) to read what it was and why it mattered.
Dates are the publication month printed in each RFC header and in the RFC Editor's index; incident dates come from the cited write-ups. Busiest year counts the events currently shown.
The ARPANET's first node went in at UCLA's Network Measurements Center in 1969, followed soon after by SRI, UC Santa Barbara and the University of Utah. Hosts did not route. Each one was attached to an Interface Message Processor, or IMP: a Honeywell 516 minicomputer with 12K of memory, programmed by Bolt Beranek and Newman (BBN). The IMPs were the network's routers, before the word was in use; they carried messages between themselves and decided which line each one should take.
The first IMP routing used the Bellman-Ford idea that Chapter 4 takes apart in detail: every IMP keeps an estimate of how far each destination is, shares those estimates with its neighbors, and believes the neighbor that offers the best number. RFC 1058, written in 1988, notes that algorithms of this kind "were used in computer routing as early as 1969 in the ARPANET." The approach is simple and needs little memory, which mattered a great deal on a 12K machine. Its weakness is that bad news travels slowly: when a line fails, the estimates can chase each other upward for a long time before every IMP agrees the destination is far away.
Around 1979 BBN replaced it. The design was published in May 1980 as "The New Routing Algorithm for the ARPANET" by John McQuillan, Ira Richer and Eric Rosen in the IEEE Transactions on Communications. Instead of passing on opinions about distances, each IMP now announced facts about itself: which neighbors it had over working lines, and the average per-packet delay on each. Those announcements were copied to every IMP in the network, and each IMP ran a shortest-path computation over the complete map. That is the link-state design that OSPF and IS-IS still use. Rosen's later account says an update "will almost always reach all other IMPs in a time period on the order of 100 ms."
| Original ARPANET routing (from 1969) | "New routing algorithm" (from about 1979) | |
|---|---|---|
| What an IMP sends | Its own estimate of the distance to every destination | Only its own links and their measured delay |
| Who receives it | Immediate neighbors | Every IMP, by flooding |
| How routes are found | Believe the neighbor with the best estimate | Each IMP computes shortest paths over the whole map |
| What keeps updates in order | Not needed: each round replaces the last | A 6-bit sequence number on every update |
| Today's descendants | RIP, Babel and other distance-vector protocols (Chapter 4) | OSPF and IS-IS (Chapter 5, Chapter 6) |
RFC 789 summarizes the updating scheme. Every IMP had to generate an update at least once a minute and was not allowed to generate more than a dozen a minute. Each update carried a 6-bit sequence number that went up by one, modulo 64, every time. When an IMP received an update from another IMP, it compared the sequence number with the last one it had accepted from the same origin. If the new one was more recent it was accepted, stored, and sent on to every neighbor, including the one it came from; if not, it was discarded.
Because a dozen updates a minute could never use up 64 numbers in the 100 milliseconds a flood took, wrap-around was considered safe. For two IMPs that had been cut off from each other for longer than a wrap, there was a rescue rule: if an IMP heard nothing more recent from an origin within one minute of its last accepted update, it would accept the next update from that origin whatever its number.
On October 27, 1980, the ARPANET became unusable for several hours. Eric Rosen of BBN wrote up what happened, and the account was circulated in 1981 as RFC 789, "Vulnerabilities of Network Control Protocols: An Example." It is still one of the clearest incident reports ever written about a routing protocol, and every link-state designer since has had to answer the problem it describes.
When BBN's network control center examined core dumps, it found that most of the IMPs' buffers were full of routing updates, all generated by a single IMP, number 50, which was not even running at the time. They all had one of three sequence numbers, 8, 40 or 44, and they sat in the queues in a repeating order: 8, 40, 44, 8, 40, 44.
The cause was the comparison rule. With only 64 numbers available, "more recent" has to be defined on a circle. RFC 789 defines it like this: update n is LATER than update m if either
In words: a number is newer if it is ahead of the other by at most half the circle. Check the three numbers. 44 is LATER than 40, because it is 4 ahead. 40 is LATER than 8, because it is 32 ahead. And 8 is LATER than 44, because 44 is 36 ahead of 8, which is more than half the circle, so the rule decides 8 has wrapped around and is newer. Each update beats one of the others, so no IMP could ever settle on one. Whichever it held, another copy arrived that looked newer, was accepted and was flooded to every neighbor, forever. The IMPs spent their time and buffers on the cycle and had little left for traffic.
How did three versions of one update exist at once? Written in binary, 8 is 001000, 40 is 101000 and 44 is 101100. Each differs from the next by a single bit. Rosen's conclusion was that there had only ever been one update, 44, and that a malfunctioning IMP had retransmitted it from a corrupted copy in memory, dropping one bit and then another. The update packets were checksummed in transit, but the tables they were rebuilt from were not, and the hardware's parity checking had been switched off because it raised too many false alarms. Because the IMPs were unattended and could only be controlled through the network itself, a patch that would normally take minutes to send took three or four hours.
Six IMPs, joined in a ring with three cross links, each remember the most recent update they have accepted from IMP 50. Below, set up to three copies of that update by flipping bits, and choose where in the network each copy appears. Then step or run the flood exactly as RFC 789 describes it: accept if LATER than what you hold, store it, and send it to every neighbor. Switch the comparison to a linear sequence space, the kind OSPF uses, and run the same copies again.
Each round, every update in flight arrives at its IMP and is either accepted and re-flooded, or discarded. The simulation stops when nothing is in flight, or after 400 rounds; "Jump to the end" computes the remaining rounds at once.
Two things show up quickly. First, a cycle in the LATER relation is what makes an endless storm possible; the instrument checks for it before you press anything. Second, whether a storm actually happens depends on timing: put the same three copies into the network at different places and the flood sometimes dies out, because one copy reaches every IMP before the others arrive. It also helps explain why RFC 789 could call this the first such problem in a year and a half of running the algorithm: the dangerous combination needed corrupted memory and unlucky timing at once.
The lessons ended up in later protocols. OSPF's sequence number (RFC 2328, section 12.1.6) is a signed 32-bit integer in a linear space: it starts at 0x80000001, only ever counts up, and when it reaches the top the old advertisement must be flushed from the whole network before the count restarts. Advertisements also carry an age and are discarded when it runs out, so nothing can circulate forever. Chapter 5 shows how that works today.
An ordering has to be transitive: if a is newer than b and b is newer than c, then a must be newer than c. A comparison on a circle cannot promise that. With "newer means ahead by at most half the circle," any three numbers spread around the circle so that each gap is less than half (here the gaps are 4, 32 and 28) form a cycle. The rule is safe only as long as all live copies sit within half a circle of each other, which the designers expected from the update rate. Corrupted memory broke that assumption.
Linear sequence spaces avoid the problem by never wrapping during normal operation: with 231 values and a cap on how often an advertisement can be refreshed, an OSPF router would take many years to run out. Wrap-around becomes an explicit, rare event with its own procedure, instead of something the comparison has to guess.
By the early 1980s the ARPANET was one network among several, joined by gateways, and the question changed from "which line inside my network?" to "which network do I hand this to?" Eric Rosen of BBN published a draft standard for it in October 1982: RFC 827, the Exterior Gateway Protocol. It organized gateways into "autonomous systems," each under one administration, and for concreteness described a "core" system at the center: the DARPA gateways on the ARPANET and SATNET, with "stub" gateways attached to it.
EGP's limits were spelled out in its own text. It was "intended for a set of autonomous systems which are connected in a tree, with no cycles," and it did "not enable the passing of sufficient information to prevent routing loops if cycles in the topology do exist." An EGP update said which networks a gateway could reach, with a distance, but not the path behind that claim. In a tree there is only one path, so that was enough. RFC 888 (January 1984) described a "stub" version for networks hanging off the core, and David Mills's formal specification, RFC 904 (April 1984), wrote the state machine down precisely, expecting that EGP would one day grow "to include topologies not restricted to tree-structures."
That day came with the NSFNET. Created in 1986 with a 56 kbit/s backbone linking five supercomputer centers, it was upgraded to T1 (1.544 Mbit/s) and later to T3 (45 Mbit/s), and it pulled regional and campus networks across the United States, and soon other countries, into one internet (RFC 2235). The NSFNET backbone ran its own link-state interior protocol, which RFC 1093 (February 1989) describes as "adapted from the IS-IS protocol" that ANSI had submitted to ISO, itself "based upon work done at Digital Equipment Corporation." Between the backbone and the regional networks it still used EGP, and RFC 1092, by Yakov Rekhter, explained how policy-based routing would be applied there. Once networks joined each other through more than one path, the tree was gone, and a protocol that could not see loops was no longer safe.
The fix is usually told as a lunch. In 1989, at an Internet Engineering Task Force meeting about improving the existing exterior routing protocol, Kirk Lougheed of Cisco and Yakov Rekhter of IBM sat down in the cafeteria and wrote out a new protocol on what paper they had, which was napkins. The Computer History Museum's account, drawn from the Cisco archive, says photocopies of the napkin notes survive but the napkins themselves were thrown away. The Internet Hall of Fame entry for Lougheed says it took two of them, which is why the internet still calls BGP "the two-napkin protocol."
The result was published in June 1989 as RFC 1105, "A Border Gateway Protocol (BGP)," by Lougheed and Rekhter. Its key idea fits in one sentence of the RFC: each route carries "information on the autonomous systems (AS's) that traffic must transit to reach these networks," which "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." Carrying the whole AS path, not just a distance, did two jobs at once. A router that finds its own AS number in a path knows the route has looped and drops it, so the tree restriction disappears. And an operator can see who a route passes through, which is what makes policy possible. RFC 1105 also put BGP on a reliable transport, TCP in the initial implementation, so the protocol did not have to provide its own retransmission. At publication, it noted, implementations already existed "for cisco routers as well as for the NSFNET Nodal Switching Systems."
BGP changed quickly. RFC 1163 (June 1990) replaced the first version, and RFC 1267 (October 1991) defined BGP-3. Then the address plan forced a bigger change. Addresses still came in fixed classes: a class C held 254 hosts, too few for most organizations, and a class B held 65,534, too many, so class B space was running out while routing tables filled with class C networks. RFC 1338 (June 1992) proposed "supernetting," and RFC 1519 (September 1993), by Vince Fuller, Tony Li, Jessica Yu and Kannan Varadhan, made it Classless Inter-Domain Routing: allocate blocks of any power-of-two size along provider lines and advertise them as single aggregated prefixes. Its abstract names the target: "the explosive growth of routing tables in default-route-free routers."
A protocol that thought in classes could not carry classless prefixes, so BGP-4 was written around them. RFC 1654 (July 1994), edited by Rekhter and Li, introduced it; RFC 1771 (March 1995) replaced 1654 and says BGP-4 "provides a new set of mechanisms for supporting classless interdomain routing," including aggregation of routes and of AS paths. The Internet Hall of Fame credits Rekhter, "with Tony Li," for BGP-4, "which brought Classless Inter-Domain Routing (CIDR) to the Internet." BGP-4 has never been replaced. Its current specification, RFC 4271 (January 2006), is a revision of the same protocol, and CIDR's own document was revised the same year as RFC 4632. How BGP sessions and policy work today is the subject of Chapter 8 and Chapter 9.
The RFC Editor's index records that RFC 1163 obsoletes RFC 1105, RFC 1267 obsoletes 1163 (the BGP-3 header itself lists both 1105 and 1163), RFC 1771 obsoletes 1654 and RFC 4271 obsoletes 1771. One link is missing: RFC 1654 does not formally obsolete BGP-3. BGP-4 was a new version of the protocol, announced by a new version number in its OPEN message, rather than a revision of the BGP-3 document; RFC 1267 is now marked Historic.
The single biggest change was in the UPDATE message. Before BGP-4, a destination was a classful network number. From BGP-4 on, every destination is written as a prefix length plus just enough bytes to hold that many bits, so a /21 and a /24 are equally natural. That encoding is why CIDR could be deployed without changing every host on the internet: only the routers had to learn to think in prefixes.
An RFC is never edited after publication. When a protocol changes, a new RFC is published that obsoletes the old one, or updates it with additions that are read alongside. Following those links is how you find the specification that is in force today, and how you find out what a decades-old document has been replaced by. The graph below shows the main routing lineages, with every link taken from the RFC Editor's index. Click or tap a document (or focus the graph and use the arrow keys) to light up its whole family and find the current one.
The status shown for each RFC (Internet Standard, Draft Standard, Proposed Standard, Historic and so on) is what the RFC Editor's index listed on October 22, 2026. "Current" means a document in this lineage that nothing has obsoleted and that is not Historic.
A few patterns stand out once you click around. OSPF went through five documents in nine years, all written by John Moy, before settling as RFC 2328, Internet Standard 54, in 1998. RIP version 2 updated the original RIP rather than replacing it, and RFC 1058 itself is now Historic. And not every successor is formal: BGP-4 began as a new protocol version, so RFC 1654 never obsoleted BGP-3, and the BGP family is split in two in the index even though everyone treats it as one story.
Inside networks, the late 1980s were about writing down what people were already running, and then doing better. RIP came first. Charles Hedrick of Rutgers wrote RFC 1058 in June 1988 to document a program that was already everywhere: routed, shipped with Berkeley Unix. RFC 1058 traces its ancestry to Xerox: the PUP protocols' Gateway Information Protocol, then the Routing Information Protocol of Xerox Network Systems, with XNS addresses replaced by a general format and updates every 30 seconds. It also states plainly that the protocol depends on "counting to infinity," with 16 standing for infinity. Gary Malkin's RIP version 2 added subnet masks, finally standardized as RFC 2453 in 1998.
OSPF, "Open Shortest Path First," was the IETF's own link-state protocol. John Moy wrote the first specification, RFC 1131, in October 1989; version 2 followed in RFC 1247 in July 1991 and became Internet Standard 54 as RFC 2328 in April 1998. Moy is the author of every one of those documents and a co-author of OSPF for IPv6 (RFC 2740 in 1999, RFC 5340 in 2008).
IS-IS came from the other side of the standards world. It was ISO's intra-domain routing protocol for OSI networks, standardized as ISO/IEC 10589; the IETF republished a draft of it as RFC 1142 in February 1990, edited by Dave Oran of Digital Equipment Corporation, "as a service to the Internet community." Ross Callon's RFC 1195 (December 1990) then extended it to carry IP routes, so one protocol could route both OSI and IP; that "integrated" IS-IS is the form in which IS-IS routes IP. The Internet Hall of Fame credits Radia Perlman with designing IS-IS in the 1980s and says her innovations "enable today's link state routing protocols to be robust, scalable, and easy to manage." The same entry credits her with the spanning tree algorithm that let Ethernet grow into large bridged networks. RFC 1142 itself was moved to Historic in 2014 by RFC 7142, which explains that the draft it reproduced differed in many significant ways from the final ISO standard and asks that references point to ISO/IEC 10589 itself. Chapter 6 explains why IS-IS kept its place in the largest networks.
Once the routing protocols were stable, the attention shifted to how packets are forwarded and how fast the network reacts. MPLS, Multiprotocol Label Switching, was published as an architecture in RFC 3031 in January 2001, by Eric Rosen, Arun Viswanathan and Ross Callon. Instead of looking up the destination address at every hop, routers forward on a short label attached at the edge of the network, an approach that went on to carry traffic engineering and VPN services in large provider networks. The Internet Hall of Fame names Yakov Rekhter as a co-developer of tag switching, one of the designs that fed into it, and of MPLS itself.
Detection got faster too. BFD, Bidirectional Forwarding Detection (RFC 5880, June 2010, by Dave Katz and Dave Ward), gave routers a light, protocol-independent way to notice a dead link in milliseconds rather than waiting for a routing protocol's own timers; Chapter 7 covers it. In 2016, RFC 7938 described something that would have puzzled the authors of RFC 1105: using BGP as the only routing protocol inside large data centers (Chapter 14).
Then labels became instructions. Segment routing, whose architecture is RFC 8402 (July 2018, edited by Clarence Filsfils and Stefano Previdi), lets the source put an ordered list of segments on a packet, so the path is carried in the packet rather than set up hop by hop with signaling. It runs over MPLS labels or, as SRv6 (RFC 8986, February 2021), over IPv6 addresses. Chapter 12 explains both.
BGP was designed among a small community of research and academic networks. A router believes what its neighbors announce unless its operator has written a filter to say otherwise. As the internet grew into a commercial system of tens of thousands of networks, the cost of that trust showed up in incidents. Two are especially well documented.
On Sunday, February 24, 2008, at 18:47 UTC, Pakistan Telecom began announcing a more specific prefix, a /24, covering part of YouTube's address space; the RIPE NCC's case study, built from its Routing Information Service data, describes how its upstream provider passed the route on and YouTube traffic was drawn away "on a global scale." Because routers prefer the longest matching prefix, YouTube's own wider announcement could not compete. At 20:07 YouTube began announcing the same /24, and at 20:18 it announced two /25s, which are more specific still and won everywhere they reached. At 21:01 the upstream provider withdrew the hijacked route. The whole event lasted a little over two hours.
On June 24, 2019, a different failure, a route leak, took parts of the internet offline. Cloudflare's write-up describes a BGP optimizer at one network splitting received prefixes into more specific routes, which were passed to a customer and then by that customer to its transit provider, which advertised them to the rest of the internet. At the worst point Cloudflare lost about 15% of its global traffic. The post's own diagnosis is that the provider "should never have forwarded those routes," and its remedies are filtering: prefix limits on sessions, filters built from routing registries, RPKI origin validation, and the practices collected by MANRS.
The cryptographic answer took years to build. The Resource Public Key Infrastructure, RPKI, was described in RFC 6480 (February 2012) by Matt Lepinski and Stephen Kent: certificates that follow the allocation of addresses and AS numbers, so the holder of a prefix can sign a statement of which AS may originate it. RFC 6811 (January 2013) defined how routers use those statements, route origin validation, marking each route valid, invalid or not found. BGPsec (RFC 8205, September 2017) went further and signed the whole AS path, though it has seen far less deployment. Chapter 11 shows how these defenses work and what each one does and does not stop.
| Incident | What went wrong | What would have helped | Source |
|---|---|---|---|
| ARPANET, Oct 27, 1980 | Corrupted copies of one update formed a cycle under a circular sequence comparison | Error-detecting memory; a linear sequence space with aging | RFC 789 |
| YouTube hijack, Feb 24, 2008 | A more specific prefix announced by a network that did not hold it, passed on by its upstream | Customer prefix filters at the upstream; origin validation | RIPE NCC |
| Route leak, Jun 24, 2019 | More-specific routes from an optimizer leaked customer-to-provider, then to the whole internet | Prefix limits, registry-based filters, RPKI, MANRS practices | Cloudflare |
Protocols are written by committees and refined by thousands of implementers, so any list of names is unfair to most of the people who did the work. The table credits only what the cited documents themselves say: authorship on the RFC, or the wording of an Internet Hall of Fame citation.
| Person | Contribution, as the source records it | Source |
|---|---|---|
| John McQuillan, Ira Richer, Eric Rosen | "The New Routing Algorithm for the ARPANET," the link-state design, 1980 | IEEE Trans. Commun., cited in RFC 789 |
| Eric C. Rosen | The 1980 outage report (RFC 789); the first EGP specification (RFC 827) | RFC 789, RFC 827 |
| David L. Mills | EGP formal specification | RFC 904 |
| Hans-Werner Braun | The NSFNET routing architecture | RFC 1093 |
| Charles Hedrick | Wrote down RIP as used by Berkeley's routed | RFC 1058 |
| Kirk Lougheed and Yakov Rekhter | Designed BGP; the two-napkin lunch; RFC 1105, 1163, 1267 | RFCs; Computer History Museum; Internet Hall of Fame |
| Yakov Rekhter and Tony Li | BGP-4, which brought CIDR to the internet; editors of RFC 1654, 1771, 4271 (with Susan Hares) | RFCs; Internet Hall of Fame |
| Vince Fuller, Tony Li, Jessica Yu, Kannan Varadhan | Supernetting and CIDR | RFC 1338, RFC 1519, RFC 4632 |
| John Moy | Author of every OSPF version 2 specification, RFC 1131 to RFC 2328 | RFCs |
| Radia Perlman | Designed IS-IS in the 1980s; the spanning tree algorithm; robust link-state routing | Internet Hall of Fame |
| Dave Oran; Ross Callon | Edited the IS-IS republication (RFC 1142); integrated IS-IS for IP (RFC 1195) | RFCs |
| Matt Lepinski and Stephen Kent | The RPKI architecture | RFC 6480 |
| Clarence Filsfils, Stefano Previdi and co-authors | The segment routing architecture | RFC 8402 |