Stop-and-Wait ARQ Protocol

In the physical world, communication channels are inherently unreliable. Electromagnetic interference, signal attenuation, thermal noise, cosmic radiation, and countless other phenomena conspire to corrupt, delay, or entirely destroy data as it traverses the network. The Data Link Layer faces a profound challenge: how do we build reliable communication on top of unreliable physical infrastructure?

This is not merely an academic concern. Every file you download, every message you send, every financial transaction you complete depends on mechanisms that detect when data has been corrupted or lost, and automatically recover from these failures—all without human intervention.

The Stop-and-Wait Automatic Repeat reQuest (ARQ) protocol represents the simplest, most intuitive solution to this problem. Understanding Stop-and-Wait is crucial because:

1. It embodies the fundamental principles that all ARQ protocols share
2. Its simplicity makes it ideal for analyzing reliability mechanisms
3. Its limitations motivate the development of more sophisticated protocols
4. It remains in use today in specific contexts where simplicity trumps efficiency

Before diving into Stop-and-Wait specifically, let's establish what ARQ means and why it exists.

Automatic Repeat reQuest (ARQ) is a family of error-control protocols that rely on two key mechanisms:

1. Error Detection: The receiver must be able to determine whether a received frame contains errors
2. Retransmission: When errors are detected (or data is lost), the sender must retransmit

The "automatic" in ARQ is significant—the protocol handles error recovery without human intervention. The "request" originally referred to the receiver explicitly asking for retransmission, though modern implementations often use implicit signaling.

The Core Contract:

ARQ protocols establish a contract between sender and receiver:

• The sender promises to keep trying until the receiver confirms successful receipt
• The receiver promises to acknowledge successful receipt and/or signal when retransmission is needed
• Together, they guarantee that data is delivered correctly and in order, or the sender is explicitly notified of failure

The Three Pillars of ARQ:

Every ARQ protocol rests on three fundamental mechanisms:

Stop-and-Wait is the simplest implementation of these mechanisms. It sends one frame, waits for acknowledgment, then sends the next. No pipelining, no buffering, no complex state management—just the essential elements of reliable transmission.

Stop-and-Wait ARQ derives its name from its fundamental behavior: after sending a frame, the sender stops and waits for an acknowledgment before proceeding to the next frame.

This paradigm has profound implications:

The Sender's Perspective:

• Send a frame
• Start a timer
• Wait for acknowledgment
• If ACK arrives: stop timer, send next frame
• If timer expires: retransmit the same frame

The Receiver's Perspective:

• Wait for a frame
• Check for errors
• If error-free: deliver to upper layer, send ACK
• If corrupted: discard silently (or send NAK in some variants)

Why "Stop-and-Wait" Works:

The elegance of Stop-and-Wait lies in its simplicity. At any moment:

• The sender has at most one outstanding (unacknowledged) frame
• The receiver expects exactly one frame
• Both parties know exactly what should happen next

This simplicity eliminates entire classes of problems that plague more complex protocols: buffer management, out-of-order delivery, flow control complexity.

The Simple State Machine:

Stop-and-Wait can be modeled as a minimal finite state machine:

Sender States:

1. Ready: Prepared to send next frame
2. Waiting: Frame sent, awaiting acknowledgment

Receiver States:

1. Waiting: Ready to receive next frame
2. Processing: Frame received, preparing acknowledgment

The transitions between these states follow predictable rules, making the protocol easy to implement and verify.

Let's trace through the complete operation of Stop-and-Wait ARQ in a successful transmission scenario. Understanding this sequence precisely is essential for analyzing the protocol's behavior.

Scenario Setup:

• Sender A wants to send a message to Receiver B
• The message has been divided into frames: F₀, F₁, F₂, ...
• The channel introduces propagation delay
• Both ends have synchronized their protocol state

Critical Timing Relationships:

The time to complete one frame transmission consists of:

