Stop-and-Wait ARQ Protocol

In any reliable communication protocol, the fundamental question is: How does the sender know the receiver got the message? Without a mechanism to confirm receipt, the sender operates blindly, unable to distinguish successful transmission from silent failure.

Acknowledgments (ACKs) are the answer. They form the feedback loop that transforms an unreliable channel into a reliable service. When a receiver sends an acknowledgment, it provides the sender with explicit confirmation that data arrived correctly.

This deceptively simple concept—"I got your message"—is the cornerstone of all reliable protocols. Yet the devil is in the details:

• What exactly should an ACK contain?
• When should ACKs be sent?
• What happens if ACKs themselves are lost or corrupted?
• Are there alternatives to positive acknowledgment?

In this section, we'll explore acknowledgments comprehensively, understanding not just what they are, but why they're designed the way they are.

Positive Acknowledgment is the primary mechanism in Stop-and-Wait ARQ. The receiver explicitly confirms successful receipt of each frame by sending an ACK frame back to the sender.

The Semantics of a Positive ACK:

When the receiver sends an ACK for frame n, it communicates:

1. "I received frame n"
2. "The CRC check passed—the frame appears uncorrupted"
3. "I have delivered the data to my network layer"
4. "I am ready for frame n+1"

All of this information is conveyed by a single, tiny ACK frame. The efficiency comes from the implicit understanding built into the protocol.

The ACK Frame Structure:

A Stop-and-Wait ACK is deliberately minimal:

Total overhead: approximately 18 bits (plus any framing delimiters). This is remarkably small—critical because an ACK is generated for every single data frame.

Why Include CRC in ACKs?

ACKs travel the same unreliable channel as data frames. A corrupted ACK could acknowledge the wrong frame, leading to protocol confusion. By protecting ACKs with CRC:

• The sender can verify the ACK is uncorrupted
• Corrupted ACKs are discarded (treated as lost)
• The timeout mechanism handles the resulting retransmission

ACK Number Semantics:

In Stop-and-Wait, the ACK number directly specifies which frame is being acknowledged:

• ACK₀ means "I received frame 0"
• ACK₁ means "I received frame 1"

This is explicit acknowledgment of what was received. Some protocols use an alternative semantics ("I expect frame n next"), but Stop-and-Wait's approach is simpler.

While Stop-and-Wait primarily uses positive acknowledgments, it's instructive to understand Negative Acknowledgments (NAKs) and why Stop-and-Wait can function without them.

What is a NAK?

A Negative Acknowledgment explicitly signals that something went wrong:

• "I received a frame, but it was corrupted"
• "I detected an error and need retransmission"

NAKs provide faster error recovery than waiting for a timeout. When the receiver detects corruption, it immediately tells the sender, which can retransmit without waiting for the timer to expire.

NAK Trade-offs:

Why Stop-and-Wait Doesn't Require NAKs:

Basic Stop-and-Wait can function without NAKs because:

1. Timeout handles all losses: Whether a frame is lost, corrupted, or its ACK is lost, the timeout triggers retransmission
2. Simplicity: One less frame type, one less code path, fewer bugs
3. Silence is sufficient: If the receiver says nothing, the sender eventually retransmits anyway

However, NAK-enhanced versions exist:

For high-latency links where the timeout is large, NAKs can significantly improve performance by cutting error recovery time.

When exactly should the receiver generate and send an acknowledgment? This question has performance implications and several subtleties.

Immediate ACK:

In basic Stop-and-Wait, the receiver should send an ACK as soon as it:

1. Receives a complete frame
2. Verifies the CRC is correct
3. Confirms the sequence number is expected (or is a known duplicate)

Receiver Timeline:
[Frame bits arriving...]
           ↓
[Last bit received]
           ↓
[CRC computed and verified] — typically microseconds
           ↓
[Data delivered to network layer]
           ↓
[ACK generated and transmitted] ← Should happen here, immediately

Why Immediate ACK Matters:

Delaying the ACK extends the time before the sender can transmit the next frame. Since Stop-and-Wait already has utilization problems due to waiting, any added delay makes it worse.

In the ideal case:

ACK_delay = 0 (ACK sent as soon as frame is validated)

ACK Generation for Duplicates:

A critical detail: the receiver should ACK duplicate frames.

Why? Consider this scenario:

1. Sender sends Frame₀
2. Receiver receives Frame₀, sends ACK₀
3. ACK₀ is lost in transit
4. Sender's timer expires, sender retransmits Frame₀
5. Receiver receives Frame₀ again (duplicate)

What should the receiver do at step 5?

