Stop and wait (sometimes abbreviated SaW) is the simplest possible ARQ protocol, used to request retransmissions of packets in a communications network.
Protocol Operation
The protocol is very easy to understand, and just as simple to implement. A communication pair is made up of a transmitter and a receiver. The transmitter sends a packet across a communications link, then stops and waits for a reply. Positive acknowledgements are sent back along the link by the receiver; negative acknowledgements can be sent back too, but are often assumed after some time out period has expired.
A sample exchange is shown below.
------------------------------------------> Time
(Packet lost) (Retransmission)
------ ------ ------
TX | Data | | Data | | Data |
------. ------. .------
. ----- . . -----
RX . | Ack | . . | Ack |
. .----- . . -----
. . . .
Link Timeout
propagation value
delay
All data packets sent by the transmitter take a certain time to reach the receiver. This is related to the length and velocity of the communications link, and is known as the link propagation delay. The receiver replies to the packet once it has been received by sending an ACK; this is also subject to the propagation delay.
When a packet is lost, as the second packet is in this case, the transmitter's acknowledgement timer expires. It then can assume that either the data or the acknowledgement didn't arrive, and so retransmits the previous packet.
Efficiency
The stop and wait protocol is clearly not particularly efficient. Even in the ideal case of no loss, most of the time is spent with the link idle, waiting for the other end to reply. When packets require retransmission, efficiency lowers further.
Efficiency can be calculated fairly easily. Let the size of the data we want to send be D bits, and the header (used for addressing or error detection, for example) be H bits long. Also let the corresponding acknowledgement packet be A bits in size. We must also take into account the link parameters, propagation time Ts and bit rate B bits/s.
The time taken to complete the transaction is the sum of three terms: the time taken to send the packet, the time taken to send the ack, and the two propagation delays inbetween. This gives us t = (D + H)/B + A/B + 2T as the total time. Ideally, the time taken to send D bits of data across a link with bit rate B would be simply D/B. Rearranging these gives a no-retransmission efficiency of:
η = D/(D + H) × 1/(A + 2TB)
The retransmission timer used by the sender has an ideal value for efficiency. Clearly, it must wait at least the maximum time taken for an acknowledgement to be returned: this is the propagation delay for the data packet, plus the time taken to send the acknowledgement, plus the propagation delay for the acknowledgement. Therefore, the stop time must be S ≥ 2T + A/B.
Since header and ACK size are normally kept to a minimum anyway, the equation above shows that efficiency is governed by the 2TB term. This has the effect that increasing link bit rate actually decreases efficiency; more obviously, efficiency also decreases as the link latency increases. Therefore, a stop and wait protocol is very inefficient over long or high bandwidth links.
Implementations
While stop and wait is time-inefficient, its requirement that the transmitter needs to buffer only one packet makes it very easy to implement. It is ideal for lightweight protocols such as Trivial FTP (TFTP), used to load kernels over a network by diskless workstations. TFTP must often be implemented in only a few tens of bytes of assembler, since it must be kept on a small ROM in the network card or BIOS of the diskless machine.
Additionally, since TFTP most commonly operates over Ethernet, link latency is normally low enough that efficiency isn't a problem. When link length becomes larger, more efficient protocols (such as go-back N or selective retransmission) are necessary for reasonable data transfer times.
References:
"Data Communications and Networks: An Engineering Approach", Irvine & Harle, Wiley, 2000
"RFC 1350: The TFTP Protocol (Revision 2)", Sollins, IETF, 1992