Stop-and-Wait ARQ Efficiency Analysis

We've explored each component that affects Stop-and-Wait performance: utilization concepts, propagation delay, transmission delay, and round-trip time. Now we synthesize everything into the comprehensive efficiency formula—the master equation that allows you to analyze any Stop-and-Wait scenario.

This formula is the key to:

• Predicting actual throughput on any link
• Understanding when Stop-and-Wait is appropriate
• Quantifying the cost of simplicity vs. pipelining protocols
• Making informed decisions about network design and protocol selection

Mastering this formula means you can analyze any Stop-and-Wait scenario—from satellite links to local networks, from dial-up connections to high-speed fiber. You'll know exactly how efficient (or inefficient) the protocol will be, and why.

This is the culmination of the module: a unified framework for Stop-and-Wait efficiency analysis.

The Efficiency Definition:

Channel utilization (efficiency) is defined as the fraction of time the channel is used for transmitting useful data:

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

The Stop-and-Wait Cycle:

A complete Stop-and-Wait cycle consists of:

1. Transmission of data frame: Sender puts L bits on the channel

   • Duration: $T_t = \frac{L}{B}$

2. Propagation to receiver: Signal travels distance d

   • Duration: $T_p = \frac{d}{v}$

3. Receiver processing: Frame verification, ACK generation

   • Duration: $T_{\text{proc}}^{\text{rx}}$ (often negligible)

4. ACK transmission: Receiver transmits acknowledgment

   • Duration: $T_t^{\text{ack}} = \frac{L_{\text{ack}}}{B}$ (often negligible)

5. ACK propagation: ACK travels back to sender

   • Duration: $T_p$ (assuming symmetric link)

6. Sender processing: ACK verification, state update

   • Duration: $T_{\text{proc}}^{\text{tx}}$ (often negligible)

The Complete Cycle Time:

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

The Complete Efficiency Formula:

$$U = \frac{T_t}{T_t + T_p + T_{\text{proc}}^{\text{rx}} + T_t^{\text{ack}} + T_p + T_{\text{proc}}^{\text{tx}}}$$

Standard Simplifications:

For most analyses, we assume:

• Processing times are negligible: $T_{\text{proc}} \approx 0$
• ACK frames are small: $T_t^{\text{ack}} \approx 0$
• Links are symmetric: same $T_p$ in both directions

Simplified Efficiency Formula:

$$\boxed{U = \frac{T_t}{T_t + 2T_p}}$$

This is the fundamental Stop-and-Wait efficiency formula used in most textbook problems.

The efficiency formula can be expressed in several equivalent forms, each useful for different analyses:

Form 1: Basic Ratio (Timing-Based)

$$U = \frac{T_t}{T_t + 2T_p}$$

Use when: Transmission and propagation times are given directly.

Form 2: Using Parameter 'a' (Normalized)

Define $a = \frac{T_p}{T_t}$:

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

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

Use when: Comparing different scenarios with the same 'a' value.

Form 3: Expanded with Physical Parameters

Substituting $T_t = \frac{L}{B}$ and $T_p = \frac{d}{v}$:

$$U = \frac{L/B}{L/B + 2d/v} = \frac{L \cdot v}{L \cdot v + 2d \cdot B} = \frac{Lv}{Lv + 2dB}$$

Use when: Physical parameters (L, B, d, v) are provided directly.

Form 4: Using Bandwidth-Delay Product

Recall $a = \frac{T_p}{T_t} = \frac{T_p \cdot B}{L} = \frac{\text{BDP}}{L}$:

$$U = \frac{1}{1 + 2 \cdot \frac{\text{BDP}}{L}} = \frac{L}{L + 2 \cdot \text{BDP}}$$

Use when: Bandwidth-delay product is known.

Form 5: With ACK Transmission Time

When ACK transmission is not negligible:

$$U = \frac{T_t}{T_t + 2T_p + T_t^{\text{ack}}}$$

Use when: Problems specify ACK frame size or low-bandwidth links.

Form 6: Including Processing Time

When processing time matters:

$$U = \frac{T_t}{T_t + 2T_p + T_t^{\text{ack}} + T_{\text{proc}}}$$

Use when: Processing delays are explicitly given.

Real networks experience errors. When frames are corrupted or lost, they must be retransmitted, reducing effective efficiency.

Error Probability:

Let P be the probability that a frame or its ACK is corrupted/lost:

• P_data = probability of data frame error
• P_ack = probability of ACK error
• P = P_data + P_ack - P_data × P_ack ≈ P_data + P_ack (for small P)

