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:

  Stop-and-Wait (No Pipelining):
  TX: [ F0 ] ---------------------------------------------> (Wait...)
  RX:        <---------------------------------- [ ACK 1 ]

  Pipelined (Go-Back-N):
  TX: [ F0 ][ F1 ][ F2 ][ F3 ][ F4 ] ---------------------> (Continuous stream!)
  RX:        <-- [ACK 1] <-- [ACK 2] <-- [ACK 3] ...

---

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$).

             |<----------- Sender Window Ws <= 2^m - 1 ------------>|
  ... 0   1  [ 2   3   4   5   6   7   8 ]  9   10  11 ...
      \_____/  \_______________/ \_______/
     Acked      Sent & Pending   Can Send
     Frames          ACK        Immediately

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

  SENDER                                              RECEIVER (Wr = 1)
    |                                                    |
    |---- Frame 0 -------------------------------------->| (Accept, Expect 1)
    |---- Frame 1 -------------------------------------->| (Accept, Expect 2)
    |---- Frame 2 ----- X (LOST!)                        |
    |---- Frame 3 -------------------------------------->| (Out of order! DISCARD!)
    |---- Frame 4 -------------------------------------->| (Out of order! DISCARD!)
    |                                                    |
    |<--- ACK 2 (Cumulative for F0 & F1) ----------------|
    |                                                    |
    | [ Timer for Frame 2 EXPIRES ]                      |
    | "GO-BACK-N" ===> Retransmits F2, F3, F4            |
    |---- Frame 2 -------------------------------------->| (Accept, Expect 3)
    |---- Frame 3 -------------------------------------->| (Accept, Expect 4)
    |---- Frame 4 -------------------------------------->| (Accept, Expect 5)

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$:

---

7. Key Exam Questions & Takeaways

1. Why is the receiver window size $W_r = 1$ in Go-Back-N?
   • The receiver does not store out-of-order frames; it only accepts frames in strict sequential order. Any frame other than the expected one is discarded immediately.
2. Explain the primary disadvantage of Go-Back-N ARQ.
   • In noisy channels with high error rates, a single corrupted frame causes all subsequent successfully received frames in the window to be discarded and retransmitted, severely degrading throughput.
3. What is cumulative ACK?
   • An acknowledgment confirming receipt of a continuous block of frames up to sequence number $N - 1$, reducing ACK traffic.