Stop-and-Wait ARQ Efficiency Analysis

Stop-and-Wait ARQ guarantees reliable data delivery through a simple mechanism: send a frame, wait for acknowledgment, then send the next frame. This simplicity comes at a cost—and understanding that cost is essential for every network engineer.

Consider this scenario: You have a 1 Gbps fiber link connecting two data centers 1000 km apart. Using Stop-and-Wait, you send a 1500-byte Ethernet frame and wait for the ACK before sending the next one. What's your actual throughput?

The answer is shocking: approximately 0.024% of the link capacity. Your 1 Gbps link effectively operates at 240 Kbps—slower than a dial-up modem from the 1990s.

Channel utilization is the metric that quantifies this inefficiency. It tells us what fraction of the available channel capacity we're actually using to transmit useful data. For Stop-and-Wait, this utilization is often abysmal—and understanding why is the key to designing better protocols.

Channel utilization (often denoted as U or η) represents the efficiency with which a communication protocol uses the available channel capacity. It is defined as the ratio of the time the channel is productively used for transmitting data to the total time a transmission cycle takes.

Formal Definition:

$$U = \frac{\text{Time spent transmitting useful data}}{\text{Total cycle time}}$$

For Stop-and-Wait ARQ, a transmission cycle consists of:

1. Transmission time — Time to push the frame bits onto the channel
2. Propagation delay — Time for the first bit to reach the receiver
3. Processing time — Time for the receiver to process the frame (often negligible)
4. ACK transmission time — Time to transmit the acknowledgment (often negligible)
5. ACK propagation delay — Time for the ACK to travel back to sender

The channel is only productive during step 1—the transmission of the actual data frame. All other time represents overhead inherent in the Stop-and-Wait protocol.

Why Utilization Matters:

Channel utilization directly translates to effective throughput. If you have a 100 Mbps link with 10% utilization, your effective data rate is only 10 Mbps. The remaining 90% of capacity is wasted waiting for acknowledgments.

Effective Throughput = Link Bandwidth × Utilization

$$\text{Throughput}_{\text{effective}} = B \times U$$

Where:

• B = Channel bandwidth (bits per second)
• U = Channel utilization (fraction between 0 and 1)

This relationship makes utilization analysis critical for:

• Capacity planning — Determining how much bandwidth to provision
• Protocol selection — Choosing appropriate ARQ mechanisms for link characteristics
• Performance prediction — Estimating actual application-level throughput
• Cost optimization — Avoiding over-provisioning expensive network links

To calculate utilization precisely, we must understand each time component in a Stop-and-Wait cycle. Let's define the key variables:

Primary Variables:

The Transmission Time (T_t):

Transmission time is the duration required to push all bits of a frame onto the communication channel. It depends on the frame size and the channel bandwidth:

$$T_t = \frac{L}{B}$$

Example:

• Frame size: 1500 bytes = 12,000 bits
• Bandwidth: 100 Mbps = 100 × 10⁶ bps

$$T_t = \frac{12,000}{100 \times 10^6} = 0.00012 \text{ seconds} = 120 \text{ μs}$$

The Propagation Delay (T_p):

Propagation delay is the time required for the first bit of the frame to travel from sender to receiver. It depends on the physical distance and the propagation velocity of the medium:

$$T_p = \frac{d}{v}$$

Example:

• Distance: 1000 km = 1,000,000 meters
• Velocity: 2 × 10⁸ m/s (typical for fiber optic)

$$T_p = \frac{1,000,000}{2 \times 10^8} = 0.005 \text{ seconds} = 5 \text{ ms}$$

The Total Cycle Time:

For Stop-and-Wait, the sender transmits a frame, waits for it to propagate, waits for the receiver to process it and send an ACK, and waits for the ACK to propagate back. Assuming processing time and ACK transmission time are negligible:

$$T_{\text{cycle}} = T_t + T_p + T_p = T_t + 2T_p$$

The factor of 2 accounts for the round-trip propagation delay—the signal must travel to the receiver AND the acknowledgment must travel back.

With our timing components defined, we can now derive the utilization formula for Stop-and-Wait ARQ.

Derivation:

Utilization is the fraction of time spent transmitting useful data:

$$U = \frac{T_t}{T_{\text{cycle}}} = \frac{T_t}{T_t + 2T_p}$$

To simplify this expression, we introduce the bandwidth-delay product ratio (often called 'a'):

