The idea: resend what got lost
A link can lose packets. ARQ (automatic repeat request) makes it reliable with three tools: a sequence number on every packet, an ACK from the receiver for what arrived, and a timer at the sender that resends a packet whose ACK does not come back in time. The three classic protocols differ only in how many packets may be unacknowledged at once (the window) and in what the receiver does with a packet that arrives out of order.
The page sends the same 8 packets through all three at once. One tick is the one-way delay, so a round trip is 2 ticks, and a timer fires 4 ticks after its packet was sent. The network drops the first copy of the packet or ACK you choose, the same in every lane. Sending time is left out: a sender may put a whole window on the wire in one tick.
Stop-and-wait
Send one packet, start a timer, wait for its ACK, then send the next. If the timer fires first, send the same packet again. One bit of sequence number is enough (0, 1, 0, 1 …, the alternating-bit protocol): when an ACK is lost and the packet comes again, the receiver sees the bit it already has, throws the copy away and ACKs again (Demo: lose ACK 1).
It is simple and slow. Only one packet is ever in flight, so the link is busy for one packet time per round trip. With a packet time L/R and round trip RTT, the utilisation is (L/R) / (RTT + L/R). For a 1500-byte packet on 1 Gbit/s with a 30 ms round trip that is 12 µs / 30 ms ≈ 0.04 %.
Go-Back-N
The sender may have up to N packets unacknowledged: the window runs from base (the oldest unacked packet) to base + N − 1. ACKs are cumulative: ACK n means "I have everything up to n". The receiver keeps no buffer: it accepts only the next packet in order, throws away anything else and repeats the ACK of the last in-order packet. There is one timer, for the oldest unacked packet; when it fires, the sender goes back and resends every packet in the window.
- Demo: lose packet 2. Packets 3, 4 and 5 arrive but are thrown away. At t = 4 the timer of packet 2 fires and Go-Back-N sends 2, 3, 4 and 5 again: 12 packets for 8.
- Demo: lose ACK 1. Nothing happens: ACK 2 arrives and covers packet 1 too. Go-Back-N finishes in 4 ticks, as if nothing was lost.
Selective Repeat
The sender's window is the same, but every packet has its own ACK and its own timer, and only a packet whose timer fires is sent again. The receiver has a window of N too: it buffers packets that arrive out of order and hands them to the application once the gap is filled.
In Demo: lose packet 2 it sends 9 packets for 8 and buffers up to 3. Both window protocols finish at t = 8 here, because both wait for the same timer; the difference is the 3 extra packets Go-Back-N puts on a link that is already losing them. The price is the opposite case: in Demo: lose ACK 1 nothing covers the lost ACK, so the timer of packet 1 fires, packet 1 is sent again, and the window cannot slide past 1 until its ACK returns: 8 ticks instead of 4.
Sequence numbers wrap
A header has room for k bits, so sequence numbers count 0 … 2k − 1 and start again. The receiver must never mistake an old copy for a new packet with the same number. That limits the window:
- Go-Back-N:
N ≤ 2k − 1. The receiver expects exactly one number, and with N below the number space an old copy never carries it. - Selective Repeat:
N ≤ 2k−1, half the space. The receiver accepts a whole window of numbers, and after it has moved on, the sender may still resend the old window (its ACKs were lost). The two windows must not share a number.
Demo: sequence numbers wrap uses 2 bits (0–3), N = 3 and loses every ACK of the first window. Go-Back-N (3 ≤ 3) throws the old copies away and finishes. Selective Repeat (3 > 2) takes old packet 0 for new packet 4: wrong data, so its lane stops with ✗. Stop-and-wait, with its 1 bit and window 1, is fine.
Which one?
| Stop-and-wait | Go-Back-N | Selective Repeat | |
|---|---|---|---|
| packets in flight | 1 | N | N |
| ACK | per packet | cumulative | per packet |
| timers | 1 | 1 (oldest packet) | 1 per packet |
| receiver buffer | none | none | N packets |
| after one loss resends | 1 packet | the whole window | 1 packet |
| a lost ACK | timeout, resend | covered by the next ACK | timeout, resend |
| window limit, k bits | 1 (1 bit is enough) | 2k − 1 | 2k−1 |
| good for | short links, tiny devices (Bluetooth LE, simple serial links) | links with rare loss, simple receivers (HDLC, X.25) | long or lossy links where a window of resends is costly |
TCP is a mix. Its ACKs are cumulative, as in Go-Back-N, but the receiver keeps out-of-order segments, and with SACK (selective acknowledgment, RFC 2018) it tells the sender exactly which blocks it has, so the sender resends only the holes, as in Selective Repeat. Three duplicate ACKs trigger a fast retransmit before the timer fires. Its sequence numbers count bytes in 32 bits, and timestamps (PAWS) guard against wrap on fast links. See TCP vs UDP for retransmission and head-of-line blocking, TCP Congestion Control for how the window size is chosen, and the TCP handshake for how the first sequence numbers are agreed.
See TCP Flow Control for the receiver's advertised window.
What the page leaves out
Transmission time (a whole window leaves in one tick) and a fixed round trip; corrupted packets and checksums (a corrupt packet is just dropped, like a lost one); NAKs; adaptive timeouts (TCP measures the round trip and sets RTO = SRTT + 4·RTTVAR, RFC 6298, doubling it on every timeout); restarting the Go-Back-N timer on each ACK; fast retransmit and SACK; flow control (the receiver's advertised window) and congestion control, which change N while the transfer runs.