# Longest Prefix Match: How Routers Decide in Nanoseconds

> A core router matches each packet against ~1M CIDR prefixes and must pick the most specific — billions of times per second. The data structures behind that (tries, TCAM, poptrie lineage) and why 'most specific wins' shapes everything from BGP hijacks to your homelab VPN.

URL: https://harshith.in/blog/longest-prefix-match/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: networking, algorithms, systems

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.