Packet 7 of a stream arrives corrupted. Packets 8 to 22 arrive intact behind it, before the sender hears about 7. One link throws away 8 to 22 and resends all sixteen, starting from 7. Another link keeps 8 to 22, resends only 7, and slots it into place. The second sounds strictly better. Most high-speed links choose the first.

After an error, resend everything from the bad packet, or only the bad packet?

The obvious answer, and why it breaks

The obvious answer is to resend only what was lost: it wastes no bandwidth. But keeping 8 to 22 means the receiver must buffer packets that arrived early, put them back in order when 7 arrives, and track exactly which ones it has. On a link where errors happen once every few seconds, that machinery is idle almost all the time, and it costs area, latency and verification effort on every link. Whether it is worth it depends entirely on how often errors happen.

The idea: two retransmission strategies

Build it: goodput against error rate

The model sends 20,000 packets with a window of 16 equal to the round trip, at packet error rates from 0 to 10%, and measures goodput (packets delivered per cycle) for both strategies.

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
51
52

"""Goodput of go-back-N and selective repeat as the packet error rate grows.

One packet per cycle; an acknowledgement (or NAK) for a packet sent in cycle t
reaches the sender in cycle t + RTT. The window covers the round trip, so with no
errors both send at full rate. Each packet is corrupted independently with
probability p (corrupted packets are discarded by the receiver, which NAKs).
  go-back-N:        on a NAK, resend the bad packet and every packet after it
  selective repeat: resend only the bad packet; the receiver buffers the others
Goodput = packets delivered in order per cycle.
"""
import random

RTT, W, PACKETS = 16, 16, 20000


def gbn(p, rng):
    t, base, sent_at = 0, 0, {}
    while base < PACKETS:
        # send the window base .. base+W-1, one per cycle
        bad = None
        for k in range(base, min(base + W, PACKETS)):
            if rng.random() < p and bad is None:
                bad = k
            t += 1
        if bad is None:
            base = min(base + W, PACKETS)
        else:
            base = bad                        # everything from the bad one is resent
    return PACKETS / t


def sr(p, rng):
    t, delivered = 0, 0
    pending = list(range(PACKETS))            # packets still to get through
    while pending:
        retry = []
        for k in pending:
            t += 1
            if rng.random() < p:
                retry.append(k)               # only this one is resent
        pending = retry
    return PACKETS / t


ps = [0.0, 0.001, 0.01, 0.03, 0.1]
g = [gbn(p, random.Random(2)) for p in ps]
s = [sr(p, random.Random(2)) for p in ps]
print("packet error rate: " + " ".join(f"{p:6.3f}" for p in ps))
print("go-back-N goodput: " + " ".join(f"{x:6.3f}" for x in g))
print("selective repeat:  " + " ".join(f"{x:6.3f}" for x in s))
assert g[0] == s[0] == 1.0 and all(a <= b + 1e-9 for a, b in zip(g, s)) and g[-1] < 0.5 < s[-1]
print("PASS: at low error rates both are nearly free; as errors grow, go-back-N wastes a window per error")

It prints:

packet error rate:  0.000  0.001  0.010  0.030  0.100
go-back-N goodput:  1.000  0.990  0.920  0.771  0.459
selective repeat:   1.000  0.999  0.990  0.969  0.901
PASS: at low error rates both are nearly free; as errors grow, go-back-N wastes a window per error

At a packet error rate of 0.1%, go-back-N loses 1% of goodput; real links with a BER of 1e-12 see packet error rates around 1e-9 (lesson 10.18), where the difference is invisible. Only at error rates of a few percent does selective repeat's buffering pay for itself.

How real protocols chose

What breaks

A team (illustrative) implemented selective repeat on a chip-to-chip link with a BER around 1e-13 because "it is more efficient". The receiver's reorder buffer and its corner cases (wrap-around, duplicates arriving during a replay) took months to verify, and on silicon it was exercised once every few minutes. Go-back-N would have cost a negligible fraction of bandwidth and a fraction of the effort.

Key takeaways

• Go-back-N resends everything from the bad packet; selective repeat resends only the bad one.

• Go-back-N wastes about a window per error but keeps the receiver simple and in order.

• At the low error rates of hardware links, go-back-N's cost is negligible; selective repeat pays only when errors are frequent.

Related topics

• Part 10 overview: Reliability and Recovery