Wrong approach: "I already delivered this frame, ignore it completely"

Problem: The sender never gets ACK₀, keeps retransmitting forever—deadlock!

Correct approach: "I already delivered this frame (don't deliver again), but send another ACK₀"

This way:

• Duplicate delivery is prevented (receiver tracks expected sequence number)
• Forward progress is ensured (sender gets the ACK it needs)

The Duplicate-ACK Rule:

if frame.seq == expected_seq:
    deliver_to_network_layer(frame)
    expected_seq = toggle(expected_seq)
    send_ack(frame.seq)
else if frame.seq == previous_seq:  // Duplicate
    // Don't deliver (already delivered)
    send_ack(frame.seq)  // But still ACK!
else:
    // Unexpected sequence (shouldn't happen in Stop-and-Wait)
    // Ignore or handle as error

ACKs are themselves frames traveling over an unreliable channel. They can be lost or corrupted just like data frames. Understanding how Stop-and-Wait handles ACK failures is essential.

Scenario 1: ACK Lost

Sender                                Receiver
   |                                      |
   |------- Frame 0 --------->            |
   |                          [Received]  |
   |                          [Send ACK0] |
   |         <<< ACK0 LOST >>>            |
   |                                      |
   | [Timer expires]                      |
   |                                      |
   |------- Frame 0 --------->            |
   |                          [Duplicate!]|
   |                          [Send ACK0] |
   |<---------- ACK0 ----------           |
   | [Timer stopped]                      |
   | [Advance to Frame 1]                 |

Analysis: The sender doesn't know it was the ACK that was lost (versus the original frame). It simply retransmits on timeout. The receiver recognizes the duplicate (same sequence number as the just-delivered frame), suppresses duplicate delivery, and re-sends ACK₀. This time, the ACK gets through, and the protocol proceeds.

Key insight: The sender and receiver recover correctly even though neither explicitly knows what failed.

Scenario 2: ACK Corrupted

Sender                                Receiver
   |                                      |
   |------- Frame 0 --------->            |
   |                          [Received]  |
   |                          [Send ACK0] |
   |<----- ACK0 (corrupted) -----         |
   | [CRC fails, discard ACK]             |
   |                                      |
   | [Timer expires]                      |
   |                                      |
   |------- Frame 0 --------->            |
   ...                                   ...

Analysis: The sender receives something, but when it checks the CRC, the ACK is corrupt. The sender discards the corrupted ACK and waits. The timer eventually expires, triggering retransmission—the same recovery as a lost ACK.

Scenario 3: ACK Delayed (Arrives After Timeout)

Sender                                Receiver
   |                                      |
   |------- Frame 0 --------->            |
   |                          [Received]  |
   |                          [Send ACK0] |
   |         <<< ACK0 delayed >>>         |
   |                                      |
   | [Timer expires]                      |
   |------- Frame 0 --------->            |
   |                          [Duplicate] |
   |                          [Send ACK0] |
   |<---------- ACK0 ----------           | (from retransmit)
   | [Got ACK0, advance]                  |
   |                                      |
   |------- Frame 1 --------->            |
   |                                      |
   |<---------- ACK0 ----------           | (delayed ACK arrives!)
   | [Wrong seq - ignore]                 |

Analysis: The delayed ACK arrives after the sender has advanced to Frame 1. But Wait—the sender is now expecting ACK₁, and the late ACK₀ arrives. The sender compares sequence numbers, finds a mismatch, and correctly ignores the late ACK.

The Resilience Pattern:

Notice that all ACK failures resolve the same way:

1. Sender doesn't get the expected ACK (for any reason)
2. Timer expires
3. Sender retransmits
4. Receiver re-ACKs (suppressing duplicate data delivery if needed)
5. Eventually, the ACK gets through

This uniform handling is a hallmark of good protocol design—the recovery mechanism is orthogonal to the failure type.

In bidirectional communication, both parties send data and both need to acknowledge. Sending separate ACK frames for each direction wastes bandwidth. Piggybacking solves this elegantly.

The Piggybacking Idea:

Instead of sending a standalone ACK, attach the acknowledgment to an outgoing data frame:

Regular data frame:     [Seq | Data | CRC]
Piggybacked data frame: [Seq | ACK | Data | CRC]

The piggybacked frame serves double duty:

• It carries data from sender to receiver (in its direction)
• It acknowledges data from the other direction

When Piggybacking Helps:

The Piggybacking Dilemma:

Piggybacking introduces a timing challenge: the receiver has data to send but wants to wait briefly to see if it will receive data needing acknowledgment (so it can piggyback). But waiting too long delays the ACK, potentially causing unnecessary retransmission.

