Stop-and-Wait, Sliding Windows, Go-Back-N & Selective Repeat

Chapter 4.2 built every reliability and flow-control equation tested on GATE: Stop-and-Wait's η = 1/(1 + 2a) and 1-bit duplicate protection, Sliding Window's η = min(1, N/(1 + 2a)) and universal window bound Ws + Wr ≤ 2ᵏ, Go-Back-N's Ws ≤ 2ᵏ − 1 with cumulative ACKs and window rollback, and Selective Repeat's Ws = Wr ≤ 2ᵏ⁻¹ with out-of-order buffering.

From 4.2.1 Stop-and-Wait ARQ, 1-bit sequence numbers & link utilisation

• Stop-and-Wait ARQ: 1 packet in flight; uses 1-bit sequence numbers (0, 1) to discard duplicates when ACKs are lost.
• Utilisation: η = Tt / (Tt + 2·Tp) = 1 / (1 + 2a), where a = Tp / Tt (with losses of prob p: (1 − p)/(1 + 2a)).
• Throughput: η × B = L / (Tt + 2·Tp).

From 4.2.2 Sliding window protocols, pipelining & k-bit sequence numbers

• Sliding-window utilisation: η = min(1, N / (1 + 2a)); full utilisation at N = ⌈1 + 2a⌉.
• k-bit sequence space: 0 .. 2ᵏ − 1 (2ᵏ numbers); universal bound: Ws + Wr ≤ 2ᵏ.

From 4.2.3 Go-Back-N (GBN): Ws ≤ 2ᵏ−1, cumulative ACKs & retransmission counting

• Go-Back-N bounds: Wr = 1, Ws ≤ 2ᵏ − 1 ⇒ minimum bits for window N is k = ⌈log₂(N + 1)⌉.
• Cumulative ACK: confirms all frames up to that number (survives lost earlier ACKs).
• On loss of frame f: receiver discards f+1 .. min(M, f+N−1); sender times out and retransmits from f.

From 4.2.4 Selective Repeat (SR): Ws = Wr ≤ 2ᵏ⁻¹ & minimum sequence bits

• Selective Repeat bounds: Ws = Wr ≤ 2ᵏ⁻¹ ⇒ minimum bits for window N is k = ⌈log₂(2N)⌉.
• Receiver: buffers out-of-order frames within W_r; sends selective ACKs / NAKs; delivers in order to upper layer.
• Every K-th tx lost (M frames): Total transmissions in SR = M + ⌊(M − 1) / (K − 1)⌋.

1. NAT · 2 marks

   A 2 Mbps link has a one-way propagation delay of 24.5 ms and uses 2000-bit data frames (ignore ACK size). What is the link utilisation (in percent) of Stop-and-Wait ARQ?

   Write your answer before opening the key.

2. NAT · 2 marks

   In the same link (B = 2 Mbps, T_t = 1 ms, T_p = 24.5 ms, so 1 + 2a = 50), if a sliding-window protocol with sender window size N = 15 is used, what is the achieved throughput in kbps?

   Write your answer before opening the key.

3. NAT · 2 marks

   Continuing with 1 + 2a = 50, what is the minimum number of sequence-number bits k required to achieve 100% link utilisation using Selective Repeat?

   Write your answer before opening the key.

4. NAT · 2 marks

   For the same link (1 + 2a = 50), what is the minimum number of sequence-number bits k required to achieve 100% link utilisation using Go-Back-N?

   Write your answer before opening the key.

5. NAT · 2 marks

   A sender uses Go-Back-N with sender window size N = 4 to transmit M = 8 frames. Every 5th transmitted frame (5th, 10th, 15th, …) is lost. How many total frame transmissions are required to deliver all 8 frames?

   Write your answer before opening the key.

6. NAT · 2 marks

   If Selective Repeat is used to transmit M = 12 frames and every 4th transmitted frame (4th, 8th, 12th, …) is lost, how many total frame transmissions occur?

   Write your answer before opening the key.

7. MCQ · 1 mark

   A sliding-window protocol uses k = 4 bits for sequence numbers and has a receiver window of size W_r = 3. What is the maximum safe sender window size W_s?

   1. 12
   2. 13
   3. 15
   4. 8
8. MSQ · 2 marks

   Which of the following statements about ARQ protocols are TRUE?

   1. Stop-and-Wait is a special case of Go-Back-N with sender window size W_s = 1.
   2. In Go-Back-N, an out-of-order error-free frame is discarded by the receiver.
   3. In Selective Repeat, an out-of-order error-free frame within the receiver window is buffered.
   4. Increasing the sequence number field by 1 bit doubles the maximum window size in Selective Repeat.