ARQ Protocols: Stop-and-Wait, Go-Back-N, and Selective Repeat with Mermaid Diagrams and Python

Introduction

ARQ (Automatic Repeat reQuest) protocols ensure reliable data transmission over error-prone channels by detecting corrupted frames and requesting retransmission. The three main variants — Stop-and-Wait, Go-Back-N, and Selective Repeat — trade efficiency for complexity. Understanding their differences is essential for network protocol design and for understanding how TCP, HDLC, and wireless protocols manage reliability.

This guide provides Mermaid sequence diagrams for all three ARQ types, a Python simulation for each, a sliding window efficiency comparison with formulas, and real-world protocol mappings.

Stop-and-Wait ARQ

The simplest ARQ: send one frame, wait for ACK, send the next. The sender uses sequence numbers 0 and 1 alternately to detect duplicates.

sequenceDiagram
    participant S as Sender
    participant R as Receiver

    S->>R: Frame 0
    activate R
    R->>S: ACK 0
    deactivate R

    S->>R: Frame 1
    activate R
    R->>S: NAK 1 (error detected)
    deactivate R

    S->>R: Frame 1 (retransmit)
    activate R
    R->>S: ACK 1
    deactivate R

    Note over S,R: Sender idle while waiting for ACK

Python Simulation

import random
import time

class StopAndWaitARQ:
    """Simulates Stop-and-Wait ARQ with configurable error rate."""
    def __init__(self, error_rate=0.1, timeout=1.0):
        self.error_rate = error_rate
        self.timeout = timeout
        self.seq_num = 0  # 0 or 1

    def send_frame(self, frame_data: str) -> bool:
        """Send one frame, wait for ACK, retry on failure."""
        attempts = 0
        while attempts < 3:
            print(f"TX: Frame {self.seq_num} ({frame_data})")
            time.sleep(self.timeout * 0.2)

            # Simulate random error
            if random.random() < self.error_rate:
                print(f"RX: ERROR on Frame {self.seq_num} — sending NAK")
                continue  # Sender retransmits

            # Successful transmission
            print(f"RX: ACK {self.seq_num}")
            self.seq_num = 1 - self.seq_num  # Toggle sequence number
            return True

        print("TX: Failed after 3 attempts")
        return False

Efficiency: U = 1 / (1 + 2a) where a = propagation_delay / transmission_time. For high-latency links (satellite), efficiency drops below 10%.

Go-Back-N ARQ

The sender transmits a window of N frames without waiting for ACKs. On error, all frames from the erroneous one are retransmitted.

sequenceDiagram
    participant S as Sender (Window=4)
    participant R as Receiver

    S->>R: Frame 0
    S->>R: Frame 1
    S->>R: Frame 2
    S->>R: Frame 3

    R-->>S: ACK 0
    R-->>S: ACK 1
    R-->>S: NAK 2 (frame 2 error)
    R-->>S: ACK 3

    Note over S: Go back to frame 2
    S->>R: Frame 2 (retransmit)
    S->>R: Frame 3 (retransmit)
    S->>R: Frame 4 (new)
    S->>R: Frame 5 (new)

    R-->>S: ACK 4

Python Simulation

class GoBackNARQ:
    """Go-Back-N with window size N."""
    def __init__(self, window_size=4, error_rate=0.1):
        self.window_size = window_size
        self.error_rate = error_rate
        self.base = 0       # Oldest unacknowledged frame
        self.next_seq = 0    # Next frame to send

    def send_window(self, total_frames: int):
        """Transmit frames within the sliding window."""
        while self.base < total_frames:
            # Send all frames in current window
            while self.next_seq < self.base + self.window_size and self.next_seq < total_frames:
                print(f"TX: Frame {self.next_seq} (window: {self.base}-{self.base + self.window_size - 1})")
                self.next_seq += 1

            # Simulate ACK/NAK for the base frame
            if random.random() < self.error_rate:
                print(f"RX: NAK {self.base} — Go back to {self.base}")
                self.next_seq = self.base  # Retransmit from base
            else:
                print(f"RX: ACK {self.base}")
                self.base += 1  # Advance window

            time.sleep(0.2)

Efficiency: Higher than Stop-and-Wait for large windows: U = N / (1 + 2a) when no errors. Wasted retransmissions when errors occur.

Selective Repeat ARQ

Only the erroneous frame is retransmitted. The receiver buffers out-of-order frames.

sequenceDiagram
    participant S as Sender (Window=4)
    participant R as Receiver (Buffer=4)

    S->>R: Frame 0
    S->>R: Frame 1
    S->>R: Frame 2
    S->>R: Frame 3

    R-->>S: ACK 0
    R-->>S: ACK 1
    R-->>S: NAK 2 (error)
    R-->>S: ACK 3

    Note over R: Buffer frames 1,3 while waiting for 2

    S->>R: Frame 2 (retransmit only)

    R-->>S: ACK 2
    Note over R: Deliver frames 0,1,2,3 in order

    S->>R: Frame 4
    S->>R: Frame 5

