Longest-Prefix Match and the Structures That Implement It

A forwarding table answers one question: given a thirty-two-bit destination address, which next hop should the packet take? The obvious data structure is a hash table keyed on the address, and it is wrong. The table does not contain addresses; it contains prefixes, several of which may match any given address, and the answer is the most specific of them. Hash lookup gives an exact match or nothing, so it cannot express the rule at all.

Why the query is a search, not a lookup

Consider a table with three entries: 10.0.0.0/8 via one next hop, 10.1.0.0/16 via another, and 10.1.2.0/24 via a third. The address 10.1.2.7 matches all three. The forwarding decision must select the /24, because the more bits a prefix specifies, the narrower the set of addresses it describes, and the narrower description is the better-informed one. This is longest-prefix match, and it is the only rule in the table.

The reason the rule exists is aggregation, covered in prefix aggregation and its limits. An upstream provider wants to announce one /8 covering many customers rather than a thousand separate /24s. Inside the provider, a more specific route points at the particular customer. Both must be present at once, and the specific one must win. Without a specificity rule, aggregation and correct delivery would be mutually exclusive.

A secondary rule handles ties. Two entries with identical prefixes and different next hops cannot both be used. The resolution is administrative distance or preference, which is a property of the protocol that installed the route rather than of the prefix, and which is discussed in route preference and the RIB. Prefix length is the primary key; protocol preference is the tiebreak.

Two degenerate cases matter in practice. A prefix of length zero, written 0.0.0.0/0, matches every address and is the default route, so it is the match of last resort. A host route of length thirty-two matches exactly one address. The same machinery handles both, which is a point in favour of treating all routes as prefixes rather than special-casing the default.

The binary trie and its one-bit-per-level descent

The natural structure is a binary trie over the address bits, most significant first. Each level consumes one bit; the left child continues on a zero, the right on a one. A prefix of length L is stored at the node reached after L bits, and the search walks down the bits of the destination address, remembering the deepest node that carried a next hop.

The remembered-node trick is the whole algorithm. The search does not stop when it reaches a node with no next hop, because a shorter match may still exist above it. It does not stop at the first node with a next hop either, because a longer match may exist below. It descends until the bits run out or the path ends, and the answer is the last next hop seen on the way down.

struct trie_node {
    struct trie_node *child[2];
    struct nexthop   *nh;      /* non-NULL when a prefix terminates here */
};

/* Returns the next hop for the longest matching prefix, or NULL. */
static struct nexthop *lpm(const struct trie_node *root, uint32_t addr)
{
    const struct trie_node *n = root;
    struct nexthop *best = NULL;
    for (int bit = 31; bit >= 0 && n; bit--) {
        if (n->nh)
            best = n->nh;                  /* shallower match, superseded later */
        n = n->child[(addr >> bit) & 1u];
    }
    if (n && n->nh)
        best = n->nh;                      /* /32 exact match at the leaf */
    return best;
}

The cost is one memory access per bit in the worst case, so thirty-two dependent loads for IPv4 and a hundred and twenty-eight for IPv6. Each load depends on the previous one, which means the latency is a chain of cache misses rather than a throughput problem. At a few hundred cycles per miss on a cold cache, that is thousands of cycles per packet, far too slow for a line-rate forwarder.

Path compression and the nodes that disappear

Most of a trie is empty. A table with a thousand prefixes spread over a thirty-two-bit space would need a node at nearly every level of every path, and the vast majority of those nodes carry no next hop and have a single child. Path compression collapses such chains into a single node that stores the bits it skipped and the length of the skip, so a comparison against the address replaces the descent. This is the Patricia trie, and it is the standard structure for software routing tables.

Compression changes the query. Instead of walking bit by bit, the search compares the skipped bits and, on mismatch, backtracks to the last branching point. Backtracking requires either parent pointers or a stack of visited nodes, which adds state to a structure that hardware would prefer to keep stateless. The trade is memory for latency and control complexity: a compressed trie holds the same prefixes in far fewer nodes, at the cost of a less predictable access pattern.