Total Time = T_frame + T_prop + T_process + T_ack + T_prop

Where:

• T_frame: Time to transmit the data frame (frame size / bandwidth)
• T_prop: One-way propagation delay (distance / signal speed)
• T_process: Receiver processing time (typically negligible)
• T_ack: Time to transmit the ACK (ACK size / bandwidth)
• Second T_prop: Propagation delay for ACK return

This timing is fundamental to understanding Stop-and-Wait's efficiency, which we'll analyze in detail in a later section.

Each component of the Stop-and-Wait protocol serves a specific purpose. Let's examine them systematically.

1. The Data Frame Structure:

A Stop-and-Wait data frame contains:

Why Only 1 Bit for Sequence Number?

This is a key insight. Since Stop-and-Wait only has one outstanding frame at a time, we only need to distinguish between "this frame" and "next frame." A single bit (0 or 1) suffices: frames alternate 0, 1, 0, 1, and so on. This minimal sequence number has profound implications for the protocol's simplicity.

2. The Acknowledgment Frame:

ACK frames are deliberately minimal:

ACKs must be small because they're administrative overhead. A large ACK would waste bandwidth on every single data frame.

3. The Retransmission Timer:

The timer is perhaps the most subtle component. It must be set appropriately:

• Too short: Premature timeouts cause unnecessary retransmissions
• Too long: Legitimate losses take forever to recover
• Just right: Expires shortly after the maximum expected round-trip time

In practice, the timeout is set to:

Timeout = 2 × T_prop + T_frame + T_ack + Safety_Margin

The safety margin accounts for variations in processing time and network conditions.

4. The CRC (Cyclic Redundancy Check):

The CRC serves as the guardian of data integrity. For Stop-and-Wait:

• The sender computes a CRC over the frame and appends it
• The receiver recomputes the CRC and compares
• A mismatch means corruption occurred

CRC can detect:

• All single-bit errors
• All double-bit errors
• Any odd number of errors
• All burst errors up to the CRC length

This high detection capability is why CRC, rather than simple checksums, is preferred at the data link layer.

5. Protocol Buffers:

Even simple Stop-and-Wait requires minimal buffering:

• Sender Buffer: One frame (the one currently awaiting ACK)
• Receiver Buffer: One frame (being processed before delivery)

This minimal memory requirement is a key advantage of Stop-and-Wait in resource-constrained environments.

Understanding Stop-and-Wait requires visualizing the message flow over time. Let's examine a successful transmission followed by various error scenarios.

Successful Transmission Timeline:

Sender A                                    Receiver B
   |                                            |
   |  -------- Frame 0 (Seq=0) --------->       |
   |                                            |
   |  [Timer starts]                 [Receives] |
   |                              [CRC OK]      |
   |                              [Deliver]     |
   |                                            |
   |  <-------- ACK (Seq=0) -------------       |
   |                                            |
   |  [Timer stops]                             |
   |  [Advance to Seq=1]                        |
   |                                            |
   |  -------- Frame 1 (Seq=1) --------->       |
   |                                            |
   ...                                        ...

Notice the characteristic "staircase" pattern—each frame must complete its full round trip before the next begins.

Key Observations from the Diagram:

1. Idle Periods: The sender spends significant time waiting. The channel is "empty" during this time—no useful data flows.

2. Round-Trip Dependency: Each frame's completion depends on the full round-trip time (RTT = 2 × propagation delay + transmission times).

3. Strict Ordering: Frames are processed in strict sequence. There's no possibility of out-of-order delivery or receiver confusion.

4. Deterministic Behavior: Given the timings, you can predict exactly when each event occurs. This determinism makes analysis straightforward.

The Efficiency Visual:

If we shade the diagram to show when the channel is carrying useful data versus when it's idle:

|████|░░░░░░░░░░░░░░░░░░░░░░░░░░░░|████|░░░░░░░░...
      ^ Frame transmission         ^ Next frame
      ←――――― Idle waiting ―――――→

