Selective Repeat Arq - Learning Module

Loading content...

0/228

Out-of-Order Delivery: Handling Sequence Gaps

Embracing Network Disorder

The Internet is chaotic. Packets sent in sequence A, B, C, D might arrive as B, D, A, C—or some might not arrive at all. Go-Back-N's response to this chaos is brutally simple: discard everything that arrives out of order. This simplicity comes at a severe efficiency cost.

Selective Repeat embraces the chaos. When frame 5 arrives before frame 3, the receiver doesn't panic and throw away perfectly good data. Instead, it:

Accepts frame 5
Buffers it safely
Continues waiting for frame 3
When frame 3 finally arrives, delivers both frames 3 and 5 in correct order

This page examines exactly how out-of-order acceptance works—the receiving window, buffering mechanisms, and the precise conditions under which data is finally delivered to the application.

What You Will Learn

By the end of this page, you will understand how Selective Repeat receivers handle out-of-order arrivals—the receiver window management, framing buffering strategies, gap detection, and the in-order delivery guarantee to higher layers.

Why Frames Arrive Out of Order

Before examining how SR handles disorder, let's understand why it occurs. Frames can arrive out of sequence due to several network phenomena:

1. Multi-Path Routing

In packet-switched networks, consecutive packets may take different paths:

Frame 0: Router A → Router B → Router D (3 hops, 20ms)
Frame 1: Router A → Router C → Router E → Router D (4 hops, 25ms)
Frame 2: Router A → Router B → Router D (3 hops, 18ms)

Arrival order: Frame 0, Frame 2, Frame 1

2. Variable Queuing Delays

Even on the same path, router queue lengths vary:

Frame 0: Hits congested router, waits 50ms in queue
Frame 1: Same router is now clear, waits only 5ms

Result: Frame 1 arrives before Frame 0

3. Retransmission of Old Frames

If a frame is retransmitted (due to timeout), it may arrive after newer frames:

Original Frame 3: Lost completely
Frame 4, 5, 6: Arrive successfully
Retransmitted Frame 3: Finally arrives

Arrival order: 4, 5, 6, 3

Network Conditions Causing Reordering
Condition	Cause	Typical Reorder Distance	Prevalence
Multi-path routing	Load balancing, ECMP	1-5 packets	Common in datacenters
Router congestion	Variable queue delays	1-2 packets	Very common
Link flapping	Route changes mid-stream	Many packets	Rare but severe
Retransmission	Timeout-triggered resend	Up to window size	Proportional to loss rate
Priority queuing	QoS differentiation	Varies	Enterprise networks

Data Link Layer vs Network Layer

At the data link layer (e.g., HDLC), reordering is less common since it's point-to-point. However, with virtual circuits over complex infrastructure, reordering can still occur. The SR protocol handles it regardless of cause.

The Receiver Window

The receiver window is the range of sequence numbers that the receiver is willing to accept. Any frame with a sequence number within this window is considered valid and will be processed.

Receiver Window Definition:

Receiver Window = [recv_base, recv_base + W - 1]

Where:
  recv_base = sequence number of next expected in-order frame
  W = window size (same as sender window size)

Example with W=4, recv_base=3:

Sequence Numbers: 0  1  2  [3  4  5  6]  7  0  1  2  ...
                         ↑   ←Window→   ↑
                      recv_base        recv_base + W - 1

Acceptable: 3, 4, 5, 6
Not acceptable: 0, 1, 2, 7 (would be in previous or future window)

Why Does the Receiver Need a Window?

Unlike Go-Back-N where the receiver only accepts the single next expected frame, SR's receiver must:

Accept out-of-order frames — Frame 5 might arrive before frame 3
Buffer multiple frames — Store frames 4, 5, 6 while waiting for frame 3
Bound the buffering — Can't buffer infinitely; window limits outstanding buffered frames
Prevent sequence ambiguity — Window ensures we can distinguish new frames from old duplicates

The Window Invariant:

At all times, the receiver guarantees:

All frames with sequence numbers less than recv_base have been received, delivered to the upper layer, and acknowledged.

Frames within [recv_base, recv_base + W - 1] may or may not have been received; those that have are buffered until all preceding frames arrive.

Converting Mermaid diagram...

Frame Acceptance Logic

When a frame arrives at the receiver, it must be classified into one of three categories based on its sequence number. Each category triggers different behavior:

