101
0/228
Loading content...
We've established that Stop-and-Wait ARQ provides reliable data transmission through acknowledgments, timeouts, and sequence numbers. But reliability comes at a cost. The fundamental question of this section is: How efficiently does Stop-and-Wait utilize the available channel capacity?
The answer, as we'll discover, is sobering: Stop-and-Wait can be remarkably inefficient, especially on high-bandwidth or high-latency links. Understanding this inefficiency is crucial because:
Let's dive deep into the numbers.
By the end of this page, you will be able to calculate Stop-and-Wait utilization, understand the bandwidth-delay product, analyze efficiency under various network conditions, and determine when Stop-and-Wait is acceptable versus when sliding window protocols are required.
Channel Utilization (also called efficiency or throughput efficiency) measures what fraction of the channel's capacity is actually used for transmitting useful data.
The Basic Definition:
Utilization = Useful_Transmission_Time / Total_Cycle_Time
Where:
Intuition:
Imagine a pipe with water flowing through it. The pipe has a certain capacity (how much water it can carry per second). But if you're only filling the pipe intermittently—squirt, wait, squirt, wait—most of the pipe is empty most of the time. The utilization measures what fraction of the pipe is actually carrying water on average.
Utilization is a percentage (0% to 100% or 0 to 1). Throughput is an absolute rate (bits per second). They're related: Throughput = Utilization × Channel_Bandwidth. A 50% utilization on a 1 Gbps link means 500 Mbps actual throughput.
What Reduces Utilization?
Several factors prevent 100% utilization:
| Factor | Description | Impact on Stop-and-Wait |
|---|---|---|
| Propagation delay | Time for signal to travel | Must wait for ACK to travel back |
| Processing delay | Time to process frame/ACK | Usually small, but adds up |
| Acknowledge overhead | ACK frame transmission | Small but non-zero |
| Protocol overhead | Headers, CRC, framing | Part of every frame |
| Idle waiting | Time spent waiting for ACK | Major impact on Stop-and-Wait |
For Stop-and-Wait, the idle waiting time dominates. The sender sits idle while the frame propagates to the receiver, the receiver processes it, the ACK propagates back, and the sender processes the ACK. All this time, the channel is either carrying a small ACK or nothing at all.
Let's derive the precise utilization formula for Stop-and-Wait.
Define the Variables:
The Stop-and-Wait Cycle:
Time →
|-------- T_frame --------|------- T_prop -------|-- T_proc --|-- T_ack --|--- T_prop ---|
| Sending data frame | Frame traveling | Processing | Sending | ACK traveling |
| | to receiver | + ACK prep | ACK | to sender |
| | | | | |
← Sender busy → ← Sender idle →
Total Cycle Time:
T_cycle = T_frame + T_prop + T_proc + T_ack + T_prop
= T_frame + 2×T_prop + T_proc + T_ack
Simplified (ignoring processing and ACK transmission):
T_cycle ≈ T_frame + 2×T_prop
The Utilization Formula:
U = T_frame / T_cycle = T_frame / (T_frame + 2×T_prop)
Divide numerator and denominator by T_frame:
U = 1 / (1 + 2×T_prop/T_frame)
Define the propagation-to-transmission ratio:
a = T_prop / T_frame
Then:
U = 1 / (1 + 2a)
This elegant formula shows that utilization depends entirely on the ratio a.
Key Insight:
The parameter 'a' is sometimes called the 'bandwidth-delay product normalized by frame size' or simply the 'propagation ratio.' It captures how 'large' the pipe is compared to the frame—or equivalently, how many frames could fit in the pipe simultaneously if we were pipelining.
Including ACK Transmission:
For a more precise formula that includes ACK transmission time:
T_cycle = T_frame + 2×T_prop + T_ack
U = T_frame / (T_frame + 2×T_prop + T_ack)
If we define:
Then:
U = L / (L + 2×T_prop×R + L_ack)
= L / (L + 2×d×R/v + L_ack)
Typically, L_ack << L (ACKs are much smaller than data frames), so the simpler formula is often accurate enough.
Let's work through concrete examples to develop intuition for Stop-and-Wait efficiency.
Example 1: Local Area Network (LAN)
Setup:
Calculations:
T_frame = L/R = 8000 / 100,000,000 = 80 μs
T_prop = d/v = 100 / (2×10⁸) = 0.5 μs
a = T_prop / T_frame = 0.5 / 80 = 0.00625
U = 1 / (1 + 2a) = 1 / (1 + 0.0125) = 0.988 ≈ 98.8%
Interpretation: On a short LAN link, Stop-and-Wait achieves excellent utilization. The propagation delay is negligible compared to transmission time.
Example 2: Wide Area Network (WAN)
Setup:
Calculations:
T_frame = 8000 / 100,000,000 = 80 μs
T_prop = 1,000,000 / (2×10⁸) = 5 ms = 5000 μs
a = T_prop / T_frame = 5000 / 80 = 62.5
U = 1 / (1 + 2a) = 1 / (1 + 125) = 1/126 ≈ 0.8%
Interpretation: On a 1000 km link, utilization drops below 1%! The sender transmits for 80 μs, then waits over 10 ms for the ACK. The channel is idle 99% of the time.
Less than 1% utilization means you're paying for 100 Mbps but only using ~0.8 Mbps effectively. This is economically disastrous and explains why Stop-and-Wait is never used on long-distance high-speed links.
Example 3: Satellite Link (Geostationary)
Setup:
Calculations:
T_frame = 8000 / 10,000,000 = 800 μs = 0.8 ms
a = T_prop / T_frame = 135 / 0.8 = 168.75
U = 1 / (1 + 2a) = 1 / (1 + 337.5) = 1/338.5 ≈ 0.3%
Interpretation: Satellite links are the worst case for Stop-and-Wait. The sender transmits for less than 1 ms, then waits 270 ms for the ACK. The efficiency is practically zero.
Summary Table:
| Scenario | T_frame | T_prop | a | Utilization |
|---|---|---|---|---|
| LAN (100m) | 80 μs | 0.5 μs | 0.00625 | 98.8% |
| Campus (1 km) | 80 μs | 5 μs | 0.0625 | 94.1% |
| Metro (100 km) | 80 μs | 500 μs | 6.25 | 7.4% |
| WAN (1000 km) | 80 μs | 5 ms | 62.5 | 0.8% |
| Satellite (GEO) | 800 μs | 135 ms | 168.75 | 0.3% |
The Bandwidth-Delay Product (BDP) is a fundamental concept in network performance analysis. It quantifies how much data can be "in flight" in the network at once.
Definition:
BDP = Bandwidth × Round_Trip_Time = R × 2×T_prop
The BDP represents the number of bits that can be in the pipe—transmitted but not yet acknowledged.
Physical Interpretation:
Imagine the network as a pipe. The bandwidth is the pipe's cross-sectional area (how much water can flow through per second). The RTT is the pipe's length (how long it takes for water to reach the other end and confirmation to return). The BDP is the pipe's volume—how much water the pipe can hold.
Stop-and-Wait and BDP:
Stop-and-Wait sends one frame, then waits. It "fills" the pipe with exactly one frame's worth of data (L bits), regardless of how large the pipe actually is.
Utilization = Data_in_pipe / Pipe_capacity = L / BDP
When L << BDP, utilization is terrible—we're using a tiny fraction of the pipe's capacity.
Example: The Empty Pipe
Consider a 1 Gbps transatlantic link with 50 ms one-way delay:
BDP = 1,000,000,000 bps × 0.1 s = 100,000,000 bits = 12.5 MB
The pipe can hold 12.5 megabytes of data in flight!
But with Stop-and-Wait sending 1500-byte frames:
Data per cycle = 1500 bytes = 12,000 bits
Utilization = 12,000 / 100,000,000 = 0.00012 = 0.012%
The pipe is 99.988% empty. We're sending a single drop of water through a massive pipeline, then waiting for it to reach the other end before sending another drop.
The Window Size Solution (Preview):
Sliding window protocols fill the pipe by keeping multiple frames in flight:
Window_size = BDP / Frame_size
= 100,000,000 bits / 12,000 bits ≈ 8333 frames
With a window of ~8333 frames, the sender can transmit continuously, achieving near 100% utilization. This is precisely what Go-Back-N and Selective Repeat enable.
For efficient transmission, the window size (in bytes) should equal or exceed the bandwidth-delay product. Stop-and-Wait has a window of 1 frame, which is grossly insufficient for large BDP links. The larger the BDP, the larger the window needed for good utilization.
So far, we've analyzed ideal conditions with no errors. Real channels have errors, which reduce efficiency further.
Error Model:
Let p be the frame error probability—the probability that a transmitted frame (or its ACK) is corrupted or lost.
Expected Transmissions:
With probability p of failure, the expected number of transmissions for one successful delivery is:
E[transmissions] = 1 + p + p² + p³ + ... = 1/(1-p)
(This is a geometric series: we succeed on the first try with probability (1-p), or fail once and retry, etc.)
Efficiency with Errors:
U_error = U_ideal × (1 - p)
More precisely, accounting for retransmissions:
U_error = (1 - p) / (1 + 2a)
Where (1-p) accounts for the overhead of failed transmissions.
Numerical Example:
Setup:
Without errors:
U = 1/(1 + 2×62.5) = 0.79%
With errors:
U_error = (1 - 0.01) / (1 + 125) = 0.99 / 126 = 0.79%
Here, the 1% error rate barely affects efficiency because utilization was already terrible.
High error rate example (p = 10%):
U_error = (1 - 0.1) / 126 = 0.9 / 126 = 0.71%
With 10% errors, we lose another 10% efficiency, but the baseline was so low it hardly matters.
When Errors Matter More:
For high-utilization scenarios (small a), errors have bigger impact:
LAN with a = 0.00625 and p = 10%:
U_error = (1 - 0.1) / (1 + 0.0125) = 0.9 / 1.0125 = 88.9%
Compared to 98.8% without errors—a 10 percentage point drop.
Beyond the average efficiency, errors also cause variable latency. Each retransmission adds a full round-trip time. For real-time applications, this jitter can be as problematic as the reduced throughput.
Given Stop-and-Wait's limitations, what can be done to improve efficiency without abandoning the protocol?
Strategy 1: Increase Frame Size
Since U = 1/(1 + 2a) and a = T_prop/T_frame, increasing T_frame (larger frames) reduces a:
Example: WAN with 1000-byte vs 10000-byte frames
1000-byte frame: a = 5000μs/80μs = 62.5, U = 0.79%
10000-byte frame: a = 5000μs/800μs = 6.25, U = 7.4%
10× larger frames yields ~10× better utilization.
Limitations:
| Frame Size | T_frame | a | Utilization |
|---|---|---|---|
| 500 bytes | 40 μs | 125 | 0.4% |
| 1000 bytes | 80 μs | 62.5 | 0.8% |
| 5000 bytes | 400 μs | 12.5 | 3.8% |
| 10000 bytes | 800 μs | 6.25 | 7.4% |
| 50000 bytes | 4000 μs | 1.25 | 28.6% |
Strategy 2: Reduce Propagation Delay
Not usually possible—it's determined by physics and geography!
However:
Strategy 3: Use Piggybacking
For bidirectional traffic, combining ACKs with data frames reduces overhead slightly.
Strategy 4: Abandon Stop-and-Wait!
The most effective "improvement" is to use a different protocol:
For high-BDP links, sliding window protocols are the only practical choice.
Stop-and-Wait is appropriate when: (1) BDP is small (short distances, low bandwidth), (2) simplicity is paramount (embedded systems, limited resources), (3) traffic is infrequent (occasional commands), or (4) it's used for control traffic (TCP connection setup). For bulk data transfer over any significant distance, use sliding window protocols.
Beyond utilization, we can analyze the effective throughput—how much useful data actually gets through per unit time.
Throughput Definition:
Throughput = Useful_data / Total_time = L_data / T_cycle
Where L_data is the payload size (excluding headers and CRC).
Accounting for Overhead:
Let:
Throughput = L_payload / T_cycle
= (L - L_overhead) / (T_frame + 2×T_prop)
= (L - L_overhead) / ((L/R) + 2×T_prop)
Normalized Throughput:
S = Throughput / Maximum_possible_throughput
For Stop-and-Wait:
S = (L_payload/L) × U
The first term accounts for protocol overhead; the second for idle time.
Example: Complete Throughput Calculation
Setup:
Calculations:
L = 1504 × 8 = 12,032 bits
T_frame = 12,032 / 100,000,000 = 120.32 μs
T_prop = 100,000 / (2×10⁸) = 0.5 ms = 500 μs
a = 500 / 120.32 = 4.16
U = 1 / (1 + 2×4.16) = 1 / 9.32 = 10.7%
Payload efficiency = 1460 / 1504 = 97.1%
Effective throughput = 100 Mbps × 10.7% × 97.1% = 10.4 Mbps
Interpretation: On a 100 Mbps metropolitan link, Stop-and-Wait achieves only ~10 Mbps effective throughput. You're paying for 100 Mbps but getting 10 Mbps.
Network capacity costs money. Using Stop-and-Wait at 10% efficiency means 90% of your investment is wasted. This is why protocol efficiency matters not just technically but economically.
We've thoroughly analyzed Stop-and-Wait efficiency, revealing both its limitations and the conditions under which it remains viable. Let's consolidate:
The Big Picture:
Stop-and-Wait trades efficiency for simplicity. When the BDP is small (LAN environments, low-speed links), this is an acceptable trade. When the BDP is large (WAN, internet, satellite), the efficiency loss is catastrophic.
Decision Framework:
If BDP < 1 frame:
Stop-and-Wait is fine
Else:
Use sliding window protocol
Window size ≥ BDP / Frame_size
Module Complete:
You now have comprehensive mastery of Stop-and-Wait ARQ: its basic operation, acknowledgment mechanisms, timeout and retransmission, sequence numbering, and efficiency characteristics. This foundation prepares you for the sliding window protocols that overcome Stop-and-Wait's limitations.
You've mastered the simplest ARQ protocol: why it exists, how it works, and when to use it. More importantly, you understand WHY it fails on high-BDP links—the motivation for the advanced protocols we'll study next. Congratulations on completing Module 1!