Stop-and-Wait ARQ Efficiency Analysis

In the previous page, we discovered that Stop-and-Wait utilization depends critically on the ratio of propagation delay to transmission time. Now we must understand propagation delay in depth—because it represents a fundamental physical constraint that no amount of engineering can overcome.

The speed of light in a vacuum is approximately 299,792,458 meters per second (~3 × 10⁸ m/s). This cosmic speed limit means that even with infinitely fast computers and infinitely wide bandwidth, information cannot travel faster than about 300,000 kilometers per second.

For a signal traveling from New York to London (approximately 5,500 km via undersea fiber), the minimum possible one-way delay is:

$$T_p^{\text{min}} = \frac{5,500,000 \text{ m}}{3 \times 10^8 \text{ m/s}} \approx 18.3 \text{ ms}$$

In practice, fiber optic cables achieve about 2/3 of light speed, giving:

$$T_p^{\text{actual}} \approx \frac{5,500,000}{2 \times 10^8} \approx 27.5 \text{ ms}$$

This delay is irreducible. It exists regardless of how fast our processors are, how wide our bandwidth is, or how advanced our protocols become. Understanding propagation delay is understanding a fundamental limit of the physical universe.

What is Propagation?

Propagation is the process by which a signal (electromagnetic wave, light pulse, or electrical voltage change) travels through a transmission medium. When we transmit a bit, we're creating a change in some physical property—voltage on a wire, light intensity in fiber, or electromagnetic field strength in wireless.

This change propagates outward from the source at a velocity determined by the medium's physical properties.

The Propagation Velocity Formula:

In a vacuum, electromagnetic waves travel at the speed of light:

$$c = 3 \times 10^8 \text{ m/s}$$

In other media, the velocity is reduced by the refractive index (n):

$$v = \frac{c}{n}$$

Where:

• c = speed of light in vacuum
• n = refractive index of the medium (always ≥ 1)
• v = actual propagation velocity in the medium

Why Different Media Have Different Velocities:

Fiber Optic Cable: Light travels through glass, which has a refractive index of approximately 1.5. The light undergoes total internal reflection, bouncing along the fiber core. Each reflection adds minuscule delays, and the glass itself slows propagation compared to vacuum.

Copper Cable: Electrical signals in copper propagate as electromagnetic waves guided by the conductor. The velocity depends on the cable's capacitance and inductance per unit length. Insulation material and cable geometry affect these properties.

Wireless/Satellite: In free space (atmosphere or vacuum), electromagnetic waves travel at essentially the speed of light. However, satellite links have enormous distances—geostationary satellites orbit at 35,786 km altitude, creating one-way delays of approximately 120 ms even at light speed.

The Fundamental Formula:

Propagation delay is simply distance divided by velocity:

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

Where:

• Tp = Propagation delay (seconds)
• d = Distance between sender and receiver (meters)
• v = Propagation velocity of the medium (meters/second)

Example 1: Local Area Network

A sender and receiver are 200 meters apart in an office building, connected by Cat6 Ethernet (v ≈ 2 × 10⁸ m/s).

$$T_p = \frac{200}{2 \times 10^8} = 1 \times 10^{-6} \text{ s} = 1 \text{ μs}$$

This is negligible—fully acceptable for Stop-and-Wait.

Example 2: Metropolitan Area Network

Two data centers 50 km apart connected by fiber optic:

$$T_p = \frac{50,000}{2 \times 10^8} = 2.5 \times 10^{-4} \text{ s} = 250 \text{ μs} = 0.25 \text{ ms}$$

Still relatively small, but becoming significant for high-bandwidth links.

Example 3: Transcontinental Link

New York to Los Angeles fiber connection (~4,000 km):

$$T_p = \frac{4,000,000}{2 \times 10^8} = 0.02 \text{ s} = 20 \text{ ms}$$

Round-trip delay: 40 ms. At 10 Gbps with 1500-byte frames:

• Transmission time: 1.2 μs
• a = 20 ms / 1.2 μs = 16,667
• Utilization: U = 1/(1 + 33,334) = 0.003%

Example 4: Transatlantic Link

New York to London undersea fiber (~6,000 km cable route):

$$T_p = \frac{6,000,000}{2 \times 10^8} = 0.03 \text{ s} = 30 \text{ ms}$$

Example 5: Geostationary Satellite

Earth to GEO satellite (35,786 km altitude). Signal travels up and back down:

$$\text{Total distance} = 2 \times 35,786 \text{ km} = 71,572 \text{ km}$$ $$T_p = \frac{71,572,000}{3 \times 10^8} \approx 239 \text{ ms}$$

For a complete request-response, the round-trip is approximately 478 ms—making Stop-and-Wait utterly impractical.

Why Round-Trip Matters for Protocols:

