Output Port Processing

Queues form at a router’s input ports and its output ports. This is the place packets are actually dropped, and a queue that never empties adds delay without adding any throughput at all.

Words you will meet

Head-of-line blocking — a packet waits although its own output port is free, because the packet in front of it is stuck.
Drop-tail — when the buffer is full, discard the arriving packet.
AQM (Active Queue Management) — dropping or marking packets before the buffer is full, to signal congestion early.
RED (Random Early Detection) — the most widely studied AQM algorithm.
Bufferbloat — a standing queue that adds constant delay while the link runs at exactly its bottleneck rate.
R_switch, R_line — the rate of the switching fabric, and the rate of one line.

Why this matters

Chapters 1 and 3 kept saying packets were “lost within the network” or “dropped at a router”. This section is where that finally becomes concrete: it is here, at these queues inside a router, that packets are actually dropped.

Everything TCP (Transmission Control Protocol) does about loss is a reaction to a buffer somewhere filling up — the timers of section 3.5.4, the three duplicate acknowledgements, the whole saw tooth of section 3.7.1. This is that buffer.

And the section ends somewhere surprising. The obvious way to lose fewer packets is to buy more buffer. The book shows that beyond a point, more buffer makes things worse — not by dropping more, but by making every packet wait.

The short one first. Output port processing takes packets that have been stored in the output port’s memory and transmits them over the outgoing link. Three jobs:

Selecting and de-queueing a packet for transmission — that is scheduling, and section 4.2.5 is entirely about how to choose.
Link-layer processing: encapsulate the datagram in a frame for this link.
Physical-layer transmission: put the bits on the wire.

Read left to right it is the input port of section 4.2.1 reversed, which is exactly what Figure 4.7 shows. The one genuinely new thing is the queue at the front, and that is the rest of this page.

Where the queues form

Queues can form at both input ports and output ports. Which, and how badly, depends on three things: the traffic load, the speed of the switching fabric, and the link rate.

Here is the book’s simplification. There are N input ports and N output ports, all lines running at R_line packets per second, and all packets the same length. Arrivals are synchronised, so in one packet time either zero or one packet arrives on each input link. Call the fabric’s transfer rate R_switch.

The condition that removes input queueing

If R_switch is N times faster than R_line, input queueing is negligible.

The reason is a worst case that still works. Suppose every one of the N input lines receives a packet in the same interval, and all N are destined for the same output port. The fabric can clear all N of them — one from each input port — before the next batch arrives, because it runs N times faster.

So R_switch ≥ N · R_line buys you an input side with essentially no queue. That is a real design rule, and it is why the next subsection is about what happens when you cannot afford it.

Input queueing, and the packet that waits for nothing

If the fabric is not fast enough, packets must queue at the input ports and wait their turn to cross. Now something unpleasant happens.

Take a crossbar, all link rates identical, and each input queue served first-come-first-served. Two packets at the front of two different input queues are destined for the same output port. Only one can cross — a fabric can deliver one packet to a given output port at a time. So the other waits.

But it is not only that packet that waits.

Figure 4.8 — head-of-line blocking at an input-queued switch

time step 0

Both input queues have a packet for out 1 at the head. Step the clock.

Both queues have a packet for out 1 at the head. Step once. Watch the amber packet in the lower queue: its own output port is free, and it still cannot move.

In plain words

The packet behind the blocked one waits too — even though its own output port is completely free.

That is head-of-line blocking . The fabric sits idle on a port that has traffic waiting for it, because the traffic is stuck behind something else in a queue it has no relationship with.

The cause is not the crossbar. The crossbar is non-blocking, as section 4.2.2 said. The cause is that only the packet at the head of a queue is ever a candidate — the scheduler never looks past it. Solutions exist and are surveyed in [McKeown 1997]; nearly all of them amount to letting the scheduler look deeper into the queue.

58 percent

[Karol 1987] showed that head-of-line blocking makes the input queue grow to unbounded length — informally, significant packet loss begins. It happens as soon as the arrival rate on the input links reaches only 58 % of their capacity.

Not 100 %. Not 90 %. Fifty-eight.

A switch built this way throws away more than 40 % of what it cost to build, and the packets it loses are lost while ports sit idle. That number is why router designers work hard to avoid input queueing. It is also why the condition in the box above — make the fabric N times faster than the lines — is worth paying for.

Output queueing, which you cannot design away

Now suppose you did pay for it: R_switch is N times R_line, and the input side is clear. Queues form at the outputs anyway.

Suppose all N input ports receive a packet in the same interval and all N are destined for the same output port. In the time it takes to transmit one packet onto the outgoing link, N packets arrive at that output port. So N − 1 of them queue. In the next packet time, N more can arrive. And so on.

Packet queues can form at the output ports even when the switching fabric is N times faster than the link rate. Eventually the queue grows large enough to exhaust the memory at that output port.

An output queue, with a finite buffer

Arrival rate a900 packets/sBuffer size10 packets

Traffic intensity La/R = (8,000 bits × 900/s) ÷ 10 Mbps = 0.72 — comfortably below 1

