The Routing Table and Longest-Prefix Match
Given 10.0.0.0/8 → A, 10.10.0.0/16 → B and 0.0.0.0/0 → gateway, the destination 10.10.42.7 goes to B because sixteen of its leading bits match that entry and only eight match the other — and this rule is what lets a router summarise the world into one entry and still carve out exceptions.
The problem
10.10.42.7: 10.0.0.0/8, 10.10.0.0/16 and 0.0.0.0/0. The router must pick one — deterministically, identically to every other router that has the same table, and within the few hundred nanoseconds it has per packet at line rate.The example table and the query
The table below is small but complete: it has a broad route, a more specific route inside it, and a default. Query it with 10.10.42.7. Every entry matches, because 10.10.42.7 begins with the 10. that 10.0.0.0/8 requires, begins with the 10.10. that 10.10.0.0/16 requires, and 0.0.0.0/0 requires nothing at all.
The table order is irrelevant. Routing tables are not searched top-down like firewall rules; the lookup is a function of the destination address and the set of prefixes, and the answer would be the same if the rows were shuffled. Many tools print the table sorted by prefix length purely for humans.
Prefix Next hop Interface 10.0.0.0/8 directly Interface A 10.10.0.0/16 directly Interface B 0.0.0.0/0 192.0.2.1 Gateway lookup(10.10.42.7): 10.0.0.0/8 matches (8 bits) 10.10.0.0/16 matches (16 bits) <- longest: chosen 0.0.0.0/0 matches (0 bits) => Interface B
Why the /16 wins, in binary
Write the addresses out as bits and the "match" becomes literal: compare the leading *n* bits, ignore the rest. 10.10.42.7 is 00001010.00001010.00101010.00000111. The /8 entry only asks about the first octet; the /16 asks about the first two. Both are satisfied. The /16 made the more specific claim and it wins.
A /16 claim covers 65,536 addresses; the /8 covers 16,777,216. Choosing the /16 is choosing the entry whose author knew the most about this particular destination. If you had a 10.10.42.0/24 entry too, it would win over both; if you had 10.10.42.7/32, a host route, that would beat everything. Longer prefix, smaller region, stronger claim.
destination 10.10.42.7 00001010 00001010 00101010 00000111 10.0.0.0/8 00001010 -------- -------- -------- 8 bits compared: match 10.10.0.0/16 00001010 00001010 -------- -------- 16 bits compared: match <- longest 0.0.0.0/0 -------- -------- -------- -------- 0 bits compared: match 10.10.42.0/24 (if present) 00001010 00001010 00101010 -------- 24 bits: would win 10.11.0.0/16 (if present) 00001010 00001011 -------- -------- bit 16 differs: NO match
Aggregation: why LPM is the rule and not just a rule
The alternative to LPM is a table with one exact entry per destination network, which is impossible: the internet has hundreds of millions of reachable networks if you count every /24 and smaller. LPM lets routes be aggregated. An ISP that owns 10.0.0.0/8 can announce that single prefix to the rest of the world; internally it hands 10.10.0.0/16 to one customer and 10.20.0.0/16 to another, and only its own routers need those entries. A router in another country holds one route for sixteen million addresses.
Exceptions are then trivially expressible. If one customer moves to a different provider, that provider announces the customer’s /16 and, by LPM, every router in the world sends that /16’s traffic to the new place while continuing to send the rest of the /8 to the old one. No coordination with the /8 holder is required. This is also how traffic engineering works: announce a more specific prefix over the path you prefer and it wins wherever it is heard.
The consequence is that the global IPv4 table is around a million prefixes rather than hundreds of millions — still large, and still growing by de-aggregation (people announcing /24s for exactly the "exception" reason above). Most operators refuse announcements longer than /24 for IPv4 and /48 for IPv6, because otherwise the table would explode. Aggregation is also why Subnetting: Splitting an Address Space matters: prefixes that can be summarised keep tables small everywhere downstream.
- Aggregate: one short prefix stands in for everything inside it.
- Exception: a longer prefix overrides the aggregate for a sub-range, with no change to the aggregate.
- The default route is the ultimate aggregate:
/0stands in for "the whole internet".
How hardware answers in nanoseconds
A software router does LPM with a trie: walk the destination’s bits from the root, remember the last node that had a route attached, stop when the path ends. That is at most 32 steps for IPv4 (128 for IPv6) and, with compression and cache-friendly layout, a few tens of nanoseconds for a table that fits in cache. Linux uses a level-compressed trie for its IPv4 forwarding table; cat /proc/net/fib_trie dumps it, and it is worth looking at once.
Line-rate routers do not want to walk anything. They use TCAM — ternary content-addressable memory. Each entry stores a value and a mask; every entry is compared against the destination *in parallel*, in one clock cycle; the bits under the mask are "don’t care", which is exactly a prefix. Entries are laid out so that longer prefixes have priority, and a priority encoder returns the first hit. The result is a constant-time lookup regardless of table size. The costs are power (every cell is active on every lookup), density (TCAM is far larger per bit than SRAM) and price, which is why a router’s "FIB capacity" is a headline specification and why the growth of the global table is an operational worry.
One more common case: two entries with the *same* prefix and the same metric, pointing at different next hops. That is equal-cost multipath (ECMP). The router hashes the packet’s 5-tuple (addresses, ports, protocol) and uses the hash to pick a path, so all packets of one TCP connection take the same path and arrive in order. Reordering would look like loss to TCP — see Packet Loss: Duplicate ACKs, Fast Retransmit and the RTO.
| Structure | Lookup time | Where | Cost |
|---|---|---|---|
| Binary / compressed trie | O(address bits), tens of ns in cache | Linux kernel, software routers, DPDK apps | memory-bound; scales with table size |
| TCAM | O(1), one cycle for all entries in parallel | ASIC-based routers and switches | power, die area, fixed entry capacity |
| Hash table | O(1) per probe, but one probe per prefix length | some IPv6 designs, exact-match caches | needs up to 32/128 probes, or a cache in front |
Key points
- All prefixes whose leading bits equal the destination’s match; the one with the most bits wins.
- Table order is irrelevant; the answer is a pure function of the destination and the set of prefixes.
- LPM makes aggregation possible: one short prefix for a whole region, longer prefixes for the exceptions.
- The global IPv4 table is roughly a million prefixes because of aggregation — and growing because of de-aggregation.
- Software does LPM with a trie; hardware does it in one cycle with TCAM, at a fixed capacity.
- Equal prefixes with equal metric → ECMP, hashed per flow so a connection stays on one path.
Why does this exist?
Mechanisms are answers to constraints. Open each question before reading the answer.
▸Why not just "first matching rule", like a firewall?
Then the answer would depend on table order, and two routers with the same routes in a different order would disagree. Routing tables are built by protocols that add and remove entries continuously; a definition that is order-independent is the only one that stays consistent.
▸Why allow overlapping prefixes at all?
Overlap is the feature. Without it, every exception to an aggregate would require the aggregate to be split into pieces around it, and every router in the world would need the pieces. With LPM the aggregate stays whole and the exception is one extra line.
▸Why does anyone care how fast a lookup is?
A 100 Gbit/s port receives up to ~150 million minimum-size packets per second; each one gets ~7 ns. Nothing that walks a data structure fits. That budget is why TCAM exists and why forwarding is done in silicon.
Routing table: longest prefix match
| Prefix | Network bits (prefix underlined) | Match | Next hop | |
|---|---|---|---|---|
| 10.0.0.0/8 | 00001010.00000000.00000000.00000000 | — | Interface A | |
| 10.10.0.0/16 | 00001010.00001010.00000000.00000000 | — | Interface B | |
| 0.0.0.0/0 | 00000000.00000000.00000000.00000000 | — | Gateway |
How it fails
What the failure looks like from inside real software.
- A static
/24left in a table after the subnet moved: everything else works, that one subnet is unreachable, and the misleading part is that the default route is fine. - Two
/1routes from a VPN client overriding the default: split-tunnel "works" until the VPN drops without cleaning up, then every destination black-holes. - FIB capacity exhausted on an older router after the global table grew past its TCAM limit: some prefixes fall back to slow-path CPU forwarding and a subset of the internet becomes lossy and slow for no visible reason.
- ECMP hashing that ignores ports: all flows between two hosts share one path, saturating it while parallel paths sit idle.
- A more-specific prefix announced by mistake — a typo in a route filter — pulls traffic for someone else’s network toward you; from the outside it is a hijack, from the inside it is a Tuesday.