Reliable delivery: Go-Back-N and Selective Repeat

Packets get lost, damaged (and thrown away by the checksum) or delayed. To deliver everything anyway, a sender needs three tools:

• sequence numbers, so the receiver knows what it has and spots duplicates;
• acknowledgements (ACKs), so the sender knows what arrived;
• a timeout: no ACK in time means "send it again".

Stop-and-wait is safe but slow

The simplest protocol sends one packet and waits for its ACK. It works, but the link sits idle for a whole round trip after every packet:

packet_bits = 8000              # a 1000-byte packet
rate = 1_000_000_000            # 1 Gbps
rtt = 0.030                     # 30 ms round trip

send_time = packet_bits / rate
busy = send_time / (rtt + send_time)
print("stop-and-wait uses", round(100 * busy, 3), "% of the link")
for window in [10, 100, 1000]:
    print("window", window, "uses", round(min(1, window * busy) * 100, 2), "%")

On a fast, long link, stop-and-wait uses a tiny fraction of the capacity. The cure is pipelining: keep up to N packets "in flight" before any ACK returns. N is the window, and it slides forward as ACKs arrive.

Go-Back-N

The receiver accepts packets only in order and sends cumulative ACKs: "ACK 5" means "everything up to 5 arrived". An out-of-order packet is thrown away. When the oldest packet times out, the sender goes back and resends it and every packet after it.

Selective Repeat

The receiver keeps out-of-order packets in a buffer and ACKs each one separately. Each packet has its own timer, and only the packets actually lost are sent again. It uses the link better, at the cost of buffer memory and more bookkeeping. Its window must be at most half the range of sequence numbers, or an old duplicate could be mistaken for a new packet.

Choose a protocol, lose a packet or an ACK, and step through:

Lose packet 2 with Go-Back-N and 10 transmissions are needed; with Selective Repeat, 9. Now lose ACK 1 instead: Go-Back-N needs no resend at all, because ACK 2 confirms packet 1 too.

packets, window = 6, 3
lost = {2}                          # packet 2 is lost the first time
base, sent = 0, 0

while base < packets:
    batch = list(range(base, min(base + window, packets)))
    sent += len(batch)
    first_lost = None
    for p in batch:
        if p in lost:
            lost.discard(p)
            if first_lost is None:
                first_lost = p
    print("send", batch, "-> lost:", first_lost)
    base = batch[-1] + 1 if first_lost is None else first_lost
print("transmissions:", sent, "for", packets, "packets")

TCP mixes the two ideas: cumulative ACKs like Go-Back-N, but receivers keep out-of-order data, and the sender usually resends only the missing segment. Three duplicate ACKs for the same byte trigger a fast retransmit without waiting for the timeout.

Mark lesson complete