Computer Networking › Section D · The network layer: data plane › Topic D.2
Inside a router
A core router may move hundreds of millions of packets a second, and most packets lost on the internet are dropped inside one. Looking at its parts explains where queues form, why packets are lost and who gets served first.
Four parts of a router
Every router has four main components. Input ports terminate incoming links, do link-layer processing and look up each datagram's output port. The switching fabric, a network inside the box, carries datagrams from input ports to output ports. Output ports queue datagrams and transmit them onto outgoing links. The routing processor, an ordinary CPU, runs the control plane: routing protocols, management, or in SDN the conversation with the remote controller. The first three form the data plane and are built in hardware; the routing processor works in software on millisecond timescales. Note that a router's physical ports are interfaces, not the port numbers of TCP and UDP.
Input ports and destination-based lookup
When a datagram arrives, the input port reads its destination address and searches the forwarding table, a copy of which each line card keeps so it need not ask the routing processor. The table does not list every address, which would mean over 4 billion rows; it lists address prefixes. A destination may match several prefixes, and the router applies longest-prefix matching: the entry whose prefix shares the most leading bits with the destination wins. The lookup must finish before the next datagram arrives, so line cards use fast memories, notably ternary content-addressable memory (TCAM), which compares an address against every entry at once.
Worked example: longest-prefix match
A router has four entries: 10.32.0.0/11 to interface 0, 10.40.0.0/13 to interface 1, 10.40.128.0/17 to interface 2, and the default 0.0.0.0/0 to interface 3. Where do four datagrams go? 1. 10.40.200.9 matches the /11, the /13 and the /17 (the /17 covers 10.40.128.0 to 10.40.255.255), so the longest, /17, wins: interface 2. 2. 10.44.1.1 lies in the /13 range, 10.40.0.0 to 10.47.255.255, but not the /17: interface 1. 3. 10.60.0.1 matches only the /11, which spans 10.32.0.0 to 10.63.255.255: interface 0. 4. 10.70.0.1 matches only the default: interface 3. Check: the default matches everything but always loses to anything longer.
Three ways to switch
Switching via memory was the first design: the CPU copies each datagram into memory and then out to the output port. Every datagram is written once and read once, so if memory handles B datagrams per second, throughput stays below B/2, and only one datagram moves at a time. Switching via a bus lets an input port send a datagram, tagged with its output port, straight across a shared bus; all outputs see it but only the tagged one keeps it. Speed is capped by the bus, since one datagram crosses at a time. A crossbar uses a grid of 2N buses joining N inputs to N outputs, so datagrams bound for different outputs cross in parallel.
Input queues and head-of-line blocking
If the fabric cannot clear arrivals as fast as they come, queues build at the input ports. Two datagrams at the front of different input queues may want the same output port; the crossbar sends one and the other waits. Worse, a datagram queued behind the waiting one must also wait, even if its own output port is free. This is head-of-line (HOL) blocking. A classic 1987 analysis showed that with first-in-first-out input queues and random destinations, it limits a large switch to about 59% of its capacity. Modern routers avoid it with virtual output queues: each input keeps a separate queue for each output port.
Output queues, drops and AQM
Even a fabric N times faster than the links cannot prevent output queues: if datagrams from all N inputs head for one output, N arrive in the time it takes to send one. When the buffer fills, the simplest policy, drop-tail, discards arriving datagrams. Active queue management (AQM) acts earlier, dropping or marking a few datagrams with Explicit Congestion Notification before the buffer is full, so TCP senders slow down in time. Random Early Detection (RED) is the classic AQM; CoDel and PIE are newer ones that target queueing delay. This is where the packet loss studied in the topic Delay, loss, and throughput actually happens.
How much buffer is enough?
An old rule of thumb sized a buffer at the round-trip time times the link capacity, \(B = \text{RTT} \times C\). For a 100 Gbps link and a 100 ms RTT that is \(10^{11} \times 0.1 = 10^{10}\) bits, or 1.25 gigabytes. Research from 2004 found that when N independent TCP flows share the link, about \(\frac{\text{RTT} \times C}{\sqrt{N}}\) is enough: with 10,000 flows, one hundredth as much, 100 megabits or 12.5 megabytes. Bigger is not better. Oversized buffers that stay full add delay without adding throughput, a problem called bufferbloat that is common in home routers and hurts gaming and video calls.
Packet scheduling
When several datagrams wait at an output port, a scheduler picks the next one. First-in-first-out (FIFO) sends them in arrival order. Priority scheduling sorts datagrams into classes and always serves the highest non-empty class first, so voice can jump ahead of bulk downloads; a datagram already being sent is not interrupted. Round robin cycles through the classes, sending one datagram from each in turn, and never leaves the link idle while any class has traffic waiting. Weighted fair queueing (WFQ) generalises round robin: class i with weight \(w_i\) receives at least the fraction \(\frac{w_i}{\sum_j w_j}\) of the link rate.
Worked example: weighted fair queueing
A 100 Mbps output link serves three classes with WFQ weights 5 (video), 3 (web) and 2 (backup). 1. The weights sum to 10. 2. When all three are busy, video gets at least \(\frac{5}{10} \times 100 = 50\) Mbps, web 30 Mbps and backup 20 Mbps. 3. Later the backup class goes idle. WFQ divides the link among the busy classes only, whose weights now sum to 8. 4. Video now gets \(\frac{5}{8} \times 100 = 62.5\) Mbps and web 37.5 Mbps. Check: in both cases the shares add up to 100 Mbps, so the link never sits idle while traffic waits, and every class keeps its guaranteed minimum.
Common mistakes to avoid
First, thinking the routing processor handles each datagram; in modern routers line cards look up and switch packets in hardware. Second, choosing the first matching entry, or the default route, when a longer prefix also matches. Third, assuming a fast fabric removes all queues; output queues still form when many inputs target one output. Fourth, assuming bigger buffers are always better, which ignores bufferbloat. Fifth, believing priority scheduling interrupts a datagram already being transmitted. Sixth, reading WFQ weights as fixed rates: an idle class's share is spread among the busy ones.
Key takeaways
A router has input ports, a switching fabric, output ports and a routing processor; the first three run the data plane in hardware. Input ports look up each destination by longest-prefix match, often in TCAM. Fabrics switch via memory (below B/2), a bus (one datagram at a time) or a crossbar (parallel for different outputs). Input queues suffer head-of-line blocking; output queues form when many inputs share one output, and drop-tail or AQM decides what is lost. Buffers near \(\text{RTT} \times C / \sqrt{N}\) suffice for many flows. Schedulers include FIFO, priority, round robin and weighted fair queueing.
Flashcards
Flashcard
Input ports, switching fabric, output ports, routing processor
Test your understanding
Question 1 of 5
A forwarding table holds 172.16.0.0/12 to interface 1, 172.20.0.0/14 to interface 2 and 0.0.0.0/0 to interface 3. Which interface does a datagram for 172.21.5.5 use?
Question 2 of 5
A router switches via memory, and its memory can handle 20 million datagram reads or writes per second. What is the most it can forward?
Question 3 of 5
A datagram for a free output port waits because the datagram ahead of it in the same input queue is blocked. What is this called?
Question 4 of 5
An 80 Mbps link uses WFQ with weights 4, 3 and 1. If the weight-3 class is idle, what rate does the weight-4 class get?
Question 5 of 5
Why does a home router with a very large, persistently full buffer make online games feel laggy?
