Stop-and-Wait Protocol

The core challenge: reliable communication over an unreliable medium

One possible role of the data link layer is to provide reliable transfer between directly connected devices. Not every link technology offers that service, so the ARQ mechanism must be defined by the particular protocol. The physical medium, such as copper cable, optical fiber, or a radio channel, is subject to noise and interference. Signals can be distorted, weakened over distance, or lost temporarily. This creates two problems:

1. Corrupted frames: How does the receiver detect a change from the frame sent by the sender?
2. Lost frames: If a frame or its acknowledgment fails to arrive, how does the sender detect the need to retransmit?

One of the simplest answers is the Stop-and-Wait protocol, a basic form of ARQ (Automatic Repeat reQuest). An FCS or CRC can detect corruption, but it cannot recover the frame by itself. The pure form has low efficiency on links with a large bandwidth-delay product. Its acknowledgments, timers, and retransmissions help explain TCP, although TCP uses a sliding window and its own control rules.

The core rule of Stop-and-Wait

The protocol's operation can be expressed as one rule for the sender:

This rule limits the number of unacknowledged frames and therefore provides flow control. Combined with an integrity check and retransmission, it also provides error control. The sender proceeds to the next frame only after receiving an acknowledgment.

Stop-and-Wait in action: a no-error scenario

Consider a scenario in which the channel loses no frames and reports no integrity errors.

1. Step 1: Sender Transmits Frame: The sender (Node A) takes the first piece of data, encapsulates it in a frame with sequence number 0, and sends it to the receiver (Node B).
2. Step 2: Sender Starts a Timer: Immediately after sending the frame, Node A starts a timeout timer. This timer acts as a failsafe.
3. Step 3: Receiver Gets the Frame: After a propagation delay, Node B receives Frame 0. It checks the FCS to ensure the frame is not corrupted.
4. Step 4: Receiver Sends Acknowledgment: After checking the frame, Node B sends an ACK. In the convention used here, the ACK identifies the sequence number of the next frame expected. After receiving Frame 0, it sends ACK 1.
5. Step 5: Sender Receives ACK: Node A receives ACK 1 before its timer expires. The acknowledgment means that the receiver accepted Frame 0 without detecting corruption. Node A stops the timer.
6. Step 6: Repeat the Cycle: Now that Frame 0 is confirmed, Node A is free to send the next frame in the sequence, Frame 1, and the cycle begins anew.

Handling frame loss: the timeout mechanism

A frame or an acknowledgment can be lost. In a variant without negative acknowledgments, the sender detects this absence when its timer expires. The timer should cover the expected round-trip time, processing, and delay variation so that it does not trigger premature retransmissions.

Scenario 1: Lost Data Frame

1. The sender transmits Frame 0 and starts its timer.
2. The frame is lost in transit due to a burst of noise on the channel.
3. The receiver, Node B, never receives anything. It continues to wait passively.
4. The sender, Node A, waits. No ACK arrives.
5. The sender's timer expires. The missing acknowledgment is treated as a reason to retransmit.
6. Assuming the frame was lost, the sender retrieves the copy of Frame 0 from its buffer and retransmits it, starting the timer again.

The timer is part of the Automatic Repeat reQuest mechanism. When it expires, the sender transmits again the frame for which it received no acknowledgment.

Scenario 2: Lost Acknowledgment (ACK) Frame

The data frame can arrive correctly while its acknowledgment is lost on the return path.

1. The sender transmits Frame 0 and starts its timer.
2. The receiver correctly receives Frame 0 and sends back ACK 1.
3. The ACK 1 frame is lost in transit.
4. The sender, unaware that the data arrived, continues to wait.
5. The sender's timer expires. The sender cannot distinguish a lost frame from a lost ACK, so it treats the missing acknowledgment as a reason to retransmit.
6. The sender retransmits Frame 0.

Solving duplicates: one sequence bit

The lost-ACK scenario means that the receiver may receive a duplicate of Frame 0. Delivering it to the network layer again would repeat the same data, for example duplicating part of a file.

