Every packet that crosses a router triggers the same question: of all the prefixes in the forwarding table, which is the longest one that contains this destination? A busy port asks it more than a hundred million times a second against a table of a million entries. This chapter is about the data structures and the memory chips that answer it in time.
Common mix-up: "longest match" does not mean the route with the best metric, the newest route or the one listed first. It means the matching prefix with the most fixed bits: 198.51.100.0/24 beats 198.51.0.0/16 for 198.51.100.7 whatever their costs. Metrics and preferences only decide between routes for the same prefix, and that happens before the forwarding table is built (Chapter 03).
If longest-prefix match is new to you, start with routing tables on networks.jelia.nyc, and with IP addresses for prefixes and masks. This chapter assumes both and asks a harder question: not what the router looks up, but how it can possibly do it fast enough.
Compare it with the lookup an Ethernet switch does. A switch has a table of MAC addresses and looks for the exact 48-bit destination. That is the problem hash tables were made for: mix the key into a bucket number, read the bucket, done. One or two memory reads, whatever the size of the table.
A router cannot do that. The destination 203.0.113.77 is almost never in the table. What is in the table is a set of prefixes, some of which contain 203.0.113.77: perhaps 203.0.113.0/24, 203.0.113.64/26 and the default route 0.0.0.0/0. The router must find all the containing prefixes, conceptually, and pick the one with the most fixed bits. RFC 1812, the requirements document for IPv4 routers, calls this rule "longest match" and makes it the heart of forwarding. Hashing the whole address finds nothing, because the address is not a key. Hashing the first 24 bits would work for that one /24, but the router does not know in advance which length to try.
The brute-force fix is one hash table per prefix length. Put every /24 in one table, every /23 in another, and so on. To look up an address, take its first 32 bits and probe the /32 table, then its first 31 bits and probe the /31 table, down to the default route. The first hit is the longest match. Correct, and hopeless: up to 33 probes for IPv4 and 129 for IPv6, inside a budget of a few nanoseconds.
In 1997 Marcel Waldvogel, George Varghese, Jon Turner and Bernhard Plattner turned the per-length hash tables into something fast. Instead of probing lengths in order, they binary-search them: probe /16 first; on a hit go longer (try /24), on a miss go shorter (try /8). A plain binary search would fail, because a miss at /16 does not prove there is nothing at /24. Their fix is to insert markers: whenever a long prefix exists, short entries along its search path are planted that say "something longer lives beyond here", each carrying the best real match known at that point so the search never has to backtrack.
With markers, the number of hash probes falls to log₂ of the address width: five for IPv4 and seven for IPv6, independent of how many prefixes the table holds. The paper reports that with further tricks a typical backbone table of the time averaged fewer than two probes. The catch, noted later by Eatherton, Varghese and Dittia, is updates: one new prefix can require markers in several tables, so insertion is slower than in a trie.
probes = ⌈log₂ W⌉ → IPv4: 5, IPv6: 7W is the number of distinct prefix lengths to search (32 or 128 bits). Binary search halves the remaining range of lengths with each hash probe.
A trie (from retrieval, and usually said "try") is a tree in which the path to a node spells out a key. For prefixes the alphabet is just 0 and 1. Start at the root. A 0 bit sends you to the left child, a 1 bit to the right. To store the prefix 101*, walk right, left, right and mark the node you land on. The default route, which has no bits at all, marks the root itself.
Looking up an address follows the same rule, reading the destination one bit at a time from the top. On the way down, whenever you pass a marked node, remember it: that prefix matches, and it is the longest match so far. Keep going until there is no child for the next bit. The last prefix you remembered is the answer. No backtracking is needed, because every marked node on the path matches by construction, and a deeper one is always longer.
To keep the pictures readable, this chapter uses toy 8-bit addresses. Everything works the same way with 32 bits; there are simply more levels. Here is the classic textbook set of nine prefixes, used in George Varghese's Network Algorithmics, with a lookup of the address 11001010:
| Step | Bits read so far | Node | Prefix here? | Best match so far |
|---|---|---|---|---|
| 1 | (none) | root | no | none |
| 2 | 1 | 1 | P4 = 1* | P4 |
| 3 | 11 | 11 | no | P4 |
| 4 | 110 | 110 | P9 = 110* | P9 |
| 5 | 1100 | 1100 | no | P9 |
| 6 | 11001 | 11001 | P3 = 11001* | P3 |
| 7 | 110010 | no child for the next bit 0 | stop | answer: P3 |
Six node reads to find that 11001* is the longest prefix containing 11001010. The trie is pleasant in every way but one. Insertion and deletion touch only the nodes on one path, so updates are cheap. Memory grows with the number of prefixes, not with the size of the address space. But the lookup costs one memory read per bit in the worst case, and memory reads are exactly what a router cannot afford.
The word dependent matters. Fast memories can start a new read every few nanoseconds, but each read has a latency of tens of nanoseconds when it goes off-chip. A chain of 32 reads, each waiting for the last, would take far longer than the 6.7 ns between packets. Hardware hides latency by pipelining, working on many packets at once with each one at a different level, but every level still needs its own slice of memory bandwidth. Fewer levels is the whole game.
Add or remove prefixes and the trie is rebuilt from scratch. Type an address (8 bits, or a number from 0 to 255) and press Walk: the lookup runs for real, one node at a time, keeping the best match so far. Turn on path compression to rebuild the same prefixes as a radix tree and watch the node count and the read count drop. Prefixes can be typed as bits with a star (1011*) or as value and length (176/4); a lone * is the default route.
Build a trie from a real routing table and look at its shape. Near the top it is bushy: there are routes everywhere in the first eight or ten bits. Further down it turns into long corridors, chains of nodes that have exactly one child and carry no prefix. Each corridor node costs a memory read and decides nothing; it only confirms that the next bit is what it has to be.
Path compression removes them. When a node has a single child and no prefix of its own, it is spliced out, and the child records the bits that were skipped. During a lookup you jump straight to the child and check the skipped bits in one comparison. If they match, carry on. If they do not, the address left the stored routes somewhere along the corridor, and the best match so far is the answer. In the instrument above, compression shows these skipped bits as a dashed edge with the bit string written on it.
This is the idea behind the PATRICIA tree (Donald Morrison, 1968) and the radix trees that BSD Unix used for its routing table. Compression bounds the number of nodes: a binary tree in which every internal node either branches or carries a prefix has at most about twice as many nodes as prefixes, however long the addresses are. It does not fix the worst case for reads, though. A table with prefixes of every length along one path still needs a node for each of them.
The IPv4 forwarding table in the Linux kernel is an LC-trie, which stands for level-compressed. The kernel's own implementation notes describe both tricks. Path compression appears as "skipped bits": a node linked from its parent can skip over bits that represent a single path with no deviations. Level compression replaces a run of full levels with one wider node: if a subtree is completely populated for k levels, its 2k grandchildren can be reached with a single array index on k bits. The kernel grows ("inflates") and shrinks ("halves") these arrays as routes are inserted and removed, so the structure keeps adapting to the table's shape.
The LC-trie comes from a 1999 paper by Stefan Nilsson and Gunnar Karlsson. The combination is powerful: path compression removes the corridors, level compression removes the depth in the bushy top, and the average lookup on a large table needs only a handful of node visits.
If one bit per read is too slow, read more bits per node. A multibit trie with a stride of 4 makes every node an array of 24 = 16 slots. The next four bits of the address index straight into the array: one memory read consumes four bits. An IPv4 lookup with stride 4 needs at most 8 reads instead of 32. With stride 8, at most 4.
There is a snag. An array indexed by four bits can only hold prefixes whose length is a multiple of four. What about 0*, or 100*? V. Srinivasan and George Varghese gave the answer a name in 1999: controlled prefix expansion. A prefix that ends inside a stride is copied into every slot it covers. 0* becomes 0000, 0001, … 0111: eight slots. 100* becomes 1000 and 1001. When two expansions want the same slot, the longer original prefix wins, which preserves longest-match semantics: the slot now answers for exactly the addresses it would have matched before.
Here is the textbook set expanded into a root array with stride 4. Read the table as "if the first four bits are these, the best prefix that ends within them is":
| Slot (first 4 bits) | Owner after expansion | Why | Child array? |
|---|---|---|---|
| 0000 – 0111 | P5 = 0* | 0* covers all eight slots starting with 0 | no |
| 1000 | P6 = 1000* | fits exactly; beats P8 (100*) and P4 (1*) | yes: P7 = 100000* |
| 1001 | P8 = 100* | expanded; beats P4 | no |
| 1010 – 1011 | P1 = 101* | expanded into two slots | no |
| 1100 | P9 = 110* | expanded; beats P4 | yes: P3 = 11001* |
| 1101 | P9 = 110* | expanded | no |
| 1110 – 1111 | P2 = 111* | expanded into two slots | no |
The lookup of 11001010 now reads slot 1100 of the root (best so far: P9, plus a pointer to a child), then slot 1010 of the child, where P3 = 11001* has been expanded into slots 1000 to 1111. Two reads instead of six. Notice that P4 = 1* has vanished entirely: every slot it would have filled was claimed by something longer. Expansion can make a prefix disappear without changing a single answer.
The price is memory. Every node is a full array of 2s slots, however few of them hold anything useful, and expansion multiplies entries. Bigger strides mean fewer reads and fatter, emptier nodes. The extreme cases show the shape of the trade-off. A stride of 1 is the binary trie: up to 32 reads, tiny nodes. A single stride of 32 is one array indexed by the whole address: one read, 232 slots, 16 GiB at four bytes a slot. Everything interesting lies in between.
In 1998 Pankaj Gupta, Steven Lin and Nick McKeown at Stanford took the trade-off to its practical extreme with strides of 24 and 8. The first table, TBL24, has one entry for every possible 24-bit prefix: 224 entries of 2 bytes, 32 MB of plain DRAM. Every route of length 24 or less is expanded into it. Each entry either holds a next hop directly or, if longer routes exist under that /24, points to a 256-entry block in a second table, TBLlong.
Because the overwhelming majority of routes are /24 or shorter (in their 1998 data, 99.93 percent), almost every lookup finishes in one memory read and none needs more than two. The design spends memory lavishly on a level that DRAM made cheap, to buy a guaranteed tiny read count. The same reasoning still holds: on 22 October 2026, potaroo.net's analysis of the IPv4 table showed /24 alone was 63.6 percent of all prefixes, and its count of entries longer than /24 was in the hundreds.
Expanded tries waste memory on repeated copies, and their updates can be slow: change one short prefix and you may rewrite many slots. Will Eatherton, George Varghese and Zubin Dittia's Tree Bitmap (2004) keeps the multibit stride but stores each node compactly with two bitmaps. The internal bitmap has a bit for each prefix that ends inside the node (all the lengths from 0 to s−1 bits within that stride). The external bitmap has a bit for each of the 2s possible children that actually exists. The children of a node are stored next to each other, so one pointer plus a count of set bits finds any child.
No prefix is ever expanded, so an update touches at most one node's worth of memory, and the paper stresses that update times are bounded by the size of a trie node. A node fits in one wide memory burst, so each level costs exactly one read. The paper keeps strides at no more than 8 bits, using logic that can scan bitmaps of a few hundred bits in a single cycle. It compares itself with the Luleå scheme (strides 16, 8 and 8, very compact, but one update can force much of the table to be rewritten). Tree Bitmap and its descendants became a standard way to do algorithmic lookup in router silicon.
Choose a stride schedule and a prefix set. The program actually expands every prefix into a multibit trie with those strides, counts the nodes that must exist at each level, and adds up the memory at 4 bytes per slot. The chart puts every preset schedule on the same axes, worst-case reads across and memory up (on a log scale), so you can see the frontier. Type your own schedule as numbers that add up to 32, such as 12,6,6,8.
| Level | Stride | Bits consumed | Nodes | Slots | Memory |
|---|
Ordinary memory takes an address and returns the data stored there. Content-addressable memory (CAM) runs the other way: give it data and it returns the address of the row that holds it, by comparing the search key against every row simultaneously. Each row has its own comparison logic, wired next to the storage cells. A binary CAM does exact matching, which suits MAC address tables.
A ternary CAM stores a mask alongside each value, so every bit of every row can be 0, 1 or "don't care", written x. The prefix 198.51.100.0/24 becomes a row whose first 24 bits are fixed and whose last 8 are x. A search drives the destination address onto match lines across every row in the same clock cycle. Every row whose fixed bits agree with the key reports a match, and a priority encoder returns the lowest-numbered matching row.
That last detail is how a TCAM does longest match: it doesn't, by itself. It returns the first match. The router's software must keep the rows sorted with longer prefixes above shorter ones, so that the first match is also the longest. Get the order wrong and the TCAM will cheerfully return a /8 when a /24 was sitting a few rows further down. The instrument below lets you do exactly that.
Each row is a prefix written as ternary bits, with x for don't care. Press Search and every row compares itself to the key at once; matching rows light up and the first one wins. The readout also computes the true longest match independently, so it can tell you when the TCAM's answer is wrong. Shuffle the rows, or move them with the arrow buttons, and search again.
A TCAM gives a lookup in one cycle with no clever data structure at all, which is why it is so attractive. It is also expensive in every physical sense. A TCAM cell needs far more transistors than an SRAM cell, because it stores two bits (value and mask) and carries its own comparator. And because every row is compared on every search, the whole array switches on every lookup: power scales with the size of the table times the lookup rate. Writing in 2004, the Tree Bitmap authors described the largest TCAM parts of the day as 18 Mbit, about 256,000 entries of 72 bits, and estimated that a ten-million-entry table would need 20 such chips, thousands of dollars of parts and possibly more than 200 watts.
Sizes have grown a great deal since, but the shape of the trade-off has not. So router designs, described here in vendor-neutral terms, tend to use each technology where it is strongest:
For you as an operator, this is why a data sheet quotes a forwarding-table capacity as a hard number, and why that number can depend on the mix of IPv4 and IPv6 routes, on whether features such as ACLs share the same TCAM, and on the prefix-length profile of the table.
| Method | Reads per lookup | Memory | Update cost | Where it lives |
|---|---|---|---|---|
| Hash per length | up to W + 1 probes | small | cheap | teaching; the starting point |
| Binary search on lengths | about log₂ W probes | small, plus markers | slower (markers) | research, some software |
| Binary trie | up to W | proportional to prefixes | one path | teaching; control-plane software |
| Path-compressed / LC-trie | a few on average | small | moderate (rebalancing) | Linux IPv4 FIB; BSD radix tree |
| Expanded multibit trie | number of strides | large (full arrays, copies) | can be slow | DIR-24-8 style designs |
| Tree Bitmap | one per stride level | compact | bounded by node size | router silicon |
| TCAM | 1 cycle | costly per entry; high power | must keep order | ACLs, classification, some FIBs |
A forwarding table is not built once and searched forever. The internet's routing system changes constantly: a link fails somewhere, a network renumbers, a provider adjusts its traffic, and BGP carries the change to every router that holds a full table. Reports such as potaroo.net's track this churn every day, and even from a single vantage point the update counts run into the thousands. Many updates only change a path's attributes and leave the forwarding entry alone; others add, remove or re-point a prefix, and the FIB must follow, ideally without stopping lookups even for a moment.
Each structure in this chapter pays for updates differently, and the instruments make the costs visible:
The standard trick for all of them is to build the change off to the side and then switch a single pointer, so a packet sees either the old state or the new one and never a mixture. Lookups and updates share the same memory bandwidth, so a design that updates cheaply leaves more of it for packets.
Quadruple the address width and every structure in this chapter gets worse. A binary trie can need 128 reads. Expanded strides that cover 32 bits in four reads would need sixteen to cover 128. TCAM rows become four times as wide, so the same chip holds a quarter as many entries, with the same power spent per row. Hashing per prefix length means 129 tables.
Two facts about how IPv6 is actually used rescue the situation. First, inside networks, subnets are /64: the IPv6 addressing architecture (RFC 4291) gives ordinary unicast addresses a 64-bit interface identifier, so the bottom half of the address names a host on a link and does not need routing beyond it. Second, in the global table, almost nothing is longer than /48. On 22 October 2026 potaroo.net counted about 47 percent of IPv6 entries at exactly /48, and only a few hundred entries, around 0.1 percent of the table, longer than that. A router's global lookup can therefore concentrate its effort on the first 48 bits, with a cheap path for the rare longer routes, and a table built for that profile behaves far better than the 128-bit worst case.
The IPv6 table is also still smaller than IPv4's, about 258,000 prefixes on the same date by the CIDR Report's count against about 1.09 million for IPv4, but it has been growing faster, which is one reason lookup designs aim at both families sharing the same memory flexibly.
Take a stride schedule of 16, 8, 8, 8, 8 for the first 48 bits. Every global IPv6 route of /48 or shorter is found in at most five reads, and the worst case for an arbitrary 128-bit table would need ten more levels that a typical global table barely populates. Because nodes are created only where some prefix continues, those deep levels cost almost no memory when they are nearly empty; they only cost reads for the rare packet that needs them. Paths like that are exactly where path compression earns its keep.