Router switching and queueing
This is an optional deep dive. Inside a router has the overview and QoS and traffic shaping has the commands. This page explains the reasoning behind both: why routers are built the way they are, and where their queues come from.
The time budget
Section titled “The time budget”A router has a fixed time to handle each packet before the next one arrives.
| Link | Packet | Time per packet |
|---|---|---|
| 10 Gbit/s | 1,500 bytes | 1.2 microseconds |
| 100 Gbit/s | 1,500 bytes | 120 nanoseconds |
| 100 Gbit/s | 64 bytes | 5.12 nanoseconds |
On Ethernet each frame also carries a preamble and an inter-frame gap, so a minimum frame takes 84 bytes of wire time. At 10 Gbit/s that is 14.88 million packets per second, and at 100 Gbit/s it is 148.8 million. These are the numbers to compare against any software forwarding path. A general-purpose CPU running the full Linux network stack handles a few million packets per second per core. That gap is why hardware routers use dedicated lookup memory (TCAM) and switching ASICs, and why software routers on commodity servers use kernel-bypass frameworks such as DPDK or XDP.
Switching fabrics
Section titled “Switching fabrics”The fabric moves a packet from an input port to the output port that the lookup chose. Three designs trade complexity against speed.
Through memory. The first routers were ordinary computers. A packet arrived, interrupted the CPU, was copied into memory, looked up, and copied out to the output port. Every packet crosses memory twice (one write, one read), so forwarding is capped at less than half the memory bandwidth, and only one packet moves at a time. Modern shared-memory routers move the lookup and storage onto the line cards, but the principle is the same. Software routers and virtual routers still forward this way.
Through a bus. The input port tags the packet with its output port, and puts it on a shared bus. Every output port sees it, and only the tagged one keeps it. Only one packet can be on the bus at once, so total speed is limited by the bus. This suits small and mid-size switches.
Through an interconnection network. A crossbar is a grid of N input buses and N output buses with a switchable crosspoint at each intersection (N x N crosspoints). A controller closes the crosspoint that links an input to its output. Packets between different input and output pairs cross in parallel. The limit is that two packets for the same output must take turns.
Larger routers chain several stages of small switching elements, so packets from different inputs can reach the same output by different internal paths. The top end runs several fabrics in parallel and sprays each packet across them in chunks, which the output port reassembles. A leaf-spine data center network is the same idea at network scale: a multistage fabric built from identical small switches.
Where queues form
Section titled “Where queues form”A queue forms wherever packets arrive faster than they can leave. In a router, that can happen at the input or the output.
Input queues and head-of-line blocking
Section titled “Input queues and head-of-line blocking”Let R_line be the port speed and R_switch the fabric speed. If R_switch is at least N x R_line for N ports, the fabric can clear a full set of arrivals before the next set comes, and input queues stay empty. A slower fabric builds queues at the inputs.
Take a crossbar where each input has one first-in, first-out (FIFO) queue:
| Input | Queue, front first |
|---|---|
| 1 | packet for output 3, packet for output 2 |
| 2 | packet for output 3 |
| 3 | packet for output 1 |
Inputs 1 and 2 both want output 3. Only one wins. Say input 1 wins. Input 2 waits. Meanwhile, output 2 is idle, but the packet for it is stuck behind input 1’s head packet in the same queue. That is head-of-line blocking: a waiting packet holds up others behind it even though their output is free. With simple FIFO inputs and uniform random traffic, the queues grow without bound and packets are lost once the load reaches about 58% of line rate.
The standard fix is virtual output queues: each input keeps a separate queue per output, so a blocked packet does not hold up the rest. A scheduler then matches inputs to outputs each cycle.
Output queues
Section titled “Output queues”Even with a fast fabric, N inputs can all send to the same output at once. The output link carries one packet per interval, so N - 1 packets have to wait in the output buffer. This is the normal queue in a router, and it is where the scheduler and the drop policy operate.
When the buffer is full, a drop-tail policy discards new arrivals. Active queue management starts dropping or marking earlier. Both are covered in QoS and traffic shaping.
How big should a buffer be?
Section titled “How big should a buffer be?”The classic rule says B = RTT x C, the bandwidth-delay product. Here is where it comes from.
A single TCP flow fills the link, then loses a packet when the buffer overflows, and halves its window. Before the loss the window holds the pipe plus the buffer, which is BDP + B. After halving it holds (BDP + B) / 2. If the link is to stay busy through the recovery, that must still be at least BDP:
(BDP + B) / 2 >= BDP => B >= BDPFor a 10 Gbit/s link and a 250 ms RTT, BDP is 2.5 Gbit, about 312 MB of memory per port.
That rule assumes one flow. A backbone link carries thousands of flows, and their sawtooth patterns are not synchronized. When one flow halves, others grow. The total fluctuates far less than any single flow, relative to its size, by a factor of about sqrt(N):
B = (RTT x C) / sqrt(N)With 10,000 flows, 2.5 Gbit shrinks to 25 Mbit, about 3 MB.
More buffer is not simply safer. A full buffer of size B adds B / C of delay to every packet. When B = RTT x C, that is one extra RTT. Persistent queues of that depth are what bufferbloat means. An edge link with a few flows gets the cost of large buffers and none of the statistical benefit.
Scheduler arithmetic
Section titled “Scheduler arithmetic”When several packets wait at an output port, the scheduler picks the next one.
Priority queuing always serves the highest non-empty class. It is non-preemptive: a packet that has started transmission finishes first. On a slow link that matters. A 1,500-byte packet on a 10 Mbit/s link takes 1.2 ms to send, so a voice packet that arrives just after it starts can wait up to 1.2 ms even in the top-priority class. That is why voice on slow links uses small packets. Strict priority also starves low classes if high-priority traffic never pauses.
Round robin takes one packet from each class in turn and skips empty classes at once. The link never idles while a packet waits (it is work-conserving). It shares packets equally, not bytes, so a class with large packets gets more bandwidth.
Weighted fair queuing gives class i weight w_i and guarantees it this share while all classes have traffic:
share_i = R x w_i / (w_1 + w_2 + ... + w_n)On a 100 Mbit/s link:
| Class | Weight | Share when all are busy | Share if class C is idle |
|---|---|---|---|
| A | 5 | 50 Mbit/s | 62.5 Mbit/s (5/8) |
| B | 3 | 30 Mbit/s | 37.5 Mbit/s (3/8) |
| C | 2 | 20 Mbit/s | 0 |
The idle class’s share is divided in proportion to the remaining weights. Nothing is wasted. The guarantee is a floor, not a cap.
# Per-class bytes, packets, drops, and backlogtc -s class show dev eth0
# Look for a standing backlog that does not draintc -s qdisc show dev eth0