Solution: Use a short delay timer:

on_frame_received(frame):
    process_data(frame)
    if has_data_to_send:
        send_data_with_piggyback_ack(pending_data, frame.seq)
    else:
        start_ack_delay_timer()
        
on_ack_delay_timer_expired():
    send_standalone_ack(last_received_seq)
    
on_data_to_send(data):
    if ack_pending:
        stop_ack_delay_timer()
        send_data_with_piggyback_ack(data, pending_ack_seq)
    else:
        send_data(data)

The delay timer is short (typically a few milliseconds)—enough to catch data that's about to be sent, but not long enough to trigger the sender's retransmission timer.

Piggybacked Frame Format:

A typical piggybacked frame structure:

The ACK number "rides along" with minimal overhead—just a few extra bits rather than an entire separate frame.

In Stop-and-Wait, each ACK acknowledges exactly one frame—there's only one outstanding frame at a time. But as we look ahead to more sophisticated protocols, two acknowledgment strategies emerge: cumulative and selective.

Cumulative Acknowledgment:

"ACK(n)" means "I have received all frames up to and including n."

• Simple for the sender: anything with sequence ≤ n can be discarded
• Used in Go-Back-N and TCP
• Loss-tolerant: if ACK(3) is lost but ACK(5) arrives, the sender knows frames 0-5 are all received

Selective Acknowledgment (SACK):

"ACK(n)" means "I have received exactly frame n" (nothing implied about other frames).

• More complex: sender tracks each frame individually
• Used in Selective Repeat and TCP SACK extension
• More efficient retransmission: only resend what's actually missing

In Stop-and-Wait:

The distinction doesn't matter—there's only one frame at a time! ACK₀ means "I got frame 0," and there's nothing else to say. But understanding the distinction prepares you for analyzing Go-Back-N (cumulative) and Selective Repeat (selective).

The Ack Number Controversy:

Different protocols use different conventions for what the ACK number means:

• Convention A: ACK(n) acknowledges receipt of frame n
• Convention B: ACK(n) requests frame n ("I've received up to n-1, send me n next")

Both are valid; you must know which convention a specific protocol uses. For Stop-and-Wait, we use Convention A: ACK₀ means "I received frame 0."

When an ACK arrives at the sender, several steps must occur in the correct order. Let's trace through the complete ACK processing logic.

Step 1: Frame Reception

The physical layer delivers bits to the data link layer, which assembles them into a complete frame.

Step 2: CRC Verification

The sender computes the CRC over the received ACK and compares it with the trailer:

received_crc = extract_crc(ack_frame)
computed_crc = compute_crc(ack_frame.header + ack_frame.ack_number)

if received_crc != computed_crc:
    discard(ack_frame)  // Corrupted, treat as lost
    return

Step 3: Sequence Number Validation

The sender checks if this ACK acknowledges the expected frame:

if ack_frame.ack_number == awaiting_ack_for:
    // This is the ACK we're waiting for
    process_valid_ack()
else:
    // Unexpected ACK - possibly duplicate or delayed
    // Ignore silently
    return

Step 4: Timer Cancellation

A critical step—stop the retransmission timer before it fires:

stop_retransmission_timer()

If we don't stop the timer, it will fire and cause an unnecessary retransmission.

Step 5: State Advancement

Advance the protocol state to prepare for the next frame:

current_seq = 1 - current_seq  // Toggle: 0→1 or 1→0
discard_stored_frame()  // No longer need retransmission copy

Step 6: Notification

Notify the upper layer (network layer) that it can submit the next packet:

network_layer.ready_to_accept_data()

Complete Sender ACK Handler:

function on_ack_received(ack_frame):
    // Step 2: Verify integrity
    if not verify_crc(ack_frame):
        log("Corrupted ACK received, discarding")
        return
    
    // Step 3: Check sequence number
    if ack_frame.ack_number != current_seq:
        log("Unexpected ACK seq, ignoring")
        return
    
    // Steps 4-6: Process valid ACK
    stop_timer()
    discard_stored_frame()
    current_seq = 1 - current_seq
    signal_ready_for_next_frame()
    log("ACK processed, ready for next frame")

Acknowledgments are the heartbeat of reliable transmission—the feedback mechanism that transforms "I hope you got it" into "I know you got it." Let's consolidate our deep dive:

Looking Ahead:

With acknowledgments thoroughly understood, we're prepared to explore the next critical component: timeout and retransmission. How long should the sender wait? What happens upon timeout? How do we set timeouts optimally? These questions complete our understanding of Stop-and-Wait's reliable transmission mechanism.