Longest Prefix
When several routes cover the same address, the one covering the fewest addresses wins. That is a requirement rather than a preference, and it is applied mechanically, with nothing anywhere asking whether the most specific announcement is one the announcer was entitled to make. On 24 February 2008 it was demonstrated on the whole internet twice in one afternoon: once by a network that should not have been announcing the block at all, and once by its owner, who took the traffic back using the same rule and nothing else.
New to how a router decides where to send a packet? Start here
A router does not know where any particular machine is. It knows ranges: blocks of addresses, each written as a starting address and a count of how many leading bits are fixed, and for each block, the next router to hand the packet to. That is the whole routing table.
Those blocks are allowed to overlap, and they nearly always do, because a large block can be handed out and then a piece of it delegated to somebody else. So a single destination address is often inside several of them at once, and the router needs a rule for which one to believe. That rule is the subject of this page, and it is simpler than the situation deserves.
A message that takes time and may not arrive
Two computers in one room are far apart by a processor's standards. A message crossing between them takes time you cannot argue with, and across a continent that floor is set by the speed of light in glass.
Worse, it may arrive after a message sent later, or arrive twice, or never arrive at all, and the sender is not told which. There is no moment at which both ends know the same thing. Every machine in this topic is a way of getting useful work done anyway, without that guarantee, and the ones that look overcomplicated are usually the ones that stopped pretending.
The machine for this idea on its own is Packet Switching, if you would rather press it than read about it.
Three routes match the address, and the longest one wins
1 An address, and a routing table in which more than one route matches it
The default table is the worked example from RFC 1812 section 5.2.4.3, and the default address is the one the RFC uses. Change either. Every route the address falls inside is listed, because the situation the rule exists for is the one where more than one of them does.
| route | length | matches |
|---|
2 The rule that picks one of them, run two ways that share no code so that agreement means something
The rule is run twice, by code that shares nothing. One walks the table and keeps a running maximum. The other walks the address one bit at a time down a binary trie and takes the deepest route it passed. They must reach the same route, and a seeded sweep checks that they do across many random tables rather than on this one; the sweep prints its own count and its own seed below, because a number typed into this sentence would be a second copy of one the sweep already knows.
| mechanism | answer | work |
|---|
3 What the rule does when the longest prefix is a lie, on the afternoon that happened to the whole internet
On 24 February 2008 the rule was exercised on the whole internet in both directions inside two hours. Every prefix and every time below is from RIPE NCC's case study. Nothing in the rule asks whether an announcement is true.
| route | announced by | gets the traffic |
|---|
| at | longest match | traffic goes to |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| the RFC's own example: three routes match one address and the longest is kept | yes | 10.144.2.5 is inside all three of 10.144.2.0/24, 10.144.0.0/16, 10.0.0.0/8, and the rule keeps 10.144.2.0/24 |
| a table walk and a bit walk reach the same route without sharing any code | yes | the linear scan made 3 comparisons and the trie descended 24 levels; neither ever compares two prefix lengths to each other except the scan's running maximum |
| and they agree on ten thousand random lookups from a seed that can be replayed | yes | 10,000 lookups across 40 random tables at seed 20260828, no disagreement; a failure would name the address, and re-running the seed would produce it again |
| the default route is a prefix of length zero and loses to everything that matches | yes | adding 0.0.0.0/0 to the table does not change the answer for 10.144.2.5, and it is the answer for an address nothing else covers; there is no special case for it in either implementation |
| a longer prefix takes the traffic, with nothing anywhere asking whether it is entitled to | yes | before the announcement 208.65.153.238 matches only 208.65.152.0/22; at 18:47 UTC a /24 inside it appears and the rule sends the traffic to AS17557 (Pakistan Telecom) |
| matching the prefix length exactly does not win it back, because the rule has stopped deciding | yes | at 20:07 UTC two routes of length 24 match, so longest-prefix has nothing left to say and the choice falls to BGP policy such as the shorter AS path; the report records that Pakistan Telecom kept attracting some of the traffic |
| and the same rule ends the hijack, which is why it is not a bug | yes | at 20:18 UTC two /25s are announced and every router that hears them prefers a /25 over the /24, exactly as it preferred the /24 over the /22 ninety minutes earlier; the mechanism did not change sides |
| the counts here are comparisons and levels, and no timing is claimed | yes | how long a lookup takes depends on the part doing it, and production routers do not walk a binary trie one bit at a time; what is modelled is the rule, and the work is counted in operations rather than dressed up as nanoseconds |
| route origin authorisation exists and is not presented here as having settled this | yes | RPKI lets a network sign which AS may originate a prefix, and adoption has grown a great deal since 2008; it changes which announcements a router will accept and it does not change this rule, which still prefers the longest of whatever it did accept |
What is real here, and what is not
The counts here are comparisons and trie levels, and no timing is claimed
How long a lookup takes depends on the part doing it, and a production router does not walk a binary trie one bit at a time; it uses content-addressable memory, or a compressed multibit trie, or one of a dozen schemes designed around a particular memory system. What is modelled here is the rule. The work is counted in operations because operations are a property of the algorithm, and nanoseconds would be a property of hardware this page has not got.
A tie of equal prefix lengths is not decided by this rule at all
At 20:07 UTC on the day in question there were two routes of the same length to the same block. The longest-prefix rule has nothing to say about that, and the choice fell to BGP's own policy, chiefly the shorter path. The report records that Pakistan Telecom kept attracting some of the traffic through it. A page that let the rule appear to decide the tie would be misdescribing the one moment where it visibly did not.
Route origin authorisation exists and has not made this go away
RPKI lets an address holder sign which network may originate its prefixes, and a router can drop announcements that fail the check. Adoption has grown a great deal since 2008 and it is a real improvement. It changes which announcements a router is willing to accept; it does not change this rule, which still prefers the longest of whatever was accepted. Presenting it as having closed the matter would be an overclaim.
The routing table here has no policy in it
A real forwarding decision has more inputs than prefix length: local preference, path length, origin, multi-exit discriminators and whatever the operator has written down. Longest prefix is applied first and dominates all of it, which is why it is worth a page on its own, but a table of prefixes with a next hop is a model of a routing table and not one.
1993 to 1995 is the range from the mechanism to the requirement
RFC 1519 defines classless addressing in September 1993, which is what makes several routes able to match one address. RFC 1812 makes longest match a requirement of a conforming router in June 1995. Routers were doing it before it was written down as a must, and the site dates the range rather than picking one end and calling it the invention.
The sweep is seeded so that a disagreement can be reproduced
The two implementations are checked against each other on ten thousand random lookups across forty random tables. Random here means a stated generator at a stated seed: if they ever disagreed, the page would name the address and re-running the seed would produce it again. An unseeded check that passes tells you nothing you can go back to.
Sources
- F. Baker, ed., Requirements for IP Version 4 Routers, RFC 1812, June 1995; sections 2.2.5.2 and 5.2.4.3 for the rule and its worked example.
- V. Fuller, T. Li, J. Yu and K. Varadhan, Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, RFC 1519, September 1993.
- RIPE NCC, YouTube Hijacking: A RIPE NCC RIS case study, 17 March 2008, for the minute-by-minute timeline of 24 February 2008.
- Logical Art, the studio this belongs to.