The ratio of shaded (busy) to total time is the channel utilization—and for Stop-and-Wait on high-latency channels, this ratio can be devastatingly low.

A well-designed protocol maintains certain invariants—properties that remain true throughout execution. Understanding these invariants helps verify correctness and debug implementations.

Stop-and-Wait Invariants:

Correctness Reasoning:

Why do these guarantees hold? Let's reason through key scenarios:

Claim: Frames are never delivered out of order.

Proof Sketch: Since the sender only transmits one frame at a time and waits for its acknowledgment, the receiver sees at most one new frame at a time. The receiver delivers frames immediately upon acceptance. With only one "in-flight" frame, reordering is impossible—there's nothing to reorder against.

Claim: Frames are never delivered twice (no duplicates).

Proof Sketch: The receiver checks the sequence number. If it matches the expected number, the frame is delivered and the expected number is toggled. If a duplicate arrives (same sequence number as already delivered), the receiver recognizes it, discards it, but still sends an ACK (to prevent infinite retransmission by the sender).

Claim: No frame is lost (assuming finite loss probability).

Proof Sketch: If a frame or its ACK is lost, the sender's timer expires, and the frame is retransmitted. This repeats until successful. With probability of success > 0 on each attempt, eventual success is guaranteed (though expected time may be long for high-loss channels).

Implementing Stop-and-Wait correctly requires attention to several practical details that academic descriptions sometimes gloss over.

Timer Implementation:

The retransmission timer is critical and tricky:

// Sender logic
function send_frame(data):
    frame = create_frame(data, current_seq)
    transmit(frame)
    stored_frame = frame  // Keep for potential retransmission
    start_timer(timeout_value)

function on_timer_expired():
    transmit(stored_frame)  // Retransmit same frame
    start_timer(timeout_value)  // Restart timer

function on_ack_received(ack):
    if ack.seq == current_seq:
        stop_timer()
        current_seq = 1 - current_seq  // Toggle: 0→1 or 1→0
        notify_ready_for_next_frame()
    // Else: ignore (unexpected ACK)

Duplicate Detection at Receiver:

// Receiver logic
expected_seq = 0

function on_frame_received(frame):
    if crc_check(frame) fails:
        return  // Silently discard corrupted frame
    
    if frame.seq == expected_seq:
        deliver_to_network_layer(frame.data)
        expected_seq = 1 - expected_seq  // Toggle
    
    // Always ACK the received seq (even duplicates)
    // This handles case where our previous ACK was lost
    send_ack(frame.seq)

Edge Cases to Handle:

Common Implementation Bugs:

1. Forgetting to store the frame: If you don't keep the frame for retransmission, you can't retransmit on timeout
2. Stopping timer on any ACK: Must verify the ACK matches the expected sequence
3. Not ACKing duplicates: Causes deadlock when ACK is lost
4. Restarting timer on ACK receipt: Timer should stop, not restart, when the correct ACK arrives
5. Generating new frame on timeout: Retransmission must send the same frame, not new data

We've established the complete operational picture of Stop-and-Wait ARQ. Let's consolidate our understanding:

The Foundation for What's Ahead:

Stop-and-Wait represents the conceptual kernel from which all ARQ protocols derive. The mechanisms we've studied—acknowledgments, timeouts, sequence numbers, retransmission—appear in every reliable protocol, from the Data Link Layer to TCP at the Transport Layer and beyond.

In subsequent pages, we'll explore:

• Acknowledgments in depth: Positive vs. negative acknowledgment, piggybacking, and window-based ACKs
• Timeout and retransmission: How to handle lost frames and ACKs, timeout sizing
• Sequence numbers: Why 1 bit suffices for Stop-and-Wait and why complex protocols need more
• Efficiency analysis: Quantifying the utilization problem and motivating sliding window protocols