Stop-and-wait ARQ
Stop-and-wait automatic repeat request (ARQ) is a basic error-control protocol employed in the data link layer of computer networks to provide reliable data transmission over error-prone channels through the use of acknowledgments and retransmissions of erroneous or lost frames.[1] In this protocol, the sender transmits a single data frame containing a sequence number and waits for an acknowledgment (ACK) from the receiver, which confirms successful reception after error detection via techniques such as cyclic redundancy checks (CRC).[2] If the frame is lost or contains an error, the sender's timer will expire, prompting retransmission of the same frame.[1] The use of a one-bit sequence number—alternating between 0 and 1—enables the receiver to distinguish new frames from potential duplicates caused by lost ACKs, ensuring ordered delivery without ambiguity.[3] As the simplest form of ARQ, stop-and-wait offers advantages in implementation, including minimal buffering requirements and straightforward logic that makes it suitable for low-complexity systems or short-distance links.[4] However, its efficiency is limited by the sender's idle time while awaiting ACKs, resulting in low channel utilization—particularly in networks with high bandwidth-delay products—where the protocol achieves utilization approaching 1/(1 + 2a) under ideal conditions, with a representing the ratio of propagation delay to transmission time.[5] This inefficiency has led to the development of more advanced sliding-window ARQ variants, such as Go-Back-N and selective repeat, which permit multiple unacknowledged frames to improve throughput while building on stop-and-wait's core principles.[6]Overview
Definition and Purpose
Stop-and-wait automatic repeat-request (ARQ) is a fundamental error-control protocol in data communications, wherein the sender transmits a single data frame and subsequently halts transmission until it receives a positive acknowledgment (ACK) from the receiver, confirming successful receipt.[1] This mechanism forms the basis of the simplest ARQ strategy, originally developed as a core technique for reliable packet delivery in potentially error-prone environments.[1] The primary purpose of stop-and-wait ARQ is to enable error detection and correction over noisy transmission channels by facilitating the retransmission of frames that are lost, corrupted, or unacknowledged, thereby guaranteeing data integrity and preserving the original sequence order without necessitating extensive buffering at either endpoint.[7] As an alternative to forward error correction (FEC) approaches, which embed redundancy in the initial transmission to correct errors proactively, ARQ protocols like stop-and-wait rely on feedback to request repeats only when issues arise, offering a balance of simplicity and reliability in resource-constrained settings.[7] Frames in stop-and-wait ARQ generally comprise a data payload, a header with a sequence number (often using a modulo-2 scheme for alternation between 0 and 1 to distinguish frames and ACKs), and an error-detection code such as a cyclic redundancy check (CRC) to identify transmission errors.[7] This protocol finds application in point-to-point links, including early modem-based systems and basic wireless connections, where its minimal overhead supports straightforward implementation over low-complexity channels.[7] In contrast to sliding window protocols that permit multiple unacknowledged frames (window size greater than 1), stop-and-wait enforces a window size of one to prioritize ease of error handling.[1]Historical Context
Stop-and-wait ARQ emerged in the 1960s and 1970s as a fundamental error control mechanism in early data communication systems, building on theoretical foundations from information theory. Claude Shannon's seminal 1948 work, "A Mathematical Theory of Communication," established the principles for reliable transmission over noisy channels, emphasizing the need for error detection and correction strategies that directly influenced subsequent ARQ protocols, including stop-and-wait variants.[8] This theoretical framework addressed channel capacity limits in the presence of noise, providing the conceptual basis for retransmission-based reliability in telecommunications.[9] The protocol's practical origins trace to precursors of modern networking, such as the ARPANET project initiated in the late 1960s, where reliable data transfer over potentially unreliable links was critical. Paul Baran's 1964 RAND Corporation report, "On Distributed Communications," proposed packet switching for robust military networks, highlighting the necessity of error recovery mechanisms like ARQ to handle message block losses in distributed systems. These ideas influenced early telegraphic and packet-based error control schemes, where stop-and-wait-like procedures ensured frame integrity in half-duplex environments, such as teletype systems prone to transmission errors. By the early 1970s, stop-and-wait ARQ was formalized as part of data link protocols for emerging computer networks. A key milestone came with its integration into standardized protocols, notably the High-Level Data Link Control (HDLC) framework developed by the International Organization for Standardization (ISO) in 1979, which specified stop-and-wait as the basic mode for automatic error correction in synchronous data links.[10] HDLC's adoption extended to international standards, including the ITU-T V.42 recommendation in 1988, which incorporated LAPM (Link Access Procedure for Modems)—an HDLC derivative using stop-and-wait ARQ—for error-free modem communications over telephone networks. In satellite communications, where propagation delays amplified retransmission inefficiencies, stop-and-wait ARQ was employed in early systems to manage high error rates, though its simplicity made it suitable for half-duplex geostationary links starting in the 1970s. Over time, stop-and-wait ARQ evolved to support full-duplex operation through the addition of a single sequence bit, enabling the alternating bit protocol to distinguish between consecutive frames and prevent duplication. While no major patents were issued for the core mechanism—reflecting its status as a foundational technique rather than a proprietary invention—it served as a conceptual basis for higher-layer reliability in protocols like TCP, outlined in RFC 793 (1981), which extended ARQ principles with sliding windows for internetworking.[11] Though largely superseded in high-speed networks due to low throughput from idle waiting periods, stop-and-wait ARQ remains pivotal for understanding the progression to advanced error control in modern telecommunications.Protocol Operation
Sender Behavior
In the stop-and-wait ARQ protocol, the sender begins by preparing a data frame for transmission. This involves encapsulating the payload data within a frame structure that includes a header containing essential control information and a trailer for error detection. The header typically features a 1-bit sequence number, which alternates between 0 and 1 to distinguish successive frames and detect duplicates, along with control bits indicating the frame type (e.g., data or supervisory). The trailer consists of a checksum, such as a cyclic redundancy check (CRC), to enable error verification at the receiver.[12] A representative frame structure can be illustrated as follows:| Field | Description | Size (bits) |
|---|---|---|
| Header | Sequence number (1 bit), control bits | Variable (e.g., 8-16) |
| Data | Payload | Variable (e.g., 1000) |
| Trailer | Checksum (e.g., CRC) | 16-32 |
This logic ensures that frames are sent in sequence and only progresses upon positive confirmation from the receiver's ACK generation.[12] The use of a 1-bit sequence number facilitates alternation between even (0) and odd (1) frames, allowing the sender to verify that the receiver has processed the prior frame correctly before sending the next, thus preserving order without complex numbering schemes. In extensions, cumulative ACKs may be supported to acknowledge multiple prior frames, but the basic protocol relies on per-frame acknowledgments.[14] For instance, on a communication link with a propagation delay of 50 ms in each direction (yielding an RTT of 100 ms), the sender remains idle for approximately this RTT after transmitting a frame, assuming no errors, before receiving the ACK and proceeding to the next transmission. This idle period highlights the protocol's inefficiency on high-latency links.[12]while data to send: prepare frame with current sequence number send frame start timer wait for ACK or timeout if ACK received and sequence matches: advance sequence number stop timer else if timeout: retransmit frame restart timerwhile data to send: prepare frame with current sequence number send frame start timer wait for ACK or timeout if ACK received and sequence matches: advance sequence number stop timer else if timeout: retransmit frame restart timer
Receiver Behavior
In Stop-and-wait ARQ, the receiver operates reactively to ensure reliable frame delivery by validating incoming data before providing feedback to the sender. Upon receiving a frame, the receiver first captures it from the communication channel and performs an integrity check using a cyclic redundancy check (CRC) to detect transmission errors. If the CRC indicates any corruption, the frame is discarded silently, as the basic protocol does not mandate negative acknowledgments (NAKs) in all implementations, leading the sender to rely on a timeout for retransmission.[15][5] The receiver then verifies the frame's sequence number, typically alternating between 0 and 1 in this simple protocol, against the expected value to confirm it is the next in-order frame and not a duplicate from a prior transmission. Only if both the CRC passes and the sequence number matches the anticipated value does the receiver accept the frame, delivering its payload to the upper network layer for further processing. In response, the receiver generates and transmits an acknowledgment (ACK) frame containing the sequence number of the next expected frame, signaling the sender to proceed. Duplicate frames are discarded without delivery to the upper layer, but the receiver sends an ACK containing the sequence number of the next expected frame to acknowledge prior successful reception. With 1-bit sequencing, out-of-sequence frames are treated as duplicates.[15][5] Buffer management at the receiver is minimal due to the protocol's one-frame-at-a-time nature, requiring space for only a single incoming frame at any moment. No reordering buffers are needed, as the sequential transmission enforced by the sender ensures frames arrive in order when error-free, simplifying the receiver's hardware and software requirements compared to more advanced ARQ variants. This single-buffer approach avoids the complexity of handling multiple outstanding frames.[15][5] For instance, consider a scenario where a frame with sequence number 1 arrives but is corrupted during transmission. The receiver detects the error via CRC validation, discards the frame without delivering it to the upper layer, and refrains from sending an ACK. This absence of acknowledgment prompts the sender's timeout mechanism after a predefined period, triggering retransmission of the same frame. If the protocol variant supports NAKs, the receiver might instead send a NAK to explicitly notify the sender of the corruption, expediting recovery, though this is not universal in basic stop-and-wait implementations.[15]Error Control Mechanisms
Acknowledgment Process
In the stop-and-wait ARQ protocol, the receiver generates acknowledgments to inform the sender of the successful or unsuccessful reception of a data frame. Positive acknowledgments (ACKs) confirm the correct receipt of a frame, while negative acknowledgments (NAKs) indicate detected errors, though NAKs are optional in basic implementations of the protocol.[16][17] Positive ACKs are typically labeled ACK0 or ACK1, corresponding to the expected next sequence number (using modulo-2 arithmetic for the single-bit sequence space), allowing the sender to verify the acknowledgment matches the sent frame as detailed in sender behavior.[18] Acknowledgments are transmitted as short control frames sent by the receiver immediately after validating the received data frame using error detection mechanisms like checksums.[16] Due to the protocol's single-frame transmission nature, piggybacking of acknowledgments onto data frames is not employed, as the receiver typically has no outgoing data during the sender's wait period.[19] In bidirectional links, whether full-duplex or half-duplex, acknowledgments utilize the reverse channel to return to the sender, ensuring feedback over the shared medium.[19] Error scenarios involving acknowledgments can degrade reliability. A lost ACK prompts the sender to retransmit the frame unnecessarily, as the receiver had successfully processed it but the feedback never arrives.[19] Similarly, a damaged ACK is interpreted by the sender as a loss, leading to retransmission of the original frame.[16]Retransmission Handling
In stop-and-wait ARQ, the sender starts a timeout timer immediately after transmitting a data frame, with the timer duration typically set to 2-3 times the estimated round-trip time (RTT) to accommodate variations in propagation, transmission, and processing delays.[15] Upon expiration of this timer without receipt of an acknowledgment (ACK), the sender retransmits an identical copy of the frame to recover from losses or undetected errors.[2] To handle potential duplicates from retransmissions, the receiver uses a 1-bit sequence number in both frames and ACKs. If a received frame's sequence number matches the one already successfully processed (indicating a duplicate), the receiver discards the frame and retransmits the prior ACK to inform the sender and prevent unnecessary further retries.[18] Backoff strategies in stop-and-wait ARQ are minimal in basic versions, relying on a fixed timer reset to the initial value after each retransmission rather than progressive increases. Adaptive timers may be used in extensions to adjust based on observed network conditions, but simple exponential backoff is not a standard feature.[20] Error detection, often via cyclic redundancy check (CRC) to identify corrupted frames and trigger a negative acknowledgment (NAK), precedes the timeout-based retransmission if immediate feedback is available.[18] A representative timeout calculation is given by T_{out} = RTT + k \cdot \sigma where RTT is the estimated round-trip time, \sigma is the standard deviation (variance margin) of RTT measurements, and k is a multiplier such as 4 to ensure conservatism. In bursty error channels, where frame losses cluster together, this leads to successive timeouts and retransmissions until an ACK is received, potentially amplifying recovery time for affected frames.[20]Performance Evaluation
Throughput and Efficiency
The throughput of stop-and-wait ARQ represents the effective data rate achieved over the channel, calculated as the frame size divided by the total time required to successfully transmit one frame and receive its acknowledgment. This total time encompasses the frame transmission time, twice the one-way propagation delay (to account for the round-trip), and the acknowledgment transmission time.[15] In an error-free channel, the efficiency η quantifies channel utilization as the ratio of useful transmission time to the overall cycle time per frame. It is given by η = t_f / (t_f + t_a + 2 t_d + t_p), where t_f is the frame transmission time, t_a is the acknowledgment transmission time, t_d is the one-way propagation delay, and t_p is the total processing time at sender and receiver. Equivalently, normalizing times to bit durations (assuming unit bit rate for simplicity), this becomes η = U / (U + A + 2 T_p + T_proc), with U denoting useful data bits per frame, A the acknowledgment bits, T_p the propagation delay in bit-times, and T_proc the processing overhead in bit-times. The derivation follows from the protocol's idle periods: after transmitting U bits, the channel is idle during the round-trip propagation (2 T_p bits worth of time) plus overhead for A bits and T_proc, yielding the denominator as the full cycle cost per successful frame. Neglecting t_a and t_p (common when acknowledgments are short and processing is minimal), this simplifies to η = 1 / (1 + 2a), where a = t_d / t_f is the ratio of propagation delay to frame transmission time.[15][21] In error-prone channels, efficiency degrades due to retransmissions triggered by frame errors or lost acknowledgments. Assuming a frame error probability P_e (encompassing both data and control errors) and geometric retransmission distribution, the expected number of attempts per successful frame is 1 / (1 - P_e). With each attempt incurring the full cycle time S = t_f + 2 t_d + t_a + t_p, the adjusted efficiency is η = [t_f / S] × (1 - P_e) = η_0 × (1 - P_e), where η_0 is the error-free efficiency; this holds when the timeout equals the round-trip time, ensuring full cycles per attempt.[22][15] Efficiency notably falls below 50% in scenarios where the round-trip time exceeds the frame transmission time, such as satellite links with propagation delays around 250 ms one-way, rendering stop-and-wait impractical without enhancements.[23]Delay Analysis
The delay in stop-and-wait ARQ arises from several key components that contribute to the total time required to successfully transmit a single frame and receive its acknowledgment. Transmission delay, denoted as T_{\text{tx}}, is the time needed to serialize the frame onto the link and equals the frame size divided by the link bandwidth, T_{\text{tx}} = L / R, where L is the frame length in bits and R is the bandwidth in bits per second.[24] Propagation delay, T_{\text{prop}}, represents the time for the signal to travel the physical distance between sender and receiver, calculated as T_{\text{prop}} = d / c, with d as the distance and c as the speed of propagation (approximately the speed of light in the medium).[24] Processing delay, T_{\text{proc}}, occurs at the receiver as it checks the frame for errors and generates the acknowledgment (ACK), typically a small value on the order of microseconds in modern hardware but potentially higher if queuing is involved.[24] The ACK round-trip includes the transmission time for the ACK frame, T_{\text{ack}} = L_{\text{ack}} / R, plus another propagation delay back to the sender, often approximating the reverse propagation if ACK size is small.[25] The total cycle time for a successful frame transmission in an error-free scenario is the sum of these components: T_{\text{cycle}} = T_{\text{tx}} + 2T_{\text{prop}} + T_{\text{ack}} + T_{\text{proc}}. This cycle dominates performance in stop-and-wait ARQ, as the sender remains idle during the round-trip wait for the ACK, leading to underutilization of the channel.[25] In high-latency environments, such as wide-area networks (WANs) or satellite links, the propagation delay often overshadows other terms, making the idle wait period the primary bottleneck and severely limiting overall protocol responsiveness.[24] For instance, in geostationary satellite links with a one-way propagation delay of approximately 250 ms, the round-trip propagation alone contributes about 500 ms per frame, restricting the protocol's suitability to low-bandwidth applications like simple telemetry rather than high-throughput data transfers.[25][26] Delay variance, or jitter, in stop-and-wait ARQ stems from factors such as variable error rates, which trigger occasional retransmissions and extend the cycle time unpredictably, and network congestion, which introduces additional queuing delays within the processing component.[24] Simulations illustrate this contrast between environments: in local area networks (LANs) with negligible propagation delays (on the order of microseconds over short distances), the total cycle time remains low and stable, often under 1 ms for typical frame sizes, enabling efficient operation for short-range links.[27] In contrast, WAN simulations show cycle times scaling to tens or hundreds of milliseconds due to dominant propagation delays, with jitter amplified by intermittent errors or congestion, resulting in highly variable end-to-end latencies unsuitable for real-time applications.[28]Limitations and Improvements
Key Drawbacks
Stop-and-wait ARQ exhibits significant inefficiency in bandwidth utilization due to the sender's idle periods while awaiting acknowledgments, particularly on links with high bandwidth-delay products such as long-distance or high-speed networks. This protocol is well-suited only to low-bandwidth-delay scenarios and becomes notably inefficient for applications like satellite communications, where propagation delays exacerbate channel underutilization.[29] The protocol's dependence on transmitting and acknowledging a single frame at a time heightens its vulnerability to losses, as the failure of either a data frame or its corresponding acknowledgment completely stalls transmission until retransmission occurs. In error-prone environments like wireless channels, this single-frame dependency amplifies the impact of losses, discarding errored data without recovery mechanisms and leading to repeated halts that mimic head-of-line blocking effects.[6] Scalability limitations further hinder stop-and-wait ARQ's applicability, especially for real-time applications such as VoIP, where cumulative waiting times for acknowledgments introduce excessive delays that degrade performance under varying traffic loads. In battery-powered IoT devices within wireless sensor networks, the frequent transmission of explicit acknowledgments contributes to higher energy consumption, making the protocol less suitable for energy-constrained environments compared to alternatives that minimize acknowledgment overhead.[30][31]Related Protocols
Stop-and-wait ARQ, with its single-frame transmission and wait-for-acknowledgment mechanism, suffers from low throughput on high-latency links due to idle periods.[32] To address this, Go-Back-N ARQ extends the protocol by permitting the sender to transmit up to N outstanding frames without acknowledgment, where N > 1 represents the window size, thereby pipelining transmissions and improving efficiency.[33] Upon detecting an error via a negative acknowledgment or timeout, the sender retransmits all frames from the erroneous one onward, discarding correctly received subsequent frames at the receiver.[32] This approach requires a larger sequence number space, typically using k bits to support a maximum window of 2^k - 1, ensuring unambiguous identification of frames within the expanded pipeline.[34] Selective Repeat ARQ further refines error recovery by retransmitting only the specific erroneous frames, while the receiver buffers out-of-order frames to maintain sequence integrity upon delivery to higher layers.[3] This selective mechanism minimizes unnecessary retransmissions compared to Go-Back-N, enhancing throughput in error-prone channels, but it demands additional receiver buffer space proportional to the window size.[33] To prevent ambiguity between new frames and retransmissions, the protocol employs sequence numbers ranging from 0 to 2W - 1, where W is the window size, allowing the receiver to distinguish frames across sender and receiver windows.[35] The following table summarizes key differences among these ARQ variants:| Protocol | Window Size | Retransmission Strategy | Sequence Number Requirements | Complexity |
|---|---|---|---|---|
| Stop-and-Wait | 1 | Retransmit single erroneous frame | Minimal (1 bit sufficient) | Low (simple ACK handling) |
| Go-Back-N | N > 1 | Retransmit from error point to end | k bits for 2^k - 1 window | Medium (cumulative ACKs) |
| Selective Repeat | W | Retransmit only erroneous frames | 2W numbers | High (buffering and selective ACKs) |