In Stop-and-Wait ARQ, the sender must wait for the acknowledgment before transmitting the next frame. This means the total waiting time includes:

1. Time for the data frame to propagate to the receiver (Tp)
2. Time for the receiver to process and send ACK (often negligible)
3. Time for the ACK to propagate back to the sender (Tp)

Round-Trip Time (RTT):

$$\text{RTT} = 2 \times T_p \quad \text{(symmetric links)}$$

This is why our utilization formula includes 2Tp, not just Tp:

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

Asymmetric Links:

In reality, forward and reverse paths may have different propagation delays:

$$\text{RTT} = T_p^{\text{forward}} + T_p^{\text{return}}$$

This occurs when:

• Routes are different in each direction (common in the Internet)
• Different media are used (e.g., satellite downlink, terrestrial uplink)
• Network congestion affects one direction more than the other

Components of Measured RTT:

When measuring RTT in real networks, the observed value includes several components:

$$\text{RTT}{\text{measured}} = 2T_p + T{\text{queue}} + T_{\text{process}} + T_{\text{transmit}}$$

Where:

• 2Tp = Pure propagation delay (outbound + return)
• T_queue = Time waiting in router queues
• T_process = Processing time at intermediate devices and destination
• T_transmit = Transmission times at each hop

For protocol efficiency analysis, we often isolate propagation delay because:

• It represents the irreducible physical minimum
• Other delays can potentially be optimized
• It allows fair comparison across different network conditions

The Speed-of-Light RTT:

The theoretical minimum RTT is determined purely by distance:

$$\text{RTT}_{\text{min}} = \frac{2d}{v} = \frac{2d}{2 \times 10^8} = \frac{d}{10^8}$$

Any measured RTT higher than this represents additional network overhead.

Propagation delay calculations become more complex in multi-hop networks. Understanding how topology affects delay is essential for accurate analysis.

Point-to-Point Links:

The simplest case—direct connection between sender and receiver:

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

Multi-Hop Networks:

When packets traverse multiple links through routers/switches:

$$T_p^{\text{total}} = \sum_{i=1}^{n} T_p^{(i)} = \sum_{i=1}^{n} \frac{d_i}{v_i}$$

Where n is the number of hops and each hop may have different distance and velocity.

Example: Three-Hop Path

Hop 1: 100 km fiber (v = 2×10⁸ m/s) → Tp = 0.5 ms Hop 2: 500 km fiber (v = 2×10⁸ m/s) → Tp = 2.5 ms Hop 3: 50 km copper (v = 2×10⁸ m/s) → Tp = 0.25 ms

Total: Tp = 0.5 + 2.5 + 0.25 = 3.25 ms

Satellite Link Configurations:

Geostationary Earth Orbit (GEO):

• Altitude: 35,786 km
• One-way delay: ~120 ms (to satellite) + ~120 ms (to ground) = ~240 ms
• RTT: ~480 ms
• Characteristic: Fixed position relative to Earth, large coverage area

Medium Earth Orbit (MEO):

• Altitude: 2,000 - 35,786 km (typically ~20,000 km for GPS)
• One-way delay: 67-120 ms
• Used by: GPS satellites, O3b constellation

Low Earth Orbit (LEO):

• Altitude: 160 - 2,000 km (Starlink: ~550 km)
• One-way delay: 1-13 ms to satellite
• Total RTT (user→satellite→ground station→server→back): 20-40 ms typical
• Tradeoff: Lower delay, but satellites move rapidly, requiring handoffs

Comparison for Stop-and-Wait:

Submarine Cable Routes:

Transcontinental communication relies on undersea fiber optic cables. The actual cable length is typically longer than the great-circle distance due to:

1. Avoiding deep ocean trenches (maintenance difficulty)
2. Landing at coastal population centers (not shortest path)
3. Political routing (avoiding certain territories)
4. Redundancy requirements (multiple diverse paths)

Example: Transatlantic Routes

The direct great-circle distance (NYC to London: ~5,500 km) suggests 27 ms, but actual cable routing adds 20-50% more delay.

Definition:

The bandwidth-delay product (BDP) represents the maximum amount of data that can be "in flight" on a network link at any given time—the capacity of the "pipe":

$$\text{BDP} = \text{Bandwidth} \times \text{Delay} = B \times T_p$$

Alternatively, for round-trip considerations:

$$\text{BDP}_{\text{RTT}} = B \times \text{RTT} = B \times 2T_p$$

Physical Interpretation:

Imagine the network link as a pipe. The bandwidth determines how much data flows in per second. The propagation delay determines how long the pipe is (in time). The product tells us how much data can be inside the pipe simultaneously.

Example Calculations:

1. Office LAN:

