Inside a Router: Longest-Prefix Match and Forwarding

Two jobs in one box: routing vs forwarding

Across this rung we built up everything a packet needs to travel between networks: the IP datagram with its source and destination addresses, the hierarchical CIDR prefixes that group addresses into blocks like 10.0.0.0/8, and the ideas of subnets, NAT, and IPv6 that keep the whole scheme working at planetary scale. What we have not yet done is open up the actual machine that moves the packets along — the router. This guide does exactly that, and lands on the single most important rule it runs.

The first thing to grasp is that a router really does two separate jobs, and confusing them is the most common beginner mistake. This is the forwarding-vs-routing split. Routing is the slow, thoughtful planning: routers gossip with their neighbors, run algorithms, and figure out, for every possible destination block, which neighbor is the best next step. The product of all that thinking is a lookup table. Forwarding is the fast, repetitive action: a packet arrives, the router glances at its destination, consults the table, and shoves the packet out the right door — and it does this millions of times a second.

The forwarding table, and why one address can match many rows

The table that forwarding reads is the forwarding table. Each row is a deal of the form "packets whose destination falls inside this prefix should leave via this interface, toward this next hop." Crucially, the rows are keyed by CIDR prefixes, not by individual addresses — a router cannot possibly store a row for each of the billions of IP addresses on the Internet, so it stores rows for blocks. One row might say 10.0.0.0/8, another 10.1.0.0/16, another the catch-all 0.0.0.0/0. The whole table is the frozen output of the routing process from the previous section.

Now the interesting wrinkle. Because the rows are prefixes of different widths, a single destination address can legitimately fall inside more than one row at once. Recall from earlier in this rung how a prefix works: 10.1.5.7 starts with 10, so it is inside 10.0.0.0/8; its first two bytes are 10.1, so it is also inside 10.1.0.0/16; and every address is trivially inside 0.0.0.0/0. So which row wins? They cannot all be right, because they may point out different doors. We need a tie-breaker, and the tie-breaker is the heart of this whole guide.

Longest-prefix match: the most specific rule wins

The tie-breaker is longest-prefix match, and it is delightfully simple: among all the rows whose prefix the address falls inside, pick the one with the longest prefix — the largest number after the slash. A longer prefix pins down a smaller, more specific block of addresses, so longest-prefix match is just the rule "the most specific instruction wins." It is the same common sense you use with directions: "turn left at the bank" beats "head roughly north," because it is more precise about where you actually are.

Forwarding table (destination prefix -> outgoing interface)

  prefix            interface     prefix length
  10.0.0.0/8        eth1          8
  10.1.0.0/16       eth2          16
  10.1.5.0/24       eth3          24
  0.0.0.0/0         eth0          0   (the default route)

Packet arrives for destination 10.1.5.7

  10.1.5.7 in 10.0.0.0/8 ?    yes   (matches 8 bits)
  10.1.5.7 in 10.1.0.0/16?    yes   (matches 16 bits)
  10.1.5.7 in 10.1.5.0/24?    yes   (matches 24 bits)  <-- longest
  10.1.5.7 in 0.0.0.0/0  ?    yes   (matches 0 bits)

  Winner: 10.1.5.0/24  ->  send out eth3

Look at that last row, 0.0.0.0/0 — a prefix of length zero matches absolutely every address, because it pins down nothing at all. This is the default route, the "if nothing more specific matched, send it this way" fallback. It is exactly the rule your home router uses: it knows the few local addresses precisely, and for everything else on the entire Internet it just shrugs and forwards toward your ISP. Because its prefix length is 0, longest-prefix match only ever falls back to it when no better, more specific row exists — which is precisely the behavior we want.

How the lookup actually runs, hop by hop

Let us trace one packet through one router, slowly, so the mechanism is concrete. The key thing to keep in mind is that this entire dance happens at every single router along the path, independently — no router knows or cares about the full route, it only answers the one question "given this destination, which of my doors is next?" The packet itself carries no route; it carries only its destination address, and each router re-decides from scratch. That hop-by-hop independence is what makes the Internet's datagram model so robust.

1. A packet arrives on an input port. The router reads the destination IP address out of the packet's header — it ignores everything else for forwarding, including the source address and the payload.
2. It performs longest-prefix match: of all forwarding-table rows whose prefix contains that destination, it selects the row with the longest prefix. That row names an outgoing interface and a next hop.
3. It decrements the packet's time-to-live (TTL) field by one. If the TTL hits zero, the packet has looped or wandered too long, so the router drops it and sends back an ICMP "time exceeded" message — which, recall from earlier, is exactly how traceroute peeks at each hop.
4. It hands the packet to the switching fabric, the internal highway that carries it from the input port across to the chosen output port — ideally without colliding with the millions of other packets being shuffled at the same instant.
5. The output port queues the packet, then transmits it onto the next link. At the far end, the next router starts again at step one — fresh destination lookup, no memory of where the packet has been.

Why prefixes — and a couple of honest caveats

Step back and notice how beautifully the pieces fit. Addresses are hierarchical (guide 2), so nearby addresses share a prefix; CIDR lets us name any-sized block with one prefix; and longest-prefix match lets a router carry a tiny general rule for a huge region while still allowing precise exceptions for special sub-blocks underneath it. This is aggregation in action — one /8 row can stand in for sixteen million addresses, which is the only reason the Internet's routing tables fit in a router at all. Hierarchy in the addresses is what keeps the tables small; longest-prefix match is what lets the small tables still be exact where it matters.

A few honest caveats so you do not over-trust the picture. First, longest-prefix match decides the next hop only — it is not a route; it is one step, re-decided at every hop, which is why a misconfigured set of routers can send a packet around in a loop until its TTL expires. Second, the forwarding table is only as good as the routing that filled it; if routing feeds it a wrong or hijacked prefix, forwarding will faithfully send packets the wrong way, since it never questions the table. Third, the destination address names an interface, not a person and not a permanent device — the same lookup machinery moves packets toward a location on the network, with no idea who or what is actually there.

And with that, the network layer's data plane is complete. You can now describe the whole journey: a packet is built with an IP header (guide 1), addressed using IPv4 or IPv6 carved into CIDR prefixes (guides 2 and 4), perhaps translated through NAT on the way out (guide 3), and then forwarded hop by hop by routers that each run longest-prefix match against a table — this guide. The one piece we deliberately left as a black box is how those tables get filled in the first place. That is routing, and it is the entire subject of the next rung, where routers finally learn to talk to each other and build the map.