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.

Comparison and Protocol Mapping

Feature	Stop-and-Wait	Go-Back-N	Selective Repeat
Window size	1	N	N
Retransmission on error	Current frame	All from error	Only erroneous
Receiver buffering	None	Discards OOO	Buffers OOO
Efficiency	Low	Medium (with errors)	High
Complexity	Simple	Moderate	Complex
Used by	Some serial links	TCP (loss-based CC)	TCP SACK, HDLC, Wi-Fi

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

Introduction

Stop-and-Wait ARQ

Python Simulation

Go-Back-N ARQ

Python Simulation

Selective Repeat ARQ

Python Simulation

Comparison and Protocol Mapping

Resources

Comments

Share this article

👍 Was this article helpful?