A 16-port switch is built with one FIFO at each input. Under full load, with packets going to random outputs, it delivers only about 60% of its capacity, however fast its crossbar and links are. Making the links faster does not help, and neither does making the FIFOs deeper. The limit is structural: it comes from the order in which each input is allowed to send.

How do switches get past head-of-line blocking, and what does the fix cost?

The obvious answer, and why it breaks

Lesson 4.14 showed the problem: an input FIFO can only offer its head packet, and when two inputs' heads want the same output, one waits, and so does everything behind it, even packets for idle outputs. The obvious fixes, deeper FIFOs or faster links, leave the structure unchanged. A deeper FIFO holds more blocked packets; it does not unblock them.

The idea: a queue per output, and a scheduler

• At each input, keep a separate queue for every output: virtual output queues (VOQs). A packet waits only behind packets going to the same output.

• Every cycle, each input can offer a packet to any output it has packets for. Choosing which inputs send to which outputs is a matching problem: each input sends at most one packet and each output receives at most one.

• A scheduler computes a good matching every cycle. Good schedulers, such as iSLIP, use rotating priority pointers so that, under heavy load, inputs settle into a pattern where every output is matched every cycle.

Build it: FIFO inputs against VOQs

The model runs a 16-port switch at full load: every input always has packets waiting. With one FIFO per input, each head packet has a random output and losers keep their head. With VOQs, every input has packets for every output, and iSLIP (one iteration) picks the matching with rotating grant and accept pointers.

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
38
39
40
41
42
43
44
45
46
47
48
49
50

"""Throughput of a 16-port switch under full load: one FIFO per input vs VOQs.

Full load: every input always has packets waiting, for every output.
  FIFO: each input can offer only its head packet, whose output is random; an
        output picks one of the inputs whose head wants it; losers keep their
        head (head-of-line blocking).
  VOQ:  each input keeps a queue per output (all non-empty at full load); a
        scheduler (iSLIP, one iteration) matches inputs to outputs each cycle
        with rotating priority pointers.
Throughput = packets delivered per output per cycle.
"""
import random

N, CYCLES = 16, 4000


def fifo():
    random.seed(11)
    head = [random.randrange(N) for _ in range(N)]
    sent = 0
    for _ in range(CYCLES):
        want = {}
        for i, o in enumerate(head):
            want.setdefault(o, []).append(i)
        for o, inputs in want.items():
            winner = random.choice(inputs)
            head[winner] = random.randrange(N)     # next packet moves to the head
            sent += 1
    return sent / (N * CYCLES)


def voq_islip():
    grant_ptr, accept_ptr, sent = [0] * N, [0] * N, 0
    for _ in range(CYCLES):
        grants = {}                                  # input -> outputs that granted it
        for o in range(N):                           # every input requests every output
            i = grant_ptr[o]                         # grant the input at the pointer
            grants.setdefault(i, []).append(o)
        for i, outs in grants.items():
            o = min(outs, key=lambda x: (x - accept_ptr[i]) % N)
            sent += 1
            grant_ptr[o] = (i + 1) % N               # pointers move only on acceptance
            accept_ptr[i] = (o + 1) % N
    return sent / (N * CYCLES)


f, v = fifo(), voq_islip()
print(f"{N}-port switch, full load: one FIFO per input {f:.3f}, VOQ + iSLIP {v:.3f}")
assert 0.55 < f < 0.65 and v > 0.95
print("PASS: head-of-line blocking caps the FIFO switch near 60%; VOQs with a good scheduler approach 100%")

It prints:

16-port switch, full load: one FIFO per input 0.599, VOQ + iSLIP 0.998
PASS: head-of-line blocking caps the FIFO switch near 60%; VOQs with a good scheduler approach 100%

The FIFO switch delivers about 60% of capacity, close to the 58.6% known for large switches with random traffic. The VOQ switch delivers almost all of it: once the pointers have moved apart, every output is matched to a different input every cycle. The crossbar and links are identical in both runs. Only the queue structure and the scheduler changed.

What VOQs cost

The alternatives

What breaks

A switch design (illustrative) added VOQs but kept a simple scheduler that always started its search at input 0. Under full load the low-numbered inputs won almost every time, the high-numbered ones starved, and total throughput stayed near 70%. VOQs remove the structural limit; the scheduler decides how much of the gain you keep, and whether it is shared fairly.

Key takeaways

• One FIFO per input caps a switch near 60% under random traffic, whatever the buffering or link speed.

• Virtual output queues let any waiting packet be scheduled; a good scheduler then approaches 100%.

• The costs are N queues per input and a fast, fair scheduler; output queuing needs fabric speedup instead.

Related topics

• Part 6 overview: Concurrency and Performance