Computer NetworksSelective Repeat ARQ

Selective Repeat ARQ: Efficient Retransmission Protocol

LevelIntermediate

Duration60 mins

TopicSelective Repeat ARQ

2 / 5

Individual ACKs: The Precision Acknowledgment Strategy

Acknowledging with Precision

In human communication, there's a difference between saying "I understand everything you said up to that point" (cumulative) versus "I understood exactly sentences 1, 2, and 4—but sentence 3 was unclear" (individual). The second approach provides far more actionable information.

Individual acknowledgments in Selective Repeat ARQ embody this precision philosophy. Rather than telling the sender "I have all frames up to N," the receiver says "I have exactly frames 0, 1, and 3." This seemingly small difference unlocks the protocol's ability to retransmit only what's missing.

This page dissects exactly how individual ACKs work—their format, semantics, timing, and the sophisticated sender/receiver bookkeeping they require.

What You Will Learn

By the end of this page, you will understand the complete mechanics of individual acknowledgments—how they're structured, when they're sent, how the sender interprets them, and why they're essential for selective retransmission. You'll also learn the ACK handling edge cases that can cause protocol failures if misunderstood.

Cumulative vs Individual Acknowledgments

To appreciate individual ACKs, we must first understand what they're replacing. Go-Back-N uses cumulative acknowledgments, which have fundamentally different semantics:

Cumulative Acknowledgment (Go-Back-N):

"ACK N" means: I have successfully received ALL frames with sequence numbers 0, 1, 2, ..., N-1. I am now expecting frame N.

This is powerful because a single ACK carries information about multiple frames. If the sender receives ACK 5, it knows frames 0-4 arrived successfully—even if ACKs 0, 1, 2, 3, 4 were all lost.

Individual Acknowledgment (Selective Repeat):

"ACK N" means: I have successfully received frame N specifically. No information about other frames is conveyed.

Each ACK is independent. ACK 5 confirms only frame 5; it says nothing about frames 0, 1, 2, 3, or 4.

Cumulative ACKs (Go-Back-N)

•"ACK N" = All frames before N received
•Single ACK can acknowledge multiple frames
•Receiver only tracks next expected frame
•Lost ACKs often recovered by later ACKs
•Cannot distinguish which specific frames missing
•Forces bulk retransmission on error

Individual ACKs (Selective Repeat)

•"ACK N" = Frame N specifically received
•One ACK per frame (more ACK traffic)
•Receiver tracks window of received frames
•Lost ACKs require timeout + retransmission
•Sender knows exactly which frames missing
•Enables surgical retransmission

The Trade-off

Individual ACKs generate more acknowledgment traffic—one ACK per frame instead of occasional cumulative ACKs. However, this overhead is usually negligible compared to the bandwidth saved by avoiding unnecessary retransmissions, especially on high-latency or error-prone links.

ACK Frame Format

The acknowledgment frame in Selective Repeat is simpler than data frames because it carries no payload—just the sequence number being acknowledged.

Minimal SR ACK Frame Structure:

+------------------+-------------------+------------------+
|     FRAME TYPE   |   ACK SEQ NUMBER  |       CRC        |
|     (1 bit)      |    (n bits)       |   (16-32 bits)   |
+------------------+-------------------+------------------+
        ↓                   ↓                   ↓
    Type=ACK         Which frame        Error detection
                     acked

Fields:

Field	Size	Description
Frame Type	1 bit	Distinguishes ACK (0) from DATA (1) frames
ACK Sequence Number	n bits	The sequence number of the frame being acknowledged
CRC/Checksum	16-32 bits	Error detection for the ACK frame itself

Why ACKs Need Error Detection:

Corrupted ACKs are dangerous:

If ACK 3 is corrupted to look like ACK 5, the sender might incorrectly believe frame 5 was received
This could cause the sender window to advance incorrectly, violating protocol correctness
Therefore, ACKs must be protected by CRC or checksum; corrupted ACKs are silently discarded

Implementation Note:

In practice, many protocols use piggybacked acknowledgments—combining ACKs with data frames traveling in the opposite direction. If station A and B are exchanging data bidirectionally:

A→B Data Frame: [Type=DATA | SeqNum=5 | ACK_NUM=3 | Payload | CRC]
                                         ↑
                            Acknowledges B's frame 3
                            while sending A's frame 5

This reduces ACK overhead but requires careful handling when no reverse data is available (in which case standalone ACKs must be sent).

ack_frame_structure.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
from dataclasses import dataclass
from enum import Enum
import struct
 
class FrameType(Enum):
    ACK = 0
    DATA = 1
 