$$a = \frac{T_p}{T_t} = \frac{d/v}{L/B} = \frac{d \cdot B}{v \cdot L}$$

Substituting into the utilization formula:

$$U = \frac{T_t}{T_t + 2T_p} = \frac{1}{1 + 2 \cdot \frac{T_p}{T_t}} = \frac{1}{1 + 2a}$$

The Fundamental Stop-and-Wait Utilization Formula:

$$\boxed{U = \frac{1}{1 + 2a}}$$

where $a = \frac{T_p}{T_t} = \frac{\text{Propagation Delay}}{\text{Transmission Time}}$

Interpreting the Formula:

1. When a = 0 (negligible propagation delay):

   • U = 1/(1 + 0) = 1 = 100%
   • Perfect efficiency—no waiting for ACKs
   • Occurs in extremely short links or very slow transmission rates

2. When a = 1 (propagation delay equals transmission time):

   • U = 1/(1 + 2) = 0.33 = 33%
   • Already significantly inefficient

3. When a = 10 (propagation delay is 10× transmission time):

   • U = 1/(1 + 20) = 0.048 = 4.8%
   • Severe efficiency loss

4. When a = 100 (high bandwidth-delay product):

   • U = 1/(1 + 200) = 0.005 = 0.5%
   • Catastrophic inefficiency

The formula reveals a fundamental truth: Stop-and-Wait efficiency degrades rapidly as the bandwidth-delay product increases.

Let's work through a comprehensive example to solidify our understanding.

Problem Statement:

A sender and receiver are connected by a 1 Gbps fiber optic link spanning 2000 km. The sender uses Stop-and-Wait ARQ with a frame size of 1500 bytes. The signal propagates at 2 × 10⁸ m/s. Calculate:

1. Transmission time (Tt)
2. Propagation delay (Tp)
3. The parameter 'a'
4. Channel utilization (U)
5. Effective throughput
6. Time to transfer a 1 GB file

Solution:

Step 1: Calculate Transmission Time

$$T_t = \frac{L}{B} = \frac{1500 \times 8 \text{ bits}}{10^9 \text{ bps}} = \frac{12,000}{10^9} = 12 \times 10^{-6} \text{ s} = 12 \text{ μs}$$

Step 2: Calculate Propagation Delay

$$T_p = \frac{d}{v} = \frac{2,000,000 \text{ m}}{2 \times 10^8 \text{ m/s}} = 0.01 \text{ s} = 10 \text{ ms}$$

Step 3: Calculate Parameter 'a'

$$a = \frac{T_p}{T_t} = \frac{10 \text{ ms}}{12 \text{ μs}} = \frac{0.01}{0.000012} = 833.33$$

Step 4: Calculate Utilization

$$U = \frac{1}{1 + 2a} = \frac{1}{1 + 2(833.33)} = \frac{1}{1667.67} = 0.0006 = 0.06%$$

Step 5: Calculate Effective Throughput

$$\text{Throughput} = B \times U = 10^9 \times 0.0006 = 600,000 \text{ bps} = 600 \text{ Kbps}$$

Despite having a 1 Gbps link, the effective data rate is only 600 Kbps!

Step 6: Calculate File Transfer Time

File size: 1 GB = 8 × 10⁹ bits

$$\text{Time} = \frac{\text{File Size}}{\text{Throughput}} = \frac{8 \times 10^9}{600,000} = 13,333 \text{ seconds} \approx 3.7 \text{ hours}$$

Comparison with Ideal:

With 100% utilization, the transfer would take:

$$\text{Time}_{\text{ideal}} = \frac{8 \times 10^9}{10^9} = 8 \text{ seconds}$$

Stop-and-Wait makes a 8-second transfer take 3.7 hours—a 1,666× slowdown.

The utilization formula U = 1/(1 + 2a) reveals four factors that influence Stop-and-Wait efficiency:

1. Distance (d) — Direct Relationship with 'a'

Longer distances mean larger propagation delays, increasing 'a' and decreasing utilization.

$$a \propto d \quad \Rightarrow \quad U \downarrow \text{ as } d \uparrow$$

Implications:

• Stop-and-Wait is acceptable for short-range communications (LANs)
• It becomes highly inefficient for long-haul links (WANs, satellite, intercontinental)
• Geostationary satellite links (~36,000 km altitude) have ~250 ms one-way delay—catastrophic for Stop-and-Wait