Arrived: 0
Sent on: 0
Dropped ✕: 0 (0.0 %)

This is §1.4.2’s queue again, now in the place the book says packets are actually dropped. Push the arrival rate past the service rate and watch the buffer fill, then overflow.

What to do when the buffer is full

Two choices, and then a third that is better than both:

Drop-tail — discard the arriving packet. Simple, and the default.

Drop from the queue — remove one or more already-queued packets to make room for the new arrival. Sometimes the right call: the queued packet may be older and less useful.

Drop or mark before the buffer is full. This sounds perverse — throwing away a packet you had room for — until you remember what a drop means to a TCP sender. It is a congestion signal. Delivering that signal early, while the queue is still short, lets the sender slow down before anything is really lost.

Marking rather than dropping is better still, and section 3.7.2 already built the machinery: the explicit congestion notification bits. The router sets a bit; the receiver echoes it; the sender halves its congestion window. Nothing is lost at all.

These proactive policies are collectively active queue management ( AQM (Active Queue Management) ). The most widely studied and implemented is RED (Random Early Detection) , random early detection [Christiansen 2001]. More recent ones are PIE [RFC 8033] and CoDel [Nichols 2012].

How much buffering is enough?

The book warns that the answer is more complicated than it looks. It also warns that the answer teaches something about how senders at the edge interact with the core. Both warnings are earned.

Two symbols change meaning here. Watch for it.

Everything above this point used N for the number of router ports, and B did not appear at all. From here on:

N means the number of independent TCP flows sharing the link. Nothing to do with ports.
B means the amount of buffering, in bits. Section 4.2.2 used B for the number of packets per second a router’s memory can handle, in the B/2 result — also unrelated.

The book reuses both letters without saying so, and the two meanings of N are barely a page apart. If a formula below looks like it contradicts one above, check which N it means first.

The old rule of thumb [RFC 3439]: buffering should equal a typical round-trip time times the link capacity.

B = RTT × C

For a 10 Gbps link with a 250 ms round trip, that is 2.5 Gbit of buffer. This came from analysing the queueing dynamics of a relatively small number of TCP flows [Villamizar 1994].

The revised rule [Appenzeller 2004]: when a large number N of independent TCP flows pass through the link,

$B = \frac{RTT \cdot C}{\sqrt{N}}$

How much buffering does a port need?

What each symbol means

B — buffering to provide at the port (bits)
RTT — a typical round-trip time (s)
C — link capacity (bits/s)
N — independent TCP flows sharing the link (—)

Read aloud: Enough buffer to hold everything in flight for one round trip — divided by the square root of the number of flows, because they do not all back off at the same moment.

link capacity CGbpsround-trip timemsindependent TCP flows Nflows

buffering needed2.50 Gbit

the old rule of thumb: B = RTT x C
  = 250 ms x 10.0 Gbps = 2.50 Gbit
with N = 1 independent TCP flows: B = RTT x C / sqrt(N)
  = 2.50 Gbit / 1.00 = 2.50 Gbit
with a single flow the two rules agree — sqrt(1) = 1
and every bit of that buffer is delay a packet may have to wait through

Change any number above and the arithmetic re-runs, carrying the units through.

The defaults are the book’s own example: a 10 Gbps link with a 250 ms round trip. Leave N at 1 for the old rule, then raise it to 10,000 for a core router link.

Why the square root

Section 3.7.1 drew one TCP connection as a saw tooth: climb, lose a packet, halve, climb again. A buffer sized for one flow must absorb that whole swing.

Put a thousand independent flows on the link and their saw teeth are not in step. One halves while another is climbing. The sum of a thousand out-of-phase saw teeth is far smoother than a thousand times one of them, so far less buffer is needed to absorb it.

In a core network, where a backbone link carries a great many flows, N is large and the saving is dramatic. Try the calculator with N = 10,000: 2.5 Gbit becomes 25 Mbit.

And notice the assumption the argument rests on — independent. Section 3.7.3 showed connections becoming synchronised when they all lose packets to the same overflow. Synchronised flows behave like one big flow, and the square root does not apply. That is another reason to prefer random early detection over drop-tail.

More buffer is not better. Buffering is like salt.

The tempting thought: bigger buffers absorb bigger bursts, so fewer packets are dropped. True.

The cost: bigger buffers mean longer queueing delays. For gamers and for interactive conferencing, tens of milliseconds matter. Increasing per-hop buffer by a factor of ten to cut the loss rate could increase the end-to-end delay by a factor of ten.

It is worse than a straight trade, because a longer round-trip time also makes TCP senders less responsive — slower to react to congestion that is already beginning. The buffer that was supposed to protect the network makes the network harder to control.

The book’s own line: buffering is a bit like salt — just the right amount makes food better, but too much makes it inedible.

Bufferbloat: a queue that never drains

Everything above assumed many independent senders competing for one congested link. In the core that is a good assumption. At the edge it is not, and the result is strange enough to have its own name.

