Multibit Tries and Longest-Prefix Matching for Address Lookups

A forwarding table maps prefixes to next hops, and a packet must be matched against the longest prefix that contains its destination address. IPv4 prefixes are 32 bits wide and IPv6 prefixes 128, and real tables contain prefix lengths spread across most of that range, with many entries at the shorter lengths because aggregated allocations are recorded as single prefixes. A binary trie over address bits answers the query exactly, and it answers it in at most 32 steps for v4 — which sounds fast until the steps are counted against a line-rate lookup budget, where a router must resolve a destination many times per microsecond and the table has to live in a memory hierarchy with several levels.

The binary trie and its 32 dependent loads

The plain structure is a trie over address bits. Each node has two children, indexed by the next bit; a node with a stored prefix carries the next hop. A lookup walks bits from the most significant end and remembers the last node that carried a prefix. When the walk hits a null child, the remembered prefix is the answer.

The problem is the shape of the walk: 32 iterations, each a dependent load, each touching a node that is eight or sixteen bytes. For IPv6 the count is 128. A dependent load from a level-two cache costs on the order of ten to twenty cycles, and from DRAM a hundred or more; 32 such loads is a latency that no amount of pipelining across packets hides completely, because each packet’s walk is a separate dependency chain. The structure is also memory-hungry in the wrong way: a binary trie over prefixes of varying length has one node per bit of the longest path, and the number of nodes is roughly the number of prefixes times their average length, which for a table of several hundred thousand prefixes reaches millions of nodes.

Both problems have the same root cause: one bit per level is too little information per memory access. The fix is to consume several bits per level, and the family of structures that do so are the multibit tries.

Stride compression and its arithmetic

A multibit trie with stride s consumes s bits per level, so a node has 2^s children and the walk takes ceil(32/s) levels. With s = 8, the walk is four levels and each node has 256 children — a 2 KB array of pointers per node, which is a cache-unfriendly size but only four dependent accesses.

The fan-out is not free, and the cost is the number of nodes that must exist at each level. A node must exist for every distinct s-bit chunk that appears at its depth in any prefix, so the node count is bounded by the number of distinct chunks, not by the number of prefixes. With s = 8 and a table of 300,000 prefixes, the first level has at most 256 nodes and the second at most 65,536, so the intermediate levels are dense but bounded; the total memory is the number of occupied nodes times 2 KB.

The choice of stride is a trade between depth and width, and it can vary by level. A common scheme uses a wide first stride — 16 or even 24 bits — because the first level is small and a wide root collapses the upper part of the tree, then narrower strides below, where nodes are numerous. Another uses uniform small strides of 4 to 6 bits to keep nodes within a cache line.

Prefixes whose length is not a multiple of the stride are the complication. A prefix of length 20 with a stride of 8 ends mid-node, so the structure must store it at every 24-bit expansion that matches it. Expanding a prefix of length L to length L’ ≥ L multiplies its entry count by 2^(L’−L), and a stride of 8 can expand a single prefix into up to 256 entries. The expansion is the real cost of multibit tries, and it is why the stride cannot simply be raised to 16 or 24 everywhere: the memory would grow by the expansion factor rather than by the node count.

Storing the prefix length instead of a marker

In a binary trie the answer is the deepest marked node, and the mark is a boolean, as discussed in marking key boundaries in a trie. A multibit trie usually stores the prefix length explicitly with each next hop, and the lookup keeps the entry with the longest stored length. Two reasons.

First, expansion can place a prefix at a node that also holds longer prefixes, so the node’s own depth no longer equals the prefix length. A 20-bit prefix expanded into a 24-bit slot is stored at depth 24 but must be treated as length 20; comparing lengths resolves which of several candidates is the longest match. Second, a single expanded slot may need to hold more than one candidate — when prefixes of different lengths land on the same expanded index — and the standard resolution is to keep the longest one in the slot, since a shorter prefix at the same slot can never be the answer for any address that reaches it. That collapse means the slot stores the winner, and the loser is discarded at build time.

