Go-Back-N Sliding Window Protocol

Definition. Go-Back-N (GBN) is an ARQ sliding-window protocol in which the sender may keep up to N unacknowledged frames in flight, while the receiver accepts only in-order frames (its window size is 1). Whenever an error or a timeout is detected, the sender goes back N: it retransmits the damaged/lost frame and every frame sent after it, even those the receiver had already accepted correctly.

Operating parameters

• Sequence numbers are taken from 0 to $2^m - 1$ with m bits and used modulo $2^m$.
• The sender window must satisfy N less than or equal to $2^m - 1$; otherwise the receiver could not tell a new frame from an old duplicate.
• Receiver window = 1, so an out-of-order frame is never buffered.
• Ideal utilisation on an error-free link: $U = N / (1 + 2a)$, where $a = T_{prop} / T_{trans}$ (capped at 1).

Sender operation

1. Maintain a window over frames that have been sent but not yet acknowledged, plus a timer for the oldest unacknowledged frame.
2. Transmit the next frame whenever the window has a free slot - this gives flow control: when N frames are outstanding the sender must stop.
3. Accept a cumulative ACK: an acknowledgement for frame k means k and everything before it arrived correctly. Slide the window forward past k and restart the timer.
4. On timeout of the oldest unacknowledged frame, retransmit that frame and all later frames still in the window (the go-back-N step), then restart the timer.
5. Duplicate or stale ACKs for frames already acknowledged are ignored.

Receiver operation

1. Expect exactly one sequence number at a time; deliver it to the network layer only if it is the expected one and the FCS/checksum is valid.
2. Send an ACK for each correctly received in-order frame.
3. If a frame arrives out of order or corrupted, discard it (no reordering buffer) and re-acknowledge the last correctly received in-order frame. That duplicate ACK tells the sender nothing was delivered beyond that point, so recovery rests on the sender's timer.

Example of operation (N = 4)

 Sender  window [ 0 ][ 1 ][ 2 ][ 3 ]      transmits 0,1,2,3
   |
   |---- F0 ---->|                         OK   -> ACK 0
   |---- F1 ---->|                         OK   -> ACK 1
   |---- F2 --X--|                         LOST
   |---- F3 ---->|                         arrives out of order -> discarded, ACK 1
   |
   |  timer for F0/F2 expires -> GO BACK N
   |---- F2 ---->|                         OK   -> ACK 2
   |---- F3 ---->|                         OK   -> ACK 3
   |
   window now slides:      [ 4 ][ 5 ][ 6 ][ 7 ]

Note that F3 was received correctly the first time yet had to be sent again - this wasted bandwidth is the main drawback of GBN.

Efficiency (worked example)

Formula: $U = N / (1 + 2a)$, with $a = T_{prop} / T_{trans}$.

• Take N = 4 frames and propagation time = 2 transmission times, so a = 2.
• $U = 4 / (1 + 2 \times 2) = 4 / 5 = 0.8$
• Channel utilisation = 80 %. Compare stop-and-wait (N = 1): $U = 1 / 5 = 0.2$, only 20 %. GBN therefore gives about 4 times the throughput of stop-and-wait for the same link.

Merits, demerits and comparison with Selective Repeat

	Go-Back-N	Selective Repeat
Receiver window	1 (no buffering)	N (buffers out-of-order frames)
On error	Retransmits the lost frame and all later frames	Retransmits only the lost/corrupt frames
Receiver complexity	Very low	Higher (reorder buffer)
Bandwidth efficiency	Lower on error-prone links	Higher
Maximum window	$2^m - 1$	$2^{m-1}$

GBN is simple and cheap to implement at the receiver, which is why it is used in many data-link protocols; its weakness is that a single loss forces retransmission of a whole window of already-correct frames.