Python Simulation

class SelectiveRepeatARQ:
    """Selective Repeat with independent ACK/NAK per frame."""
    def __init__(self, window_size=4, error_rate=0.1):
        self.window_size = window_size
        self.error_rate = error_rate
        self.base = 0
        self.next_seq = 0
        self.acknowledged = set()  # Track individual ACKs

    def send_frames(self, total_frames: int):
        """Transmit frames, retransmitting only on NAK."""
        while self.base < total_frames:
            # Fill window with unacknowledged frames
            while self.next_seq < self.base + self.window_size and self.next_seq < total_frames:
                if self.next_seq not in self.acknowledged:
                    print(f"TX: Frame {self.next_seq}")
                self.next_seq += 1

            # Simulate response for the base frame
            if random.random() < self.error_rate:
                print(f"RX: NAK {self.base}")
            else:
                print(f"RX: ACK {self.base}")
                self.acknowledged.add(self.base)
                # Advance base if next frame is already acked
                while self.base in self.acknowledged:
                    self.base += 1

            time.sleep(0.2)

Efficiency: Best of the three: U = N / (1 + 2a) even with errors (only bad frames retransmitted). Requires more complex receiver buffering.

Protocol Mapping to Real-World Systems

Understanding which ARQ mechanism underlies real protocols clarifies their behavior:

TCP (Transmission Control Protocol) uses a modified Go-Back-N with cumulative ACKs. The sender maintains a transmission window bounded by the receiver’s advertised window and the congestion window. When packets are lost, TCP retransmits all unacknowledged segments from the lost packet onward — this is the defining Go-Back-N behavior. TCP Selective Acknowledgment (SACK, RFC 2018) extends this to Selective Repeat, allowing the receiver to specify non-contiguous blocks received, so the sender retransmits only the gaps.

HDLC (High-Level Data Link Control) supports both Go-Back-N and Selective Repeat modes. Configuration determines which mode is active. HDLC’s polling mechanism (used in Frame Relay and early cellular networks) determines when frames can be transmitted.

Wi-Fi (IEEE 802.11) uses a form of Selective Repeat with ACKs. Each data frame is acknowledged individually. If the sender does not receive an ACK within a short timeout, only that frame is retransmitted. The 802.11 ACK is itself not acknowledged, which is a deliberate trade-off: acknowledging every ACK would create an infinite regression.

LTE and 5G NR use Hybrid ARQ (HARQ), which combines forward error correction (FEC) with ARQ. The receiver attempts to decode immediately and stores soft-decision data (not just the raw bits) if decoding fails. A NAK triggers a retransmission, which the receiver combines with the previously stored soft data before decoding again. This Chase combining or incremental redundancy significantly improves throughput on wireless links where errors are bursty.

def calculate_arq_efficiency(window_size: int, propagation_ms: float, bandwidth_mbps: float, frame_size_bytes: int = 1500) -> float:
    """Calculate theoretical maximum efficiency for Go-Back-N/Selective Repeat.

    Args:
        window_size: Sender's window size (N)
        propagation_ms: One-way propagation delay in milliseconds
        bandwidth_mbps: Link bandwidth in Mbps
        frame_size_bytes: Size of each data frame in bytes

    Returns:
        Efficiency as a fraction (0.0 to 1.0)
    """
    bandwidth_bps = bandwidth_mbps * 1_000_000
    transmission_time = (frame_size_bytes * 8) / bandwidth_bps  # seconds
    a = (propagation_ms / 1000) / transmission_time  # propagation / transmission

    efficiency = window_size / (1 + 2 * a)
    return min(efficiency, 1.0)

# Satellite link (high latency, moderate bandwidth)
sat_eff = calculate_arq_efficiency(window_size=4, propagation_ms=600, bandwidth_mbps=10)
print(f"Satellite (10 Mbps, 600ms RTT): {sat_eff:.1%} efficiency")

# Data center (low latency, high bandwidth)
dc_eff = calculate_arq_efficiency(window_size=16, propagation_ms=0.5, bandwidth_mbps=10000)
print(f"Data center (10 Gbps, 0.5ms RTT): {dc_eff:.1%} efficiency")

# Mobile 4G (moderate latency, moderate bandwidth)
mobile_eff = calculate_arq_efficiency(window_size=8, propagation_ms=50, bandwidth_mbps=100)
print(f"Mobile 4G (100 Mbps, 50ms RTT): {mobile_eff:.1%} efficiency")

This formula illustrates why high-latency links need large windows: a satellite with 600ms RTT and 10 Mbps link achieves less than 1% efficiency with Stop-and-Wait (window=1) but reaches 33%+ with window=4. Modern protocols like TCP BBR actively measure the bandwidth-delay product to size their windows appropriately.

Comparison and Protocol Mapping

Resources

• RFC 3366 — ARQ in Reliable Protocols
• TCP Selective Acknowledgment (SACK) — RFC 2018
• Sliding Window Protocol — Tanenbaum, Computer Networks