Category 1: Within Current Window [recv_base, recv_base + W - 1]

Action: Accept the frame, send ACK
If seq == recv_base: attempt to deliver to upper layer
If seq > recv_base: buffer for later delivery
If already received: duplicate, ACK but don't re-buffer

Category 2: Within Previous Window [recv_base - W, recv_base - 1]

Action: Re-send ACK, do NOT buffer
This frame was already delivered; the retransmission is due to ACK loss
Receiver must help sender by re-acknowledging

Category 3: Outside Both Windows

Action: Silently discard
Either severely delayed or has corrupted sequence number
ACKing would violate protocol correctness

frame_acceptance.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
class FrameClassifier:
    """
    Classifies received frames based on receiver window position.
    Essential for correct Selective Repeat behavior.
    """
    
    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
        
    def classify(self, seq_num: int) -> str:
        """
        Classify a received frame's sequence number.
        
        Returns one of:
          - 'CURRENT_WINDOW': Accept and possibly buffer
          - 'PREVIOUS_WINDOW': Re-ACK, already delivered
          - 'OUT_OF_RANGE': Discard silently
        """
        # Current window check: [recv_base, recv_base + W - 1]
        current_start = self.recv_base
        current_end = (self.recv_base + self.W - 1) % self.max_seq
        
        if self._in_range(seq_num, current_start, current_end):
            return 'CURRENT_WINDOW'
        
        # Previous window check: [recv_base - W, recv_base - 1]
        # Note: In modular arithmetic, recv_base - W might wrap around
        prev_start = (self.recv_base - self.W) % self.max_seq
        prev_end = (self.recv_base - 1) % self.max_seq
        
        if self._in_range(seq_num, prev_start, prev_end):
            return 'PREVIOUS_WINDOW'
        
        return 'OUT_OF_RANGE'
    
    def _in_range(self, seq: int, start: int, end: int) -> bool:
        """Check if seq is in [start, end] with wraparound."""
        if start <= end:
            return start <= seq <= end
        else:  # Range wraps around max_seq
            return seq >= start or seq <= end
 
 
class SRReceiverFrameHandler:
    """Complete frame handling logic for Selective Repeat receiver."""
    
    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
        
        # Tracking received frames in current window
        self.received = {}  # seq_num -> True
        self.buffer = {}    # seq_num -> frame data
        
        self.classifier = FrameClassifier(window_size, seq_num_bits)
        
    def handle_frame(self, frame) -> dict:
        """
        Process a received frame.
        
        Returns dict with:
          - 'action': What was done ('accepted', 'reacked', 'discarded')
          - 'delivered': List of frames delivered to upper layer
          - 'ack_sent': Sequence number ACKed (or None)
        """
        seq = frame.sequence_number
        category = self.classifier.classify(seq)
        
        if category == 'CURRENT_WINDOW':
            return self._handle_current_window(frame)
            
        elif category == 'PREVIOUS_WINDOW':
            return self._handle_previous_window(frame)
            
        else:  # OUT_OF_RANGE
            return {
                'action': 'discarded',
                'delivered': [],
                'ack_sent': None
            }
    
    def _handle_current_window(self, frame) -> dict:
        """Handle frame within current receiver window."""
        seq = frame.sequence_number
        delivered = []
        
        # Always ACK frames in current window
        send_ack(seq)
        
        # Check for duplicate
        if not self.received.get(seq, False):
            # New frame - mark received and buffer
            self.received[seq] = True
            self.buffer[seq] = frame.data
            
            # If this is recv_base, try to deliver consecutive frames
            if seq == self.recv_base:
                delivered = self._deliver_consecutive()
        
        return {
            'action': 'accepted',
            'delivered': delivered,
            'ack_sent': seq
        }
    
    def _handle_previous_window(self, frame) -> dict:
        """Handle frame from previous window (retransmission)."""
        seq = frame.sequence_number
        
        # Re-ACK but don't buffer (already delivered)
        send_ack(seq)
        
        return {
            'action': 'reacked',
            'delivered': [],
            'ack_sent': seq
        }
    
    def _deliver_consecutive(self) -> list:
        """Deliver all consecutive frames starting from recv_base."""
        delivered = []
        
        while self.received.get(self.recv_base, False):
            # Deliver this frame to upper layer
            data = self.buffer.pop(self.recv_base)
            deliver_to_upper_layer(data)
            delivered.append(self.recv_base)
            
            # Clean up tracking
            del self.received[self.recv_base]
            
            # Advance window and classifier base
            self.recv_base = (self.recv_base + 1) % self.max_seq
            self.classifier.recv_base = self.recv_base
        
        return delivered

Buffering Out-of-Order Frames

The receiver buffer is the core data structure enabling out-of-order acceptance. It must efficiently support:

Insertion — Store frames as they arrive out of order
Lookup — Check if a specific sequence number has been received
Consecutive delivery — Extract and deliver frames in order
Space efficiency — Minimize memory for potentially sparse sequences

Buffer Implementation Options:

Implementation	Insert	Lookup	Memory	Best For
Fixed array	O(1)	O(1)	O(max_seq)	Small sequence spaces
Hash map	O(1) avg	O(1) avg	O(buffered)	Large/sparse sequences
Circular buffer	O(1)	O(1)	O(W)	Window-bounded (typical)

receiver_buffer.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class SelectiveRepeatBuffer:
    """
    Circular buffer for Selective Repeat receiver.
    Efficiently handles out-of-order frame storage and in-order delivery.
    
    Memory usage is O(W) where W is window size, regardless of sequence space.
    """
    
    def __init__(self, window_size: int, max_frame_size: int = 1500):
        self.W = window_size
        self.max_frame_size = max_frame_size
        
        # Pre-allocated circular buffer
        # Index is derived from sequence number modulo W
        self.slots = [None] * window_size
        self.received_flags = [False] * window_size
        
        self.recv_base = 0
        self.max_seq = window_size * 2  # Minimum required sequence space
        
    def _slot_index(self, seq_num: int) -> int:
        """Map sequence number to buffer slot."""
        return seq_num % self.W
    
    def store(self, seq_num: int, data: bytes) -> bool:
        """
        Store an out-of-order frame.
        
        Returns:
            True if stored successfully
            False if slot occupied (duplicate) or out of window
        """
        # Validate within current window
        if not self._in_current_window(seq_num):
            return False
        
        slot = self._slot_index(seq_num)
        
        # Check for duplicate
        if self.received_flags[slot]:
            # Already have this slot filled
            # Could be same seq (duplicate) or window wraparound conflict
            return False
        
        # Store frame
        self.slots[slot] = data
        self.received_flags[slot] = True
        return True
    
    def is_received(self, seq_num: int) -> bool:
        """Check if a sequence number has been received and buffered."""
        slot = self._slot_index(seq_num)
        return self.received_flags[slot]
    
    def deliver_consecutive(self) -> list:
        """
        Extract and return all consecutive frames starting from recv_base.
        Updates recv_base as frames are delivered.
        
        Returns:
            List of (seq_num, data) tuples in order
        """
        delivered = []
        
        while True:
            slot = self._slot_index(self.recv_base)
            
            if not self.received_flags[slot]:
                # Gap found - stop delivery
                break
            
            # Extract frame
            data = self.slots[slot]
            delivered.append((self.recv_base, data))
            
            # Clear slot for reuse
            self.slots[slot] = None
            self.received_flags[slot] = False
            
            # Advance recv_base
            self.recv_base = (self.recv_base + 1) % self.max_seq
        
        return delivered
    
    def _in_current_window(self, seq_num: int) -> bool:
        """Check if seq_num is within [recv_base, recv_base + W - 1]."""
        distance = (seq_num - self.recv_base) % self.max_seq
        return distance < self.W
    
    def get_gaps(self) -> list:
        """Return list of sequence numbers in window that haven't been received."""
        gaps = []
        for i in range(self.W):
            seq = (self.recv_base + i) % self.max_seq
            slot = self._slot_index(seq)
            if not self.received_flags[slot]:
                gaps.append(seq)
        return gaps
    
    def get_status(self) -> str:
        """Return visual representation of buffer state."""
        status = []
        for i in range(self.W):
            seq = (self.recv_base + i) % self.max_seq
            slot = self._slot_index(seq)
            if self.received_flags[slot]:
                status.append(f"[{seq}:✓]")
            else:
                status.append(f"[{seq}:_]")
        return " ".join(status)

Memory Efficiency

The circular buffer uses only O(W) memory regardless of sequence number space size. With W=64 and 1500-byte frames, buffer needs only 96KB maximum—trivial for modern systems.

