Longest-prefix match — the algorithm that decides every packet

Longest-prefix match is the algorithm the kernel runs on every outgoing packet. It is faster than administrative-distance preference: AD is consulted only when two routes cover the same prefix, and longest-prefix match chooses the prefix first.

The routing engineer who confuses the two will misdiagnose routing incidents. A more-specific prefix always wins over a less-specific one — even when the more-specific route is from an untrusted source and the less-specific is from the most trusted source. The kernel does not know or care about “trusted”. The kernel looks up the prefix.

This lesson is the operator’s foundation in longest-prefix match: how it works, how it interacts with administrative distance, and the production failure modes that surface as unexpected route selection.

How longest-prefix match works

The Linux kernel stores routes in a trie (a prefix tree). When a packet arrives and the kernel needs to forward it, the kernel walks the trie from the most-significant bit of the destination address to the least-significant bit, looking for matching prefixes at each level. The first matching prefix at the deepest level is the one the kernel uses.

flowchart TB
  P["Packet to 10.0.5.50"] --> R["Root"]
  R -->|"10"| N1["node: 10.*"]
  N1 -->|"10.0"| N2["node: 10.0.*"]
  N2 -->|"10.0.0"| N3["node: 10.0.0.*"]
  N2 -->|"10.0.5"| N4["node: 10.0.5.*"]
  N4 -->|"10.0.5.50"| L["leaf: 10.0.5.50/32"]

  N1 -.->|"default"| D["0.0.0.0/0"]
  N3 -.->|"specific"| S1["10.0.0.0/16"]
  N4 -.->|"most specific"| S2["10.0.5.0/24 — WINNER"]

For a packet to 10.0.5.50, the kernel finds matches at three levels: the default route (0.0.0.0/0), the summary route (10.0.0.0/16), and the specific route (10.0.5.0/24). The longest prefix is /24, so the kernel uses that.

Longest-prefix match outranks administrative distance

The two mechanisms do not compete, because they run in different places on different inputs:

1. Administrative distance is resolved per prefix, in FRR. zebra holds the RIB. For one prefix — say 10.0.5.0/24 — it compares every protocol offering that exact prefix, keeps the lowest-AD candidate, and installs only that winner into the kernel. A route that loses the AD comparison never reaches the kernel at all. When two candidates tie on AD, the protocol’s own metric breaks the tie inside that protocol.
2. Longest-prefix match is resolved across prefixes, in the kernel. The FIB the kernel forwards from is a set of distinct prefixes, one entry per prefix. There is no administrative distance in it; ip route show prints no AD column because the kernel has no such concept. Forwarding walks the trie and takes the most specific match.

So administrative distance never gets the chance to overrule a more-specific prefix: by the time forwarding happens, AD has already done its only job, which was to decide who represents 10.0.5.0/24 and who represents 10.0.0.0/16 — never which of the two a packet uses.

The routing engineer who says “OSPF should win over static because OSPF is dynamic” is wrong on the order. OSPF wins only when the AD comparison applies, and it applies only when both routes carry the same prefix.

The practical consequence: a /32 static host route always wins over an OSPF /24 covering route, regardless of AD.

Predicting route selection in production

When two routes cover overlapping prefixes, the routing engineer must apply both rules: longest-prefix first, then AD.

flowchart LR
  P["Packet to 10.0.5.50"] --> L1{"Most specific\nprefix?"}
  L1 -->|"/24 (specific)"| W1["Use /24 route"]
  L1 -->|"/16 only"| L2{"Same prefix\nor two candidates?"}
  L2 -->|two routes for same prefix| L3{"Lowest\nAD?"}
  L2 -->|one route| W2["Use that route"]
  L3 -->|"AD 1 (static)"| W3["Static wins"]
  L3 -->|"AD 110 (OSPF)"| W4["OSPF wins"]
  L3 -->|"AD 20 (eBGP)"| W5["eBGP wins"]

The diagnostic command for predicting selection:

ip route get 10.0.5.50

The kernel returns the route it would use. If the operator expected a different route, the discrepancy is either a configuration error or a misunderstanding of LPM.

Summarisation in BGP

Aggregation in BGP produces a summary route that is less specific than its components. The summary acts as a blackhole route by default (no specific next-hop), and traffic to addresses within the summary but not covered by any more-specific prefix is dropped.

On VyOS 1.5 the aggregate lives under the address family, and the local ASN is a system-as leaf rather than a level in the path:

configure
set protocols bgp system-as 65000
set protocols bgp address-family ipv4-unicast aggregate-address 192.0.2.0/24 summary-only
commit
save

This creates a 192.0.2.0/24 aggregate and suppresses the advertisement of the more-specific routes it covers. FRR only generates the aggregate while at least one component prefix is present in the BGP table; with no components, nothing is advertised.

Configuring routes with priority

VyOS exposes several knobs for controlling route preference:

configure
# Static route with an explicit administrative distance (default 1)
set protocols static route 10.0.0.0/24 next-hop 192.0.2.1 distance 100

