CS Atlas GATE 2027
Computer Networks course
0 / 90 complete

Computer Networks/Phase 4 · Transport Layer (TCP)

Lesson 4.2.4 · Item 65 of 90

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

Read at your own pace. Try the questions before opening the answers.

On this page

Recall warm-up

  1. In Go-Back-N with k-bit sequence numbers, why are all frames after a lost frame discarded by the receiver?
    Stuck? Peek at 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.

    Read lesson 4.2.3

  2. From the universal bound W_s + W_r ≤ 2ᵏ, if we set W_s = W_r, what is the maximum value of W_s?
    Stuck? Peek at 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ᵏ.

    Read lesson 4.2.2

  3. If a link has T_t = 1 ms and T_p = 15 ms, how many frames can be in flight in one round-trip cycle (1 + 2a)?
    Stuck? Peek at 1.3.3 RTT, bandwidth-delay product, utilisation and a = Tp/Tt
    • RTT = 2·Tp for tiny signals (add Tt / queuing if stated).
    • BDP = B × Tp bits in flight; B × RTT before any reply.
    • a = Tp / Tt.
    • Send-and-wait: U = Tt/(Tt + 2Tp) = 1/(1 + 2a); throughput = U·B.
    • To keep the link busy: about 1 + 2a units in flight.

    Read lesson 1.3.3

The Hook

On a high-speed link with a slight bit-error rate, throwing away an entire window of 500 good packets just because 1 packet was corrupted is a tragic waste of bandwidth. Selective Repeat (SR) fixes this: the receiver opens a buffer of size Wr = Ws, stores out-of-order packets quietly, and asks the sender to retransmit ONLY the specific packet that was lost!

What is the price we pay for this smart receiver? Besides buffer memory, look at the sequence number bound: Ws + Wr ≤ 2ᵏ with Ws = Wr means each window can be at most half the sequence number space (2ᵏ⁻¹)!

Predict First

With k = 3 bits (8 sequence numbers: 0..7), suppose a Selective Repeat designer sets Ws = Wr = 5 (more than half of 8). Sender sends 0, 1, 2, 3, 4; Receiver accepts all 5 and slides its receiver window to [5, 6, 7, 0, 1]. Now suppose all 5 ACKs are lost, so the sender retransmits old 0! Is 0 inside the receiver's new window [5, 6, 7, 0, 1]?

,

YES! Because 5 + 5 = 10 > 8, the receiver's new window [5, 6, 7, 0, 1] overlaps the sender's old window [0, 1, 2, 3, 4] on sequence numbers 0 and 1! The receiver accepts retransmitted old 0 as a brand-new 9th packet! To prevent overlap, Ws + Wr ≤ 2ᵏ → Ws = Wr ≤ 2ᵏ⁻¹ = 4.

Core Concept

Rules of Selective Repeat (SR) ARQ

In Selective Repeat with k-bit sequence numbers:

  • Window Size Bound: Ws = Wr ≤ 2ᵏ⁻¹ = 2ᵏ / 2 (so minimum bits for window N is k = ⌈log₂(2N)⌉ = 1 + ⌈log₂(N)⌉).
  • Out-of-Order Buffering: The receiver buffers any error-free frame whose sequence number falls inside its current window Wr, even if earlier frames are still missing. Once the missing frame arrives, the contiguous batch is delivered to the upper layer and Wr slides forward.
  • Individual ACKs & NAKs: Each error-free arrival is acknowledged individually (selective ACK); if the receiver detects a gap (e.g., sees Frame 2 while waiting for Frame 1), it can immediately send a NAK 1 (Negative ACK) so the sender retransmits Frame 1 without waiting for a timeout!
Sender (Ws = 4, k = 3)Receiver (Wr = 4)Frame 0 (buffered & delivered)✕Frame 1 (LOST!)Frame 2 (out of order → BUFFERED!)NAK 1 + Selective ACK 2Frame 3 (out of order → BUFFERED!)Retransmit ONLY Frame 1!Frame 1 fills gap → deliver 1, 2, 3 together!
Selective Repeat on loss of Frame 1: Frames 2 and 3 are buffered (not discarded!), and ONLY Frame 1 is retransmitted.

Visual Proof: Why Ws = Wr ≤ 2ᵏ⁻¹ (No Window Overlap)

In the worst case, all Ws frames arrive at the receiver (advancing the receiver window by Ws positions to [Ws .. Ws + Wr − 1]), while all Ws ACKs are lost (leaving the sender window at [0 .. Ws − 1]). For those two intervals on a ring of size 2ᵏ to be completely disjoint, their combined length cannot exceed 2ᵏ:

