Stop-and-Wait ARQ Efficiency Analysis

We've examined propagation delay (how long signals take to travel) and transmission delay (how long it takes to push bits onto the wire). Now we combine these to understand Round-Trip Time (RTT)—the total time for a complete request-response cycle.

In Stop-and-Wait ARQ, RTT is the critical metric because the sender cannot transmit the next frame until the acknowledgment completes its round trip. Every nanosecond added to RTT is a nanosecond the sender sits idle, wasting channel capacity.

Consider what happens when you ping a server:

C:\> ping google.com

Pinging google.com [142.250.185.46] with 32 bytes of data:
Reply from 142.250.185.46: bytes=32 time=14ms TTL=118
Reply from 142.250.185.46: bytes=32 time=13ms TTL=118
Reply from 142.250.185.46: bytes=32 time=12ms TTL=118
Reply from 142.250.185.46: bytes=32 time=14ms TTL=118

That 12-14ms represents your RTT to Google—the time for your packet to reach Google's server and for the response to return. For Stop-and-Wait, this would limit you to roughly 71-83 round trips per second, regardless of your bandwidth.

The Complete RTT Cycle:

For Stop-and-Wait ARQ, RTT represents the time from when the sender begins transmitting a frame until it receives the acknowledgment. This cycle includes:

1. Transmission of Data Frame (Tt_data)

• Sender pushes all frame bits onto the link
• Duration: L_data / B

2. Propagation to Receiver (Tp)

• Signal travels from sender to receiver
• Duration: d / v

3. Receiver Processing (Tproc_rx)

• Receiver verifies checksum, processes frame, generates ACK
• Duration: Typically microseconds (often negligible)

4. Transmission of ACK Frame (Tt_ack)

• Receiver pushes ACK bits onto link
• Duration: L_ack / B (often negligible)

5. Propagation of ACK (Tp)

• ACK signal travels from receiver to sender
• Duration: d / v (same as forward propagation for symmetric links)

6. Sender Processing (Tproc_tx)

• Sender processes ACK, updates state
• Duration: Typically negligible

The Complete RTT Formula:

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

Simplifying with common assumptions:

$$\text{RTT} = T_t^{\text{data}} + 2T_p + T_t^{\text{ack}} + T_{\text{proc}}$$

Standard Simplifications:

In most textbook problems and practical analyses:

• ACK frames are small (typically 64 bytes minimum), so Tt_ack << Tt_data
• Processing times are negligible compared to propagation
• Links are symmetric (same Tp in both directions)

Simplified RTT for Analysis:

$$\text{RTT} \approx T_t + 2T_p$$

This is the formula we use for Stop-and-Wait utilization:

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

The Simplest Case:

For a direct connection between sender and receiver:

$$\text{RTT} = T_t + 2T_p = \frac{L}{B} + \frac{2d}{v}$$

Example 1: Campus Network

Two buildings connected by 1 km fiber, 1 Gbps link, 1500-byte frames:

$$T_t = \frac{12,000}{10^9} = 12 \text{ μs}$$ $$2T_p = \frac{2 \times 1000}{2 \times 10^8} = 10 \text{ μs}$$ $$\text{RTT} = 12 + 10 = 22 \text{ μs}$$

Utilization: U = 12/22 = 54.5%

Example 2: Cross-Country Link

New York to San Francisco (4000 km), 10 Gbps, 1500-byte frames:

$$T_t = \frac{12,000}{10^{10}} = 1.2 \text{ μs}$$ $$2T_p = \frac{2 \times 4,000,000}{2 \times 10^8} = 40 \text{ ms} = 40,000 \text{ μs}$$ $$\text{RTT} = 1.2 + 40,000 = 40,001.2 \text{ μs} \approx 40 \text{ ms}$$

Utilization: U = 1.2/40,000 = 0.003%

Propagation utterly dominates!

Store-and-Forward Effects:

In multi-hop networks, frames are transmitted and received at each intermediate device. For n hops:

Forward Path:

• Frame transmitted n times (once per hop)
• Frame propagates across all links
• Each router adds processing delay
• Each router may add queuing delay

Return Path (ACK):

• ACK transmitted n times
• ACK propagates across all links
• Router processing and queuing again

Complete RTT for n Hops (Store-and-Forward):

