A network router forwards IP packets from one network to another. In destination-based forwarding, the output port for a packet depends entirely on the destination IP address. To enable this, routers manage a forwarding table (also known as a forwarding information base).

Because there are a huge number of possible IP addresses, routers typically work with ranges of addresses, as in CIDR. In this convention, and assuming IPv4, a range is denoted a.b.c.d/x where x indicates the number of bits associated with the network. This leaves 32-x bits for hosts. So for example, 0.0.0.0/0 is a range that covers all IP addresses, whereas 192.168.1.0/24 covers just those addresses of the form 192.168.1.*.

Rather than require that the ranges in the forwarding table be disjoint, the convention is that ranges may overlap. Both 0.0.0.0/0 (a ‘default’ route) and 192.168.1.0/24 (a more specific override) could appear in a forwarding table. When resolving the output port for a given IP packet, it’s not enough to find an entry in the forwarding table that matches. Instead, we are interested in the longest prefix match.

It’s useful to distinguish between the “data plane” and “control plane” of a router. The data plane is the part of the router that actually forwards packets. The control plane is the part that manages the forwarding table and coordinates with other routers as part of a routing algorithm.

The data plane has stringent performance requirements and typically involves custom hardware. Here Kurose & Ross suggest considering a simplified picture with three components:

1. An input port receives incoming data. This is where the physical and link (e.g. Ethernet) layers end, and the IP processing begins. Each input port can separately resolve the output port based on a lookup to the forwarding table.
2. After the output port is resolved, a packet is sent through a switching fabric. This is basically a piece of digital logic (e.g. a bus or interconnection network) that physically implements the forwarding.
3. An output port receives packets from the switching fabric and does the necessary link and physical layer operations to send these out.

Each of these components has its own complexities. For example, while “forwarding table lookup” sounds innocent enough, the implementation can be highly nontrivial. This article goes into a few details, noting that forwarding tables in high-end routers can contain millions of entries and may exceed the capacity of on-chip SRAM. Meanwhile, the router’s line rate may require that a longest-prefix match lookup happens in as little as a single clock cycle. Routers may use (seemingly) esoteric elements such as “ternary content-addressable memories” to efficiently implement forwarding calculations.

Another issue is that an output port may not be able to keep up with all of the inbound packets (for example, if they are arriving from multiple inputs simultaneously). Routers typically have memory buffers that can hold a short backlog of packets, smoothing out a burst of activity by making some packets wait around. But ultimately, excess packets are dropped, and packets which are delayed too long may be considered failures by the transport or application layers. Determining the optimal size of these buffers, and an efficient policy for managing them, can be highly nontrivial.

While we won’t go into any further details here, I hope this gives some appreciation for some of what goes into a router. It’s not the sort of knowledge I find myself needing for typical software work, but it is still nice to have some perspective on this essential pillar of networking.