Jacobson's Algorithm: Variance-Based Timeout Calculation

In October 1986, the Internet experienced its first congestion collapse. Networks that should have been operating at megabit speeds slowed to a crawl—throughput dropped by factors of 100 or more. The cause? TCP's inability to adapt to network conditions. Among the critical weaknesses exposed was the primitive timeout calculation that caused massive spurious retransmissions, further amplifying congestion.

Van Jacobson, a researcher at Lawrence Berkeley Laboratory, responded with a series of algorithmic improvements that literally saved the early Internet. Chief among these was his variance-based timeout algorithm, published in his seminal 1988 paper "Congestion Avoidance and Control." This algorithm fundamentally changed how TCP calculates retransmission timeouts—and remains the foundation of timeout calculation in modern TCP implementations over 35 years later.

The original TCP specification (RFC 793) used a simple approach to timeout calculation:

RTO = β × SRTT

Where SRTT was a simple moving average of RTT samples and β was typically 2. This approach had three critical problems:

Problem 1: No Variance Tracking

As we explored in Page 1, networks with the same average RTT can have vastly different RTT variance. A network with mean RTT of 100ms but variance causing occasional 300ms samples needs a much higher timeout than a stable network with the same mean. The simple β multiplier couldn't distinguish these cases.

Problem 2: Slow Adaptation

When network conditions changed, the SRTT adapted slowly because it was a heavily smoothed average (typically α = 0.875, meaning new samples only contributed 12.5% weight). If RTT suddenly doubled due to congestion, it took many samples for SRTT to catch up.

Problem 3: No Lower Bound on β

Using β = 2 worked reasonably for many networks, but failed spectacularly for high-variance networks. Yet there was no principled way to determine what β should be—it was a magic number chosen by intuition.

The 1986 congestion collapse demonstrated that this positive feedback loop wasn't theoretical—it was a practical disaster waiting to happen whenever networks approached capacity. Jacobson's insight was that the solution wasn't a better fixed multiplier, but a dynamic one based on observed variance.

Jacobson's fundamental insight was elegant: if we track how much RTT varies, we can set the timeout just high enough to accommodate normal variation while still detecting actual losses promptly.

The Statistical Foundation

Consider RTT as a random variable with some distribution. If we assume (approximately) that RTT follows a normal distribution with mean μ and standard deviation σ:

• 68% of samples fall within μ ± 1σ
• 95% of samples fall within μ ± 2σ
• 99.7% of samples fall within μ ± 3σ
• 99.99% of samples fall within μ ± 4σ

If we set RTO = μ + 4σ, we expect only about 0.01% of legitimate ACKs to arrive after the timeout. This makes spurious retransmissions extremely rare while maintaining responsiveness.

Why Not Use Standard Deviation Directly?

Calculating true standard deviation requires:

σ = √(Σ(xᵢ - μ)² / n)

This involves:

• Squaring (computationally expensive, especially in 1980s embedded systems)
• Accumulating squares (overflow risk with large values)
• Square root (very expensive to compute)

Jacobson needed something that behaves like standard deviation but is much cheaper to compute. His solution: mean deviation.

The Trade-off

Mean deviation isn't a perfect substitute for standard deviation:

Jacobson compensated for the relationship by using a multiplier. If we want RTO ≈ μ + 4σ and we have MD ≈ 0.8σ, then:

RTO ≈ μ + 4σ ≈ μ + 4 × (MD/0.8) ≈ μ + 5 × MD

In practice, Jacobson used a multiplier of 4 for the deviation term, providing a robust safety margin.

Jacobson's algorithm tracks two quantities using exponentially weighted moving averages (EWMA):

1. SRTT (Smoothed RTT): The estimated mean RTT
2. RTTVAR (RTT Variance): Actually the smoothed mean deviation, despite the name

The Update Equations

When a new RTT sample (R) is measured:

Step 1: Calculate the error

Err = R - SRTT

This is the difference between the new sample and our current estimate.

Step 2: Update the smoothed RTT

SRTT = SRTT + (1/8) × Err = SRTT + (Err >> 3)

This adds 1/8 of the error to the current estimate.

Step 3: Update the variance estimate

RTTVAR = RTTVAR + (1/4) × (|Err| - RTTVAR) = RTTVAR + ((|Err| - RTTVAR) >> 2)

This moves the variance estimate toward the absolute error.

Step 4: Calculate RTO

RTO = SRTT + 4 × RTTVAR = SRTT + (RTTVAR << 2)