$$\text{RTT} = \sum_{i=1}^{n}(T_t^{\text{data}(i)} + T_p^{(i)} + T_{\text{queue}}^{(i)} + T_{\text{proc}}^{(i)}) + \sum_{i=1}^{n}(T_t^{\text{ack}(i)} + T_p^{(i)} + T_{\text{queue}}^{(i)} + T_{\text{proc}}^{(i)})$$

Simplifying with identical links and negligible ACK/processing:

$$\text{RTT} \approx n \cdot T_t + 2 \sum_{i=1}^{n} T_p^{(i)}$$

Example: Three-Hop Internet Path

Path from client to server with three router hops:

Hop 1: 100 km fiber, 1 Gbps Hop 2: 2,000 km fiber, 10 Gbps Hop 3: 50 km fiber, 100 Mbps

Frame: 1500 bytes = 12,000 bits

Transmission Delays: $$T_t^{(1)} = \frac{12,000}{10^9} = 12 \text{ μs}$$ $$T_t^{(2)} = \frac{12,000}{10^{10}} = 1.2 \text{ μs}$$ $$T_t^{(3)} = \frac{12,000}{10^8} = 120 \text{ μs}$$

Propagation Delays: $$T_p^{(1)} = \frac{100,000}{2 \times 10^8} = 0.5 \text{ ms}$$ $$T_p^{(2)} = \frac{2,000,000}{2 \times 10^8} = 10 \text{ ms}$$ $$T_p^{(3)} = \frac{50,000}{2 \times 10^8} = 0.25 \text{ ms}$$

Total Forward Delay: $$T_{\text{forward}} = (12 + 1.2 + 120) \text{ μs} + (0.5 + 10 + 0.25) \text{ ms}$$ $$= 133.2 \text{ μs} + 10.75 \text{ ms} = 10.88 \text{ ms}$$

RTT (assuming symmetric return, negligible ACK): $$\text{RTT} \approx 2 \times 10.75 \text{ ms} + 133.2 \text{ μs} = 21.63 \text{ ms}$$

Note: Transmission delay is small compared to propagation in this WAN scenario.

The Gap Between Theory and Reality:

Theoretical RTT (RTT_min) considers only propagation delays—the absolute minimum determined by physics:

$$\text{RTT}_{\text{min}} = \frac{2d}{v}$$

Measured RTT includes all real-world delays:

$$\text{RTT}{\text{measured}} = \text{RTT}{\text{min}} + T_{\text{queuing}} + T_{\text{processing}} + T_{\text{transmission}}$$

Where Does the Extra Time Go?

1. Queuing Delay (Highly Variable):

• Packets wait in router buffers when links are congested
• Can range from 0 to hundreds of milliseconds
• Primary source of RTT variability
• Depends on instantaneous network load

2. Processing Delay:

• Routing table lookups
• Checksum verification
• NAT translation
• Firewall inspection
• Typically 10-1000 μs per hop

3. Transmission Delay:

• Multiple transmissions in store-and-forward networks
• Usually small on modern high-speed links
• Significant on slow links (DSL, cellular)

Example: New York to London RTT Analysis

Cable distance: approximately 6,000 km

Theoretical minimum: $$\text{RTT}_{\text{min}} = \frac{2 \times 6,000,000}{2 \times 10^8} = 60 \text{ ms}$$

Measured RTT (typical): 70-90 ms

Where does the extra 10-30 ms go?

RTT Inflation Factor: $$\text{Inflation} = \frac{\text{RTT}{\text{measured}}}{\text{RTT}{\text{min}}} = \frac{80}{60} = 1.33 \text{ (typical)}$$

Real-world RTT is typically 20-50% higher than theoretical minimum.

Why RTT Fluctuates:

Unlike propagation delay (constant) and transmission delay (constant for fixed frame size), measured RTT varies significantly over time:

Sources of RTT Variability:

1. Queuing Delay Variation:

   • Network traffic is bursty
   • Router queues fill and drain unpredictably
   • Congestion varies by time of day
   • Flash crowds cause sudden spikes

2. Route Changes:

   • BGP routing updates
   • Link failures and failovers
   • Load balancing across paths
   • Different paths have different delays

3. Processing Variation:

   • Router CPU load fluctuates
   • Deep packet inspection varies by packet type
   • Encryption/decryption processing

4. Wireless/Mobile Effects:

   • Retransmissions at link layer
   • Channel contention
   • Handoffs between access points/cells