The build step is therefore a preprocessing pass: sort prefixes by length descending, expand each to the stride grid, and insert it, overwriting any shorter entry already present at that index. Overwriting is correct because the insertion order is longest-first: a shorter prefix written later would otherwise displace a longer one that is the correct answer for the same expanded slot.

Lookups in a fixed number of accesses

The lookup loop for a uniform stride is short enough to state completely.

#define STRIDE 8
#define LEVELS (32 / STRIDE)

typedef struct {
    uint32_t prefix_len;   /* 0 when the slot holds nothing */
    uint32_t next_hop;
} entry;

/* table[d] points to 256 entries for depth d. */
int lookup(entry *const table[LEVELS], uint32_t addr, uint32_t *hop)
{
    int found = 0;
    for (int d = 0; d < LEVELS; d++) {
        uint32_t idx = (addr >> (32 - STRIDE * (d + 1))) & 0xFF;
        const entry *e = &table[d][idx];
        if (e->prefix_len != 0) {
            *hop = e->next_hop;   /* deeper levels hold longer prefixes */
            found = 1;
        }
    }
    return found ? 0 : -1;
}

Two properties are visible in the code. The loop has a fixed trip count, so the number of memory accesses is a constant known at compile time — the property that matters when one lookup is staged in hardware across a fixed number of stages, since the number of stages is bounded. And the shift amount is computed from the level, which means the address bits are consumed from the most significant end; a structure that shifted from the other end would still find every prefix but would answer with a different, wrong match whenever prefixes of unequal length share a suffix.

The unconditional overwrite of *hop is correct only because expansion guarantees that an entry at level d represents a prefix at least as long as any entry at a shallower level. A slot at level 3 that holds a 20-bit prefix expanded to 24 bits and a slot at level 2 that holds a 16-bit prefix are both candidates for an address reaching both, and the deeper one is the longer match. If the build wrote entries in any but longest-first order, a short prefix could end up in a deep slot and the loop would silently prefer it, which is why the longest-first build pass is mandatory rather than an optimization.

Where the trade lands

The comparison to a binary trie is stark on access count and unfavorable on memory. A binary trie over 300,000 prefixes might use millions of small nodes, but the nodes are small; a multibit trie with stride 8 uses at most a few tens of thousands of 2 KB nodes in its upper levels, so tens of megabytes. That is acceptable in a router’s dedicated memory and unacceptable in a general-purpose cache, which is why software implementations often use smaller strides — 4 or 5 bits — and accept eight or nine levels.

The deeper trade is against a different lookup mechanism entirely. Ternary content-addressable memory performs the match in one cycle by comparing the address against every prefix in parallel, with the length encoded in the mask. Its cost is per-bit silicon area and power, and it scales badly with table size, so it is used where the table is small and the lookup budget is one access. A multibit trie scales with table size in memory rather than in silicon, which is the reason software and merchant-silicon routers use it.

The structure also inherits the update problem of expanded prefixes. Inserting a prefix requires expanding it into the grid and overwriting entries; deleting it requires restoring the entries that it displaced, which are not recorded unless the build keeps a shadow copy. Most implementations rebuild the whole structure on a change, and the frequency of routing updates is low enough that a rebuild is affordable. That assumption — read-mostly, rebuild on write — is exactly the one that the compressed and adaptive layouts in adaptive radix tree node layouts relax in the other direction, favoring incremental mutation over compactness.

For a purely static table that must be shared between processes or mapped from disk, the multibit trie’s fixed-stride arrays are attractive: all levels are dense arrays of equal-size entries, so they can be laid out in one file and read with one load per level and no pointer chasing at all. The double-array construction discussed in child representation in tries achieves a similar flatness for variable-length keys, and both approaches accept a build step in exchange for a read path with no allocation.