Stop And Wait Arq - Learning Module

Loading content...

0/228

Basic Operation of Stop-and-Wait ARQ

The Challenge of Reliable Transmission

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:

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

What You Will Learn

By the end of this page, you will thoroughly understand how Stop-and-Wait ARQ operates, including the precise sequence of events during successful transmission, the role of each protocol component, and why this simple protocol forms the conceptual foundation for all reliable data transfer mechanisms.

Understanding ARQ Fundamentals

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:

Error Detection: The receiver must be able to determine whether a received frame contains errors
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

ARQ vs. FEC

ARQ protocols contrast with Forward Error Correction (FEC), where the sender includes enough redundant information that the receiver can correct errors without retransmission. ARQ is more bandwidth-efficient when errors are rare; FEC is better when feedback is impractical (satellite, broadcast) or latency is critical. Many modern systems use hybrid approaches.

The Three Pillars of ARQ:

Every ARQ protocol rests on three fundamental mechanisms:

Mechanism	Purpose	Implementation
Error Detection	Identify corrupted frames	CRC, checksum, parity
Acknowledgment	Confirm successful receipt	ACK frames, piggybacking
Retransmission	Recover from errors/loss	Timeouts, explicit requests

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.

The Stop-and-Wait Paradigm

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.

Mental Model

Think of Stop-and-Wait like a polite conversation where you say one sentence, then wait for the other person to nod before continuing. It's slow but ensures mutual understanding. You wouldn't speak for 10 minutes without checking if your listener is still with you.

The Simple State Machine:

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

Sender States:

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

Receiver States:

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

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

Step-by-Step Operation

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

Successful Transmission Sequence

•Frame Preparation: Sender A takes data from the network layer, encapsulates it into a frame with header (including sequence number) and trailer (including CRC for error detection)
•Frame Transmission: The frame is passed to the physical layer and transmitted bit-by-bit across the medium. Simultaneously, Sender A starts a retransmission timer
•Propagation Delay: The frame travels across the physical medium (wire, fiber, wireless). This takes time proportional to distance and medium characteristics
•Frame Reception: Receiver B's physical layer delivers the bits to the data link layer. The frame is reconstructed from the bit stream
•Error Checking: Receiver B computes the CRC over the received frame and compares it with the trailer. If they match, the frame is accepted; otherwise, it's discarded
•Data Delivery: If the frame is error-free, Receiver B extracts the payload and delivers it to the network layer. The frame's sequence number is noted
•ACK Generation: Receiver B constructs an acknowledgment frame (typically much smaller than data frames) indicating which frame was successfully received
•ACK Transmission: The ACK is transmitted back to Sender A. Note: ACKs are also subject to propagation delay and potential errors
•ACK Reception: Sender A receives the ACK, stops the retransmission timer, and verifies it acknowledges the expected frame
•Advance State: Sender A advances to the next frame (F₁) and the cycle repeats

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.

The Waiting Problem

Notice that during T_prop (both directions), the sender sits idle. If propagation delay is large relative to transmission time (as in satellite links or long-haul fiber), the channel utilization becomes devastatingly poor. This is the fundamental efficiency limitation of Stop-and-Wait.

Protocol Components in Detail

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:

Field	Size (typical)	Purpose
Start Delimiter	1 byte	Frame boundary identification
Sequence Number	1 bit	Distinguish consecutive frames (0 or 1)
Data Payload	Variable	Actual data from network layer
CRC	2-4 bytes	Error detection code
End Delimiter	1 byte	Frame boundary identification

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:

Field	Size	Purpose
Type	1 bit	Distinguish ACK from data
Sequence Number	1 bit	Identify which frame is being acknowledged
CRC	2 bytes	Error detection for ACK itself

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.

Adaptive Timeouts

In real implementations (like TCP, which uses a variant of Stop-and-Wait for connection setup), timeouts are adaptive. The protocol measures actual round-trip times and adjusts the timeout dynamically. This is especially important for variable-latency networks like the Internet.

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.

Visual Protocol Flow

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.

The Time Diagram

Time flows downward in these diagrams. The horizontal dimension represents the physical separation between sender and receiver. The diagonal lines represent message propagation—their slope indicates the propagation delay.

Key Observations from the Diagram:

Idle Periods: The sender spends significant time waiting. The channel is "empty" during this time—no useful data flows.
Round-Trip Dependency: Each frame's completion depends on the full round-trip time (RTT = 2 × propagation delay + transmission times).
Strict Ordering: Frames are processed in strict sequence. There's no possibility of out-of-order delivery or receiver confusion.
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.

Protocol Invariants and Guarantees

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:

Protocol Guarantees

•Single Outstanding Frame: At any time, at most one frame is unacknowledged. The sender never transmits frame n+1 until frame n is acknowledged
•Sequence Alternation: Frame sequence numbers alternate strictly: 0, 1, 0, 1, ... The same sequence is never used for consecutive distinct frames
•Ordered Delivery: Frames are delivered to the network layer in exactly the order they were submitted by the sender—never reordered
•Reliable Delivery: Every frame is eventually delivered exactly once, assuming the channel isn't permanently broken and timeouts are configured correctly
•State Synchronization: Sender and receiver sequence expectations remain synchronized even after errors, thanks to the sequence number mechanism

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).

Assumptions Matter

These guarantees assume: (1) errors are transient, not permanent, (2) the timeout is set correctly, (3) the CRC detects all corruption. If these assumptions fail—say, the channel is permanently broken or the CRC misses an error—the guarantees don't hold. Real systems include higher-level mechanisms (end-to-end checksums, application-level acknowledgments) as safety nets.

Implementation Considerations

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)

Why ACK Duplicates?

The receiver sends an ACK even for duplicate frames. Why? If frame 0 arrived and we sent ACK0, but ACK0 was lost, the sender will retransmit frame 0. We must re-send ACK0 to break the deadlock. Ignoring the duplicate frame while still acknowledging it achieves both duplicate suppression and forward progress.

Edge Cases to Handle:

Scenario	Correct Behavior
ACK arrives after timeout	Compare seq; if matches, accept (late ACK)
ACK for wrong sequence	Ignore; likely a delayed duplicate
Corrupted ACK received	Ignore; timer will handle retransmission
Multiple timeouts for same frame	Keep retransmitting; maybe increase timeout
Receiver gets same frame repeatedly	Discard data, but always acknowledge

Common Implementation Bugs:

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

Summary: The Foundation of Reliable Transmission

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

Key Takeaways

•Stop-and-Wait is the simplest ARQ protocol: One frame at a time, wait for acknowledgment, then proceed. No pipelining, no complex state
•Three mechanisms underpin reliability: Error detection (CRC), positive acknowledgment (ACK), and timeout-triggered retransmission
•Only 1 bit needed for sequence numbers: Since only one frame is outstanding, we need only distinguish 'current' from 'next'
•The sender maintains minimal state: Current sequence number, stored frame for retransmission, and timer
•The receiver maintains minimal state: Expected sequence number. That's it
•Correctness follows from simplicity: In-order delivery, no duplicates, and eventual reliability all follow from the protocol's constraints
•Implementation requires care: Duplicate ACKs, timer management, and edge cases must be handled correctly
•Efficiency is the tradeoff: Simplicity and low resource needs come at the cost of poor channel utilization

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

Foundation Established

You now understand the complete basic operation of Stop-and-Wait ARQ—the simplest and most fundamental reliable transmission protocol. This foundation is essential for understanding the more sophisticated protocols (Go-Back-N, Selective Repeat) and real-world protocols like TCP that build upon these principles.