Flow Control at the Data Link Layer: Stop-and-Wait, Go-Back-N and Selective Repeat

Error detection tells a receiver that a frame is damaged; it does not get the data through. Automatic repeat request (ARQ) protocols add acknowledgements, timers and retransmission so that every frame is eventually delivered once and in order. The same machinery also provides flow control: the sender may have only a limited number of unacknowledged frames, its window, so a slow receiver is not flooded.

There are three classic protocols. Stop-and-wait sends one frame and waits for its acknowledgement. Go-Back-N (GBN) keeps up to $N$ frames outstanding and, after a loss, resends the lost frame and everything after it. Selective Repeat (SR) also keeps a window outstanding but resends only the frames that were actually lost, at the price of buffering out-of-order frames at the receiver.

The quantities to compute are link utilisation from $a = T_p/T_t$, the window needed to fill a link, the number of sequence-number bits, the maximum window for a given number of bits, and the number of transmissions under a stated loss pattern. TCP uses the same ideas with byte-numbered windows (TCP Flow Control).

Efficiency convention used in all CN notes. Utilisation (efficiency) $U$ is the fraction of time the sender's link is busy sending new data frames. Unless a question states otherwise, ACK frames are taken to have negligible transmission time, processing and queueing are zero, and the round trip is $2T_p$. The ratio is $a = T_p/T_t$ (one-way propagation over frame transmission).

Send a frame, start a timer, wait for its ACK, then send the next. One sequence bit (0 and 1, alternating) is enough: if an ACK is lost, the sender times out and resends, and the receiver recognises the duplicate by its sequence number, discards it and re-acknowledges it. Without sequence numbers a lost ACK would cause a duplicate to be delivered.

The figure uses $T_t = 1$ time unit, $T_p = 2$ units, a timeout of 8 units after the end of a frame's transmission, frames 0 to 6, and only the first transmission of frame 2 lost. Frames 0 to 3 go out back to back at times 0 to 4; ACK 0 returns at time 5, so frame 4 is sent at 5 and frame 5 at 6. Then the window is stuck on frame 2. Its timer expires at 11, and the two protocols diverge.

A frame sent at time 0 finishes at $T_t$, its last bit arrives at $T_t + T_p$, and the ACK is back at $T_t + 2T_p$. Stop-and-wait sends one frame per cycle:

With a window of $W$ frames, the sender can send $W$ frames in each cycle of $T_t + 2T_p$:

The smallest window that keeps the link fully busy is $W = \lceil 1 + 2a \rceil$. In bits, this is the frame plus the round-trip bandwidth-delay product: $W L \ge L + R \cdot 2T_p$. Throughput is $U \cdot R$.

If ACK time and processing are included, replace the cycle $T_t + 2T_p$ by $T_t + T_{\text{ack}} + 2T_p + T_{\text{proc}}$.

If each frame is lost or damaged independently with probability $p$ and the timeout equals the round trip, the number of transmissions per frame is geometric with mean $1/(1-p)$, so

With $k$-bit sequence numbers (modulus $2^k$):

Why GBN cannot use $2^k$. Suppose $W_s = 2^k$. The sender sends frames numbered $0, \ldots, 2^k - 1$; all arrive, the receiver now expects number 0 again, and all ACKs are lost. The sender times out and resends the old frame 0, which the receiver accepts as new. With $W_s = 2^k - 1$ the receiver expects $2^k - 1$ after a full window, which is not among the resent numbers.

Why SR needs half. After the receiver accepts a full window of $W$ frames, its window moves to the next $W$ numbers. If the ACKs are lost, the sender resends the old $W$ numbers. The two sets of numbers must not overlap modulo $2^k$, which needs $2W \le 2^k$.

Bits needed. For a target window $W$: GBN needs the smallest $k$ with $2^k - 1 \ge W$; SR needs the smallest $k$ with $2^{k-1} \ge W$, so SR usually needs one bit more than GBN for the same window (compute both; Example 3).

A 1 Mbps link, 1000-bit frames, $T_p = 10$ ms. $T_t = 1$ ms, $a = 10$, $U = 1/21 \approx 0.0476$, throughput about 47.6 kbps. If the ACK is also 1000 bits, $U = 1/22 \approx 0.0455$. If each frame is lost with probability 0.2 (ACKs not counted), $U = 0.8/21 \approx 0.0381$.

