Efficiency numbers tell only half the story. Selective Repeat may achieve 95% utilization where Go-Back-N manages only 12%—but at what cost? How much more memory, processing power, and engineering effort does that efficiency require?

In real systems, resources are finite. A network interface card (NIC) has limited on-chip memory. An embedded sensor node runs on a microcontroller with 4KB of RAM. A satellite transceiver must minimize power consumption. The 'best' protocol isn't always the most efficient—it's the one that delivers acceptable performance within the available resource envelope.

This page quantifies the implementation complexity of each ARQ protocol, enabling informed tradeoff decisions.

Protocol complexity manifests across multiple dimensions. A thorough comparison must consider each:

Memory Complexity:

• Buffer space for frames awaiting acknowledgment (sender)
• Buffer space for out-of-order frames (receiver)
• State variables (sequence numbers, window bounds, flags)
• Timer state

Computational Complexity:

• Processing per frame sent/received
• Timer management overhead
• Reordering/sorting operations
• Acknowledgment processing

Implementation Complexity:

• Lines of code
• Edge cases and corner conditions
• Testing and verification difficulty
• Potential for bugs

State Management Complexity:

• Number of distinct states
• State transition complexity
• Concurrency considerations
• Recovery from inconsistent states

Stop-and-Wait represents the baseline—the simplest possible reliable protocol. Its complexity analysis sets the lower bound.

Memory Requirements:

For a 1500-byte frame: Sender needs ~1502 bytes, Receiver needs 1 bit. This is essentially zero overhead beyond the frame itself.

Computational Overhead:

State Machine:

Stop-and-Wait has the simplest state machine. The sender alternates between two states:

• Wait for data from upper layer → Send frame, start timer
• Wait for ACK → On ACK: advance to next frame. On timeout: resend.

The receiver is even simpler:

• Wait for frame → If expected seq: deliver and ACK. If duplicate: just ACK.

Implementation Statistics:

Go-Back-N adds significant complexity to the sender while keeping the receiver simple. This asymmetry was historically important when receivers had limited resources (terminals, early PCs).

Memory Requirements:

For N=127, 1500-byte frames:

• Sender: 127 × 12,000 bits = 190 KB
• Receiver: ~10 bytes

The sender bears the entire memory burden. The receiver remains trivial.

Computational Overhead:

The Single Timer Simplification:

Go-Back-N uses one timer for the entire window—the timer for the oldest unacknowledged frame (at base). When this timer expires, all frames from base onward are retransmitted.

This simplification has profound implications:

• Advantage: Only one timer to manage, minimal timer overhead
• Disadvantage: Can't individually timeout specific frames
• Consequence: If one frame is lost deep in the window, we wait for the base timer even though the loss was detected earlier

State Machine Complexity:

Go-Back-N sender states:

• Idle: Window empty, waiting for data
• Sending: Data available, window not full, actively transmitting
• Window Full: Waiting for ACKs before sending more
• Timeout Recovery: Retransmitting from base

Receiver states:

• Wait for expected frame: Same as Stop-and-Wait

The sender state machine has more transitions but remains manageable.

Selective Repeat achieves optimal efficiency at the cost of maximum complexity. Both sender and receiver must maintain substantial state.

Memory Requirements:

For N=127, 1500-byte frames:

• Sender: 127 × 12,000 + 127 × 33 = ~190 KB + 528 bytes
• Receiver: 127 × 12,000 + 127 + 7 = ~190 KB + 17 bytes

Total: ~380 KB — nearly double Go-Back-N's memory!

The receiver now needs as much buffer as the sender. This is the fundamental resource cost of efficiency.

Computational Overhead:

The N Timers Challenge:

Selective Repeat requires N independent timers—one for each outstanding frame. This creates substantial implementation complexity:

Naive Implementation:

• Array of N timer structures
• Check all N timers periodically (inefficient)
• O(N) time per timer check

Efficient Implementation (Timer Wheel/Heap):

• Priority queue (heap) of pending timeouts
• O(log N) to insert/cancel timers
• O(log N) to get next expiring timer
• Significantly more complex code

The Reordering Challenge:

When the receiver delivers frames to the upper layer, it must deliver them in order. This requires tracking which buffer positions are filled and scanning for consecutive filled positions from the base.

Let's consolidate the complexity analysis across all dimensions:

Complexity Ratios (relative to Stop-and-Wait):

Implications by Deployment Scenario:

When protocols are implemented in hardware (NICs, switches, FPGAs), complexity constraints differ significantly from software.

Hardware Resource Categories:

Line-Rate Processing Challenges:

At 100 Gbps, a minimum-size 64-byte packet arrives every ~5 nanoseconds. The protocol logic must complete all per-packet operations within this budget. Complex operations like heap-based timer management may not achieve line rate.

Hardware solutions:

• Pipelining: Spread operations across multiple clock cycles
• Parallelism: Process multiple packets simultaneously
• Approximation: Use simpler timer schemes (e.g., coarse-grained timer wheels)
• Offloading: Handle common case in hardware, exceptions in software

SmartNIC Example (TCP Offload):

Modern SmartNICs implement Selective Repeat-like TCP processing. They use:

• Multi-bank SRAM for out-of-order packet buffers
• Hardware timer wheels with 1024+ slots
• Dedicated reordering engines
• ~500K logic elements (substantial silicon investment)

Protocol complexity directly impacts the difficulty of ensuring correctness. This section examines the verification challenges for each protocol.

Stop-and-Wait Verification:

With only 2 states per endpoint and 5 edge cases, exhaustive testing is feasible. A test suite can cover:

• Normal operation (frame sent, ACK received)
• Lost frame (timeout, retransmit)
• Lost ACK (timeout, retransmit, duplicate delivery prevented)
• Corrupted frame (CRC fails, silence, timeout)
• Corrupted ACK (treated as lost)

Formal verification is straightforward—the state space is tiny.

Go-Back-N Verification:

The window adds complexity. Test scenarios must include:

• Window fill and drain
• Cumulative ACK advancement (multiple frames acknowledged at once)
• Timeout with partially acknowledged window
• Window wraparound (sequence number recycling)
• Out-of-order frame arrival (should be discarded)

The state space grows with window size but remains manageable. Model checking tools can verify correctness for small N.

Selective Repeat Verification:

SR's state space explodes combinatorially. For a window of N frames, each can be in multiple states (sent/not-sent at sender; received/not-received at receiver). The receiver buffer can hold any subset of frames. Arrival orders are arbitrary.

Critical Edge Cases:

Verification Techniques:

Protocol complexity is the price paid for efficiency. This page has quantified that price across multiple dimensions:

The Complexity-Efficiency Tradeoff Curve:

Visualize complexity vs. efficiency as a curve:

• Low complexity, low efficiency: Stop-and-Wait lives here
• Medium complexity, high efficiency (if low errors): Go-Back-N offers a good compromise
• High complexity, highest efficiency (regardless of errors): Selective Repeat maximizes throughput

The 'knee' of this curve shifts based on error rates. At p=0.001%, GBN is nearly optimal (why pay for SR?). At p=5%, SR's complexity is amply justified by its 7× throughput advantage.

What's Next:

With efficiency and complexity both quantified, we can now synthesize decision criteria. The next page provides comprehensive guidance on when to use each protocol, integrating channel characteristics, system constraints, and application requirements into actionable selection rules.