Forwarding and Longest-Prefix Match
- Forwarding is the per-packet data plane job: look up the destination in the forwarding table, decrement TTL, fix the checksum, queue, send. Routing is the control plane job that fills that table, and it lives on other pages.
- A destination can match many table rows. The router picks the one with the longest prefix, the most specific route.
0.0.0.0/0is the default route and only wins when nothing else matches. - Longest prefix is decided before metric or administrative distance. Distance and metric only choose among routes for the same prefix.
- A real table row carries a next hop, an interface, a metric and a route source, not just prefix to interface. Equal-cost rows give ECMP, where a hash of the flow keeps each flow on one path.
- A router rewrites the link-layer header on every hop and subtracts 1 from TTL. It never needs to know the whole path, only the next hop.
Mental model
Think of the signs in an airport. One sign says "Flights to Europe", a closer one says "Flights to Paris", and at the end of the hall a catch-all says "All other flights". You follow the most specific sign that covers your flight. If no sign names your destination, you follow "All other flights". Nobody at any sign knows your whole journey; each one only tells you which corridor to take next.
Where it breaks: an airport sign works on meaning, and a person can read all the signs at once. A router matches leading bits of an address, not meaning, and it must find the winning row in nanoseconds for every packet.
It is a most-specific-key-wins lookup, the same idea as an HTTP router choosing between the patterns /api/* and /api/users/*, or a map keyed by prefix where you walk down a trie and remember the deepest node that has a value. The table is the map, the destination IP is the key, and the default route is the catch-all handler at the root.
Where it breaks: a URL router's routes are written by one team in one file. A routing table is filled by several independent sources (connected networks, static config, OSPF, BGP) that can disagree, and a second rule, administrative distance, arbitrates between them.
How it works
A router does two very different jobs, and routers are built so the two do not slow each other down.
- The data plane (forwarding) is the local per-packet action. A packet arrives, the router looks up the destination in its forwarding table (the FIB) and sends the packet toward the right next hop. It runs for every packet, often in dedicated hardware.
- The control plane (routing) builds that table. Routing protocols such as OSPF and BGP and static configuration decide which routes exist and which one wins. How those protocols work is on the link-state and distance-vector routing page and the module 05 pages, not here. This page starts at the point where the table already exists; the module overview is routing overview.
The four-row table
Here is a small forwarding table. A packet may match several rows, because prefixes overlap.
| Destination prefix | Outgoing interface |
|---|---|
| 200.23.16.0/20 | 0 |
| 200.23.24.0/23 | 1 |
| 200.23.0.0/16 | 2 |
| 0.0.0.0/0 (default) | 3 |
When several rows match a destination, the router picks the row with the longest prefix, the one that pins down the most leading bits. That is the most specific route. The default route 0.0.0.0/0 has prefix length 0, so it matches everything and wins only when nothing longer matches. The standard CIDR rules are in RFC 4632, and RFC 1812 is the router requirements document that expects routers to forward this way.
A destination matches a prefix when its first L bits equal the prefix's first L bits, where L is the prefix length. So the way to check a match by hand is to write both in binary and compare the leading bits.
Worked example 1: 200.23.24.50
In binary the destination is 11001000.00010111.00011000.00110010. Align it against each prefix:
All four rows match. The /20 pins down 20 bits, the /23 pins down 23, so the /23 wins and the packet leaves on interface 1. Notice the third octet: 24 is 00011000, and the /23 covers its first 7 bits 0001100.
Worked example 2: 200.23.18.100
In binary: 11001000.00010111.00010010.01100100. The third octet 18 is 00010010.
The /23 prefix 200.23.24.0 has third octet 00011000. It agrees with the destination for 20 bits, then differs at bit 21 (1 against 0), but a /23 needs 23 bits to agree, so it does not match. The /20 needs 20 bits and gets them, the /16 needs 16 and gets them, and the /20 is longer, so the packet leaves on interface 0.
Worked examples 3 and 4
The other two destinations in the same table, with the first bit that differs for each prefix (computed from the binary, and checked with Python's ipaddress module):
| Destination | Binary | /23 (if 1) | /20 (if 0) | /16 (if 2) | Default (if 3) | Winner |
|---|---|---|---|---|---|---|
| 200.23.5.9 | 11001000.00010111.00000101.00001001 | differs at bit 20 | differs at bit 20 | matches | matches | /16, interface 2 |
| 74.125.20.1 | 01001010.01111101.00010100.00000001 | differs at bit 1 | differs at bit 1 | differs at bit 1 | matches | default, interface 3 |
For 200.23.5.9 the third octet is 00000101. The /20 and /23 both need the fourth bit of that octet (overall bit 20) to be 1, and it is 0, so both fail. The /16 only needs the first two octets, which match. For 74.125.20.1 the very first bit is 0 while every 200.23 prefix starts with 1, so only the default route is left.
Try your own destination against this table, edit or add rows, and watch which prefix wins bit by bit:
| Prefix/len | Next hop | Interface | Source | AD (Cisco default) | Metric | Against this destination | Remove |
|---|---|---|---|---|---|---|---|
| matches 20 bits, shadowed by the more specific /23 | |||||||
| winner (23 bits match) | |||||||
| matches 16 bits, shadowed by the more specific /23 | |||||||
| matches 0 bits, shadowed by the more specific /23 |
Longest prefix is decided first; AD and metric never override it.
What the router does to each packet
For a packet that is being forwarded (not addressed to the router itself), a router does roughly this. The exact order of the steps varies by platform.
- Validate the IP header: version, header length, and header checksum. A bad header is dropped.
- Look up the destination address in the FIB by longest-prefix match. The result is a next hop and an output interface.
- Check TTL. If TTL is 1 or 0 the router does not forward the packet. It drops it and sends an ICMP time exceeded message (type 11, code 0) to the source, as covered on the IP packet page. Otherwise it subtracts 1.
- Recompute the header checksum, because TTL changed. Routers usually do this as an incremental update (RFC 1624) rather than summing the whole header again.
- Rewrite the link-layer header. The new source MAC is the router's output interface, and the new destination MAC is the next hop's, found with ARP (or neighbour discovery in IPv6). The IP addresses do not change on an ordinary hop; only NAT changes them (NAT).
- Queue the packet on the output interface and transmit it when the link is free.
- On failure, report it. No matching route gives an ICMP destination unreachable (type 3, code 0, network unreachable, RFC 792). A packet that is too big with DF set gives type 3 code 4, covered in MTU, MSS and fragmentation. A full queue drops the packet silently.
The side of this that belongs to the sending host (is the destination local, or do I use my gateway?) is the host forwarding decision. The host uses the same longest-prefix rule over a much smaller table.
Deep dive
A real table row is more than prefix and interface
The textbook table maps prefix to interface. A real forwarding or routing entry also holds the next hop address, a metric, and where the route came from. This is the shape of ip route show on a Linux host (annotated, abbreviated):
| Prefix | Next hop | Device | Proto | Metric | Reads as |
|---|---|---|---|---|---|
| default | 192.168.1.1 | eth0 | dhcp | 100 | everything with no better row goes to the gateway, learned from DHCP |
| 10.8.0.0/24 | none (on-link) | tun0 | kernel | none shown | a connected network: the kernel added it when the interface came up |
| 172.16.0.0/12 | 10.8.0.1 | tun0 | static | 50 | an operator added this by hand |
| 192.168.1.0/24 | none (on-link) | eth0 | kernel | 100 | the directly connected LAN; deliver with ARP, no gateway |
A row with no via is a connected route: the destination is on the link, so the router ARPs for the destination itself. A row with via forwards to the next hop's MAC. The proto field records the route source (kernel, static, dhcp, and for a routing daemon its protocol name such as ospf or bgp); see the ip-route manual page for the field list. Output varies by iproute2 version.
RIB, FIB and recursive lookup
Routers keep two structures. The RIB (routing information base) holds every candidate route from every source. The FIB (forwarding information base) holds only the single best route (or equal-cost set) per prefix, in a form the forwarding hardware can search fast. The control plane picks winners from the RIB and installs them into the FIB, which is the arrow in the figure above.
Some routes name a next hop that is not directly connected, for example a BGP route whose next hop is a loopback address several hops away. The router must then look that next hop up too, and repeat until it reaches a connected route. This is called a recursive lookup. Production platforms usually resolve it when the route is installed, so the FIB entry the hardware reads is already flattened to an interface and neighbour.
Route sources and administrative distance
Several sources can offer a route to the same prefix. A router has to pick one source, and it does so with administrative distance (AD): a per-source trust number where lower wins. The values below are Cisco's defaults, from Cisco's What Is Administrative Distance? page:
| Route source | Default AD | Why that rank |
|---|---|---|
| Connected interface | 0 | the router is physically attached; nothing is more certain |
| Static route | 1 | an operator typed it on purpose |
| eBGP | 20 | learned from a neighbouring AS |
| OSPF | 110 | an interior protocol |
| RIP | 120 | an older, coarser interior protocol |
| iBGP | 200 | learned inside your own AS; prefer the IGP |
Other vendors call the concept route preference and use different default values, and the Linux kernel itself has no AD: it keeps routes for one prefix ordered by metric. When you run FRR or another routing daemon on Linux, the daemon applies distance before it installs the winner into the kernel.
The order of decisions: specificity first
Three separate rules apply, in a fixed order:
- Longest prefix decides between routes for different prefixes. This is the lookup.
- Administrative distance decides between sources that offer the same prefix.
- Metric decides between routes with the same prefix from the same source (for example two OSPF paths).
This ordering explains the classic confusion about a stale static route shadowing a dynamic one. It depends on which prefix the static route has:
| Stale static route | Dynamic route | Who wins | Why |
|---|---|---|---|
| 10.20.0.0/24 via a dead gateway | 10.20.0.0/24 from OSPF | the static route | same prefix, so AD decides: 1 beats 110, and the packet is sent to the dead gateway |
| 10.20.0.0/16 via a dead gateway | 10.20.0.0/24 from OSPF | the OSPF route | different prefixes, so the longer /24 wins and AD is never consulted |
| 10.20.0.0/28 via a dead gateway | 10.20.0.0/24 from OSPF | the static route for its 16 addresses | the /28 is more specific, so it shadows the dynamic route for that slice only |
In an FRR routing table the first row looks like this (the > marks the selected route and * marks the one installed in the FIB; ages and weights vary):
The bracketed numbers are [distance/metric]. The OSPF route is correct and fully known to the router, but it is not in the FIB, so it carries no traffic.
ECMP: equal-cost multipath
When a FIB holds several next hops for the same prefix at equal cost, the router can spread traffic across them. This is ECMP. Splitting packet by packet would reorder them within a TCP connection and trigger needless retransmissions (see retransmission and timers), so routers choose a path by hashing the flow, normally the source and destination addresses and often the ports and protocol as well. Every packet of one flow hashes to the same next hop, so the flow stays in order. RFC 2992 analyses hash-based algorithms for this.
The costs are worth knowing. A few large flows can land on one path and leave another idle, because the hash balances flows and not bytes. Changing the number of next hops can remap many flows if the scheme is naive. And on Linux, which fields are hashed is a setting: see fib_multipath_hash_policy in the kernel ip-sysctl documentation for the options.
How a lookup is made fast
The router cannot compare the destination to every row. Real implementations trade memory for speed:
- Tries. Store prefixes in a binary tree keyed by bits; walk down the destination's bits and remember the last node that held a route. Linux's IPv4 FIB is an LC-trie, a level-compressed trie, in
net/ipv4/fib_trie.c. - Binary search on prefix lengths. Waldvogel, Varghese, Turner and Plattner showed lookups can be done by binary search over hash tables grouped by prefix length (Scalable High Speed IP Routing Lookups, SIGCOMM 1997).
- Big direct tables. The DIR-24-8 scheme of Gupta, Lin and McKeown indexes a table with the top 24 bits of the address, so most lookups need one memory access and a longer prefix needs a second (Routing Lookups in Hardware at Memory Access Speeds, INFOCOM 1998).
- TCAM. A ternary content-addressable memory compares the key against every stored entry in parallel and each bit can be 0, 1 or "don't care", which is exactly a prefix (content-addressable memory). Entries are kept ordered by prefix length so the first hit is the longest. TCAM is fast but small, costly and power hungry, which is why hardware platforms have a fixed route capacity.
How big must the table be? The default-free zone (routers with no default route, holding the global BGP table) is on the order of a million IPv4 prefixes in the mid 2020s. The number moves every day, so read the live figure at the CIDR Report or bgp.potaroo.net rather than trusting a number frozen on this page. This is why route aggregation (one /16 instead of 256 /24s) matters.
At line rate the time budget is tiny. The smallest Ethernet frame is 64 bytes, plus 8 bytes of preamble and 12 bytes of inter-frame gap, so 84 bytes or 672 bits per packet. At 10 Gb/s that is 67.2 ns per packet (14.88 million packets per second), and at 100 Gb/s it is 6.72 ns. Each packet needs its own lookup inside that budget.
Queues at a router
Packets queue on the output port when they arrive faster than the link can send. A queue that fills up has to drop something, and where the drop happens matters:
- Drop-tail discards new arrivals when the buffer is full. It is simple, and it makes many TCP flows back off at the same moment.
- AQM (active queue management) drops or marks packets early to signal congestion before the buffer fills. RFC 7567 gives the recommendation and RFC 8289 specifies CoDel, one algorithm.
- Head-of-line (HOL) blocking happens in switches that queue at the input: a packet at the front waiting for a busy output port blocks the packets behind it, even those headed for idle ports. Karol, Hluchyj and Morgan showed that FIFO input queueing saturates at 2 minus the square root of 2, about 58.6 percent of link capacity, for uniform traffic and many ports (Input versus output queueing on a space-division packet switch, 1987). Routers avoid it by keeping a separate virtual queue per output at each input.
Congestion behaviour at the end hosts is the subject of congestion control.
Router, switch and L3 switch
| Device | Forwards by | Table | Rewrites |
|---|---|---|---|
| Switch (L2) | destination MAC address | MAC table, exact match, flood if unknown | nothing; the frame passes unchanged |
| Router (L3) | destination IP, longest-prefix match | FIB | link-layer header, TTL, header checksum |
| L3 switch | MAC inside a VLAN, IP between VLANs | MAC table plus FIB in the same ASIC | as a router, when it routes |
A L3 switch is a switch whose hardware can also do the router's job at line rate, typically to route between VLANs. The lookup is the same longest-prefix match; the difference from a "router" box is mostly packaging and feature set. How switches learn MAC addresses is on the switches page.
Textbook vs real world
| The textbook says | Production does | Why |
|---|---|---|
| The table maps prefix to outgoing interface | Each row has a next hop, interface, metric and route source, and may hold several equal-cost next hops | the router needs the next hop's MAC to build the frame, and several sources compete for the same prefix |
| The longest match wins | True for the lookup, but a second rule (administrative distance) decides which source's route for a prefix is installed at all | separate protocols know nothing about each other's metrics |
| Only routers have routing tables | Every host has one too: a connected route plus a default route via the gateway | the host asks the same longest-prefix question |
| Forwarding is a table scan | Tries in software, TCAM or tree/hash structures in forwarding ASICs | a scan cannot meet the per-packet time budget |
| Forwarding is hardware | A Linux router forwards in the kernel (software); big platforms use ASICs; both exist | hardware gives line rate, software gives flexibility |
| One best path per destination | ECMP spreads flows over equal-cost paths, using a flow hash | capacity: use all links, not one |
In production
- Linux keeps the IPv4 FIB as an LC-trie (
fib_trie.c). Linux 3.6 removed the older IPv4 routing cache, so every forwarded packet is resolved from the FIB (Linux 3.6 release notes). - Hardware routers commonly hold the FIB in TCAM or similar forwarding memory with a fixed capacity per platform. When the global table outgrows the allocation, a device can stop installing new routes, so operators watch the table size on the CIDR Report and the vendor's capacity documentation.
- AWS VPC route tables apply longest-prefix match first, and only for equal prefixes use a documented priority order (for example static routes before propagated ones, then Direct Connect and VPN BGP routes). Read the order in the route table documentation. The cloud side, including subnets, gateways and where a default route points, is on VPC, subnets and routing.
- Data centre fabrics lean heavily on ECMP across many equal-cost uplinks, which is why the flow hash and its fields (
fib_multipath_hash_policyon Linux) matter in practice (kernel ip-sysctl).
History and evolution
- 1981 RFC 791 defines classful addressing. A router reads the class from the leading bits of the address, then does an exact match on the network number, so lookup is simple.
- 1993 Class B exhaustion and a fast-growing routing table force CIDR (RFC 1519), later replaced by RFC 4632. Prefixes can now be any length, so exact match is no longer enough and every router must do longest-prefix match, which forced new lookup hardware and software.
- 1997 Waldvogel et al. publish binary search over prefix lengths, and in 1998 Gupta, Lin and McKeown describe DIR-24-8 for hardware, so lookups fit the time budget of fast links.
- 2012 Linux 3.6 removes the IPv4 routing cache and forwards straight from the FIB trie (release notes).
- Now The default-free zone is on the order of a million IPv4 prefixes; the live figure is on the CIDR Report and bgp.potaroo.net. ECMP and hash-based path selection are routine in data centres.
- Next Aggregation pressure keeps the table growing, and segment routing over IPv6 (RFC 8986) moves some path choice out of the per-hop table and into the packet.
Hands-on
ip route show lists the table. ip route get X asks the kernel which route it would use for X and which source address it would pick, so it is the fastest way to test longest-prefix match on a real machine. Try it with an address inside your LAN (the answer has no via) and one outside (the answer goes via the gateway). Newer iproute2 versions print slightly different trailing fields, such as cache.
On macOS the same table is netstat -rn:
default is the 0.0.0.0/0 row. A link#N gateway means a connected route (no next hop). macOS has no ip route; use route -n get 8.8.8.8 for the equivalent of ip route get. The exact flags and the number of rows differ by macOS version.
traceroute -n <destination> shows the next hop each router chose in turn, by watching TTL expire at each hop (the mechanism is on the IP packet page, and the tool on ping, traceroute and mtr):
The hop addresses and timings will differ on your network. A * * * line means that hop did not answer; it does not by itself mean packets are lost, since many routers rate-limit or filter ICMP.
If the machine runs FRR, vtysh -c "show ip route" prints the full RIB with the source code (C connected, S static, O OSPF, B BGP) and the [distance/metric] pair, as in the example in the deep dive.
Gotchas
Interview questions
Show answer
A destination address can match several table prefixes, because prefixes overlap. The router chooses the matching row with the longest prefix length, meaning the most leading bits in common, because that is the most specific route. For example, with routes 200.23.16.0/20, 200.23.24.0/23, 200.23.0.0/16 and a default, the address 200.23.24.50 matches all four, and the /23 wins because 23 bits is more than 20, 16 or 0. In binary the third octet is 00011000 and the /23 covers its first seven bits 0001100.
Follow-ups:
- Why does
200.23.18.100not match the /23? Its third octet00010010differs from00011000at bit 21, and a /23 needs 23 bits to agree. It lands on the /20. - When does the default route win? Only when no other prefix matches, because its length is 0.
Show answer
The data plane forwards each packet: look up the destination in the forwarding table, decrement TTL, fix the checksum, queue and send. It must run in nanoseconds per packet, usually in hardware. The control plane builds the table: routing protocols such as OSPF and BGP, static routes and connected networks, working at seconds to minutes in software. The control plane installs the winning routes into the forwarding table, and the data plane only reads it.
Follow-ups:
- What happens to forwarding if the routing daemon crashes? The FIB keeps forwarding with its last routes until they are removed or age out; some platforms add graceful restart to hold routes across a restart.
- Why split them? Per-packet work cannot wait on slow, complex route computation, and route computation should not be slowed by packet load.
Show answer
A switch forwards frames by destination MAC address inside one broadcast domain and does not change the frame. A router forwards packets by destination IP using longest-prefix match, between networks, and rewrites the link-layer header, decrements TTL and recomputes the checksum. A L3 switch is a switch whose hardware can also route at line rate, normally between VLANs, so it behaves as a switch inside a VLAN and as a router between them.
Follow-ups:
- Does a router forward broadcasts? No; routers separate broadcast domains, switches do not.
- Does the IP address change across a router? Not on an ordinary hop; only NAT rewrites it.
Show answer
Administrative distance ranks how much the router trusts a source of routes: lower wins, for example connected 0, static 1, eBGP 20, OSPF 110, RIP 120, iBGP 200 on Cisco defaults. A metric ranks paths within one source, such as OSPF cost. Distance is used to choose between sources that offer the same prefix. Metrics from different protocols are not comparable, which is why the router needs distance first.
Follow-ups:
- Does distance affect which prefix is chosen? No. The longest-prefix lookup happens first; distance only breaks ties for an identical prefix.
- Does Linux have administrative distance? Not in the kernel, which orders same-prefix routes by metric. A routing daemon such as FRR applies distance before installing.
Show answer
A static route is configured by hand and never changes by itself. A dynamic route is learned from a routing protocol and updates when the topology changes. A static route has a low administrative distance (1 by default on Cisco), so for the same prefix it beats an OSPF route (110) even when its gateway is dead. If the static route is more specific, it also shadows the dynamic route through longest-prefix match. A shorter static prefix does not shadow a longer dynamic one.
Follow-ups:
- How would you spot it?
ip route getor the routing table shows the static source, and the dynamic route is listed but not selected (S>*against a plainO). - How do you make a static route a backup? Give it a higher distance than the dynamic protocol (a floating static route).
Show answer
Equal-cost multipath lets a router use several next hops for one prefix at once. To avoid reordering packets inside a TCP connection, the router hashes the flow, usually the addresses and often the ports and protocol, and uses the hash to choose a next hop, so every packet of one flow takes the same path. Different flows spread across the paths.
Follow-ups:
- What is the downside? The hash balances flows, not bytes, so a few large flows can overload one path, and changing the next-hop count can remap flows.
- Which fields are hashed on Linux? Controlled by
fib_multipath_hash_policy, documented in the kernel ip-sysctl page.
Show answer
If the packet is being forwarded, the router must not send it on. It discards it and sends an ICMP time exceeded message (type 11, code 0) to the source, with the original IP header and the first bytes of the payload inside. If the packet is addressed to the router itself, TTL does not matter and the router delivers it locally. This is exactly how traceroute discovers each hop.
Follow-ups:
- Why must the checksum change on every hop? TTL is in the IP header, so changing it changes the header checksum; routers update it incrementally (RFC 1624).
- Why might traceroute show a
*? The router dropped the packet but did not send, or rate-limited, the ICMP reply.
Show answer
A default route is 0.0.0.0/0, the row that matches every address and therefore wins only when nothing longer matches. It is how a host or edge router sends everything unknown to its gateway. It can black-hole traffic when it is missing (no match, so the router drops the packet), when it points at a next hop that is dead or discards traffic (a match, so no error), or when a broad aggregate attracts traffic for addresses nobody can reach.
Follow-ups:
- What does the sender see? Usually a timeout, because the ICMP unreachable is often rate-limited or filtered.
- How do you debug it? Run
ip route getfor the destination on each router in turn and follow the next hop.
Fun facts
- Each packet is a lookup. A minimum-size Ethernet frame takes 84 bytes of wire time (64 plus 8 preamble plus 12 gap), which is 6.72 ns at 100 Gb/s, so one lookup per packet fits in a few nanoseconds.
- A FIFO input queue can use at most 2 minus the square root of 2, about 58.6 percent, of a switch's capacity because of head-of-line blocking (Karol, Hluchyj and Morgan, 1987).
- The router never needs the whole path. It only picks the next hop, and the next router picks its own.
- Hosts have routing tables too, and the default gateway is simply the next hop of their
0.0.0.0/0row.
Cheat sheet
- Different prefixes for the destination: the longest prefix wins.
- Same prefix, different sources: the lowest administrative distance wins.
- Same prefix, same source: the lowest metric wins.
- Still tied: ECMP, by flow hash.