Every IP packet, at every hop, triggers the same query: of all the routes I know, which most specific prefix covers this destination? Your laptop answers it over a table of five entries; a default-free core router answers it over roughly a million, at hundreds of millions of packets per second, in a handful of nanoseconds each. Longest prefix match is simultaneously a policy language, an algorithms problem with a beautiful lineage, and — once you internalize “most specific wins” — the explanation for VPN client tricks and BGP hijacks alike.

The Rule Is the Policy Language

CIDR routes are prefixes: 10.0.0.0/8 covers everything starting with byte 10; 10.1.2.0/24 covers a narrower slice; 0.0.0.0/0 covers the universe. Overlaps aren’t conflicts — they’re the mechanism:

text
  destination 10.1.2.77 matches:
    0.0.0.0/0      → ISP uplink        (len 0)
    10.0.0.0/8     → corporate WAN     (len 8)
    10.1.2.0/24    → local segment     (len 24)  ← wins

The default route is just the least-specific prefix, always losing to anything better — no special case needed. Exceptions are expressed by adding a longer prefix, not editing anything: your VPN client claiming 0.0.0.0/1 + 128.0.0.0/1 beats the existing /0 without touching it (sneakier than replacing the default, and now you know why every VPN does it). The dark twin: a BGP hijacker announcing a /24 out of someone’s /16 attracts that traffic globally, because every router prefers the longer match — the Pakistan Telecom/YouTube incident of 2008 was exactly this, and it’s why providers filter announcements and cap acceptable prefix lengths (/24 is the classic IPv4 internet floor).

ip route get 8.8.8.8 asks your own kernel to run the match and show its choice — the single most underused command in “why is traffic going out the wrong interface” debugging.

Making It Fast

Naive matching scans all N prefixes; the structure that fixes it is the binary trie: walk the destination bit by bit, remember the last node that carried a route, and the deepest one remembered when you fall off is the answer — LPM by construction:

text
        (root: 0/0 → uplink)
        0/ \1
        ...  (10.0.0.0/8 → wan)
              \ ...
               (10.1.2.0/24 → local)   deepest match wins

Thirty-two dependent branches per lookup is still too slow, so the whole subsequent literature is about compressing the walk: path compression (skip single-child chains — Patricia/radix tries, the classic BSD choice), level compression (consume 4–16 bits per step in stride tables — Linux uses an LC-trie, visible at /proc/net/fib_trie), and cache-line-conscious bitmap encodings (Lulea, poptrie) that pack a 16-bit stride’s worth of children into a few machine words with popcount arithmetic. The through-line is pure systems: the algorithmic win was settled early; everything since is about touching fewer cache lines.

Hardware routers cheat differently. TCAM — ternary CAM, where every stored bit is 0/1/don’t-care — compares a destination against all prefixes in parallel in one cycle; priority encoding returns the longest. Constant time, brutal cost: TCAM is power-hungry, hot, and small, which is why “FIB capacity” is a headline router spec, and why the day the global IPv4 table crossed 512k routes in 2014, older boxes with 512k TCAM partitions dropped routes to software paths and parts of the internet had a very bad Tuesday. Capacity of a lookup memory as global infrastructure risk — LPM all the way down.

One more place the rule quietly runs: kernels apply it for the source address selection and policy routing too, and every cloud VPC “route table” you edit is an LPM table with a GUI. The mental model transfers everywhere: find all covering prefixes, longest wins, and if traffic surprises you, some longer prefix you forgot about is winning.

Takeaways

  • LPM = most specific covering prefix wins; default routes, VPN /1-pairs, and /24 hijacks are all the same rule at different lengths.
  • ip route get shows the kernel’s actual decision — start debugging there.
  • Software lookup is a compressed trie story: Patricia → LC-trie (Linux) → bitmap tries, each step buying fewer cache-line touches.
  • Hardware uses TCAM for one-cycle parallel match; its capacity limits have caused internet-scale incidents (512k day).
  • When routing surprises you, hunt for the longer prefix — it exists.