For simplicity, we often use a single error probability P representing any error that requires retransmission.

Expected Number of Transmissions:

With error probability P, the expected number of transmissions until success follows a geometric distribution:

$$E[\text{attempts}] = \frac{1}{1-P}$$

For P = 0.1 (10% error rate): E[attempts] = 1.11 For P = 0.01 (1% error rate): E[attempts] = 1.01

Efficiency with Errors:

The efficiency formula must account for retransmissions:

$$U_{\text{with errors}} = U_{\text{ideal}} \times (1 - P)$$

Or more precisely:

$$U = \frac{T_t}{T_t + 2T_p} \times (1 - P)$$

Using parameter 'a':

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

Example Calculation:

Link parameters: a = 5, P = 0.05 (5% error rate)

Without errors: $$U_{\text{ideal}} = \frac{1}{1 + 10} = 0.0909 = 9.09%$$

With errors: $$U = \frac{1 - 0.05}{1 + 10} = \frac{0.95}{11} = 0.0864 = 8.64%$$

Errors reduce efficiency by: (9.09 - 8.64) / 9.09 = 5% (exactly the error rate!)

From Utilization to Throughput:

Channel utilization tells us what fraction of capacity is used. To find actual data rate:

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

Where:

• Throughput is in bits per second
• U is the utilization (0 to 1)
• B is the link bandwidth

Complete Throughput Formula:

$$\text{Throughput} = \frac{B}{1 + 2a} = \frac{B}{1 + 2\frac{T_p}{T_t}}$$

Substituting $T_t = L/B$ and $T_p = d/v$:

$$\text{Throughput} = \frac{B}{1 + \frac{2d \cdot B}{v \cdot L}} = \frac{B \cdot v \cdot L}{v \cdot L + 2d \cdot B}$$

Alternative Form (Frames per Second):

$$\text{Frame Rate} = \frac{1}{T_t + 2T_p} = \frac{1}{\text{RTT}}$$

$$\text{Throughput} = \text{Frame Rate} \times L = \frac{L}{T_t + 2T_p}$$

Payload Throughput vs. Gross Throughput:

Gross throughput counts all transmitted bits (including headers): $$\text{Throughput}{\text{gross}} = U \times B = \frac{L{\text{total}}}{T_t + 2T_p}$$

Payload throughput counts only useful data: $$\text{Throughput}{\text{payload}} = \text{Throughput}{\text{gross}} \times \eta_{\text{overhead}}$$

Where overhead efficiency: $$\eta_{\text{overhead}} = \frac{L_{\text{payload}}}{L_{\text{total}}}$$

Example:

• TCP/IP over Ethernet: 1460 bytes payload per 1538 bytes total
• Overhead efficiency: 1460/1538 = 94.9%
• If gross throughput = 500 Kbps, payload throughput = 475 Kbps

Throughput with Errors:

$$\text{Throughput} = U \times B \times (1 - P) = \frac{B(1-P)}{1 + 2a}$$

Let's work through several comprehensive problems that integrate all concepts.

Problem 1: Complete Analysis

A terrestrial microwave link connects two cities 300 km apart. The link operates at 155 Mbps (OC-3). Frame size is 1024 bytes. Signal propagation velocity is 3 × 10⁸ m/s (wireless). Calculate:

a) Transmission time b) Propagation delay c) Parameter 'a' d) Channel utilization e) Effective throughput f) Time to transfer 100 MB file

Solution:

a) Transmission Time: $$T_t = \frac{L}{B} = \frac{1024 \times 8}{155 \times 10^6} = \frac{8,192}{1.55 \times 10^8} = 52.85 \text{ μs}$$

b) Propagation Delay: $$T_p = \frac{d}{v} = \frac{300,000}{3 \times 10^8} = 1 \text{ ms} = 1,000 \text{ μs}$$

c) Parameter 'a': $$a = \frac{T_p}{T_t} = \frac{1,000}{52.85} = 18.92$$

d) Channel Utilization: $$U = \frac{1}{1 + 2a} = \frac{1}{1 + 37.84} = \frac{1}{38.84} = 2.57%$$

e) Effective Throughput: $$\text{Throughput} = U \times B = 0.0257 \times 155 \times 10^6 = 3.99 \text{ Mbps}$$

f) File Transfer Time: $$\text{File size} = 100 \times 10^6 \times 8 = 8 \times 10^8 \text{ bits}$$ $$\text{Time} = \frac{8 \times 10^8}{3.99 \times 10^6} = 200.5 \text{ seconds} \approx 3.34 \text{ minutes}$$

