A receiver with a 32-word buffer sends "stop" to its sender when the buffer is full. In the lab, the buffer overflows anyway, by several words, every time traffic is heavy. The stop message works: the sender does stop. It just stops too late.

When should a receiver say stop, so that everything already on its way still fits?

The obvious answer, and why it breaks

The obvious answer is to say stop when the buffer is full. But "stop" takes time to reach the sender, and during that time the sender keeps sending. Then the words that were already on the wire when the sender stopped keep arriving. All of those land in a buffer that was already full. The stop signal must be sent early, with room left for everything still coming.

The idea: stop early, by one round trip

In on/off (also called XON/XOFF, or PAUSE) flow control, the receiver sends "stop" when its fill level reaches a threshold, and "go" when it has drained to a lower threshold. The room above the stop threshold must hold everything that arrives after the decision:

With a one-way delay of D cycles in each direction, the stop message takes D cycles to reach the sender and the words already on the wire take another D to arrive: a full round trip of words at the sender's rate. The go threshold is set lower than the stop threshold, called hysteresis, so the link does not flip between stop and go on every word.

Build it: find the safe threshold

The model has a sender at one word per cycle, a receiver draining one word every other cycle into a 32-word buffer, and a one-way delay of 8 cycles. It tries five stop thresholds (with go at half of each) and reports the peak fill.

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

"""On/off (XON/XOFF) flow control and where to put the threshold.

The sender sends one word per cycle unless stopped. The receiver drains one word every
other cycle into a buffer of B = 32 words. When the buffer reaches the XOFF threshold,
the receiver sends "stop"; it takes D = 8 cycles to reach the sender, and words already
on the wire keep arriving for another D cycles. "Go" is sent when the buffer falls to
the XON threshold. Find which XOFF thresholds overflow the buffer.
"""
from collections import deque

B, D = 32, 8


def run(xoff, xon, cycles=3000):
    buf, peak, overflow = 0, 0, False
    stopped_at_sender = False
    wire = deque([0] * D)              # words on their way to the receiver
    ctrl = deque([None] * D)           # stop/go messages on their way to the sender
    sent_stop = False
    for t in range(cycles):
        msg = ctrl.popleft()
        if msg is not None:
            stopped_at_sender = msg == "stop"
        send = 0 if stopped_at_sender else 1
        wire.append(send)
        buf += wire.popleft()
        if t % 2 == 0 and buf > 0:     # receiver drains one word every other cycle
            buf -= 1
        if buf > B:
            overflow = True
        peak = max(peak, buf)
        if not sent_stop and buf >= xoff:
            ctrl.append("stop"); sent_stop = True
        elif sent_stop and buf <= xon:
            ctrl.append("go"); sent_stop = False
        else:
            ctrl.append(None)
    return peak, overflow


print("XOFF threshold  peak fill (buffer 32)  overflow?")
results = {}
for xoff in (8, 16, 20, 24, 28):
    peak, ovf = run(xoff, xon=xoff // 2)
    results[xoff] = ovf
    print(f"{xoff:14d}  {peak:20d}  {'yes' if ovf else 'no'}")
# Words still arriving after XOFF is sent: about D cycles for the message to arrive plus
# D cycles of words already in flight, minus what the receiver drains meanwhile.
assert not results[16] and results[28]
print("PASS: the threshold must leave room for a round trip of words; XOFF at 28 overflows")

It prints:

XOFF threshold  peak fill (buffer 32)  overflow?
             8                    15  no
            16                    23  no
            20                    27  no
            24                    31  no
            28                    35  yes
PASS: the threshold must leave room for a round trip of words; XOFF at 28 overflows

In every case the peak is 7 words above the threshold: 16 cycles of round trip at one word per cycle, minus the 8 or so words the receiver drained in that time, minus one for when the threshold is noticed. A threshold of 24 leaves exactly enough room in a 32-word buffer; 28 overflows by 3. So the receiver's stop threshold is not "full" but "full minus a round trip of net arrivals".

The design space

Compared with credits, on/off wastes buffer: the room above the threshold is reserved for the worst case even when traffic is light. Its advantage is simplicity: the sender only obeys two messages.

How real protocols chose

Ethernet's priority flow control is the same idea extended to traffic classes, the problem credits solve with separate credit pools (lesson 4.6).

What breaks

The opening overflow, as debug steps (illustrative):

• Symptom: buffer overflow under heavy traffic, always by a few words, despite a working stop signal.

• Evidence: the stop was sent when the buffer was full; the overflow equals the words that arrived during the round trip after it.

• Root cause: threshold at full, not at full minus a round trip of net arrivals.

• Fix: move the stop threshold down by the round trip times the rate (minus what drains), and set the go threshold lower still to avoid oscillation. Recompute whenever the path's latency changes.

Key takeaways

• On/off flow control stops the sender when the receiver's fill reaches a threshold, and restarts it at a lower one.

• The stop threshold must leave room for a round trip of net arrivals: the stop's delay plus the words already in flight.

• It is simple but leaves buffer idle; thresholds must be re-derived whenever the path latency changes.

Related topics

• Part 4 overview: Flow Control