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:

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

---

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:

---

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

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

4. Receiver sends acknowledgments ACK 0, ACK 1, ACK 2.
5. Catastrophic Failure: All 3 ACKs are lost in transit due to line noise!
6. Sender's timer for Frame 0 expires. Sender retransmits Frame 0.
7. Receiver receives Frame 0. Looking at its active window [3, 0, 1], Slot 0 is open!
8. The receiver erroneously assumes this is the brand-new Frame 0 of the next cycle, accepts it, and places it into the buffer!
9. 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:

Since optimal performance requires $W_s = W_r$:

---

4. Operational Mechanics of Selective Repeat

1. Individual Retransmission Timers:
   • The sender runs an independent countdown timer for every transmitted frame.
   • Only the frame whose individual timer expires is retransmitted.
2. 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.
3. 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\%$)

---