2. Bandwidth (B) — Direct Relationship with 'a'

Higher bandwidth means faster transmission, which makes the fixed propagation delay relatively larger.

$$a = \frac{d \cdot B}{v \cdot L} \propto B \quad \Rightarrow \quad U \downarrow \text{ as } B \uparrow$$

The counterintuitive result: Increasing bandwidth can decrease effective throughput with Stop-and-Wait!

3. Frame Size (L) — Inverse Relationship with 'a'

Larger frames mean longer transmission times, reducing the relative impact of propagation delay.

$$a = \frac{d \cdot B}{v \cdot L} \propto \frac{1}{L} \quad \Rightarrow \quad U \uparrow \text{ as } L \uparrow$$

Implications:

• Larger frames improve Stop-and-Wait efficiency
• However, frame size is constrained by MTU limits (typically 1500 bytes for Ethernet)
• Larger frames also increase retransmission cost if errors occur
• Jumbo frames (9000 bytes) can help, but have compatibility issues

4. Propagation Velocity (v) — Inverse Relationship with 'a'

Faster signal propagation reduces propagation delay, decreasing 'a' and improving utilization.

$$a \propto \frac{1}{v} \quad \Rightarrow \quad U \uparrow \text{ as } v \uparrow$$

Practical limits:

• Signal velocity is bounded by the speed of light (3 × 10⁸ m/s)
• In most practical media, velocity is about 2/3 of light speed
• This parameter is essentially fixed by physics—not a design variable

Despite its efficiency limitations, Stop-and-Wait remains appropriate in certain scenarios:

Scenario 1: Low Bandwidth-Delay Product (a << 1)

When propagation delay is much smaller than transmission time, utilization remains high.

Example:

• 56 Kbps modem
• 10 km link
• 1000-byte frames

$$T_t = \frac{8000}{56,000} = 143 \text{ ms}$$ $$T_p = \frac{10,000}{2 \times 10^8} = 50 \text{ μs}$$ $$a = \frac{0.00005}{0.143} = 0.00035$$ $$U = \frac{1}{1 + 2(0.00035)} = 99.93%$$

Scenario 2: Half-Duplex Links

On half-duplex channels where only one direction can transmit at a time, Stop-and-Wait's simplicity is advantageous since you can't pipeline anyway.

Scenario 3: Resource-Constrained Devices

When sender/receiver have limited memory for buffering, Stop-and-Wait's minimal buffer requirements (one frame at a time) make it attractive.

When solving utilization problems, several common errors can lead to incorrect answers:

Mistake 1: Unit Conversion Errors

The most common source of wrong answers is inconsistent units:

• Bandwidth: Convert to bits per second (not bytes, not Kbps, not Mbps)
• Frame size: Convert to bits (not bytes)
• Distance: Convert to meters (not km)
• Time: Keep track of seconds, milliseconds, microseconds

Always verify units before calculating!

Mistake 2: Forgetting the Round-Trip

Propagation delay appears twice (once for data, once for ACK). The formula uses 2Tp, not Tp alone.

$$U = \frac{T_t}{T_t + 2T_p} \quad \text{NOT} \quad \frac{T_t}{T_t + T_p}$$

Mistake 3: Confusing Throughput with Bandwidth

Bandwidth is the capacity. Throughput is the actual data rate achieved. They are only equal when U = 100%.

$$\text{Throughput} = \text{Bandwidth} \times \text{Utilization}$$

Mistake 4: Processing Time Assumptions

Receiver processing time is usually negligible but some problems include it. If specified:

$$T_{\text{cycle}} = T_t + T_p + T_{\text{proc}} + T_{\text{ack}} + T_p$$

Mistake 5: Mixing Up 'a' and Utilization

Remember:

• 'a' is the ratio Tp/Tt (can be > 1)
• Utilization is always between 0 and 1 (0% to 100%)
• As 'a' increases, utilization decreases

Mistake 6: Ignoring Overhead in Frame Size

Some problems specify payload size rather than total frame size. If headers are not included:

$$L_{\text{total}} = L_{\text{payload}} + L_{\text{header}} + L_{\text{trailer}}$$

Use total frame size for transmission time calculations.

This page established the fundamental framework for analyzing Stop-and-Wait ARQ efficiency. Here are the essential concepts: