Selective Repeat Operation

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

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_end

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

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_end