@dataclass
class SelectiveRepeatACK:
    """Represents an individual acknowledgment frame in Selective Repeat."""
    ack_number: int  # The sequence number being acknowledged
    
    # Constants for our implementation
    SEQ_BITS = 3     # 3-bit sequence numbers (0-7)
    CRC_SIZE = 16    # 16-bit CRC
    
    def serialize(self) -> bytes:
        """Convert ACK to bytes for transmission."""
        # Pack: 1 bit type (0=ACK) + 3 bit seq num + padding + CRC
        header = (FrameType.ACK.value << 7) | (self.ack_number << 4)
        
        # Simple representation (real impl would use proper bit packing)
        frame_bytes = struct.pack('>B', header)
        
        # Calculate and append CRC
        crc = calculate_crc16(frame_bytes)
        frame_bytes += struct.pack('>H', crc)
        
        return frame_bytes
    
    @classmethod
    def deserialize(cls, data: bytes) -> 'SelectiveRepeatACK':
        """Parse bytes into an ACK frame."""
        # Verify CRC first
        payload = data[:-2]
        received_crc = struct.unpack('>H', data[-2:])[0]
        calculated_crc = calculate_crc16(payload)
        
        if received_crc != calculated_crc:
            raise CorruptedFrameError("ACK frame CRC mismatch")
        
        # Extract fields
        header = struct.unpack('>B', payload)[0]
        frame_type = (header >> 7) & 0x01
        
        if frame_type != FrameType.ACK.value:
            raise ValueError("Not an ACK frame")
        
        ack_number = (header >> 4) & 0x07  # Extract 3-bit seq number
        
        return cls(ack_number=ack_number)
 
 
@dataclass  
class PiggybackedDataFrame:
    """Data frame with piggybacked acknowledgment."""
    seq_number: int    # This frame's sequence number
    ack_number: int    # Acknowledges a received frame (piggybacked)
    ack_valid: bool    # True if ack_number field is valid
    payload: bytes     # The actual data
    
    def serialize(self) -> bytes:
        """Serialize frame with piggybacked ACK."""
        # Header: type(1) | seq(3) | ack_valid(1) | ack(3) = 8 bits
        header = (
            (FrameType.DATA.value << 7) |
            (self.seq_number << 4) |
            (int(self.ack_valid) << 3) |
            (self.ack_number if self.ack_valid else 0)
        )
        
        frame = struct.pack('>B', header) + self.payload
        crc = calculate_crc16(frame)
        frame += struct.pack('>H', crc)
        
        return frame

When to Send ACKs

In Selective Repeat, the receiver sends acknowledgments under very specific conditions. The timing rules are essential for protocol correctness:

Rule 1: Immediate ACK for In-Window Frames

When a frame arrives with sequence number in [recv_base, recv_base + W - 1]:

Send ACK immediately for that specific sequence number
Buffer the frame if out-of-order (or deliver if in-order)
Always ACK, even if the frame was previously received (duplicate)

Rule 2: Re-ACK for Previous-Window Frames

When a frame arrives with sequence number in [recv_base - W, recv_base - 1]:

