Forwarding Tables: Longest-Prefix Matching and Route Aggregation

Destination-Based Forwarding

When a router receives a datagram, it uses the destination address to look up the output link interface in its forwarding table. There are $2^{32}$ IPv4 addresses, so a forwarding table cannot keep a separate entry for every address. Because addresses in the same subnet share a network prefix, the forwarding table stores address prefixes instead: a destination matches an entry when its leading bits equal that prefix.

Suppose a router has four link interfaces and this forwarding table (* marks bits that are not compared):

The destination 200.23.22.161 (11001000 00010111 00010110 10100001) agrees with the first entry in its first 21 bits, so it is forwarded on interface 0. The last row has prefix length 0 and matches any address. It is the default route, used when nothing else matches.

Longest-Prefix Matching

One destination may match several entries. For example, 200.23.24.170 (11001000 00010111 00011000 10101010) agrees with the second entry in its first 24 bits and with the third entry in its first 21 bits. The router then applies the longest-prefix matching rule: among all matching entries, it chooses the one with the longest prefix. The datagram is therefore forwarded on interface 1.

A longer prefix describes a smaller, more specific address range, so longest-prefix matching means "use the most specific route." High-speed routers must finish each lookup in nanoseconds. Instead of scanning the table entry by entry, they use specialized data structures and hardware such as tries or ternary content-addressable memory (TCAM).

Route Aggregation

Hierarchical address allocation keeps forwarding tables small. Suppose an ISP obtains the block 200.23.16.0/20 and assigns eight /23 blocks to eight organizations:

The eight blocks share their first 20 bits, so the ISP advertises a single route to the rest of the Internet: "send me any datagram whose first 20 address bits match 200.23.16.0/20." Using one prefix to represent several networks is called route aggregation, or route summarization.

Several blocks can be aggregated into one prefix only if three conditions hold: the addresses are contiguous, the number of blocks is a power of two, and the first block starts on a boundary aligned to the aggregated size. Aggregating $2^k$ blocks of prefix length $x$ gives prefix length $x-k$.

What if organization 1 switches to another ISP? The new ISP can advertise the more specific route 200.23.18.0/23 while the original ISP keeps advertising 200.23.16.0/20. A datagram for organization 1 matches both routes; by longest-prefix matching, the /23 wins and the datagram goes to the new ISP. Datagrams for the other organizations match only the /20 and still go to the original ISP.