Explain longest prefix match with an example. Which route does the router use for a few different destinations?
Show the answer
Say this first
The router compares the destination address with every prefix in its table and uses the matching entry with the most mask bits. A /25 beats a /24, which beats a /16, which beats the /0 default, no matter which protocol or AD each came from. The default route matches everything, which is why it is used last.
Go deeper
The table
S* 0.0.0.0/0 [1/0] via 203.0.113.1
O 10.0.0.0/8 [110/30] via 10.255.0.2, 00:10:02, GigabitEthernet0/0/1
D 10.20.0.0/16 [90/3072] via 10.255.1.2, 00:10:02, GigabitEthernet0/0/2
O 10.20.30.0/24 [110/20] via 10.255.0.2, 00:10:02, GigabitEthernet0/0/1
S 10.20.30.128/25 [1/0] via 10.255.2.2The lookups
| Destination | Entries that match | Winner |
|---|---|---|
| 10.20.30.200 | /0, /8, /16, /24, /25 | static /25 via 10.255.2.2 |
| 10.20.30.100 | /0, /8, /16, /24 | OSPF /24, even though the EIGRP /16 has a lower AD |
| 10.20.99.1 | /0, /8, /16 | EIGRP /16 |
| 10.99.1.1 | /0, /8 | OSPF /8 |
| 172.16.5.5 | /0 | static default |
Why .200 and .100 split
A /25 fixes the first bit of the last octet. 10.20.30.128/25 covers .128 to .255.
- 200 is
11001000: the first bit is 1, so it is inside the /25. - 100 is
01100100: the first bit is 0, so it is not, and the /24 is the best match.
How fast routers do it
IOS CEF stores the FIB in a multiway trie keyed on address bits. Hardware platforms do the same lookup in the ASIC, with TCAM (entries sorted so the first hit is the longest) or an algorithmic LPM table. Either way the lookup cost does not grow with the number of routes.
They will ask next
Why would anyone install a /32 route?
A /32 is the most specific match possible, so it always wins. Loopbacks used as router IDs and BGP next hops are /32s, remotely triggered black holing uses /32s, and a /32 static can pin an IP SLA probe to one path.
What if the most specific match points at Null0?
The packet is dropped, even if a shorter route (like the default) would have delivered it. That is exactly how summary discard routes stop loops.
Traps
- Picking the route with the lower AD or metric when the prefix lengths differ. Length is compared first.
- Doing the binary on the wrong octet. Find the octet where the mask stops, and only look there.