7a:Tf86,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_end7b:Tb69,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_end72:{"json":{"id":"seed_ba0508c1a13026efebf934f9cbdf2d25","slug":"selective-repeat-arq","category":"Computer Networks","topic":"Selective Repeat ARQ","title":"Selective Repeat ARQ: Efficient Retransmission Protocol","description":"Master the Selective Repeat ARQ protocol—the most efficient sliding window protocol that retransmits only lost frames. Explore its sophisticated mechanism for handling out-of-order delivery, receiver buffering, and the precise window size constraints that prevent sequence number ambiguity.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_7a3f1f7ba4b295843b99eb61470a3902","title":"Selective Repeat Operation","order":0,"content":[{"id":"opening-hook","title":"The Selective Precision Paradigm","content":[{"data":{"content":"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.\n\n**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.\n\nThis 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."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"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.","variant":"info"},"type":"callout"}]},{"id":"gbn-limitations","title":"The Problem with Go-Back-N","content":[{"data":{"content":"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:\n\n**Go-Back-N's Retransmission Behavior:**\n\nWhen a frame is lost or corrupted in Go-Back-N:\n1. The receiver discards **all subsequent frames**, even if they arrive correctly\n2. The sender's timer expires for the lost frame\n3. The sender retransmits **the lost frame AND all frames sent after it**\n\nConsider a window size of 8 where frame 3 is lost:\n- Frames 4, 5, 6, 7, 8, 9, 10 arrive correctly but are **discarded**\n- After timeout, sender retransmits frames 3, 4, 5, 6, 7, 8, 9, 10\n- If frame 5 is now lost on retransmission, the cycle repeats\n\nThis creates a multiplicative penalty where each error causes O(W) retransmissions, where W is the window size."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Go-Back-N Efficiency Degradation Analysis","headers":["Error Rate (p)","Window Size","Expected Retransmissions per Error","Effective Bandwidth Waste"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"The High-BDP Problem","content":"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.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Core Inefficiency:**\n\nGo-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.\n\n**What We Actually Need:**"},"type":"text"},{"data":{"rows":[["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"]],"headers":["Requirement","Go-Back-N","What We Want"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"sr-core-concept","title":"Selective Repeat: The Core Concept","content":[{"data":{"content":"**Selective Repeat ARQ** is a sliding window protocol where:\n\n> **Only the specific frames that are lost or corrupted are retransmitted.**\n\nThis simple statement has profound implications for both sender and receiver design:\n\n**Key Principles:**\n\n1. **Selective Retransmission** — The sender retransmits **only** those frames that have not been acknowledged, never frames that were successfully received.\n\n2. **Out-of-Order Acceptance** — The receiver accepts frames that arrive out of sequence and buffers them until missing frames arrive.\n\n3. **Individual Acknowledgments** — Each frame is acknowledged individually (not cumulatively), so the sender knows exactly which frames made it.\n\n4. **Per-Frame Timers** — Each outstanding frame has its own timeout timer, allowing independent retransmission decisions.\n\n5. **Window Synchronization** — Both sender and receiver maintain synchronized windows into the sequence number space."},"type":"text"},{"data":{"height":"450px","mermaidSyntax":"sequenceDiagram\n participant S as Sender\n participant N as Network\n participant R as Receiver\n \n Note over S,R: Window Size = 4, Sequence Numbers 0-7\n \n S->>N: Frame 0\n S->>N: Frame 1\n S->>N: Frame 2 (LOST)\n S->>N: Frame 3\n \n N->>R: Frame 0\n R-->>S: ACK 0\n N->>R: Frame 1\n R-->>S: ACK 1\n Note over R: Frame 2 missing, buffer Frame 3\n N->>R: Frame 3\n R-->>S: ACK 3 (Not 2!)\n \n Note over S: Timer for Frame 2 expires\n S->>N: Frame 2 (Retransmit ONLY Frame 2)\n N->>R: Frame 2\n R-->>S: ACK 2\n Note over R: Deliver Frames 2,3 in order"},"type":"mermaid-excalidraw"},{"data":{"icon":"Lightbulb","title":"The Fundamental Trade-off","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"sender-operation","title":"Sender Operation in Detail","content":[{"data":{"content":"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.\n\n**Sender State Variables:**"},"type":"text"},{"data":{"rows":[["`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"]],"headers":["Variable","Description"]},"type":"table"},{"data":{"content":"**Sender Window Boundaries:**\n\nThe sender window contains sequence numbers in the range:\n\n```\n[send_base, send_base + W - 1]\n```\n\n- Frames with sequence numbers **less than send_base** have been sent AND acknowledged\n- Frames with sequence numbers in **[send_base, next_seqnum - 1]** have been sent but not yet acknowledged\n- Frames with sequence numbers in **[next_seqnum, send_base + W - 1]** can be sent immediately\n- Frames with sequence numbers **≥ send_base + W** must wait for the window to advance"},"type":"text"},{"data":{"fileName":"selective_repeat_sender.py","languages":[{"code":"$7a","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"Timer Complexity","content":"Managing 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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"sender-events","title":"Sender Event Processing","content":[{"data":{"content":"The Selective Repeat sender must handle three distinct events. Each event triggers a specific, well-defined response:\n\n**Event 1: Data from Application Layer**\n\nWhen the upper layer has data to send:\n\n```\nIF (next_seqnum < send_base + W) THEN\n // Window has room\n Create frame with sequence number = next_seqnum\n Store frame in buffer[next_seqnum]\n Start timer[next_seqnum]\n Send frame to network\n next_seqnum = next_seqnum + 1\nELSE\n // Window full, refuse data or buffer at application\n Signal \"window full\" to application\nENDIF\n```"},"type":"text"},{"data":{"content":"**Event 2: ACK Received**\n\nWhen an acknowledgment arrives for frame n:\n\n```\nIF (n is within [send_base, send_base + W - 1]) THEN\n Mark frame n as acknowledged\n Stop timer[n]\n \n IF (n == send_base) THEN\n // Slide window forward over consecutive ACKed frames\n WHILE (frame at send_base is marked as ACKed) DO\n Advance send_base by 1\n END WHILE\n ENDIF\nENDIF\n```\n\n**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."},"type":"text"},{"data":{"content":"**Event 3: Timeout for Frame n**\n\nWhen timer[n] expires:\n\n```\n// Retransmit ONLY frame n — this is the key SR behavior\nResend frame n from buffer[n]\nRestart timer[n]\n```\n\nThe 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**."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Comparison of Sender Timeout Behavior","headers":["Protocol","On Timeout for Frame n","Frames Retransmitted","Timer Restart"]},"type":"table"}],"titleType":"number","titleNumber":4},{"id":"receiver-operation","title":"Receiver Operation in Detail","content":[{"data":{"content":"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.\n\n**Receiver State Variables:**"},"type":"text"},{"data":{"rows":[["`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"]],"headers":["Variable","Description"]},"type":"table"},{"data":{"content":"**Receiver Window:**\n\nThe 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."},"type":"text"},{"data":{"fileName":"selective_repeat_receiver.py","languages":[{"code":"$7b","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":5},{"id":"re-ack-mechanism","title":"The Critical Re-ACK Mechanism","content":[{"data":{"content":"One 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.\n\n**The Scenario:**\n\nConsider what happens when an ACK is lost:\n\n1. Sender sends Frame 0, Frame 1, Frame 2\n2. Receiver receives all three, sends ACK 0, ACK 1, ACK 2\n3. ACK 0 is lost in transit\n4. Sender's timer for Frame 0 expires\n5. Sender retransmits Frame 0\n\n**Without Re-ACK:**\n\nIf 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.\n\n**With Re-ACK (Correct Behavior):**\n\nThe 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."},"type":"text"},{"data":{"height":"400px","mermaidSyntax":"sequenceDiagram\n participant S as Sender\n participant R as Receiver\n \n Note over S,R: Normal transmission\n S->>R: Frame 0\n S->>R: Frame 1\n R-->>S: ACK 0 (LOST!)\n R-->>S: ACK 1\n \n Note over S: Timeout for Frame 0\n S->>R: Frame 0 (retransmit)\n \n Note over R: Frame 0 in previous window\nAlready delivered, but re-ACK!\n R-->>S: ACK 0 (re-acknowledgment)\n \n Note over S: Now can advance window!"},"type":"mermaid-excalidraw"},{"data":{"icon":"AlertCircle","title":"Window Overlap is Essential","content":"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.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"protocol-walkthrough","title":"Complete Protocol Walkthrough","content":[{"data":{"content":"Let's trace through a complete Selective Repeat scenario to solidify understanding. We'll use:\n- **Window size W = 4**\n- **Sequence numbers 0-7** (3 bits, space of 8)\n- Frame 2 will be lost\n\n**Initial State:**\n- Sender: send_base = 0, next_seqnum = 0\n- Receiver: recv_base = 0"},"type":"text"},{"data":{"rows":[["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!"]],"caption":"Step-by-Step Protocol Execution","headers":["Step","Event","Sender State","Receiver State","Network"]},"type":"table"},{"data":{"icon":"CheckCircle","title":"Efficiency Achieved","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Selective Repeat Operation","content":[{"data":{"content":"We've covered the complete operational mechanics of Selective Repeat ARQ. Let's consolidate the key concepts:"},"type":"text"},{"data":{"type":"ordered","items":["**Selective retransmission** — Only lost/unacknowledged frames are retransmitted, never correctly-received frames.","**Individual acknowledgments** — Each frame gets its own ACK; no cumulative acknowledgments.","**Receiver buffering** — The receiver stores out-of-order frames until gaps are filled.","**Per-frame timers** — The sender maintains independent timeout timers for each outstanding frame.","**Re-acknowledgment** — Frames in the previous window are re-ACKed to handle lost ACKs.","**Window synchronization** — Both sender and receiver maintain identical window sizes."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn 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."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_5123223833ab83944451e13deca16ca1","title":"Individual ACKs: The Precision Acknowledgment Strategy","order":1,"content":null,"isLocked":true},{"id":"seed_f1d0e978fe8f7a3a7a79fdf86b541f3c","title":"Out-of-Order Delivery: Handling Sequence Gaps","order":2,"content":null,"isLocked":true},{"id":"seed_9f9b29ebd725bb7a5cce9e95b1ca6db7","title":"Buffer Requirements: Memory Constraints and Sizing","order":3,"content":null,"isLocked":true},{"id":"seed_96190dbfe2d36e95e9a7063ab01c2f24","title":"Window Size Constraints: The 2W Rule","order":4,"content":null,"isLocked":true}]}}