How a router forwards a packet

If longest-prefix match, connected routes and the time-to-live are new to you, start with routing tables on networks.jelia.nyc; and if you have not met Ethernet frames and ARP, read Ethernet there first. This chapter assumes both and goes inside the machine.

Every router, from a home gateway to a chassis the size of a refrigerator, is built around one division of labour. The control plane works out where packets should go. It is software on a general-purpose processor: the routing protocols (OSPF, IS-IS, BGP), the static routes an operator typed in, and the process that merges all of them into one answer per destination. It talks to neighboring routers, it changes its mind when links fail, and it takes milliseconds to seconds to do anything.

The data plane, also called the forwarding plane, moves packets. It does not run protocols or hold opinions. It holds a table the control plane gave it and applies that table to every packet that arrives, at whatever rate the wires deliver them. On a software router the data plane is a tight loop in the operating system kernel; on a large router it is custom silicon on every line card.

A third, quieter layer is the management plane: how people and systems operate the router. Remote shell sessions, configuration pushes, SNMP and streaming telemetry, logs, software upgrades. It shares the control-plane processor on most boxes, but it is useful to name separately because it has different users and different security needs: it should be reachable only from the operator's own network.

The split exists for two reasons. The first is speed. Deciding a route can involve running Dijkstra's algorithm over a whole network or comparing a dozen BGP attributes; doing that per packet would be hopeless. Deciding once, then compiling the decision into a table that a dumb, fast engine can apply, is the only way to keep up with modern links.

The second is failure isolation. Because the forwarding table is a copy, the data plane can keep forwarding on its last good copy while the control plane is busy, overloaded or even restarting. Protocols were later extended to take advantage of this on purpose: BGP's graceful restart mechanism (RFC 4724) lets a router tell its neighbors "my routing process is restarting but my forwarding state is preserved; keep sending me traffic for a while," and OSPF and IS-IS have similar extensions.

A router hears about destinations from several places at once. It knows the subnets on its own interfaces (connected routes). An operator may have typed some in (static routes). An interior protocol like OSPF reports routes inside the organization, and BGP reports routes to the rest of the internet. Each source hands its routes to a central store called the routing information base, the RIB.

The RIB is allowed to be messy. It can hold three different routes to the same prefix from three protocols, routes whose next hop is currently unreachable, and routes whose next hop is not even on a connected network. That last case is normal for BGP: a route learned from a router across the network names that router's loopback address as the next hop, and the router has to look up that address to find out which way to send the packet. This is a recursive next hop.

Out of this mess the control plane compiles the forwarding information base, the FIB. For each prefix it keeps exactly one winner (or a set of equal winners, which Chapter 3 covers along with the rules for choosing), and it resolves every next hop all the way down to something the hardware can act on: an outgoing interface and a directly connected neighbor. The FIB has no protocol names, no metrics and no losers. It is built for one question only, asked at line rate: "for this destination address, which way?"

The last step, from neighbor's IP address to neighbor's hardware address, lives in a third table, the adjacency table, filled by ARP for IPv4 (RFC 826) and Neighbor Discovery for IPv6 (RFC 4861). Keeping it separate matters. Thousands of FIB entries usually share a handful of next hops; when a neighbor's hardware address changes, the router updates one adjacency entry instead of rewriting thousands of routes.

RFC 1812, the 1995 requirements document for IPv4 routers, describes the forwarding algorithm as a list of twelve steps. It also says, wisely, that no implementation has to follow the list literally; it only has to have the same effect. Real routers merge, reorder and parallelise the steps, but every one of them still does these things to every packet.

Receive and validate. The packet arrives from the link layer, and the router checks that the header makes sense: long enough to hold an IP header (20 bytes), version 4, a header-length field of at least 5 words, a total-length field no larger than what actually arrived, and a correct header checksum. A packet that fails any of these is silently discarded. No error message goes back, because the router cannot trust the header enough to know whom to tell.