In-Order Delivery Guarantee

A critical invariant of Selective Repeat is:

Data is always delivered to the upper layer in sequence order.

Even though the receiver accepts and buffers out-of-order frames, it never delivers them out of order. The upper layer sees a perfectly ordered stream, unaware of the network disorder handled below.

The Delivery Algorithm:

when frame with seq == recv_base arrives:
    buffer[recv_base] = frame.data
    
    while buffer[recv_base] is filled:
        deliver buffer[recv_base] to upper layer
        clear buffer[recv_base]
        recv_base = recv_base + 1

This "delivery chain" only triggers when the expected frame (recv_base) arrives. Buffered frames beyond recv_base wait patiently.

Example: Out-of-Order Arrival and In-Order Delivery
Time	Event	Buffer State	Delivered
T1	Frame 0 arrives (expected)	[0:✓]	Frame 0
T2	Frame 2 arrives (out of order)	[_][2:✓]	None
T3	Frame 3 arrives (out of order)	[_][2:✓][3:✓]	None
T4	Frame 1 arrives (fills gap!)	[1:✓][2:✓][3:✓]	Frames 1, 2, 3
T5	Frame 5 arrives (out of order)	[_][5:✓]	None
T6	Frame 4 arrives (fills gap)	[4:✓][5:✓]	Frames 4, 5

Key Observations:

Batch delivery — When a gap is filled, multiple frames may be delivered at once
No partial delivery — We never skip a missing frame
recv_base only advances on delivery — Not on reception
Buffered frames are guaranteed to be delivered — Eventually, the missing frame arrives (or protocol times out)

The Upper Layer Is Unaware

From the application's perspective, data arrives as a perfect, ordered stream. All the buffering and reordering is invisible. This is the beauty of protocol layering—each layer handles its complexity internally.

Gap Detection and Handling

Gap detection is the process of recognizing when frames are missing. The receiver implicitly detects gaps when frames arrive out of order.

Implicit Gap Detection:

When frame N+k arrives before frame N:

The receiver buffers N+k
The absence of frames N, N+1, ..., N+k-1 is evident from the buffer
Gap = any sequence number in window that hasn't been marked as received

Gap Significance:

Gap Size	Meaning	Typical Response
1 frame	Single frame lost or delayed	Wait for timeout/retransmit
2-3 frames	Consecutive loss or reordering	Likely will resolve
Many frames	Severe congestion or link failure	May trigger fast recovery
Entire window	Complete outage	Wait for sender timeout

gap_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class GapAnalyzer:
    """
    Analyzes gaps in received frames for Selective Repeat.
    Can be used for debugging, statistics, or NAK generation.
    """
    
    def __init__(self, buffer: 'SelectiveRepeatBuffer'):
        self.buffer = buffer
        
    def get_gaps(self) -> list:
        """Return list of missing sequence numbers in window."""
        return self.buffer.get_gaps()
    
    def get_longest_gap(self) -> tuple:
        """
        Find the longest consecutive gap.
        
        Returns:
            (start_seq, length) or (None, 0) if no gaps
        """
        gaps = self.get_gaps()
        if not gaps:
            return (None, 0)
        
        # Find longest consecutive sequence in gaps
        longest_start = gaps[0]
        longest_len = 1
        curr_start = gaps[0]
        curr_len = 1
        
        for i in range(1, len(gaps)):
            expected = (gaps[i-1] + 1) % self.buffer.max_seq
            if gaps[i] == expected:
                curr_len += 1
            else:
                if curr_len > longest_len:
                    longest_start = curr_start
                    longest_len = curr_len
                curr_start = gaps[i]
                curr_len = 1
        
        if curr_len > longest_len:
            longest_start = curr_start
            longest_len = curr_len
        
        return (longest_start, longest_len)
    
    def get_buffer_utilization(self) -> float:
        """Return percentage of window slots in use."""
        gaps = len(self.get_gaps())
        filled = self.buffer.W - gaps
        return filled / self.buffer.W * 100
    
    def should_send_nak(self, gap_threshold: int = 3) -> list:
        """
        Determine which frames should have NAKs sent.
        
        Heuristic: After receiving 'gap_threshold' frames beyond
        a gap, assume the gap is due to loss, not reordering.
        
        Returns:
            List of sequence numbers to NAK
        """
        gaps = self.get_gaps()
        if not gaps:
            return []
        
        # Find frames received beyond the first gap
        first_gap = gaps[0] if gaps else None
        if first_gap is None:
            return []
        
        received_beyond = 0
        for i in range(1, self.buffer.W):
            seq = (first_gap + i) % self.buffer.max_seq
            if self.buffer.is_received(seq):
                received_beyond += 1
        
        if received_beyond >= gap_threshold:
            # First gap is likely lost, NAK it
            return [first_gap]
        
        return []
 
 