A home router is sending a gamer’s TCP segments to a remote game server. There is no other traffic on the home network at all.

Figure 4.10(b) — a queue that fills once and never drains

burst of packets at t = 025.0 packetstime to transmit one packet10.0 msround-trip time200 ms

At 500 ms (move the pointer over the plot to read it anywhere):

queue length:5.0
queueing delay (ms):50.0

Figure 4.10(b) is a schematic with no numbers on its axes, and section 4.2.4’s own numbers do not agree with each other — see the note below. This curve is re-derived from the ACK-clocking argument, using the one set of values that reproduces the shape the book draws.

The burst drains until the first acknowledgement returns. After that, one packet arrives for every packet sent, and the queue length freezes. Move the sliders: nothing you do to the link makes the standing queue go away — only a smaller burst does.

Step through what happens

At t = 0, a burst of 25 packets arrives at the home router’s outgoing queue. The link sends one packet at a time, so the queue starts draining.

At t = 200 ms — one round-trip time — the first acknowledgement arrives. By now 20 packets have been sent and 5 remain queued.

And here is the trap. That acknowledgement causes the TCP sender to release another packet, which joins the queue. Twenty milliseconds later the next acknowledgement arrives and another packet is released, as the next queued packet is being transmitted. And so on.

One packet arrives for every packet sent. The queue stops draining. It sits at five packets for ever.

Nothing is wrong. The end-to-end pipe is full, delivering packets to the destination at exactly the path’s bottleneck rate. Throughput is perfect. And every single packet still waits behind four others before it is even transmitted — a constant, persistent queueing delay that no amount of waiting will clear.

The gamer is unhappy. The parent, who even knows Wireshark, is baffled: why are delays long and persistent when nothing else is using the network?

That is bufferbloat , and it is section 3.7.1’s acknowledgement clocking working exactly as designed, against a buffer big enough to hold the whole burst.

Section 4.2.4’s numbers do not agree with each other

Three printed values conflict, and any reader who checks the arithmetic will find it. Recorded here rather than quietly fixed.

Figure 4.10(a) labels the round trip 250 ms. The text says 200 ms.
The text says 20 ms to transmit a packet. But it then says the 21st packet is being transmitted at t = 200 ms — which needs 10 ms per packet, not 20. At 20 ms only the 11th packet would be going out.
The text and figure both say the queue settles at five packets. From a burst of 25 that needs 20 packets sent by t = 200 ms — again 10 ms each. At the printed 20 ms the queue would settle at fifteen.

The one self-consistent set that reproduces Figure 4.10(b) as drawn is 25 packets, 10 ms per packet, 200 ms round trip, and that is what the widget above starts from. Set the transmission time slider to 20 ms and watch the standing queue jump to 15 — the shape survives, the numbers do not.

None of this touches the lesson. Whatever the constants, the queue drains until the first acknowledgement returns and then freezes, because acknowledgement clocking replaces every departure with an arrival. That is the point, and it is true for any burst larger than the bandwidth-delay product.

What is actually done about it

The DOCSIS (Data-Over-Cable Service Interface Specifications) 3.1 standard for cable networks — chapter 6’s subject — recently added a specific AQM (Active Queue Management) mechanism [RFC 8033, RFC 8034] to combat bufferbloat while preserving bulk throughput.

Note what that fix has to achieve. It cannot simply make the buffer smaller, because the buffer is doing useful work for bulk transfers. It has to keep the buffer available for bursts while refusing to let a standing queue build up. That is exactly what CoDel does, by watching how long packets linger rather than how many there are.

The general lesson the book draws: not only is throughput important, minimal delay is important as well [Kleinrock 2018]. The interaction between senders at the edge and queues inside the network is complex and subtle.

Check yourself

0 of 7 answered

1.predictStep the head-of-line widget once. The second packet in the lower queue is destined for out 3, and out 3 is free. Why does it not cross?
2.At what load do an input-queued switch's queues grow without bound, because of head-of-line blocking?
3.The switching fabric runs N times faster than the line rate, so input queueing is negligible. Can queues still form?
4.predictIn the buffer-sizing calculator, raise N from 1 to 10,000 on a 10 Gbps link. Why does the required buffer fall by a factor of 100?
5.predictIn the bufferbloat scenario the queue settles at a constant length and stays there. What is going wrong?
6.Why might a router drop or mark a packet before its buffer is full?
7.Section 4.2.4 says a packet takes 20 ms to transmit, that the 21st packet is transmitting at t = 200 ms, and that the queue settles at five. What should you conclude?

What to remember

This is where packets are dropped. Every “lost in the network” in chapters 1 and 3 means a queue in a router that had no memory left.
Head-of-line blocking: a packet waits although its output port is free, because it is stuck behind one that lost a contest. The crossbar is not at fault — serving each input queue head-first is.
More buffer is not better. It trades loss for delay, and longer delay makes TCP slower to react. Bufferbloat is the end state: acknowledgement clocking freezes a queue at a constant length, throughput is perfect, delay is permanently bad, and nothing is malfunctioning.