Options and destination. If the header carries IP options, they are processed now. Then the destination address is examined. If it belongs to the router itself, the packet is not forwarded at all: it is handed up to the router's own software, the control plane, for local delivery. That is how routing protocol messages, pings to the router and management sessions reach it.

Lookup. Otherwise the destination is looked up in the FIB, which answers with an outgoing interface and the next hop's address. If there is no matching route, not even a default, the packet is dropped and the router sends an ICMP Destination Unreachable, code 0 (network unreachable), back to the source. How that lookup can be made fast enough is the whole of Chapter 2.

Time to live. The router lowers the TTL by one. If that takes it to zero, the packet is discarded and an ICMP Time Exceeded message (type 11, code 0) goes back to the source. This is what stops a packet circling forever in a routing loop, and it is also what traceroute uses to discover each hop.

Checksum. Changing the TTL changes the header, so the header checksum must change too. Instead of recomputing it over all twenty bytes, routers patch it using the arithmetic in the next section.

Fit the link. If the packet is larger than the outgoing link's maximum transmission unit (MTU), it either has to be split into fragments or, if the sender set the Don't Fragment (DF) bit, dropped with an ICMP Destination Unreachable, code 4 ("fragmentation needed and DF set"), which since RFC 1191 carries the MTU of the next hop so that the sender can shrink its packets. That conversation is called path MTU discovery.

Rewrite, queue, transmit. Finally the router looks up the next hop's hardware address in the adjacency table, builds a new link-layer header (its own interface's address as the source, the next hop's as the destination) and places the frame on the output queue for that interface. The IP addresses inside are untouched.

The IPv4 header checksum is the one's complement of the one's complement sum of the header's 16-bit words (RFC 791, with the computation explained in RFC 1071). One's complement addition is ordinary addition where any carry out of the top bit is wrapped around and added back in at the bottom. The receiver adds up all the words, checksum included, and a correct header sums to all ones, 0xFFFF.

A router changes exactly one byte of the header, the TTL, which shares a 16-bit word with the protocol number. Rather than adding up all ten words again, it can take the old checksum and adjust it for the one word that changed. RFC 1624 gives the safe form of that adjustment:

A worked example, using the packet in Instrument 2's default setting: a 1,000-byte UDP packet from 192.0.2.10 to 203.0.113.9 with DF set. Its header checksum is 0xFE74. The word holding TTL 64 and protocol 17 (UDP) is 0x4011; after the TTL drops to 63 it is 0x3F11. Then ~HC = 0x018B, ~m = 0xBFEE and m′ = 0x3F11. Their one's complement sum is 0x008B (0x018B + 0xBFEE = 0xC179, plus 0x3F11 = 0x1008A, and the carry wraps around to make 0x008B), and flipping its bits gives HC′ = 0xFF74: the same value a full recomputation of all ten words produces. The pattern is easy to see: m′ is m minus 0x0100, so the checksum goes up by 0x0100. The TTL went down by one in the high byte, and the checksum goes up by one in the high byte. Step the instrument through and it shows both computations side by side.

Why the complicated form instead of the obvious "subtract the old word, add the new one"? One's complement arithmetic has two zeros, 0x0000 and 0xFFFF. RFC 1141, the earlier incremental-update document, used a formula that could produce 0xFFFF where a full recomputation produces 0x0000. A receiver checking the header would still accept it, but the result differed from a full recomputation; RFC 1624 corrected the formula so the two always agree.

The forwarding pipeline is fast because it is simple. Anything that would need judgement, memory or a reply is handed upward to the control-plane processor. Router engineers call this punting, and the route a packet takes to get there the slow path. The processor is a general-purpose CPU that may be orders of magnitude slower than the forwarding hardware beneath it, so on a large router punted packets are the rare exception that must stay rare.