01234567Sender old window [0..3] (if ACKs lost)Receiver new window [4..7] (disjoint!)
With k = 3 bits (8 numbers) and Ws = Wr = 4: [0..3] and [4..7] have zero overlap!

Retransmission Counting & GBN vs SR Head-to-Head

How many total transmissions occur in Selective Repeat when sending M frames and every K-th transmission is lost? Because out-of-order frames are NEVER discarded, only the lost frames themselves are retransmitted! Every block of K transmissions delivers K − 1 frames and loses 1:

SR Retransmission Formula (every K-th lost, M frames):
Each cycle of K transmissions delivers K − 1 frames. You can also step through: tx = 1, 2, … until tx − ⌊tx / K⌋ == M!
FeatureStop-and-WaitGo-Back-N (GBN)Selective Repeat (SR)
Max Sender Window Ws (k bits)12ᵏ − 12ᵏ⁻¹
Receiver Window Wr11 (no out-of-order buffer)2ᵏ⁻¹ (buffers out-of-order)
Min bits k for window N1 bit (0, 1)⌈log₂(N + 1)⌉⌈log₂(2N)⌉ = 1 + ⌈log₂ N⌉
ACK typeIndividual (0/1)Cumulative ACKSelective (individual) ACK + NAK
Retransmissions on 1 lost frame1 frameUp to N frames (whole window)Only 1 frame (the lost one)
The complete ARQ comparison table for GATE.

Putting it together

  • Selective Repeat sets W_r = W_s so the receiver can buffer out-of-order frames and retransmit only the lost frame.
  • To prevent overlap between the old sender window and advanced receiver window when ACKs are lost, W_s = W_r ≤ 2ᵏ⁻¹ (so k = ⌈log₂(2N)⌉).
  • On noisy high-BDP links, SR saves massive bandwidth over GBN at the cost of receiver buffer memory and 1 extra sequence-number bit.

Visual

74k = 3 bits (space 8)158k = 4 bits (space 16)3116k = 5 bits (space 32)
Go-Back-N max Ws (2ᵏ − 1)Selective Repeat max Ws (2ᵏ⁻¹)
For the same k-bit header field, GBN allows nearly twice the sender window size of SR.

Worked Examples

Easy

A Selective Repeat protocol uses a 4-bit sequence number field (k = 4). What are the maximum permissible sender window size Ws and receiver window size Wr?

Show the full solution

Ws = Wr = 2⁴⁻¹ = 2³ = 8 frames.

Medium

A link has Tt = 1 ms and one-way propagation delay Tp = 4 ms. What is the minimum number of sequence-number bits k needed to achieve 100% link utilisation using (a) Go-Back-N and (b) Selective Repeat?

Show the full solution

First find required window size for 100% utilisation: a = 4 / 1 = 4 → N = 1 + 2a = 9 frames.
(a) Go-Back-N: 2ᵏ − 1 ≥ 9 → 2ᵏ ≥ 10 → k = 4 bits (allows up to 15).
(b) Selective Repeat: 2ᵏ⁻¹ ≥ 9 → 2ᵏ ≥ 18 → k = 5 bits (since 4 bits only allow 2³ = 8 < 9!).

GATE

A sender transmits M = 10 frames using Selective Repeat (window size 4), and every 5th transmitted frame (5th, 10th, 15th, …) is lost. How many total frame transmissions are required, and how many transmissions were saved compared to Go-Back-N with window size 3?

Show the full solution

In SR, only lost frames are retransmitted:
• Send 1, 2, 3, 4, 5 (tx5 lost) → 4 delivered, 1 to retry.
• Send 5, 6, 7, 8, 9 (tx10 lost) → 8 delivered, 1 to retry.
• Send 9, 10 (tx11, tx12 — both succeed!).
Total in SR = 12 transmissions (10 originals + 2 retransmissions). Compared to GBN (18 transmissions in Lesson 4.2.3), SR saved 18 − 12 = 6 transmissions!

GATE Traps

  • The N = 8 trap in SR vs GBN: If N = 8, GBN needs ⌈log₂(9)⌉ = 4 bits, AND SR ALSO needs ⌈log₂(16)⌉ = 4 bits (since 2⁴⁻¹ = 8)! Always plug into the exact inequality 2ᵏ − 1 ≥ N (GBN) vs 2ᵏ⁻¹ ≥ N (SR).
  • Receiver buffering != out-of-order delivery to the application! The SR receiver buffers out-of-order packets at Layer 4/2, but it still delivers data to the upper-layer application strictly in order once the missing gap is filled.

Memory Hook