# BGP peer; eBGP routes arrive with AD 20, iBGP with 200
set protocols bgp system-as 65000
set protocols bgp neighbor 192.0.2.1 remote-as 65001
set protocols bgp neighbor 192.0.2.1 ebgp-multihop 2

# OSPF link cost — an SPF input, not an administrative distance
set protocols ospf interface eth0 cost 10

# OSPF administrative distance, if you really mean to change it
set protocols ospf distance global 110
commit
save

Keep the two numbers apart. distance selects between protocols offering the same prefix; cost is consumed inside OSPF’s own shortest-path calculation and is never compared with a static route’s distance. The frequent mistake is to read “OSPF is 110” as a cost — 110 is OSPF’s default administrative distance, and the default cost is derived from interface bandwidth against the reference bandwidth.

The distance keyword under set protocols static route ... sets the AD for that one route, overriding the default of 1. That is the standard lever for AD conflicts, and the mechanism behind the floating static below.

Failure modes

Wrong route wins due to LPM

The most common production failure: an operator expects traffic to a specific IP to take path A but it takes path B because a more-specific prefix overrides the less-specific route they were thinking about.

Diagnostic:

• ip route show <prefix> shows all routes covering the destination.
• ip route get <dst> shows which route the kernel will use.
• Compare the expected path to the actual path. Identify the more-specific route that is winning.

Aggregate attracts traffic the router cannot deliver

The operator summarises several specific routes into a /24 aggregate. The peers now send everything in that /24 here. Addresses inside the /24 that the router has no component route for have nowhere to go.

Diagnostic:

• show ip bgp 192.0.2.0/24 confirms the aggregate is being generated locally.
• show ip route 192.0.2.0/24 shows what the router will actually do with the traffic — a blackhole entry if the discard route is present, and nothing at all if it is not.
• show ip route 192.0.2.99 for a specific unserved address: if the answer is the default route, the traffic is being sent back towards the peer that sent it.

Floating static route does not activate

A floating static route has a higher AD than the dynamic route. It activates only when the dynamic route disappears.

Diagnostic:

• ip route show <prefix> shows the dynamic route, not the floating static.
• When the dynamic route disappears, the floating static takes over.
• Check that the floating static’s AD is higher than the dynamic route’s AD.

A configured static route is never installed

The operator commits a static route, commit succeeds, and the route does not appear in the kernel. Two distinct causes look identical from ip route show, and only the RIB view tells them apart:

• The next-hop does not resolve. FRR will not install a static route whose next-hop it cannot reach over some other route. show ip route marks the entry inactive rather than hiding it. This is a next-hop problem, not a prefix problem, and the more-specific prefix does not rescue it.
• The prefix collides with a connected route. A static route for exactly the prefix of a connected interface loses the AD comparison to that connected route (AD 0) and never reaches the kernel. Note this only applies to the same prefix — a genuinely more-specific static inside a connected subnet is a different prefix and does get installed.

Diagnostic:

• show ip route 10.0.5.0/24 — the RIB view. An inactive static appears here; a route the operator never actually committed does not.
• show configuration commands | match 10.0.5.0 confirms the route is in the configuration at all.
• ip route show 10.0.5.0/24 — the kernel view. Empty means FRR did not install it.
• Fix depends on which cause: give the next-hop a route (or bind the static to an interface with set protocols static route ... interface ethN), or choose a prefix that does not duplicate a connected one.

Validation

The validation sequence for “the route chosen by the kernel is not the route I expected”:

1. All matching routes: ip route show <prefix> lists every route covering the destination.
2. The kernel’s choice: ip route get <dst> returns the route the kernel will use.
3. The most specific prefix: identify which route has the longest prefix.
4. The AD: if two routes have the same prefix, identify the one with the lowest AD.
5. The configuration: show configuration commands | match <prefix> shows the configured routes.
6. The FRRouting view: the VyOS operational command show ip route <prefix> prints zebra’s RIB, including the candidates that lost the AD comparison and were therefore never installed. This is the step that distinguishes “the route is not configured” from “the route is configured and lost”.

If the kernel picks a route the operator did not expect, the configuration is wrong (a more-specific route was added unintentionally) or the operator’s expectation is wrong (they thought the OSPF route was the most specific).

Cross-course references

• The Linux course’s V-Linux-NetConfig covers the routing-table trie from the host perspective.
• The lesson on routing tables in Part II covers the field semantics in depth.
• The lessons on BGP and OSPF in later parts cover how dynamic routes enter the table.

Quiz

Production discipline

Longest-prefix match is the algorithm that runs on every outgoing packet. The routing engineer who understands it can predict route selection in every case. The routing engineer who does not will misdiagnose incidents because they expect the “more trusted” route to win, when in fact the more-specific route always wins.

Plan the addressing once. Plan the aggregations once. Plan the floating-static ADs once. Then routing either works or fails predictably.