Selective Repeat (SR) ARQ Protocol

1. Motivation: Overcoming GBN Inefficiency

In Go-Back-N (GBN), if a single frame is lost, the receiver discards all subsequent correctly delivered frames, forcing the sender to retransmit the entire window. On high-error or high-bandwidth links, this retransmission of good frames causes severe throughput degradation.

Selective Repeat (SR) ARQ solves this by:

Buffering out-of-order frames at the receiver.
Retransmitting only the specific damaged or lost frames.

  Go-Back-N Retransmission:
  F0, F1, [F2 Lost], F3, F4  ===> Sender Retransmits: [ F2, F3, F4 ] (Wastes F3 & F4)

  Selective Repeat Retransmission:
  F0, F1, [F2 Lost], F3, F4  ===> Sender Retransmits: [ F2 ONLY ]    (F3 & F4 buffered!)

2. Sliding Window Sizes in Selective Repeat

In Selective Repeat, sequence numbers use $m$ bits (modulo $2^m$ , ranging from $0$ to $2^m - 1$ ).

Unlike GBN where $W_r = 1$ , both sender and receiver maintain active sliding windows:

W_s \leq 2^{m-1} \quad \text{and} \quad W_r = W_s \leq 2^{m-1}

  Sender Window (Ws <= 2^(m-1)):
  ... [ 0   1   2   3 ] 4   5   6   7 ...

  Receiver Window (Wr <= 2^(m-1)):
  ... [ 0   1   2   3 ] 4   5   6   7 ...
  (Receiver holds internal memory buffers for all Wr slots)

3. Why Must $W_s = W_r \leq 2^{m-1}$ in Selective Repeat?

This is one of the most frequently asked theoretical proofs in networking examinations.

Proof by Contradiction:

Suppose $m = 2$ bits (sequence numbers: $0, 1, 2, 3$ , modulo 4).
Assume we violate the rule and set $W_s = W_r = 3$ (which is $> 2^{2-1} = 2$ ).

Initial State:
- Sender window: [0, 1, 2].
- Receiver window: [0, 1, 2].
Sender transmits frames 0, 1, 2.
Receiver receives all 3 frames correctly, buffers them, delivers them to the application layer, and slides its window forward by 3:

\text{New Receiver Window} = [3, 0, 1]

Receiver sends acknowledgments ACK 0, ACK 1, ACK 2.
Catastrophic Failure: All 3 ACKs are lost in transit due to line noise!
Sender's timer for Frame 0 expires. Sender retransmits Frame 0.
Receiver receives Frame 0. Looking at its active window [3, 0, 1], Slot 0 is open!
The receiver erroneously assumes this is the brand-new Frame 0 of the next cycle, accepts it, and places it into the buffer!
Result: Duplicate data delivered to the application layer, silently corrupting the file!

Conclusion:

To avoid ambiguity between duplicate old frames and fresh new frames, the sum of sender and receiver windows must never exceed the sequence space:

W_s + W_r \leq 2^m

Since optimal performance requires $W_s = W_r$ :

2 W_s \leq 2^m \implies \mathbf{W_s \leq 2^{m-1}}

4. Operational Mechanics of Selective Repeat

  SENDER (Ws = 4)                                     RECEIVER (Wr = 4)
    |                                                    |
    |---- Frame 0 -------------------------------------->| (Accept & Deliver to App)
    |---- Frame 1 -------------------------------------->| (Accept & Deliver to App)
    |---- Frame 2 ----- X (LOST!)                        |
    |---- Frame 3 -------------------------------------->| (Out of order! BUFFER F3, Send NAK 2)
    |                                                    |
    |<--- ACK 0, ACK 1 ----------------------------------|
    |<--- NAK 2 (Negative ACK for F2) -------------------|
    |                                                    |
    | [ Retransmits Frame 2 ONLY! ]                      |
    |---- Frame 2 -------------------------------------->| (Accept F2! Reorder [F2, F3])
    |                                                    | (Deliver F2 & F3 together to App)
    |<--- ACK 3 (Cumulative ACK up to 3) ----------------|

Individual Retransmission Timers:
- The sender runs an independent countdown timer for every transmitted frame.
- Only the frame whose individual timer expires is retransmitted.
Negative Acknowledgment (NAK):
- When the receiver detects a gap in arriving sequence numbers (e.g., receives Frame 3 when expecting Frame 2), it immediately generates a NAK 2, prompting an instant fast retransmit before the sender's timeout.
Buffering & In-Order Delivery:
- Arriving frames within the receive window are stored in temporary buffers.
- Once the missing frames arrive, the buffer is sorted sequentially and delivered in contiguous order to the network layer.

5. Comprehensive Comparison: ARQ Protocols

Feature	Stop-and-Wait ARQ	Go-Back-N ARQ	Selective Repeat ARQ
Sender Window Size ( $W_s$ )	$1$	$\leq 2^m - 1$	$\leq 2^{m-1}$
Receiver Window Size ( $W_r$ )	$1$	$1$	$W_s \leq 2^{m-1}$
Out-of-Order Frames	Not possible	Discarded immediately	Buffered in receiver memory
Retransmissions	Single frame	Entire window ( $N$ frames)	Only the lost frame
Number of Timers	1 timer	1 timer (for oldest frame)	$W_s$ independent timers
Acknowledgment Type	Individual ACK	Cumulative ACK	Individual ACK / NAK / Cumulative
Complexity & Cost	Minimal	Low	High (buffer & timer management)
Bandwidth Efficiency	Lowest ( $\frac{1}{1+2a}$ )	Moderate ( $\frac{W_s}{1+2a}$ )	Highest (approaches $100\%$ )

6. Key Exam Questions & Numericals

If sequence numbers are 4 bits wide ( $m = 4$ ), what are the maximum sender window sizes for Go-Back-N and Selective Repeat?
- Total sequence space: $2^4 = 16$ (values $0$ to $15$ ).
- For Go-Back-N: $W_s = 2^m - 1 = 16 - 1 = \mathbf{15}$ .
- For Selective Repeat: $W_s = 2^{m-1} = 2^3 = \mathbf{8}$ .
Why does Selective Repeat require more buffer memory at the receiver than Go-Back-N?
- In GBN, the receiver discards any frame that does not match the exact next expected sequence number ( $W_r = 1$ , zero buffer). In Selective Repeat, the receiver must store up to $W_r$ out-of-order frames until missing predecessors arrive.
What is the condition on sequence number space for Selective Repeat?
- $W_s + W_r \leq 2^m$ . With symmetric windows ( $W_s = W_r$ ), $W_s \leq 2^{m-1}$ .

Selective Repeat ARQ