Characterizing RTT Distribution:

Minimum RTT (RTT_min):

• The lowest observed RTT
• Close to theoretical minimum
• Represents best-case performance
• Measured during low congestion

Mean RTT (RTT_avg):

• Average over many samples
• Most commonly reported
• Used for capacity planning

Maximum RTT (RTT_max):

• Worst-case observed
• Can be 10× or more of minimum
• Critical for timeout calculations

Jitter (RTT Variation):

$$\text{Jitter} = \text{RTT}{\text{max}} - \text{RTT}{\text{min}}$$

Or as standard deviation:

$$\sigma_{\text{RTT}} = \sqrt{\frac{1}{n}\sum_{i=1}^{n}(\text{RTT}i - \text{RTT}{\text{avg}})^2}$$

Active Measurement:

1. ICMP Ping: The simplest and most common method:

ping -c 4 target.example.com

Measures RTT for ICMP Echo Request/Reply packets.

Limitations:

• ICMP may be rate-limited or blocked
• Doesn't measure actual application path (different routing)
• Small packets don't reflect larger transfer behavior

2. TCP Handshake Timing: Measure time from SYN to SYN-ACK:

Time SYN sent: T1
Time SYN-ACK received: T2
RTT ≈ T2 - T1

Advantage: Measures actual TCP path Limitation: Includes server processing time

3. HTTP Timing: Measure time from request start to first byte:

Time of Request (TOR) = T1
Time to First Byte (TTFB) = T2
RTT ≈ TTFB - TOR - server_processing

Advantage: Application-realistic Limitation: Hard to separate RTT from server latency

Passive Measurement:

Observe RTT from ongoing traffic without injecting probes:

1. TCP Timestamp Echo: TCP timestamps allow receivers to echo sender's timestamp:

• Sender includes timestamp T1 in segment
• Receiver echoes T1 in acknowledgment
• Sender computes RTT = current_time - T1

2. ACK Observation: For each data segment, measure time until ACK received: $$\text{RTT}i = T{\text{ACK}i} - T{\text{DATA}_i}$$

RTT Estimation (Exponential Weighted Moving Average):

TCP uses EWMA to smooth RTT measurements:

$$\text{SRTT}{\text{new}} = (1 - \alpha) \cdot \text{SRTT}{\text{old}} + \alpha \cdot \text{RTT}_{\text{measured}}$$

Typically α = 1/8 = 0.125

Retransmission Timeout (RTO) Calculation:

$$\text{RTO} = \text{SRTT} + 4 \cdot \text{RTTVAR}$$

Where RTTVAR tracks RTT deviation:

$$\text{RTTVAR}{\text{new}} = (1 - \beta) \cdot \text{RTTVAR}{\text{old}} + \beta \cdot |\text{SRTT} - \text{RTT}_{\text{measured}}|$$

Typically β = 1/4 = 0.25

The Fundamental Constraint:

Stop-and-Wait sends one frame per RTT. Maximum frame rate:

$$\text{Frame Rate}_{\text{max}} = \frac{1}{\text{RTT}}$$

Maximum throughput:

$$\text{Throughput}_{\text{max}} = \frac{L}{\text{RTT}}$$

This is independent of bandwidth!

Example Analysis:

Key Insight: At 500 ms RTT (satellite), Stop-and-Wait on a 1 Gbps link achieves only 24 Kbps—slower than a 56K modem!

The RTT Sensitivity Problem:

Small changes in RTT cause proportional changes in throughput:

$$\frac{\Delta \text{Throughput}}{\text{Throughput}} = -\frac{\Delta \text{RTT}}{\text{RTT}}$$

Example:

• Base RTT: 50 ms, Throughput: 240 Kbps
• RTT increases 20% to 60 ms
• Throughput drops to 240 × (50/60) = 200 Kbps (17% drop)

This sensitivity explains why Stop-and-Wait performance varies significantly with network conditions.

Comparison with Sliding Window:

Sliding window protocols decouple throughput from RTT by allowing multiple frames in flight:

Window size needed for full utilization:

$$W = \frac{\text{RTT} \times B}{L} = \frac{0.05 \times 10^9}{12,000} \approx 4,167 \text{ frames}$$

This page provided comprehensive coverage of Round-Trip Time—the complete cycle time that determines how fast Stop-and-Wait can operate.