With ideal utilization, transfer would take: 8 × 10⁸ / (155 × 10⁶) = 5.16 seconds

Problem 2: Including ACK and Errors

A satellite link operates at 2 Mbps with 270 ms one-way propagation delay. Data frames are 500 bytes, ACK frames are 25 bytes. The bit error rate is 10⁻⁵, and errors are detected at frame level. Calculate utilization.

Solution:

Step 1: Calculate timing components: $$T_t = \frac{500 \times 8}{2 \times 10^6} = \frac{4,000}{2 \times 10^6} = 2 \text{ ms}$$ $$T_t^{\text{ack}} = \frac{25 \times 8}{2 \times 10^6} = \frac{200}{2 \times 10^6} = 0.1 \text{ ms}$$ $$T_p = 270 \text{ ms}$$

Step 2: Calculate cycle time: $$T_{\text{cycle}} = T_t + 2T_p + T_t^{\text{ack}} = 2 + 540 + 0.1 = 542.1 \text{ ms}$$

Step 3: Calculate frame error probability: With BER = 10⁻⁵ and 4000-bit frame: $$P_{\text{frame}} = 1 - (1 - 10^{-5})^{4000} \approx 1 - e^{-0.04} \approx 0.0392 = 3.92%$$

Step 4: Calculate utilization: $$U = \frac{T_t}{T_{\text{cycle}}} \times (1 - P) = \frac{2}{542.1} \times (1 - 0.0392)$$ $$= 0.00369 \times 0.9608 = 0.00355 = 0.355%$$

How Utilization Responds to Parameter Changes:

Understanding sensitivity helps identify which improvements provide the greatest benefit.

Sensitivity to Frame Size (L):

$$\frac{\partial U}{\partial L} = \frac{\partial}{\partial L}\left(\frac{1}{1 + \frac{2dB}{vL}}\right) > 0$$

Utilization increases with frame size. Doubling frame size nearly doubles utilization when a >> 1.

Sensitivity to Bandwidth (B):

$$\frac{\partial U}{\partial B} = \frac{\partial}{\partial B}\left(\frac{1}{1 + \frac{2dB}{vL}}\right) < 0$$

Counter-intuitively, increasing bandwidth decreases utilization!

Sensitivity to Distance (d):

$$\frac{\partial U}{\partial d} = \frac{\partial}{\partial d}\left(\frac{1}{1 + \frac{2dB}{vL}}\right) < 0$$

Utilization decreases with distance (propagation delay increases).

| d | Tp | a (1 Gbps) | U | |---|----|-----------|-|| | 10 km | 50 μs | 4.17 | 10.7% | | 100 km | 500 μs | 41.7 | 1.18% | | 1,000 km | 5 ms | 417 | 0.12% | | 10,000 km | 50 ms | 4,170 | 0.012% |

Summary of Sensitivities:

When is Stop-and-Wait Acceptable?

Generally, Stop-and-Wait is acceptable when utilization exceeds some threshold (commonly 50%):

$$U > 0.5 \Rightarrow \frac{1}{1 + 2a} > 0.5 \Rightarrow 1 + 2a < 2 \Rightarrow a < 0.5$$

Condition for acceptable efficiency: $$a = \frac{T_p}{T_t} = \frac{d \cdot B}{v \cdot L} < 0.5$$

Rearranging: $$d < \frac{v \cdot L}{2B}$$

Maximum Distance for 50% Efficiency (1500-byte frames):

Protocol Selection Decision Tree:

1. Calculate 'a' for your link:

   • a = (d × B) / (v × L)

2. If a < 0.5:

   • Stop-and-Wait is acceptable (U > 50%)
   • Simpler implementation
   • Lower buffer requirements

3. If 0.5 < a < 10:

   • Stop-and-Wait is inefficient but functional
   • Consider sliding window if throughput matters
   • Go-Back-N may suffice

4. If a > 10:

   • Stop-and-Wait is severely inefficient (U < 10%)
   • Sliding window is mandatory for reasonable throughput
   • Selective Repeat for noisy channels

5. If a > 100:

   • Stop-and-Wait is catastrophically inefficient (U < 1%)
   • Must use sliding window with large windows
   • Consider TCP with window scaling
   • May need specialized protocols (satellite, LFN)

This module has provided comprehensive coverage of Stop-and-Wait ARQ efficiency analysis. Let's consolidate the essential knowledge.