OneNoughtOne
0/240
Loading content...
Read aloud is unavailable in this browser.
Imagine a factory shipping products where one box in every hundred gets damaged. Go-Back-N's approach would be to throw away all boxes received after the damaged one and request the entire shipment again—even if 99 boxes arrived perfectly. This is spectacularly wasteful.
Selective Repeat (SR) ARQ takes the intelligent approach: keep all correctly received boxes, buffer them temporarily, and request only the specific damaged box be re-sent. Once it arrives, assemble everything in order and deliver.
This seemingly obvious optimization represents a fundamental shift in protocol design philosophy—from simplicity at the receiver to efficiency in the network. Selective Repeat trades receiver complexity for dramatically improved bandwidth utilization, especially on high-latency, error-prone links where Go-Back-N's wholesale retransmissions would be catastrophic.
By the end of this page, you will understand the complete operational mechanics of Selective Repeat ARQ—how senders track individual frame acknowledgments, how receivers buffer and reorder out-of-sequence frames, and why this approach represents the gold standard for reliable data transfer on challenging network links.
Before diving into Selective Repeat, we must understand precisely what problem it solves. Go-Back-N ARQ has a critical inefficiency that becomes devastating under certain conditions:
Go-Back-N's Retransmission Behavior:
When a frame is lost or corrupted in Go-Back-N:
Consider a window size of 8 where frame 3 is lost:
This creates a multiplicative penalty where each error causes O(W) retransmissions, where W is the window size.
| Error Rate (p) | Window Size | Expected Retransmissions per Error | Effective Bandwidth Waste |
|---|---|---|---|
| 1% | 8 | ~8 frames | ~7% overhead |
| 1% | 32 | ~32 frames | ~31% overhead |
| 5% | 8 | ~8 frames per 5% = ~40 extra/100 | ~40% bandwidth wasted |
| 5% | 64 | ~64 frames per 5% = ~320 extra/100 | Unusable (>300% overhead) |
| 10% | 32 | ~32 frames per 10% | Protocol effectively fails |
On satellite links with 500ms round-trip times, you need large windows (often 64+) to fully utilize bandwidth. With Go-Back-N on such links, even a 1% error rate causes 60%+ of bandwidth to be wasted on unnecessary retransmissions. Selective Repeat becomes essential, not optional.
The Core Inefficiency:
Go-Back-N assumes the receiver has no ability to store out-of-order frames. This was historically accurate for simple hardware implementations, but modern systems universally have sufficient memory to buffer received frames.
What We Actually Need:
| Requirement | Go-Back-N | What We Want |
|---|---|---|
| Retransmit lost frames | ✓ Yes (plus extras) | Only lost frames |
| Accept out-of-order delivery at receiver | ✗ No | ✓ Yes |
| Per-frame acknowledgments | ✗ Cumulative only | ✓ Individual ACKs |
| Receiver buffering | ✗ None | ✓ Buffer out-of-order frames |
| Sender per-frame timers | ✗ Single timer | ✓ Individual timers |
Selective Repeat ARQ is a sliding window protocol where:
Only the specific frames that are lost or corrupted are retransmitted.
This simple statement has profound implications for both sender and receiver design:
Key Principles:
Selective Retransmission — The sender retransmits only those frames that have not been acknowledged, never frames that were successfully received.
Out-of-Order Acceptance — The receiver accepts frames that arrive out of sequence and buffers them until missing frames arrive.
Individual Acknowledgments — Each frame is acknowledged individually (not cumulatively), so the sender knows exactly which frames made it.
Per-Frame Timers — Each outstanding frame has its own timeout timer, allowing independent retransmission decisions.
Window Synchronization — Both sender and receiver maintain synchronized windows into the sequence number space.
Selective Repeat trades receiver simplicity for network efficiency. Go-Back-N receivers are trivial—just accept in-order frames. SR receivers must buffer, reorder, and track which frames were received. This complexity is universally worth it on modern hardware.
The Selective Repeat sender is significantly more complex than Go-Back-N because it must track the status of each individual frame rather than just maintaining a window boundary.
Sender State Variables:
| Variable | Description |
|---|---|
send_base | Sequence number of oldest unacknowledged frame |
next_seqnum | Sequence number to assign to next new frame |
window_size (W) | Maximum number of outstanding unacknowledged frames |
frame_status[i] | Status of each frame: UNSENT, SENT, ACKED |
timer[i] | Individual retransmission timer for each frame |
buffer[i] | Stored copy of each sent but unacknowledged frame |
Sender Window Boundaries:
The sender window contains sequence numbers in the range:
[send_base, send_base + W - 1]
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
class SelectiveRepeatSender: def __init__(self, window_size: int, seq_num_bits: int): self.W = window_size self.max_seq = 2 ** seq_num_bits # Sequence number space size self.send_base = 0 self.next_seqnum = 0 # Per-frame tracking self.frame_status = {} # seq_num -> 'unsent' | 'sent' | 'acked' self.frame_buffer = {} # seq_num -> frame data self.timers = {} # seq_num -> Timer object def can_send(self) -> bool: """Check if sender can transmit a new frame.""" # Window allows sending if next_seqnum is within window outstanding = (self.next_seqnum - self.send_base) % self.max_seq return outstanding < self.W def send_frame(self, data: bytes) -> int: """Send a new frame, returns sequence number assigned.""" if not self.can_send(): raise WindowFullError("Sender window full, cannot send") seq = self.next_seqnum frame = create_frame(seq, data) # Store frame for potential retransmission self.frame_buffer[seq] = frame self.frame_status[seq] = 'sent' # Start individual timer for this frame self.timers[seq] = Timer( timeout=RETRANSMISSION_TIMEOUT, callback=lambda: self.timeout_handler(seq) ) self.timers[seq].start() # Transmit frame network_send(frame) # Advance next sequence number self.next_seqnum = (self.next_seqnum + 1) % self.max_seq return seq def receive_ack(self, ack_num: int): """Handle receipt of an acknowledgment.""" # Check if ACK is within current window if not self.in_window(ack_num): return # Ignore ACKs outside window (could be duplicate) # Mark frame as acknowledged if ack_num in self.frame_status and self.frame_status[ack_num] == 'sent': self.frame_status[ack_num] = 'acked' # Stop timer for this frame if ack_num in self.timers: self.timers[ack_num].stop() del self.timers[ack_num] # Free buffer for this frame if ack_num in self.frame_buffer: del self.frame_buffer[ack_num] # Advance send_base if oldest frame is now acknowledged self.advance_window() def advance_window(self): """Slide window forward over consecutively ACKed frames.""" while self.send_base != self.next_seqnum: if self.frame_status.get(self.send_base) == 'acked': # Clean up tracking for this frame del self.frame_status[self.send_base] self.send_base = (self.send_base + 1) % self.max_seq else: break # Stop at first unacknowledged frame def timeout_handler(self, seq_num: int): """Handle timeout for a specific frame - retransmit ONLY that frame.""" if seq_num in self.frame_buffer: # Retransmit the specific frame frame = self.frame_buffer[seq_num] network_send(frame) # Restart timer for this frame self.timers[seq_num] = Timer( timeout=RETRANSMISSION_TIMEOUT, callback=lambda: self.timeout_handler(seq_num) ) self.timers[seq_num].start() def in_window(self, seq_num: int) -> bool: """Check if sequence number is within current window.""" # Handle wraparound in sequence number space window_start = self.send_base window_end = (self.send_base + self.W - 1) % self.max_seq if window_start <= window_end: return window_start <= seq_num <= window_end else: # Window wraps around return seq_num >= window_start or seq_num <= window_endManaging individual timers for each frame adds significant complexity. Real implementations often use a single timer with a sorted list of timeout events, or timer wheels for efficiency with many outstanding frames.
The Selective Repeat sender must handle three distinct events. Each event triggers a specific, well-defined response:
Event 1: Data from Application Layer
When the upper layer has data to send:
IF (next_seqnum < send_base + W) THEN
// Window has room
Create frame with sequence number = next_seqnum
Store frame in buffer[next_seqnum]
Start timer[next_seqnum]
Send frame to network
next_seqnum = next_seqnum + 1
ELSE
// Window full, refuse data or buffer at application
Signal "window full" to application
ENDIF
Event 2: ACK Received
When an acknowledgment arrives for frame n:
IF (n is within [send_base, send_base + W - 1]) THEN
Mark frame n as acknowledged
Stop timer[n]
IF (n == send_base) THEN
// Slide window forward over consecutive ACKed frames
WHILE (frame at send_base is marked as ACKed) DO
Advance send_base by 1
END WHILE
ENDIF
ENDIF
Critical Observation: The window only advances when send_base itself is acknowledged. If frames 0, 2, 3 are ACKed but frame 1 is missing, send_base stays at 1 until frame 1's ACK arrives.
Event 3: Timeout for Frame n
When timer[n] expires:
// Retransmit ONLY frame n — this is the key SR behavior
Resend frame n from buffer[n]
Restart timer[n]
The beauty of Selective Repeat is in this timeout handler. Unlike Go-Back-N which would retransmit n, n+1, n+2, ... , SR retransmits only the specific frame that timed out.
| Protocol | On Timeout for Frame n | Frames Retransmitted | Timer Restart |
|---|---|---|---|
| Stop-and-Wait | Resend frame n | 1 frame | Single timer restarted |
| Go-Back-N | Resend frames n, n+1, ..., next_seqnum-1 | All in-flight frames (up to W) | Single timer restarted |
| Selective Repeat | Resend ONLY frame n | 1 frame | Timer[n] restarted only |
The Selective Repeat receiver is considerably more complex than its Go-Back-N counterpart. It must maintain a sliding window, buffer out-of-order frames, and carefully manage delivery to the upper layer.
Receiver State Variables:
| Variable | Description |
|---|---|
recv_base | Sequence number of next frame expected (in-order) |
window_size (W) | Size of receiver window (same as sender) |
received[i] | Boolean indicating if frame i has been received |
buffer[i] | Storage for out-of-order frames |
Receiver Window:
The receiver maintains a window spanning [recv_base, recv_base + W - 1]. Any frame arriving within this window is accepted and acknowledged. The critical insight is that the receiver window must be the same size as the sender window.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
class SelectiveRepeatReceiver: def __init__(self, window_size: int, seq_num_bits: int): self.W = window_size self.max_seq = 2 ** seq_num_bits self.recv_base = 0 # Track which frames in window have been received self.received = {} # seq_num -> True if received self.buffer = {} # seq_num -> frame data def receive_frame(self, frame): """Process a received frame.""" seq_num = frame.sequence_number # Case 1: Frame is within receiver window [recv_base, recv_base + W - 1] if self.in_window(seq_num): # Always send ACK for frames in window send_ack(seq_num) # If not already received (avoid duplicates) if not self.received.get(seq_num, False): self.received[seq_num] = True self.buffer[seq_num] = frame.data # If this is recv_base, deliver consecutive frames if seq_num == self.recv_base: self.deliver_buffered_frames() # Case 2: Frame is in [recv_base - W, recv_base - 1] (previously ACKed) elif self.in_previous_window(seq_num): # This is a retransmission; our ACK was lost # Re-ACK to help sender (even though we already delivered it) send_ack(seq_num) # Case 3: Frame completely outside expected range else: # Ignore silently — corrupted or severely delayed pass def deliver_buffered_frames(self): """Deliver consecutive in-order frames to upper layer.""" while self.received.get(self.recv_base, False): # Deliver frame to application data = self.buffer[self.recv_base] deliver_to_upper_layer(data) # Clean up del self.received[self.recv_base] del self.buffer[self.recv_base] # Advance window self.recv_base = (self.recv_base + 1) % self.max_seq def in_window(self, seq_num: int) -> bool: """Check if seq_num is in [recv_base, recv_base + W - 1].""" window_start = self.recv_base window_end = (self.recv_base + self.W - 1) % self.max_seq if window_start <= window_end: return window_start <= seq_num <= window_end else: return seq_num >= window_start or seq_num <= window_end def in_previous_window(self, seq_num: int) -> bool: """Check if seq_num is in [recv_base - W, recv_base - 1].""" prev_start = (self.recv_base - self.W) % self.max_seq prev_end = (self.recv_base - 1) % self.max_seq if prev_start <= prev_end: return prev_start <= seq_num <= prev_end else: return seq_num >= prev_start or seq_num <= prev_endOne of the most subtle and critical aspects of Selective Repeat is the re-acknowledgment of previously received frames. This mechanism prevents the protocol from stalling when ACKs are lost.
The Scenario:
Consider what happens when an ACK is lost:
Without Re-ACK:
If the receiver ignores the retransmitted Frame 0 (since it already delivered it), the sender never learns Frame 0 was received. The sender would endlessly retransmit Frame 0.
With Re-ACK (Correct Behavior):
The receiver recognizes Frame 0 as a previously-ACKed frame (sequence number is in the previous window) and re-sends ACK 0. This allows the sender to finally mark Frame 0 as acknowledged and advance its window.
The receiver must track frames in BOTH the current window AND the previous window. Frames in the previous window are re-ACKed but not buffered again. This is why the total sequence number space must be at least 2W—to distinguish current from previous window frames.
Let's trace through a complete Selective Repeat scenario to solidify understanding. We'll use:
Initial State:
| Step | Event | Sender State | Receiver State | Network |
|---|---|---|---|---|
| 1 | Send Frame 0 | base=0, next=1, sent={0} | base=0, rcvd={} | Frame 0 in transit |
| 2 | Send Frame 1 | base=0, next=2, sent={0,1} | base=0, rcvd={} | Frames 0,1 in transit |
| 3 | Send Frame 2 | base=0, next=3, sent={0,1,2} | base=0, rcvd={} | Frame 2 LOST |
| 4 | Send Frame 3 | base=0, next=4, sent={0,1,2,3} | base=0, rcvd={} | Frames 0,1,3 in transit |
| 5 | Rcv Frame 0 | base=0, next=4 | base=1, rcvd={}, deliver F0 | ACK 0 sent |
| 6 | Rcv Frame 1 | base=0, next=4 | base=2, rcvd={}, deliver F1 | ACK 1 sent |
| 7 | Rcv Frame 3 | base=0, next=4 | base=2, rcvd={3}, buffer F3 | ACK 3 sent (NOT ACK 2!) |
| 8 | Rcv ACK 0 | base=1, next=4, acked={0} | base=2, rcvd={3} | Window slides |
| 9 | Rcv ACK 1 | base=2, next=4, acked={0,1} | base=2, rcvd={3} | Window slides |
| 10 | Rcv ACK 3 | base=2, next=4, acked={0,1,3} | base=2, rcvd={3} | F3 acked, base stays at 2 |
| 11 | Timeout F2 | Retransmit ONLY F2 | base=2, rcvd={3} | F2 (retransmit) in transit |
| 12 | Rcv Frame 2 | base=2, next=4 | base=4, rcvd={}, deliver F2,F3 | ACK 2 sent |
| 13 | Rcv ACK 2 | base=4, next=4, all acked | base=4, rcvd={} | Complete! |
Notice that only Frame 2 was retransmitted—not Frames 2, 3 as Go-Back-N would require. When Frame 2 arrived, the receiver immediately delivered both Frame 2 and the buffered Frame 3 to the upper layer.
We've covered the complete operational mechanics of Selective Repeat ARQ. Let's consolidate the key concepts:
What's Next:
In the next page, we'll explore Individual ACKs in depth—the acknowledgment strategy that enables Selective Repeat's efficiency. We'll examine the protocol messages, ACK formats, and the precise semantics that distinguish SR acknowledgments from Go-Back-N's cumulative approach.
You now understand how Selective Repeat ARQ operates—the sender's per-frame tracking, the receiver's buffering and reordering, and the elegant selective retransmission mechanism. Next, we'll dive deeper into the individual acknowledgment scheme that makes it all work.