A related trick removes the need for a default route to be a special case. If every node without a next hop inherits the next hop of its nearest ancestor, then any node reached by the search carries a valid answer, and the search can stop at the first node it lands on. The cost moves to updates: changing a route at an ancestor requires pushing the change down to all inheriting descendants. The technique is used where updates are rare relative to lookups, which is the usual ratio on a transit router but not on a host.

Multibit tries and the stride choice

Reading one bit per level wastes the granularity of memory. A multibit trie consumes k bits per level, so each node has 2^k children, and the number of levels drops to 32/k. A stride of eight gives four levels for IPv4 and sixteen for IPv6; a stride of sixteen gives two levels, at the cost of 65,536 entries per node.

The complication is that prefixes are not aligned to strides. A /13 prefix is not aligned to a sixteen-bit boundary, and its coverage must be replicated across every stride entry it overlaps. Replication is the price of a shorter tree: fewer memory accesses, more memory. The expansion factor depends on the stride size and the distribution of prefix lengths, and it is the reason hardware lookup engines expose the stride as a configurable parameter rather than a constant.

A second technique does not remove the expansion but makes it affordable. Instead of storing a next hop in each leaf, store an index into a small table of distinct next hops. The number of distinct next hops is bounded by the number of neighbours, not by the number of prefixes, so the leaf entries shrink from a full next-hop record to a few bytes. Replication still multiplies the leaf count; the indirection bounds the width of each leaf, which is what makes a two-level sixteen-bit stride fit in ordinary memory.

Ternary content-addressable memory

The alternative to any tree is to search all entries at once. A content-addressable memory compares the input against every stored word in parallel and returns the matching index. A ternary variant adds a mask bit per position, so an entry can specify “this bit must be zero, that bit is irrelevant” and therefore encode a prefix directly.

The lookup is a single operation regardless of table size, which is exactly the property a line-rate forwarder wants. The costs are physical. Each cell holds comparison logic alongside storage, so density is far below ordinary memory, and the parallel compare consumes power proportional to the number of entries searched. The mask bits also make updates harder: changing one prefix can require reordering entries because the device returns the first match in a priority order rather than the longest one.

That last point is the one that bites. A ternary memory does not know about prefix lengths. To get longest-prefix behaviour, the entries must be arranged so that the most specific prefixes sit at the lowest indices, and the device must return the lowest matching index. Inserting a route means finding the right position in that order, and if the hardware only supports appending at the end, the table must be rebuilt. Implementations work around this by partitioning the memory by prefix length, or by pre-expanding prefixes into a form where order is implicit.

What the structures cost in updates

Lookup speed dominates the design of every structure above, and update cost is the thing that gets sacrificed. A compressed trie handles an insertion by splitting one node, which is a constant amount of work, so software tables absorb churn cheaply. A multibit trie must expand a new prefix across every stride entry it covers, so an insertion can touch many leaves. A ternary memory may need a reorder or a rebuild. A hardware pipeline with a fixed number of stages may need a full table reload when the shape changes.

The operational consequence is that a router’s control plane can usually compute a new table faster than the forwarding plane can install it. That gap is why route churn is a stability problem and not merely a CPU cost, and why the split between the routing information base and the forwarding information base described in route preference and the RIB is explicit rather than incidental.

Special cases the general algorithm hides

Three situations do not fit the plain prefix model. The first is the receive path: addresses assigned to the router itself must be delivered locally rather than forwarded, and implementations add them to the table as host routes pointing at a local-delivery next hop. The second is martian and reserved space, where the correct action is to drop rather than forward, which needs a next hop of “discard” that the trie can store like any other. The third is anycast, where the same prefix is announced from many places and the “correct” next hop depends on where the query is asked, so the table on each router differs even though the prefix does not.

None of these require a new lookup rule. They require the next-hop object to carry an action as well as an address, which is a design lesson the header format did not anticipate and every forwarding table since has adopted.