The specific values in Jacobson's algorithm weren't arbitrary—they were carefully chosen for both mathematical properties and practical implementation.

The Smoothing Factor α = 1/8 for SRTT

Mathematical rationale: An EWMA with α = 1/8 gives a "time constant" of approximately 8 samples. After 8 samples, the contribution of the oldest sample has decayed to about 1/e ≈ 37% of its original weight. This provides stability while still adapting to trends.

Practical rationale: 1/8 = 2⁻³. This means the multiplication can be implemented as a right bit-shift by 3 positions:

SRTT + Err/8 = SRTT + (Err >> 3)

In 1988, this was a significant optimization. Bit shifts were single-cycle operations; division was expensive.

The Smoothing Factor β = 1/4 for RTTVAR

Mathematical rationale: The variance estimate uses a larger weight (1/4 vs 1/8) for new samples. This makes it more responsive to changes in network variability. If the network suddenly becomes more unpredictable, RTTVAR adapts faster than SRTT.

Practical rationale: 1/4 = 2⁻². Right bit-shift by 2 positions:

RTTVAR + ((|Err| - RTTVAR)) >> 2)

The Multiplier K = 4 for RTTVAR

Mathematical rationale: This multiplier determines how many "units" of variance we add to the mean to get the timeout. With K = 4 and RTTVAR ≈ 0.8σ:

RTO ≈ SRTT + 4 × 0.8σ ≈ SRTT + 3.2σ

For a normal distribution, this means about 99.9% of samples should fall below the RTO. The extra margin accounts for:

• Non-normality in RTT distributions (typically right-skewed)
• Clock granularity effects
• Safety margin for loss detection

Practical rationale: 4 = 2². Left bit-shift by 2 positions:

SRTT + 4 × RTTVAR = SRTT + (RTTVAR << 2)

Complete Implementation with Bit Operations

Putting it all together, the entire algorithm can be implemented using only additions, subtractions, and bit shifts:

To truly understand Jacobson's algorithm, we need to see how it behaves in different scenarios. Let's trace through several examples:

Scenario 1: Stable Network

Consider a network with consistent RTT around 100ms:

Key observation: In a stable network, RTTVAR shrinks over time, and RTO converges toward SRTT plus a small safety margin. This allows tight loss detection.

Scenario 2: Sudden RTT Increase

Now consider what happens when RTT suddenly jumps (e.g., route change or congestion):

Key observation: When RTT jumps, both SRTT and RTTVAR increase. RTTVAR increases faster (larger α), immediately expanding RTO to prevent spurious timeouts during the transition. After the network stabilizes at the new level, RTTVAR shrinks again.

Scenario 3: High Variance Network

Consider a network with highly variable RTT (e.g., mobile or satellite):

To appreciate Jacobson's contribution, let's compare the performance of the original simple averaging approach versus the variance-based approach:

Quantitative Impact

Studies following the 1988 publication showed dramatic improvements:

These weren't incremental improvements—they were order-of-magnitude changes that made TCP viable as an Internet protocol.

Real-world implementations of Jacobson's algorithm must handle several edge cases and practical considerations:

Initial Measurement

Before any RTT samples are collected, the algorithm has no data to work with. RFC 6298 specifies:

Before first measurement:

• RTO = 1 second (initial, conservative default)

After first measurement R:

• SRTT = R
• RTTVAR = R/2
• RTO = SRTT + 4 × RTTVAR = 3R

The initial RTTVAR = R/2 is a heuristic: assume variance is proportional to the mean until we have more data. This gives a conservative initial RTO of 3× the first measurement.

Minimum RTO Bound

RFC 6298 specifies a minimum RTO (typically 1 second) to prevent pathologically small timeouts:

Clock Granularity

The algorithm's accuracy depends on the granularity of the system clock. RFC 6298 recommends:

RTO ≥ G (clock granularity)

With modern systems providing microsecond or better timing, this is rarely a concern. However, older systems with 500ms granularity required special handling.

Maximum RTO Bound

While not specified in RFC 6298, implementations typically enforce a maximum RTO (often 60-120 seconds) to ensure connections eventually attempt recovery even in pathological conditions.

Interaction with Karn's Algorithm

Jacobson's algorithm only tells us how to update estimates given an RTT sample. It doesn't tell us which samples to use. That's where Karn's algorithm (covered in the next page) comes in—specifying that retransmitted segments should not generate RTT samples due to the ambiguity problem.