Longest prefix match and the routing decision

Every routing decision on every packet is a lookup against the FIB, and every lookup follows one rule: longest prefix match wins. Not “best metric”, not “preferred source”, not “shortest AS path” — those are preferences within a prefix length. The prefix length decides first; only when two routes have the same prefix length does the comparison move on to metric or preference.

This lesson explains how FreeBSD walks the table, what happens at the edges (literal /0 matching everything, literal /32 matching one host), and how to predict and verify the kernel’s decision for any destination.

The rule, stated simply

For each packet, the kernel asks: “for this destination IP, which prefix in the FIB has the longest network mask that still matches?”

Destination: 203.0.113.50

FIB:
  0.0.0.0/0          via 198.51.100.1   (default)
  203.0.113.0/24     via 192.0.2.1      (static)
  203.0.113.48/28    via 10.0.0.1       (static)

Longest matching prefix: 203.0.113.48/28  →  via 10.0.0.1

If two routes have the same prefix length (two /24 candidates for the same prefix, say), the kernel uses a tie-breaker. On FreeBSD that tie-breaker is “first matching route in the FIB order”, which is usually “youngest entry first” — but it is not a stable guarantee and should not be relied on. The lesson on multi-WAN and gateway groups covers the supported way to express preference.

Walking the table

If you wanted to write the lookup by hand, the algorithm is:

1. Start with the destination IP.
2. For each prefix length from /32 down to /0:
   • Is there a route in the FIB with that prefix length that matches the destination?
   • If yes, use it. Stop.
3. If no match for any prefix, the destination is unreachable.

In a small table with eight or ten routes this is fine. In a production table with tens of thousands of routes (BGP feeds, VPN aggregates, multi-WAN), walking linearly from /32 down is expensive. Real routers and the FreeBSD kernel use a radix tree (a binary trie keyed on the bits of the destination address) so the lookup is O(prefix length) regardless of table size.

$ route -n get 203.0.113.50

   route to: 203.0.113.50
destination: 203.0.113.48
     mask: 255.255.255.240
  gateway: 10.0.0.1
interface: igb2
    flags: <UP,GATEWAY,DONE,STATIC>
recvpipe  sendpipe  ssthresh  rtt,msec    mtu        expire
 0         0         0         0         1500        0

What /0 really means

A route to 0.0.0.0/0 is a route whose prefix is zero bits long. Zero bits match every possible IPv4 address. So 0.0.0.0/0 is the “match anything” route — the default route. It is the last prefix length checked (after /1, /2, … down to /32 in the worst case) and it catches every destination that no more-specific prefix matched.

In production this means: if a packet goes out via the default route’s gateway, no more-specific prefix exists for its destination. If the operator believes a more-specific prefix should exist, the operator’s table is wrong, not the kernel’s.

Why “metric” comes second

Many operators have a mental model from Cisco / Juniper / vendor configurations where “lower administrative distance wins”. That model is wrong on FreeBSD (and on most modern router platforms in its strict form). The precedence on FreeBSD is:

1. Most specific prefix wins. Two routes for the same prefix length tie.
2. Tie-break on route type. Connected > static > dynamic, by default. (Configurable in FRR per protocol.)
3. Tie-break on metric, if the routing daemon provides one.
4. First matching route in FIB order as the final fallback.

The metric a routing daemon advertises is used only when the prefix length is equal. A dynamic /24 route will never override a static /16 route for an overlapping destination, because the /16 is more specific. The lesson on routing daemons and FRR covers this in depth.

Predicting the kernel’s decision

For any destination, predict the outcome:

1. Is the destination in a directly-connected subnet? If yes, the connected route wins, regardless of any more-specific static route that might exist (because you cannot define a more-specific route that overlaps a connected subnet and have it win in practice — the kernel refuses to install overlapping connected routes).
2. If not, walk prefixes from /32 down. The first match wins.
3. If nothing matches /1, the default route /0 catches it.
4. If there is no default route, the packet is dropped at the IP layer with no log entry.

For a complex table, the fastest verification is route -n get <dest> — the kernel reports which route it would use, and which interface and gateway that route resolves to. If the operator’s prediction and the kernel’s report disagree, the table has changed since the operator last looked at it.

Production failure modes

Three incidents trace directly to LPM surprises:

1. “I added a static route but traffic still uses the default” — the static route’s prefix is less specific than an existing route (a /16 static vs. a /24 connected, for example). The kernel correctly uses the more-specific connected route. The fix is to make the static route more specific or to remove the conflicting connected route.
2. “The static route works from one host but not another” — the two hosts are in different subnets; one falls into the static route’s prefix and the other falls into the default. The fix is to widen the static route’s prefix or to add a second static route for the other subnet.
3. “A VPN’s subnet overlaps our LAN” — the VPN pushes a route for 10.0.0.0/8 but the LAN has 10.1.0.0/16. The LAN traffic stays on the LAN (correct), but VPN-bound traffic from the LAN to 10.2.0.0/16 falls into the VPN’s /8 and is sent down the tunnel (correct only if that was the intent). The trap is when the VPN’s /8 route was intended to be a fallback but accidentally catches more than intended. Tighten the prefix.

Summary

• Longest prefix match wins. Every time, every packet.
• Tie-break by route type (connected > static > dynamic), then metric, then FIB order.
• /0 matches everything; /32 matches one host.
• The verification command is route -n get <dest>.
• When LPM surprises you, the operator’s mental model is wrong, not the kernel’s.