This frame was already received and delivered in the past
The sender retransmitted because our original ACK was lost
Re-send the ACK to unblock the sender
Do NOT re-deliver the data (it's a duplicate)

Rule 3: Ignore Out-of-Range Frames

When a frame arrives with sequence number outside both windows:

This should not happen in correct operation
Likely severely delayed or corrupted sequence number
Silently discard—do not ACK

ACK Decision Matrix (Example: recv_base=4, W=4, max_seq=8)
Received Seq#	Window Check	Action	Rationale
4	In current [4,7]	ACK 4, deliver	Expected next frame
5	In current [4,7]	ACK 5, buffer	Out-of-order, valid
7	In current [4,7]	ACK 7, buffer	Far out-of-order, valid
3	In previous [0,3]	ACK 3, no buffer	Already delivered, re-ACK
1	In previous [0,3]	ACK 1, no buffer	Already delivered, re-ACK
0	In previous [0,3]	ACK 0, no buffer	Already delivered, re-ACK

Duplicate ACKs for Duplicates

A critical detail: if we receive Frame 5 twice (because our first ACK 5 was lost and the sender retransmitted), we send ACK 5 both times. The sender's timer will stop when either ACK arrives. This is correct and necessary behavior.

Sender ACK Processing

The sender's handling of incoming ACKs is more complex than Go-Back-N because each ACK only confirms one specific frame. The sender must maintain a per-frame acknowledgment status map.

ACK Processing Algorithm:

ON RECEIVE ACK(N):
    // Step 1: Validate ACK is within current window
    IF N is NOT in [send_base, send_base + W - 1] THEN
        // ACK for old frame or out of range
        DISCARD and RETURN
    ENDIF
    
    // Step 2: Mark frame as acknowledged
    IF frame[N].status == SENT THEN
        frame[N].status = ACKED
        STOP timer[N]
        FREE buffer[N]  // No longer need to store for retransmission
    ENDIF
    
    // Step 3: Attempt to advance window
    WHILE send_base has been ACKed DO
        send_base = send_base + 1
    END WHILE

The Crucial Step 3:

The sender window advances only when send_base itself has been acknowledged. This is different from cumulative ACKs where any ACK ≥ N advances the window to N+1.

With individual ACKs, it's possible to have a "hole"—frames 0, 2, 3, 4 are ACKed but frame 1 is not. The window stays at send_base=1 until ACK 1 arrives.

sender_ack_processing.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
class SRSenderACKHandler:
    """Handles individual ACK processing for Selective Repeat sender."""
    
    def __init__(self, window_size: int, seq_bits: int):
        self.W = window_size
        self.max_seq = 2 ** seq_bits
        self.send_base = 0
        self.next_seqnum = 0
        
        # Per-frame tracking - critical for individual ACKs
        self.frame_status = {}  # seq_num -> 'sent' | 'acked'
        self.frame_buffer = {}  # seq_num -> frame data
        self.timers = {}        # seq_num -> Timer
        
    def process_ack(self, ack_num: int) -> dict:
        """
        Process received ACK and return status update.
        
        Returns:
            dict with keys:
                - 'valid': bool - whether ACK was accepted
                - 'newly_acked': bool - whether this ACK marked a new frame
                - 'window_advanced': int - how many positions window slid
                - 'can_send_count': int - how many new frames can now be sent
        """
        result = {
            'valid': False,
            'newly_acked': False,
            'window_advanced': 0,
            'can_send_count': 0
        }
        
        # Validate: is ACK within current sender window?
        if not self._in_sender_window(ack_num):
            # Duplicate ACK for already-delivered frame, or garbage
            return result
        
        result['valid'] = True
        
        # Check if this is a new ACK (not a duplicate)
        if self.frame_status.get(ack_num) == 'sent':
            result['newly_acked'] = True
            
            # Mark as acknowledged
            self.frame_status[ack_num] = 'acked'
            
            # Stop timer for this frame
            if ack_num in self.timers:
                self.timers[ack_num].cancel()
                del self.timers[ack_num]
            
            # Free buffer space
            if ack_num in self.frame_buffer:
                del self.frame_buffer[ack_num]
        
        # Try to advance window
        old_base = self.send_base
        self._advance_window()
        result['window_advanced'] = (self.send_base - old_base) % self.max_seq
        
        # Calculate how many new frames can be sent
        outstanding = (self.next_seqnum - self.send_base) % self.max_seq
        result['can_send_count'] = self.W - outstanding
        
        return result
    
    def _advance_window(self):
        """Slide window forward over consecutively ACKed frames."""
        while self.send_base != self.next_seqnum:
            current = self.send_base
            
            if self.frame_status.get(current) == 'acked':
                # This frame is acknowledged, advance
                del self.frame_status[current]
                self.send_base = (self.send_base + 1) % self.max_seq
            else:
                # Hit an unacknowledged frame, stop
                break
    
    def _in_sender_window(self, seq: int) -> bool:
        """Check if sequence number is within [send_base, send_base + W - 1]."""
        # Using modular arithmetic for wraparound
        distance = (seq - self.send_base) % self.max_seq
        return distance < self.W
    
    def get_outstanding_frames(self) -> list:
        """Return list of sequence numbers that are sent but not yet ACKed."""
        outstanding = []
        seq = self.send_base
        while seq != self.next_seqnum:
            if self.frame_status.get(seq) == 'sent':
                outstanding.append(seq)
            seq = (seq + 1) % self.max_seq
        return outstanding
    
    def get_acked_but_undelivered(self) -> list:
        """Return frames that are ACKed but window hasn't advanced past them."""
        # These are frames between send_base and next unacked frame
        acked_frames = []
        seq = self.send_base
        while seq != self.next_seqnum:
            if self.frame_status.get(seq) == 'acked':
                acked_frames.append(seq)
            seq = (seq + 1) % self.max_seq
        return acked_frames

ACK Loss and Recovery

Lost ACKs are the Achilles heel of individual acknowledgments. With cumulative ACKs, losing ACK 3 doesn't matter if ACK 5 arrives later—it implicitly acknowledges frames 0-4. With individual ACKs, losing ACK 3 means the sender has no information about frame 3.

What Happens When ACK N is Lost:

Receiver received and processed frame N successfully
Receiver delivered frame N to upper layer (if in-order) or buffered it
Receiver sent ACK N, but ACK was lost
Sender's timer for frame N continues running
Timer expires → Sender retransmits frame N
Receiver receives frame N again (duplicate)
Receiver recognizes it as duplicate and re-sends ACK N
Sender finally receives ACK N

Converting Mermaid diagram...

Duplicate Detection at Receiver

The receiver must detect duplicates. If in the current window, it checks if already received. If in the previous window, it's definitely a duplicate. Either way, the receiver re-ACKs without re-processing the data.

The Cost of ACK Loss:

With individual ACKs, each lost ACK causes:

One extra timeout delay (typically 200ms - 1s)
One frame retransmission
One additional ACK

This is much better than Go-Back-N where a lost ACK for frame N might not matter (later ACKs cover it), but losing the most recent ACK causes W frames to be retransmitted.

Mitigating ACK Loss:

Delayed ACKs with ACK timer — Wait briefly before sending ACK in case more frames arrive (batching effect)
Negative ACKs (NAK) — Explicitly request retransmission when gap detected (more complex)
Select ACK (SACK) — TCP's approach: cumulative ACK + bitmap of additional received packets

Handling Out-of-Order ACKs

ACKs themselves can arrive out of order due to network reordering. Unlike data frames, ACK reordering is usually harmless but requires careful handling.

Scenario: ACKs Arrive Out of Order

Sender sends: Frame 0, Frame 1, Frame 2, Frame 3
Receiver ACKs: ACK 0, ACK 1, ACK 2, ACK 3 (sent in order)

Due to network reordering, sender receives: ACK 2, ACK 0, ACK 3, ACK 1

What the sender does:

Received	Action	send_base After
ACK 2	Mark frame 2 as ACKed	0 (can't advance, 0,1 pending)
ACK 0	Mark frame 0 as ACKed	0 (can't advance, 1 pending)
ACK 3	Mark frame 3 as ACKed	0 (can't advance, 1 pending)
ACK 1	Mark frame 1 as ACKed	4 (0,1,2,3 all ACKed, slide!)

Key Insight:

Out-of-order ACKs never cause problems—they just mean the window might not advance until a "completing" ACK arrives. The individual ACK semantics handle this naturally.

ACK Reordering vs Data Reordering

ACK reordering is benign. The sender just marks each frame as ACKed when its ACK arrives. Data frame reordering is what SR was designed to handle—buffering out-of-order frames at the receiver.

Duplicate ACKs:

Duplicate ACKs can arise from:

Receiver retransmitting ACK (timer-based or proactive)
Network duplicating packets
Sender retransmitting frame and receiving second ACK

Duplicate ACKs are harmless—the sender simply notices the frame is already marked as ACKed:

def receive_ack(self, ack_num):
    if self.frame_status.get(ack_num) == 'acked':
        # Duplicate ACK - frame already acknowledged
        # No action needed, ignore
        return
    # ... normal ACK processing

Negative ACKs (NAK) Extension

Some Selective Repeat implementations augment individual ACKs with Negative Acknowledgments (NAKs). A NAK explicitly requests retransmission of a specific frame, potentially speeding up error recovery.

When to Send a NAK:

The receiver sends NAK N when:

It receives a frame with sequence number greater than expected
This indicates frame N was likely lost
NAK allows sender to retransmit immediately (instead of waiting for timeout)

Example:

Receiver expects: Frame 3
Receiver gets:    Frame 5

Receiver can deduce: "Frame 3 (and maybe 4) appear to be lost"
Action: Send NAK 3 immediately

NAK vs Timeout-Based Recovery
Aspect	Timeout Only	With NAK
Detection Speed	Must wait for timeout (100ms - 1s)	Immediate on gap detection
Accuracy	Correct (frame is definitely lost)	Might be false positive (reordering)
Complexity	Simple sender logic	Sender must handle NAKs
Duplicate Work	None	Might retransmit unnecessarily
Best For	Low-error, stable networks	High-error, in-order networks

NAK Complexity:

NAKs introduce several complications:

False Positives — If frames arrive out of order (not lost), NAK triggers unnecessary retransmission
Duplicate NAKs — Receiver might send NAK multiple times for same frame
NAK Loss — If the NAK itself is lost, falls back to timeout
One NAK per Frame — Must track "NAK already sent for frame N" to avoid flooding

Implementation Consideration:

class SRReceiverWithNAK:
    def __init__(self):
        self.nak_sent = set()  # Track which NAKs we've already sent
        
    def on_receive_frame(self, frame):
        seq = frame.sequence_number
        
        if seq > self.expected_seq:
            # Gap detected - some frames missing
            for missing in range(self.expected_seq, seq):
                if missing not in self.nak_sent:
                    send_nak(missing)
                    self.nak_sent.add(missing)

Most modern protocols (like TCP SACK) avoid explicit NAKs in favor of sophisticated ACK schemes that convey the same information.

NAK is Optional

Pure Selective Repeat does not require NAKs. The protocol works correctly with only positive ACKs and timeouts. NAKs are an optimization that can reduce latency in high-error conditions but add complexity.

Summary: Individual ACKs

We've thoroughly examined the individual acknowledgment mechanism that powers Selective Repeat's efficiency. Let's consolidate the essential concepts:

Key Takeaways

•Individual semantics — ACK N acknowledges only frame N, conveying no information about other frames.
•Immediate ACKs — Receiver ACKs every valid frame immediately, including out-of-order frames.
•Re-ACK mechanism — Frames in the previous window trigger re-acknowledgment to handle ACK loss.
•Per-frame tracking — Sender maintains acknowledgment status for each outstanding frame.
•Window advancement — Sender window slides only when send_base is acknowledged; ACKed frames beyond send_base don't advance the window.
•NAK extension — Optional negative acknowledgments can speed up error detection but add complexity.

What's Next:

In the next page, we'll explore Out-of-Order Delivery—how the receiver handles frames that arrive in the wrong sequence, the buffering strategies required, and the conditions under which buffered frames are finally delivered to the application layer.

Page Complete

You now understand how individual acknowledgments work in Selective Repeat—their format, timing, sender processing, and the critical re-ACK mechanism that handles ACK loss. Next, we'll examine how the receiver manages out-of-order frame delivery.

2 / 5

Loading learning content...

Computer NetworksSelective Repeat ARQ

Selective Repeat ARQ: Efficient Retransmission Protocol

LevelIntermediate

Duration60 mins

TopicSelective Repeat ARQ

2 / 5

Individual ACKs: The Precision Acknowledgment Strategy

Acknowledging with Precision

This page dissects exactly how individual ACKs work—their format, semantics, timing, and the sophisticated sender/receiver bookkeeping they require.

What You Will Learn

Cumulative vs Individual Acknowledgments

To appreciate individual ACKs, we must first understand what they're replacing. Go-Back-N uses cumulative acknowledgments, which have fundamentally different semantics:

Cumulative Acknowledgment (Go-Back-N):

"ACK N" means: I have successfully received ALL frames with sequence numbers 0, 1, 2, ..., N-1. I am now expecting frame N.

This is powerful because a single ACK carries information about multiple frames. If the sender receives ACK 5, it knows frames 0-4 arrived successfully—even if ACKs 0, 1, 2, 3, 4 were all lost.

Individual Acknowledgment (Selective Repeat):

"ACK N" means: I have successfully received frame N specifically. No information about other frames is conveyed.

Each ACK is independent. ACK 5 confirms only frame 5; it says nothing about frames 0, 1, 2, 3, or 4.

Cumulative ACKs (Go-Back-N)

•"ACK N" = All frames before N received
•Single ACK can acknowledge multiple frames
•Receiver only tracks next expected frame
•Lost ACKs often recovered by later ACKs
•Cannot distinguish which specific frames missing
•Forces bulk retransmission on error

Individual ACKs (Selective Repeat)

•"ACK N" = Frame N specifically received
•One ACK per frame (more ACK traffic)
•Receiver tracks window of received frames
•Lost ACKs require timeout + retransmission
•Sender knows exactly which frames missing
•Enables surgical retransmission

The Trade-off

ACK Frame Format

The acknowledgment frame in Selective Repeat is simpler than data frames because it carries no payload—just the sequence number being acknowledged.

Minimal SR ACK Frame Structure:

+------------------+-------------------+------------------+
|     FRAME TYPE   |   ACK SEQ NUMBER  |       CRC        |
|     (1 bit)      |    (n bits)       |   (16-32 bits)   |
+------------------+-------------------+------------------+
        ↓                   ↓                   ↓
    Type=ACK         Which frame        Error detection
                     acked

Fields:

Field	Size	Description
Frame Type	1 bit	Distinguishes ACK (0) from DATA (1) frames
ACK Sequence Number	n bits	The sequence number of the frame being acknowledged
CRC/Checksum	16-32 bits	Error detection for the ACK frame itself

Why ACKs Need Error Detection:

Corrupted ACKs are dangerous:

If ACK 3 is corrupted to look like ACK 5, the sender might incorrectly believe frame 5 was received
This could cause the sender window to advance incorrectly, violating protocol correctness
Therefore, ACKs must be protected by CRC or checksum; corrupted ACKs are silently discarded

Implementation Note:

In practice, many protocols use piggybacked acknowledgments—combining ACKs with data frames traveling in the opposite direction. If station A and B are exchanging data bidirectionally:

A→B Data Frame: [Type=DATA | SeqNum=5 | ACK_NUM=3 | Payload | CRC]
                                         ↑
                            Acknowledges B's frame 3
                            while sending A's frame 5

This reduces ACK overhead but requires careful handling when no reverse data is available (in which case standalone ACKs must be sent).

ack_frame_structure.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
from dataclasses import dataclass
from enum import Enum
import struct
 
class FrameType(Enum):
    ACK = 0
    DATA = 1
 
@dataclass
class SelectiveRepeatACK:
    """Represents an individual acknowledgment frame in Selective Repeat."""
    ack_number: int  # The sequence number being acknowledged
    
    # Constants for our implementation
    SEQ_BITS = 3     # 3-bit sequence numbers (0-7)
    CRC_SIZE = 16    # 16-bit CRC
    
    def serialize(self) -> bytes:
        """Convert ACK to bytes for transmission."""
        # Pack: 1 bit type (0=ACK) + 3 bit seq num + padding + CRC
        header = (FrameType.ACK.value << 7) | (self.ack_number << 4)
        
        # Simple representation (real impl would use proper bit packing)
        frame_bytes = struct.pack('>B', header)
        
        # Calculate and append CRC
        crc = calculate_crc16(frame_bytes)
        frame_bytes += struct.pack('>H', crc)
        
        return frame_bytes
    
    @classmethod
    def deserialize(cls, data: bytes) -> 'SelectiveRepeatACK':
        """Parse bytes into an ACK frame."""
        # Verify CRC first
        payload = data[:-2]
        received_crc = struct.unpack('>H', data[-2:])[0]
        calculated_crc = calculate_crc16(payload)
        
        if received_crc != calculated_crc:
            raise CorruptedFrameError("ACK frame CRC mismatch")
        
        # Extract fields
        header = struct.unpack('>B', payload)[0]
        frame_type = (header >> 7) & 0x01
        
        if frame_type != FrameType.ACK.value:
            raise ValueError("Not an ACK frame")
        
        ack_number = (header >> 4) & 0x07  # Extract 3-bit seq number
        
        return cls(ack_number=ack_number)
 
 
@dataclass  
class PiggybackedDataFrame:
    """Data frame with piggybacked acknowledgment."""
    seq_number: int    # This frame's sequence number
    ack_number: int    # Acknowledges a received frame (piggybacked)
    ack_valid: bool    # True if ack_number field is valid
    payload: bytes     # The actual data
    
    def serialize(self) -> bytes:
        """Serialize frame with piggybacked ACK."""
        # Header: type(1) | seq(3) | ack_valid(1) | ack(3) = 8 bits
        header = (
            (FrameType.DATA.value << 7) |
            (self.seq_number << 4) |
            (int(self.ack_valid) << 3) |
            (self.ack_number if self.ack_valid else 0)
        )
        
        frame = struct.pack('>B', header) + self.payload
        crc = calculate_crc16(frame)
        frame += struct.pack('>H', crc)
        
        return frame

When to Send ACKs

In Selective Repeat, the receiver sends acknowledgments under very specific conditions. The timing rules are essential for protocol correctness:

Rule 1: Immediate ACK for In-Window Frames

When a frame arrives with sequence number in [recv_base, recv_base + W - 1]:

Send ACK immediately for that specific sequence number
Buffer the frame if out-of-order (or deliver if in-order)
Always ACK, even if the frame was previously received (duplicate)

Rule 2: Re-ACK for Previous-Window Frames

When a frame arrives with sequence number in [recv_base - W, recv_base - 1]:

This frame was already received and delivered in the past
The sender retransmitted because our original ACK was lost
Re-send the ACK to unblock the sender
Do NOT re-deliver the data (it's a duplicate)

Rule 3: Ignore Out-of-Range Frames

When a frame arrives with sequence number outside both windows:

This should not happen in correct operation
Likely severely delayed or corrupted sequence number
Silently discard—do not ACK

ACK Decision Matrix (Example: recv_base=4, W=4, max_seq=8)
Received Seq#	Window Check	Action	Rationale
4	In current [4,7]	ACK 4, deliver	Expected next frame
5	In current [4,7]	ACK 5, buffer	Out-of-order, valid
7	In current [4,7]	ACK 7, buffer	Far out-of-order, valid
3	In previous [0,3]	ACK 3, no buffer	Already delivered, re-ACK
1	In previous [0,3]	ACK 1, no buffer	Already delivered, re-ACK
0	In previous [0,3]	ACK 0, no buffer	Already delivered, re-ACK

Duplicate ACKs for Duplicates

Sender ACK Processing

The sender's handling of incoming ACKs is more complex than Go-Back-N because each ACK only confirms one specific frame. The sender must maintain a per-frame acknowledgment status map.

ACK Processing Algorithm:

ON RECEIVE ACK(N):
    // Step 1: Validate ACK is within current window
    IF N is NOT in [send_base, send_base + W - 1] THEN
        // ACK for old frame or out of range
        DISCARD and RETURN
    ENDIF
    
    // Step 2: Mark frame as acknowledged
    IF frame[N].status == SENT THEN
        frame[N].status = ACKED
        STOP timer[N]
        FREE buffer[N]  // No longer need to store for retransmission
    ENDIF
    
    // Step 3: Attempt to advance window
    WHILE send_base has been ACKed DO
        send_base = send_base + 1
    END WHILE

The Crucial Step 3:

The sender window advances only when send_base itself has been acknowledged. This is different from cumulative ACKs where any ACK ≥ N advances the window to N+1.

With individual ACKs, it's possible to have a "hole"—frames 0, 2, 3, 4 are ACKed but frame 1 is not. The window stays at send_base=1 until ACK 1 arrives.

sender_ack_processing.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
class SRSenderACKHandler:
    """Handles individual ACK processing for Selective Repeat sender."""
    
    def __init__(self, window_size: int, seq_bits: int):
        self.W = window_size
        self.max_seq = 2 ** seq_bits
        self.send_base = 0
        self.next_seqnum = 0
        
        # Per-frame tracking - critical for individual ACKs
        self.frame_status = {}  # seq_num -> 'sent' | 'acked'
        self.frame_buffer = {}  # seq_num -> frame data
        self.timers = {}        # seq_num -> Timer
        
    def process_ack(self, ack_num: int) -> dict:
        """
        Process received ACK and return status update.
        
        Returns:
            dict with keys:
                - 'valid': bool - whether ACK was accepted
                - 'newly_acked': bool - whether this ACK marked a new frame
                - 'window_advanced': int - how many positions window slid
                - 'can_send_count': int - how many new frames can now be sent
        """
        result = {
            'valid': False,
            'newly_acked': False,
            'window_advanced': 0,
            'can_send_count': 0
        }
        
        # Validate: is ACK within current sender window?
        if not self._in_sender_window(ack_num):
            # Duplicate ACK for already-delivered frame, or garbage
            return result
        
        result['valid'] = True
        
        # Check if this is a new ACK (not a duplicate)
        if self.frame_status.get(ack_num) == 'sent':
            result['newly_acked'] = True
            
            # Mark as acknowledged
            self.frame_status[ack_num] = 'acked'
            
            # Stop timer for this frame
            if ack_num in self.timers:
                self.timers[ack_num].cancel()
                del self.timers[ack_num]
            
            # Free buffer space
            if ack_num in self.frame_buffer:
                del self.frame_buffer[ack_num]
        
        # Try to advance window
        old_base = self.send_base
        self._advance_window()
        result['window_advanced'] = (self.send_base - old_base) % self.max_seq
        
        # Calculate how many new frames can be sent
        outstanding = (self.next_seqnum - self.send_base) % self.max_seq
        result['can_send_count'] = self.W - outstanding
        
        return result
    
    def _advance_window(self):
        """Slide window forward over consecutively ACKed frames."""
        while self.send_base != self.next_seqnum:
            current = self.send_base
            
            if self.frame_status.get(current) == 'acked':
                # This frame is acknowledged, advance
                del self.frame_status[current]
                self.send_base = (self.send_base + 1) % self.max_seq
            else:
                # Hit an unacknowledged frame, stop
                break
    
    def _in_sender_window(self, seq: int) -> bool:
        """Check if sequence number is within [send_base, send_base + W - 1]."""
        # Using modular arithmetic for wraparound
        distance = (seq - self.send_base) % self.max_seq
        return distance < self.W
    
    def get_outstanding_frames(self) -> list:
        """Return list of sequence numbers that are sent but not yet ACKed."""
        outstanding = []
        seq = self.send_base
        while seq != self.next_seqnum:
            if self.frame_status.get(seq) == 'sent':
                outstanding.append(seq)
            seq = (seq + 1) % self.max_seq
        return outstanding
    
    def get_acked_but_undelivered(self) -> list:
        """Return frames that are ACKed but window hasn't advanced past them."""
        # These are frames between send_base and next unacked frame
        acked_frames = []
        seq = self.send_base
        while seq != self.next_seqnum:
            if self.frame_status.get(seq) == 'acked':
                acked_frames.append(seq)
            seq = (seq + 1) % self.max_seq
        return acked_frames

ACK Loss and Recovery

What Happens When ACK N is Lost:

Receiver received and processed frame N successfully
Receiver delivered frame N to upper layer (if in-order) or buffered it
Receiver sent ACK N, but ACK was lost
Sender's timer for frame N continues running
Timer expires → Sender retransmits frame N
Receiver receives frame N again (duplicate)
Receiver recognizes it as duplicate and re-sends ACK N
Sender finally receives ACK N

Converting Mermaid diagram...

Duplicate Detection at Receiver

The Cost of ACK Loss:

With individual ACKs, each lost ACK causes:

One extra timeout delay (typically 200ms - 1s)
One frame retransmission
One additional ACK

This is much better than Go-Back-N where a lost ACK for frame N might not matter (later ACKs cover it), but losing the most recent ACK causes W frames to be retransmitted.

Mitigating ACK Loss:

Delayed ACKs with ACK timer — Wait briefly before sending ACK in case more frames arrive (batching effect)
Negative ACKs (NAK) — Explicitly request retransmission when gap detected (more complex)
Select ACK (SACK) — TCP's approach: cumulative ACK + bitmap of additional received packets

Handling Out-of-Order ACKs

ACKs themselves can arrive out of order due to network reordering. Unlike data frames, ACK reordering is usually harmless but requires careful handling.

Scenario: ACKs Arrive Out of Order

Sender sends: Frame 0, Frame 1, Frame 2, Frame 3
Receiver ACKs: ACK 0, ACK 1, ACK 2, ACK 3 (sent in order)

Due to network reordering, sender receives: ACK 2, ACK 0, ACK 3, ACK 1

What the sender does:

Received	Action	send_base After
ACK 2	Mark frame 2 as ACKed	0 (can't advance, 0,1 pending)
ACK 0	Mark frame 0 as ACKed	0 (can't advance, 1 pending)
ACK 3	Mark frame 3 as ACKed	0 (can't advance, 1 pending)
ACK 1	Mark frame 1 as ACKed	4 (0,1,2,3 all ACKed, slide!)

Key Insight:

Out-of-order ACKs never cause problems—they just mean the window might not advance until a "completing" ACK arrives. The individual ACK semantics handle this naturally.

ACK Reordering vs Data Reordering

ACK reordering is benign. The sender just marks each frame as ACKed when its ACK arrives. Data frame reordering is what SR was designed to handle—buffering out-of-order frames at the receiver.

Duplicate ACKs:

Duplicate ACKs can arise from:

Receiver retransmitting ACK (timer-based or proactive)
Network duplicating packets
Sender retransmitting frame and receiving second ACK

Duplicate ACKs are harmless—the sender simply notices the frame is already marked as ACKed:

def receive_ack(self, ack_num):
    if self.frame_status.get(ack_num) == 'acked':
        # Duplicate ACK - frame already acknowledged
        # No action needed, ignore
        return
    # ... normal ACK processing

Negative ACKs (NAK) Extension

When to Send a NAK:

The receiver sends NAK N when:

It receives a frame with sequence number greater than expected
This indicates frame N was likely lost
NAK allows sender to retransmit immediately (instead of waiting for timeout)

Example:

Receiver expects: Frame 3
Receiver gets:    Frame 5

Receiver can deduce: "Frame 3 (and maybe 4) appear to be lost"
Action: Send NAK 3 immediately

NAK vs Timeout-Based Recovery
Aspect	Timeout Only	With NAK
Detection Speed	Must wait for timeout (100ms - 1s)	Immediate on gap detection
Accuracy	Correct (frame is definitely lost)	Might be false positive (reordering)
Complexity	Simple sender logic	Sender must handle NAKs
Duplicate Work	None	Might retransmit unnecessarily
Best For	Low-error, stable networks	High-error, in-order networks

NAK Complexity:

NAKs introduce several complications:

False Positives — If frames arrive out of order (not lost), NAK triggers unnecessary retransmission
Duplicate NAKs — Receiver might send NAK multiple times for same frame
NAK Loss — If the NAK itself is lost, falls back to timeout
One NAK per Frame — Must track "NAK already sent for frame N" to avoid flooding

Implementation Consideration:

class SRReceiverWithNAK:
    def __init__(self):
        self.nak_sent = set()  # Track which NAKs we've already sent
        
    def on_receive_frame(self, frame):
        seq = frame.sequence_number
        
        if seq > self.expected_seq:
            # Gap detected - some frames missing
            for missing in range(self.expected_seq, seq):
                if missing not in self.nak_sent:
                    send_nak(missing)
                    self.nak_sent.add(missing)

Most modern protocols (like TCP SACK) avoid explicit NAKs in favor of sophisticated ACK schemes that convey the same information.

NAK is Optional

Summary: Individual ACKs

We've thoroughly examined the individual acknowledgment mechanism that powers Selective Repeat's efficiency. Let's consolidate the essential concepts:

Key Takeaways

•Individual semantics — ACK N acknowledges only frame N, conveying no information about other frames.
•Immediate ACKs — Receiver ACKs every valid frame immediately, including out-of-order frames.
•Re-ACK mechanism — Frames in the previous window trigger re-acknowledgment to handle ACK loss.
•Per-frame tracking — Sender maintains acknowledgment status for each outstanding frame.
•Window advancement — Sender window slides only when send_base is acknowledged; ACKed frames beyond send_base don't advance the window.
•NAK extension — Optional negative acknowledgments can speed up error detection but add complexity.

What's Next:

Page Complete

2 / 5