The slow path is also the router's soft spot. If anyone can make the router punt packets, then a large enough stream of them could keep the processor busy answering exceptions while the routing protocols starve, and a router whose protocols time out loses its neighbors and its routes. So the path to the processor is protected, and the protection lives in the data plane where there is capacity to spare. RFC 6192 describes the standard defence: identify the traffic the control plane legitimately needs (routing protocol sessions from known neighbors, management from the operator's own addresses, a modest amount of ICMP), filter everything else that is addressed to the router, and put a rate limit, a policer, on each class that is allowed through. Generating ICMP errors is rate-limited too; RFC 1812 explicitly allows routers to limit how many they send.

The practical consequence for anyone debugging a network: a router that answers ping slowly, or drops some traceroute probes, is often perfectly healthy. Replies to packets addressed to the router are produced on the slow path and deliberately limited, while traffic passing through the router never touches it. Chapter 15 comes back to what that does to traceroute.

A router port runs at line rate when it can forward every packet the wire can deliver, even when all of them are the smallest legal size. That worst case is the one router designers plan for, because the work per packet barely depends on size: a 64-byte packet needs the same checks, lookup and rewrite as a 1,500-byte one.

The smallest Ethernet frame is 64 bytes, counting its header and its 4-byte frame check sequence. On the wire every frame also costs 8 bytes of preamble and start-of-frame delimiter and a minimum gap of 12 byte-times before the next frame, so a minimum frame occupies 84 bytes, or 672 bits, of the link's time.

With full-size 1,500-byte packets the frame is 1,518 bytes and occupies 1,538 on the wire, so the same port carries only about 8.1 million packets a second, one every 123 ns. Real traffic is a mixture, but a router that only coped with big packets could be knocked over by small ones, so specifications quote the small-packet number. RFC 3222 defines terms for benchmarking FIB-based router performance, such as FIB size and how forwarding is measured as the FIB grows.

The budget explains a great deal about how routers are built. A random access to ordinary DRAM costs tens of nanoseconds, several times the whole per-packet budget at 100 Gb/s. A design that needs several memory reads per lookup must therefore either use faster on-chip memory, spread the work over many lookups running in parallel, or both. Try it below.

The pipeline is the same everywhere; where it runs is not. Router hardware has gone through a few broad generations, and all of them are still in use somewhere.

Software router. An ordinary computer with several network interfaces. The kernel does the forwarding: it receives the packet into memory, looks up the destination in its FIB (on Linux, a compressed trie), rewrites the headers and hands the packet to the outgoing driver. It is flexible and cheap, and with batching and kernel-bypass techniques a modern server can forward many millions of packets a second, but every packet still costs CPU cycles and memory bandwidth.

Shared bus. Early dedicated routers put interface cards on a common backplane bus with a central processor and a central FIB. Every packet crossed the bus at least twice, in and out, so the bus capacity was a hard ceiling for the whole box.

Distributed forwarding with a switched fabric. The design used by large routers today. Each line card carries its own ports, its own forwarding engine and its own copy of the FIB, so lookups happen in parallel on every card. Cards are joined by a switch fabric, a crossbar or multistage network that can connect any input card to any output card at the same time as others. The control-plane processor sits on a separate route processor card, computes the RIB, and pushes FIB updates down to every line card.

ASICs and network processors. The forwarding engines themselves are either fixed-function application-specific chips (ASICs), in which parsing, lookup and rewrite are hard-wired pipeline stages, or network processors (NPUs): programmable chips with many cores and specialised memory, slower per watt than an ASIC but able to take new features through software. Many modern switch chips sit in between, with a pipeline whose parsing and match-action stages can be reprogrammed.

An IPv6 router does the same job in the same order, but its designers removed several things that made IPv4 forwarding slow or awkward.

The net effect on the data plane: a fixed 40-byte header, one field to change, no checksum to patch, and no fragmentation work. The price is paid elsewhere. Because routers will not fragment, path MTU discovery has to work, which means the Packet Too Big messages it depends on must not be filtered out. A network that drops all ICMPv6 breaks IPv6 in confusing ways, typically with connections that open fine and then hang when the first large packet is sent.