Forwarding with longest-prefix match
Choose the next hop by finding the most specific route that matches a destination address.
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
Explanation
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.
Explore the dry run
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 |
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.