• B = 1 Gbps = 10⁹ bps
• Tp = 1 μs = 10⁻⁶ s
• BDP = 10⁹ × 10⁻⁶ = 1,000 bits = 125 bytes

2. Cross-Country Link:

• B = 10 Gbps = 10¹⁰ bps
• Tp = 20 ms = 0.02 s
• BDP = 10¹⁰ × 0.02 = 2 × 10⁸ bits = 25 Megabytes

3. GEO Satellite:

• B = 100 Mbps = 10⁸ bps
• Tp = 240 ms = 0.24 s
• BDP = 10⁸ × 0.24 = 24 × 10⁶ bits = 3 Megabytes

Why BDP Determines Protocol Requirements:

The bandwidth-delay product directly relates to our parameter 'a':

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

Therefore:

$$a = \frac{\text{Bandwidth-Delay Product}}{\text{Frame Size}}$$

This reveals the fundamental relationship:

• When BDP > L (BDP exceeds frame size), we have a > 1 and poor efficiency
• When BDP < L (BDP smaller than frame size), we have a < 1 and acceptable efficiency

The BDP tells us how many frames "fit in the pipe":

$$\text{Frames in flight} = \frac{\text{BDP}}{L} = a$$

For efficient transmission, we want at least as many frames in flight as 'a' suggests—but Stop-and-Wait only allows one frame at a time, regardless of how many could fit.

*Frames needed = BDP / 12,000 bits (assuming 1500-byte frames). This column shows how many frames could theoretically be "in the pipe" simultaneously.

The LFN Problem:

Networks with large bandwidth-delay products are affectionately called "Long Fat Networks" (LFNs, pronounced "elephants"). These networks pose unique challenges for reliable data transfer protocols.

RFC 1323 Definition:

A "long" network has a large RTT (high propagation delay). A "fat" network has high bandwidth. When both are present, the BDP becomes enormous.

Characteristics of LFNs:

• BDP exceeds typical window sizes (65,535 bytes for original TCP)
• Traditional Stop-and-Wait becomes extremely inefficient
• Even sliding window protocols struggle with fixed window sizes
• Sequence number space can be exhausted

Example LFN Scenarios:

These BDP values far exceed original TCP's 64 KB window, necessitating extensions like window scaling (RFC 1323).

LFN Protocol Solutions:

Networks with large BDPs require protocols that can:

1. Keep the pipe full — Multiple frames in flight simultaneously
2. Handle large sequence spaces — Prevent wrap-around during RTT
3. Scale buffer sizes — Accommodate BDP worth of data
4. Manage congestion intelligently — Large BDP means large standing queues

Stop-and-Wait on LFNs:

For a 100 Gbps × 50 ms LFN (BDP = 625 MB):

• Frame size: 1,500 bytes = 12,000 bits
• Transmission time: 12,000 / 10¹¹ = 0.12 μs
• a = 50 ms / 0.12 μs = 416,667
• U = 1 / (1 + 833,334) = 0.00012%

Stop-and-Wait would use 0.00012% of a 100 Gbps link—effectively reducing it to 120 Kbps. This is why sliding window protocols are essential for LFNs.

Network delay consists of multiple components. Understanding how propagation delay relates to other delays is essential for complete network analysis.

The Four Types of Network Delay:

1. Propagation Delay (Tp)

• What: Time for signal to travel through medium
• Formula: d / v
• Controllable? NO — determined by physics and geography
• Typical magnitude: Microseconds (LAN) to hundreds of milliseconds (satellite)

2. Transmission Delay (Tt)

• What: Time to push bits onto the link
• Formula: L / B
• Controllable? YES — increase bandwidth or decrease frame size
• Typical magnitude: Microseconds for high-speed links

3. Processing Delay (Tproc)

• What: Time for devices to process packets (routing decisions, checksums, etc.)
• Formula: Hardware/software dependent
• Controllable? YES — better hardware, optimized software
• Typical magnitude: Microseconds to milliseconds

4. Queuing Delay (Tqueue)

• What: Time spent waiting in router buffers
• Formula: Depends on traffic load; highly variable
• Controllable? PARTIALLY — traffic engineering, QoS
• Typical magnitude: Negligible to hundreds of milliseconds under congestion

Total End-to-End Delay:

$$T_{\text{total}} = T_t + T_p + T_{\text{proc}} + T_{\text{queue}}$$

For multi-hop paths with n links and n-1 routers:

$$T_{\text{total}} = \sum_{i=1}^{n}(T_t^{(i)} + T_p^{(i)}) + \sum_{j=1}^{n-1}(T_{\text{proc}}^{(j)} + T_{\text{queue}}^{(j)})$$

Relative Importance Across Network Types:

This page provided an in-depth exploration of propagation delay—the physics-constrained component of network latency that fundamentally limits Stop-and-Wait efficiency.