A router input receives traffic for two outputs, X and Y. Output X is always free. Output Y is busy half the time. Measured, traffic to X gets only half its bandwidth, even though nothing ever blocks output X. The packets for X are stuck somewhere they should never be: behind packets for Y.

Why can traffic for a free output be held up, and how do you stop it?

The obvious answer, and why it breaks

The obvious input buffer is one FIFO: packets arrive, wait in order, and leave in order. It is simple and preserves order. But a FIFO can only send its head. When the head packet's output is busy, it cannot leave, and neither can anything behind it, including packets for outputs that are completely free. This is head-of-line (HoL) blocking: the queue's order, not the outputs, decides who waits.

The idea: queue by where packets are going

The fix is to give each destination (or each class of traffic) its own queue at the input, so a packet waits only behind packets going to the same place. In a switch these are virtual output queues (VOQs): one queue per output at each input. In an on-chip network the same idea appears as virtual channels: separate buffers on one physical link, so a blocked packet in one channel does not hold up the others. A packet now blocks only traffic that would have waited for the same output anyway.

Build it: measure the loss

The model sends packets alternately to X and Y, with Y busy for ten cycles out of every twenty, and counts how many X packets get through in 1,000 cycles with one shared FIFO and with a queue per output.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

"""Head-of-line blocking at an input with traffic for two outputs.

An input receives one packet per cycle, alternating between output X and output Y.
Output Y is blocked every other 10 cycles (busy downstream); output X is always free.
  single FIFO: packets leave in arrival order; a Y packet at the head blocks X packets behind it
  per-output queues: X and Y packets wait in separate queues and leave independently
Measure how many X packets get through in 1000 cycles (offered: 500).
"""
from collections import deque


def run(per_output, cycles=1000, depth=8):
    q = {"X": deque(), "Y": deque()} if per_output else deque()
    x_out = 0
    for t in range(cycles):
        dest = "X" if t % 2 == 0 else "Y"
        if per_output:
            if len(q[dest]) < depth:
                q[dest].append(dest)
        elif len(q) < depth:
            q.append(dest)
        y_free = (t // 10) % 2 == 0
        if per_output:
            if q["X"]:
                q["X"].popleft(); x_out += 1
            if q["Y"] and y_free:
                q["Y"].popleft()
        elif q and (q[0] == "X" or y_free):
            if q.popleft() == "X":
                x_out += 1
    return x_out


shared, voq = run(False), run(True)
print(f"X packets delivered (500 offered): single FIFO {shared}, per-output queues {voq}")
assert voq == 500 and shared < voq
print("PASS: in one FIFO a blocked Y packet holds back the X packets behind it")

It prints:

X packets delivered (500 offered): single FIFO 251, per-output queues 500
PASS: in one FIFO a blocked Y packet holds back the X packets behind it

With one FIFO, X gets about half of what it offered, even though output X was never busy: whenever a Y packet reached the head during Y's busy period, everything behind it waited. With a queue per output, X receives all 500. The cost is extra queues and the logic to choose among them.

In a larger switch the loss is a known number: with one FIFO per input and uniformly random traffic, head-of-line blocking limits throughput to about 58.6% of the outputs' capacity, however fast the switch is. Virtual output queues remove that limit.

The design space

Where it appears

• Network switches and routers: input-queued designs use virtual output queues with a scheduler; HoL blocking is the classic reason.

• On-chip networks: virtual channels let packets bypass a blocked one on the same link, and keep traffic classes from blocking each other (Part 9).

• Inside protocols: any single in-order channel carrying independent streams has the same problem; protocols that allow responses out of order (transaction IDs, Part 6) let a slow target stop holding up a fast one.

What breaks

The opening router (illustrative) had one input FIFO per port. Under a mixed workload, traffic to a fast memory controller was throttled by traffic to a slow peripheral queued in front of it, and the fast controller sat idle about half the time. Adding a second virtual channel for peripheral traffic gave the memory traffic a path around the slow packets and restored its bandwidth, at the cost of a second buffer and an arbiter on each port.

Key takeaways

• A queue sends only its head: a blocked head packet holds back everything behind it, even traffic for free outputs.

• One FIFO per input limits a switch to about 58.6% throughput under uniform random traffic.

• Separate queues by destination or class (virtual output queues, virtual channels) remove it, at the cost of buffers and scheduling.

Related topics

• Part 4 overview: Flow Control