Sliding Window: Stop-and-Wait, Go-Back-N & Selective Repeat
“Window sizes, link efficiency eta = W / (1 + 2a), and timer retransmissions.”
1.The Stop-and-Wait Protocol & Fundamental Efficiency
§ 3.1.In Stop-and-Wait ARQ, the sender transmits a single frame and halts until an acknowledgment (ACK) is received from the receiver. If a timer expires before the ACK arrives, the sender retransmits the frame.
Total Round-Trip Cycle Time T_cycle = T_t + 2 * T_p + T_proc + T_ack.
Assuming processing delay T_proc approx 0 and ACK frame transmission delay T_ack approx 0: T_cycle = T_t + 2 * T_p.
Link Efficiency (Utilization) eta = Useful Time / Total Time = T_t / (T_t + 2 * T_p) = 1 / (1 + 2a), where a = T_p / T_t = (Propagation Delay) / (Transmission Delay).
Throughput = eta Bandwidth = (Size of Frame) / (T_t + 2 T_p).
On satellite links or high-speed fiber where propagation delay T_p is huge compared to transmission delay T_t (i.e., a >> 1), Stop-and-Wait efficiency collapses near 0%! Pipelined sliding window protocols are essential.
2. Sliding Window Architectural Comparison: GBN vs Selective Repeat
Detailed comparison of window bounds, receiver buffering, acknowledgment types, and retransmission behavior:
| Feature / Aspect | Feature | Go-Back-N (GBN) |
|---|---|---|
| Sender Window Size (W_s) | W_s <= 2^k - 1 (for k-bit sequence numbers) | W_s <= 2^(k - 1) |
| Receiver Window Size (W_r) | W_r = 1 (strictly accepts in-order only) | W_r = W_s <= 2^(k - 1) |
| Window Sum Condition | W_s + W_r <= 2^k (W_s + 1 <= 2^k) | W_s + W_r <= 2^k (W_s = W_r = 2^(k-1)) |
| Out-of-Order Frames | Discarded completely (not buffered) | Buffered in receiver window until gap is filled |
| Acknowledgment Type | Cumulative ACK (ACK n confirms all frames <= n) | Individual Selective ACK (NACK / SACK) |
| Retransmission on Timeout | Retransmits entire window of unacknowledged frames | Retransmits ONLY the single lost frame |
| Hardware Complexity | Low (no receiver buffer needed) | High (sorting buffer, individual timers per frame) |
3. GATE Worked Numerical: 100% Link Utilization & Sequence Number Bits
In Go-Back-N, if optimal window size is W, you need at least W + 1 distinct sequence numbers! Sequence bits k = ceil(log2(W + 1)). In Selective Repeat, k = ceil(log2(2 * W)).
Problem: A 1000 km link has bandwidth B = 100 Mbps and propagation speed s = 2 * 10^8 m/s. Frame size L = 1000 bytes. Find:
1. Stop-and-Wait efficiency.
2. Minimum sender window size W_s to achieve 100% link utilization.
3. Minimum sequence number bits required for GBN and Selective Repeat.
Step 1: Compute T_t and T_p:
T_t = (1000 8 bits) / (100 10^6 bps) = 8,000 / 100,000,000 = 0.08 ms = 80 microseconds.
T_p = Distance / Speed = 1000 10^3 m / (2 10^8 m/s) = 5 * 10^-3 s = 5 ms.
a = T_p / T_t = 5 ms / 0.08 ms = 62.5.
Step 2: Stop-and-Wait Efficiency eta = 1 / (1 + 2a) = 1 / (1 + 125) = 1 / 126 approx 0.00794 (0.79%).
Step 3: For 100% utilization: Efficiency eta = 1 => W_s >= 1 + 2a = 1 + 125 = 126 frames.
Step 4: Sequence number bits:
For Go-Back-N: Total sequence numbers N >= W_s + 1 = 126 + 1 = 127. k = ceil(log2 127) = 7 bits.
For Selective Repeat: Total sequence numbers N >= 2 W_s = 2 126 = 252. k = ceil(log2 252) = 8 bits.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-level numerical drilling and PYQ analysis.
Step-by-step conceptual walkthroughs with worked GATE numericals.
Clear whiteboard lectures for foundational and semester exam coverage.