Go-Back-N (GBN) ARQ Protocol

---

1. Concept of Pipelining and Sliding Window

In Stop-and-Wait, the sender must wait for an acknowledgment after every single frame, wasting immense bandwidth on high-latency links.

Pipelining allows the sender to transmit multiple consecutive frames before receiving an acknowledgment, keeping the communication link full:

---

2. Sliding Window in Go-Back-N

In Go-Back-N, sequence numbers are represented with $m$ bits, cycling modulo $2^m$ ($0, 1, 2, \dots, 2^m - 1$).

Window Sizes:

• Sender Window Size ($W_s$):

• Receiver Window Size ($W_r$):

---

3. Why Must $W_s \leq 2^m - 1$ in Go-Back-N?

This is a classic university exam question.

The Proof by Contradiction:

Suppose $m = 2$ bits (sequence numbers: $0, 1, 2, 3$).
Assume we set $W_s = 2^m = 4$.

1. Sender transmits frames 0, 1, 2, 3. The window is full.
2. Receiver receives all 4 frames correctly and advances its expected sequence number to 0 (modulo 4).
3. Receiver sends cumulative acknowledgment ACK 0 (expecting frame 0 of the next cycle).
4. Disaster Scenario: The ACK 0 frame is lost in transmission due to channel noise.
5. Sender times out. Because it received no ACK, it retransmits the entire window: frames 0, 1, 2, 3.
6. Receiver receives frame 0. The receiver is expecting frame 0 of the new cycle, but it just received a retransmission of the old frame 0!
7. The Receiver cannot distinguish between a duplicate old frame and a fresh new frame!

By restricting $W_s \leq 2^m - 1$ (e.g., $W_s \leq 3$), the retransmitted frame numbers never overlap with the receiver's next expected sequence number.

---

4. Operational Mechanics of GBN

1. Cumulative Acknowledgment:
   • ACK N acknowledges all frames up to and including $N - 1$, and indicates that the receiver is waiting for frame $N$.
   • A single lost ACK does not trigger retransmissions if a subsequent higher ACK arrives before timeout.
2. Receiver Discard Policy:
   • Because $W_r = 1$, the receiver has no buffer for out-of-order frames.
   • If frame 2 is lost, arriving frames 3, 4, 5 are dropped on the floor, even if completely uncorrupted!
3. Sender Retransmission:
   • The sender maintains a single retransmission timer for the oldest unacknowledged frame.
   • When timeout occurs, the sender rewinds its pointer and retransmits all frames starting from the lost frame (Frames $2, 3, 4$).

---

5. Performance & Efficiency Analysis

The maximum efficiency of Go-Back-N ARQ depends on window size $W_s$ and parameter $a = \frac{T_p}{T_t}$:

Optimal Window Size for 100% Channel Utilization:

To ensure the transmitter never starves while waiting for the first ACK:

Minimum Sequence Number Bits:

Since $W_s \leq 2^m - 1$, the minimum number of sequence bits required is:

---

6. Solved Numerical Example

• Problem: A $1\text{ Mbps}$ satellite link has a round-trip propagation delay ($2 \cdot T_p$) of $500\text{ ms}$. Data frames are $1{,}000\text{ bytes}$ ($8{,}000\text{ bits}$).
  1. Find the transmission delay $T_t$.
  2. Find parameter $a$.
  3. Find the optimal sender window size $W_s$ for $100\%$ efficiency.
  4. Find the minimum number of bits $m$ needed in the sequence number field for GBN.
• Solution:
  1. $T_t = \frac{8{,}000\text{ bits}}{10^6\text{ bps}} = 0.008\text{ s} = 8\text{ ms}$.
  2. $a = \frac{T_p}{T_t} = \frac{250\text{ ms}}{8\text{ ms}} = 31.25$.
  3. $W_{\text{optimal}} = 1 + 2a = 1 + 2(31.25) = 1 + 62.5 = 63.5 \implies \mathbf{64\text{ frames}}$.
  4. For GBN, $W_s \leq 2^m - 1$:

---