SR buffers out-of-order frames and resends only the lost one, but splits the sequence space in half: Ws = Wr ≤ 2ᵏ⁻¹!

Connect the Dots

Chapter 4.2 complete! You now have the complete mathematical toolkit for Stop-and-Wait, Go-Back-N, and Selective Repeat. After the Chapter 4.2 Lock-in, Chapter 4.3 shows how real-world TCP combines byte-numbered sliding windows, cumulative ACKs, flow control, adaptive RTT timers, and congestion control!

Self-Test

  1. NAT

    A Selective Repeat protocol uses a 5-bit sequence number field (k = 5). What is the maximum permissible sender window size W_s?

    Write your answer before opening the key.

  2. NAT

    A link has 1 + 2a = 12. What is the minimum number of bits k required in the sequence-number field to achieve 100% link utilisation using Selective Repeat?

    Write your answer before opening the key.

  3. NAT

    Using Selective Repeat, a sender transmits 25 frames over a link where every 6th transmitted frame (6th, 12th, 18th, …) is lost. How many total frame transmissions are required until all 25 frames are successfully received?

    Write your answer before opening the key.

  4. MSQ

    Which of the following statements accurately compare Go-Back-N (GBN) and Selective Repeat (SR) for a given k-bit sequence number field?

    1. For k = 4, the maximum sender window is 15 in GBN and 8 in SR.
    2. When a single frame is lost in a large window, SR retransmits only that frame whereas GBN retransmits the lost frame and all subsequent frames in the window.
    3. SR requires out-of-order buffering at the receiver, whereas GBN does not.
    4. SR delivers frames to the upper-layer application out of order as soon as they arrive.

Rule Card

  • Selective Repeat bounds: Ws = Wr ≤ 2ᵏ⁻¹ ⇒ minimum bits for window N is k = ⌈log₂(2N)⌉.
  • Receiver: buffers out-of-order frames within Wr; 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)⌋.

Concept Ledger

  • Selective Repeat (SR)
  • Ws = Wr ≤ 2ᵏ⁻¹
  • individual (selective) ACK and NAK
  • receiver out-of-order buffering
  • minimum sequence bits for target utilisation

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up answers

  1. Because the GBN receiver has window size W_r = 1 and cannot buffer out-of-order frames.
  2. 2 · W_s ≤ 2ᵏ ⇒ W_s = W_r ≤ 2ᵏ / 2 = 2ᵏ⁻¹.
  3. 1 + 2(15 / 1) = 31 frames.

Self-test answers

  1. 16 — In Selective Repeat, W_s ≤ 2ᵏ⁻¹ = 2⁵⁻¹ = 2⁴ = 16.
  2. 5 — We need W_s = 12. Since W_s ≤ 2ᵏ⁻¹, we need 2ᵏ⁻¹ ≥ 12 → 2ᵏ ≥ 24 → minimum integer k = 5 bits (2⁴ = 16 ≥ 12).
  3. 29 — Using the SR formula: M + ⌊(M − 1)/(K − 1)⌋ = 25 + ⌊24 / 5⌋ = 25 + 4 = 29 transmissions (losses occur at tx 6, 12, 18, 24).
  4. ABC — For k=4, GBN max is 15 and SR max is 8; SR retransmits only the lost frame and buffers out-of-order arrivals at the receiver. However, SR still delivers data to the upper layer strictly in order once gaps are filled.
    • D: SR buffers out-of-order frames until the missing frame arrives, then delivers them in order to the application.

Flashcards

  1. In Selective Repeat with k-bit sequence numbers, what are max W_s and W_r?
    Reveal answerW_s = W_r = 2ᵏ⁻¹ (half the sequence number space).
  2. Formula for minimum sequence-number bits k in SR for window size N?
    Reveal answerk = ⌈log₂(2N)⌉ = 1 + ⌈log₂(N)⌉.
  3. Total transmissions in SR to send M frames when every K-th transmission is lost?
    Reveal answerM + ⌊(M − 1) / (K − 1)⌋.

Exam shortcuts

  • SR Minimum Bits Shortcut: For window size N, SR needs k = ⌈log₂(2N)⌉ bits (whereas GBN needs ⌈log₂(N + 1)⌉). — solving "minimum sequence number bits for Selective Repeat" in 5 seconds.
  • SR Every-Kth-Lost Formula: Number of lost frames (retransmissions) when sending M frames with every K-th transmission lost is ⌊(M − 1) / (K − 1)⌋, so total transmissions = M + ⌊(M − 1) / (K − 1)⌋! — instant formula for SR retransmission counting (e.g. M=10, K=5: 10 + ⌊9/4⌋ = 10 + 2 = 12)!
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.