Same link. A window of 5 frames gives $U = 5/21 \approx 0.238$. A window of 21 or more gives $U = 1$. In bits: $L + R \cdot 2T_p = 1000 + 20{,}000 = 21{,}000$ bits must be in flight, which is 21 frames.

For a window of 21 frames, GBN needs $k = 5$ ($2^5 - 1 = 31 \ge 21$, while $2^4 - 1 = 15$ is too small), and SR needs $k = 6$ ($2^5 = 32 \ge 21$, $2^4 = 16$ too small). If the field has only $k = 4$ bits: GBN can use $W = 15$, $U = 15/21 \approx 0.714$; SR can use $W = 8$, $U = 8/21 \approx 0.381$.

Ten frames are sent with window 3, every 5th transmission (5th, 10th, 15th, ...) is lost, ACKs are never lost, $T_t = 1$, $T_p = 1$ and the timeout is longer than the time to send a window.

For SR and stop-and-wait each loss costs exactly one extra transmission: 12 transmissions deliver 10 frames because only the 5th and 10th are lost. For GBN each loss also costs the frames sent behind the lost one, and those extra transmissions shift which later frame is the 5th, 10th or 15th transmission. With nine frames instead of ten, GBN with window 3 needs 16 transmissions. Answers to such questions depend on the conventions (what counts as a transmission, whether the window fills before the timeout); state them, then trace frame by frame.

With $k = 2$ (numbers 0 to 3): GBN with $W = 4$ sends 0, 1, 2, 3; if all four ACKs are lost, the receiver expects 0 and wrongly accepts the resent old 0. With $W = 3$ it expects 3, and the resent 0, 1, 2 are rejected. SR with $W = 3$: the receiver's window moves to $\{3, 0, 1\}$ after accepting 0, 1, 2, so resent old 0 and 1 are wrongly accepted as new; with $W = 2$ the windows $\{0, 1\}$ and $\{2, 3\}$ are disjoint and the scheme is safe.

Two stations exchange data in both directions. Without piggybacking each data frame needs a separate ACK frame; with piggybacking the ACK number rides in the header of the next data frame in the reverse direction. If no reverse data is ready within a short ACK timer, a stand-alone ACK is sent, so that the sender does not time out.

The link of Example 1 ($T_t = 1$ ms, $T_p = 10$ ms), now with a 100-bit ACK ($T_{\text{ack}} = 0.1$ ms) and 0.4 ms of processing at the receiver before it sends the ACK. One cycle is

Stop-and-wait gives $U = 1/21.5 \approx 0.0465$, and a window of 10 gives $U = 10/21.5 \approx 0.465$. Full utilisation now needs $W \ge 21.5$, so $W = 22$: the window of 21 that was enough in Example 2 reaches only $21/21.5 \approx 0.977$.

Frames 1 to $n$, window $W$, only frame $i$ lost (once), ACKs never lost, and a timeout long enough for the sender to fill its window before the timer fires.

With $n = 10$ and $W = 4$: losing frame 6 costs GBN $10 + 4 = 14$ transmissions (6, 7, 8 and 9 are sent again), losing frame 9 costs $10 + 2 = 12$ (only 9 and 10 are behind it), and SR needs 11 in both cases. If the timer fires before the window is full, fewer frames are outstanding and GBN resends fewer; the question must then give the timing, and the frames are traced one by one.

With $k = 3$ (numbers 0 to 7) and a receiver window $W_r = 3$, the rule $W_s + W_r \le 2^k$ allows $W_s \le 5$. With $W_s = 6$ it fails: the receiver accepts 0 to 5 and its window moves to $\{6, 7, 0\}$; if all six ACKs are lost, the resent old frame 0 falls inside the new window and is accepted as new. $W_r = 1$ is the Go-Back-N case ($W_s \le 7$); equal windows give $W \le 4$.

Both stations always have data and use a one-bit sliding window with piggybacked ACKs only: a station sends its next frame, carrying the ACK, as soon as a frame from the other side has fully arrived. On the link of Example 1, A sends at 0; its frame has fully arrived at B at $T_t + T_p = 11$ ms, when B sends its own frame with the ACK; that frame reaches A at 22 ms, when A sends its next frame. Each station sends one frame every $2(T_t + T_p) = 22$ ms, so each direction has $U = 1/22 \approx 0.0455$, the same as stop-and-wait with an ACK as long as a data frame (Example 1): an ACK cannot be read until the whole frame carrying it has arrived. The gain is that no separate ACK frames are sent and both directions carry data.

Common misconceptions.