Stop-and-Wait solves this with alternating sequence numbering. One bit is enough, with values 0 and 1 identifying successive frames.

How 1-bit sequence numbers work

The receiver compares each sequence number with the value it expects:

1. Sender sends Frame 0.
2. Receiver gets Frame 0, sends back ACK 1, and now expects Frame 1.
3. The ACK 1 is lost. Sender's timer expires.
4. Sender retransmits Frame 0.
5. Receiver gets the duplicate Frame 0. It checks the sequence number. It was expecting Frame 1, but it received Frame 0.
6. The receiver recognizes the duplicate. It discards the duplicate frame and repeats the last successful acknowledgment, ACK 1, so the sender can complete the outstanding exchange.

With a valid integrity check, consistent timers, and duplicate handling, this 1-bit number distinguishes a retransmission from a new frame. The receiver repeats the acknowledgment for the last accepted value, allowing the sender to retry without delivering the data twice. A correctly received data frame can then be delivered to the higher layer at most once, including after an ACK is lost.

Analyzing Stop-and-Wait link utilization

Stop-and-Wait is simple, but its performance on fast long-distance links is limited by the time spent waiting for an acknowledgment. With no frame errors, the main limitation is propagation delay relative to frame transmission time. Actual throughput is further reduced by headers, processing time, and any retransmissions.

Calculation example: transatlantic fiber

For this calculation, assume a dedicated fiber-optic link between New York and London with a length of 5,600 km.

• Link Bandwidth (R): 1 Gigabit per second ($1 \times 10^9$ bps).
• Distance (d): Approximately 5,600 km.
• Propagation speed (v): The signal speed in fiber is about $2 \times 10^8$ m/s.
• Data payload (L): 1,500 bytes (12,000 bits), with header overhead omitted.

Calculate the three time components used in the cycle:

1. Transmission time $(T_{tx})$: The time needed to place all payload bits on the link.

   $T_{tx} = \frac{\text{Frame Size (L)}}{\text{Bandwidth (R)}} = \frac{12,000 \text{ bits}}{1 \times 10^9 \text{ bps}} = 0.000012 \text{ seconds} = 12\,\mu\text{s}$

2. Propagation delay $(T_p)$: The time needed for the first bit to travel from one end to the other.

   $T_p = \frac{\text{Distance (d)}}{\text{Speed (v)}} = \frac{5,600,000 \text{ m}}{2 \times 10^8 \text{ m/s}} = 0.028 \text{ seconds} = 28,000\,\mu\text{s}$

3. Round-Trip Time (RTT): The time for the frame to arrive and the ACK to return. We assume negligible ACK transmission and processing time, so RTT is approximated by twice the propagation delay.

   $RTT \approx 2 \times T_p = 2 \times 28,000\,\mu\text{s} = 56,000\,\mu\text{s}$

Calculating link utilization

The sender spends $12\,\mu\text{s}$ transmitting and $56,000\,\mu\text{s}$ waiting. Link utilization $(U)$ is the share of time used to send data:

$U = \frac{T_{tx}}{T_{tx} + RTT} = \frac{12}{12 + 56000} \approx \frac{12}{56012} \approx 0.000214$

Under these assumptions, the link is idle for 99.9786% of the time. The theoretical data rate is $1 \text{ Gbps} \times 0.000214 \approx 214 \text{ kbps}$. This is an upper estimate that omits headers, processing time, and retransmissions; the actual rate is lower.

Conclusion: a simple method with limited efficiency

Stop-and-Wait is a useful way to introduce reliability at the link layer. It limits the number of outstanding frames and, with integrity checks, sequence numbers, acknowledgments, and retransmissions, can provide reliable transfer.

Its throughput falls when the waiting time is large relative to transmission time. For this reason, sliding window protocols such as Go-Back-N and Selective Repeat are used. They retain acknowledgments and retransmissions while allowing several frames to be sent before responses arrive, which improves link utilization.