Forwarding with longest-prefix match
Choose the next hop by finding the most specific route that matches a destination address.
On this page
IP addressing and CIDR prefixes.
- Choose the next hop by finding the most specific route that matches a destination address.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
A router forwards each packet by looking up its destination IP address in a forwarding table. Each entry is a prefix plus a next hop. Several entries can match the same address, for example a broad default route and a narrow route to one lab network. The rule is longest-prefix match: the router uses the matching entry with the longest prefix, because a longer prefix is more specific.
Forwarding and routing are different jobs. Forwarding is the per-packet lookup described here. Routing is how the table gets filled in: routing protocols such as OSPF inside a network and BGP between networks exchange reachability information, and administrators add static routes. The default route 0.0.0.0/0 matches every address and has prefix length 0, so it is used only when nothing more specific matches.
The program stores routes as ip_network objects and a next-hop label. It selects all matching routes for a destination and takes the one with the largest prefix length. Real routers do this in hardware with specialized data structures such as tries or TCAMs, not by scanning a list.
Code example
import ipaddress
routes = [
(ipaddress.ip_network("0.0.0.0/0"), "default gateway"),
(ipaddress.ip_network("10.0.0.0/8"), "corporate core"),
(ipaddress.ip_network("10.1.0.0/16"), "branch office"),
(ipaddress.ip_network("10.1.2.0/24"), "lab switch"),
]
def next_hop(destination):
address = ipaddress.ip_address(destination)
matches = [(network.prefixlen, hop) for network, hop in routes if address in network]
return max(matches)[1]
for destination in ("10.1.2.9", "10.1.9.9", "10.200.0.1", "8.8.8.8"):
print(destination, next_hop(destination))10.1.2.9 lab switch 10.1.9.9 branch office 10.200.0.1 corporate core 8.8.8.8 default gateway
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
import ipaddress routes = [ (ipaddress.ip_network("0.0.0.0/0"), "default gateway"), (ipaddress.ip_network("10.0.0.0/8"), "corporate core"), (ipaddress.ip_network("10.1.0.0/16"), "branch office"), (ipaddress.ip_network("10.1.2.0/24"), "lab switch"),] def next_hop(destination): address = ipaddress.ip_address(destination) matches = [(network.prefixlen, hop) for network, hop in routes if address in network] return max(matches)[1] for destination in ("10.1.2.9", "10.1.9.9", "10.200.0.1", "8.8.8.8"): print(destination, next_hop(destination))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Collect every route whose prefix contains the destination. 10.1.2.9 matches all four routes. | 10.1.2.9 matches /0, /8, /16, /24 | — | |
| The largest prefix length wins: the /24 is the most specific, so the lab switch is chosen. | 10.1.2.9 matches /0, /8, /16, /24 | — | |
| 10.1.9.9 is outside the /24 but inside the /16, so it goes to the branch office. 8.8.8.8 matches only the default route. | 10.1.2.9 matches /0, /8, /16, /24 | 10.1.2.9 lab switch 10.1.9.9 branch office 10.200.0.1 corporate core 8.8.8.8 default gateway |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
This list scan is O(r) for r routes. Hardware tries give O(w) lookup for w address bits, independent of table size.
- Choosing the first match instead of the longest is a common bug. Order in the table must not decide the result.
- Without a default route, a destination that matches nothing has to be dropped, typically with an ICMP unreachable message.
- Longest-prefix match applies to the destination only. Policy routing can use other fields, but that is a separate mechanism.
Try it yourself
Which next hop is chosen for 10.1.2.255, and for 10.2.0.1?
Reveal answer and reasoning
10.1.2.255 is inside the /24, so the lab switch. 10.2.0.1 matches only the /8 and the default, so the corporate core.