def visualize_receiver_state(buffer: 'SelectiveRepeatBuffer'):
    """Create ASCII visualization of receiver buffer state."""
    
    lines = []
    lines.append(f"recv_base = {buffer.recv_base}")
    lines.append("")
    
    # Show window graphically
    window_line = "Window: ["
    for i in range(buffer.W):
        seq = (buffer.recv_base + i) % buffer.max_seq
        if buffer.is_received(seq):
            window_line += f" {seq}✓"
        else:
            window_line += f" {seq}_ "
    window_line += " ]"
    lines.append(window_line)
    
    # Gap analysis
    analyzer = GapAnalyzer(buffer)
    gaps = analyzer.get_gaps()
    
    if gaps:
        lines.append(f"Gaps: {gaps}")
        start, length = analyzer.get_longest_gap()
        lines.append(f"Longest gap: {length} frames starting at seq {start}")
    else:
        lines.append("No gaps - ready to deliver!")
    
    lines.append(f"Buffer utilization: {analyzer.get_buffer_utilization():.1f}%")
    
    return "\n".join(lines)

Comparison: SR vs GBN Out-of-Order Handling

Let's crystallize the difference between Selective Repeat and Go-Back-N when frames arrive out of order:

Scenario: Window size = 4, Frames 0,1,2,3 sent, Frame 1 is lost, Frames 0,2,3 arrive at receiver.

Go-Back-N Behavior

•Frame 0 arrives: ACK 0, deliver
•Frame 2 arrives: DISCARD (expected 1)
•Frame 3 arrives: DISCARD (still expecting 1)
•Sender timeout: Retransmit 1, 2, 3
•Frame 1 arrives: ACK 1, deliver
•Frame 2 arrives again: ACK 2, deliver
•Frame 3 arrives again: ACK 3, deliver
•Total transmissions: 7 frames

Selective Repeat Behavior

•Frame 0 arrives: ACK 0, deliver
•Frame 2 arrives: ACK 2, buffer
•Frame 3 arrives: ACK 3, buffer
•Sender timeout: Retransmit only Frame 1
•Frame 1 arrives: ACK 1, deliver 1,2,3
•
•
•Total transmissions: 5 frames

Bandwidth Savings

In this simple example, SR saved 2 frame transmissions (29% reduction). With larger windows and higher error rates, the savings become dramatic—potentially 50-90% reduction in retransmission overhead.

Protocol Behavior Summary
Aspect	Go-Back-N	Selective Repeat
Out-of-order frame	Discarded	Buffered
Receiver complexity	Trivial (track 1 number)	Complex (track window)
Receiver buffer	Not needed	Required (size W)
Retransmit on timeout	All from lost frame onward	Only lost frame
Bandwidth efficiency	Poor with errors	Excellent
Implementation effort	Simple	Moderate

Summary: Out-of-Order Delivery

We've thoroughly examined how Selective Repeat handles the messy reality of network disorder. Let's consolidate the key concepts:

Key Takeaways

•Receiver window — Defines the range of acceptable sequence numbers [recv_base, recv_base + W - 1].
•Frame classification — Every frame is categorized as current window, previous window, or out-of-range.
•Buffering — Out-of-order frames are stored in a circular buffer indexed by sequence number.
•In-order delivery guarantee — Data is only delivered to the upper layer in correct sequence order.
•Gap filling — When recv_base arrives, all consecutive buffered frames are delivered at once.
•Efficiency gain — By not discarding out-of-order frames, SR dramatically reduces retransmissions.

What's Next:

In the next page, we'll explore Buffer Requirements—the memory constraints on both sender and receiver, how to size buffers appropriately, and the relationship between buffer size, window size, and protocol performance.

Page Complete

You now understand how Selective Repeat handles out-of-order delivery—the receiver window, frame acceptance logic, buffering mechanisms, and the in-order delivery guarantee. Next, we'll examine the buffer requirements that make this possible.