TCP Variants

In October 1986, the Internet experienced a series of congestion collapses that brought network throughput down by a factor of 1000—from an expected 32 Kbps to a mere 40 bps on some links. Traffic that should have flowed smoothly became stuck in congested routers, retransmissions piled upon retransmissions, and the nascent Internet ground nearly to a halt.

This crisis catalyzed one of the most important developments in networking history. Van Jacobson, working at the Lawrence Berkeley Laboratory, analyzed the problem and developed a series of algorithms that would fundamentally transform how TCP manages network congestion. The result, published in 1988 and implemented in BSD 4.3 Tahoe, became known as TCP Tahoe—the first TCP variant with sophisticated congestion control.

TCP Tahoe wasn't just a fix for a crisis; it established the philosophical foundation for all subsequent congestion control work. Its core insight—that end hosts should infer network congestion from packet loss and respond by reducing their sending rate—remains the dominant paradigm over three decades later.

To truly understand TCP Tahoe, we must first understand the problem it was designed to solve. Before Tahoe, TCP had no congestion control whatsoever. The protocol was designed under the assumption that networks had sufficient capacity and that packet loss was primarily due to transmission errors, not congestion.

The Original TCP Behavior:

In the pre-Tahoe era, TCP senders would transmit data as fast as the receiver's advertised window allowed. If packets were lost, TCP would dutifully retransmit them. But here's the critical flaw: if packets were lost due to router buffer overflow (congestion), sending more packets only made the problem worse.

Van Jacobson's Key Insights:

Jacobson observed that congestion collapse resulted from a fundamental mismatch between how TCP operated and how networks behaved. He identified three critical insights:

1. Conservation of Packets: A well-behaved network in equilibrium has a certain number of packets "in flight." New packets should only be injected when old packets leave (are acknowledged). If senders inject packets faster than the network can deliver them, queues build and collapse follows.

2. Packet Loss as a Signal: In most networks, packet loss indicates router buffer overflow—congestion. Rather than treating loss as random noise, TCP should interpret it as a signal to slow down.

3. Probing for Capacity: A sender cannot know in advance what rate the network can sustain. The only way to discover this is to probe by gradually increasing the sending rate until loss occurs, then backing off.

Before diving into Tahoe's algorithms, we must understand the fundamental state variables that govern TCP congestion control. These variables represent the sender's model of the network and determine how much data can be in flight at any moment.

The Congestion Window (cwnd):

The congestion window is the sender's estimate of how many bytes (or segments) the network can handle without becoming congested. Unlike the receiver's advertised window (rwnd), which reflects the receiver's buffer capacity, cwnd reflects the sender's perception of network capacity.

The effective window—the actual amount of data the sender can have outstanding—is:

Effective Window = min(cwnd, rwnd)

This means the sender is always constrained by whichever is smaller: the receiver's ability to accept data or the network's ability to carry it.

The Slow Start Threshold (ssthresh):

The slow start threshold marks the boundary between two operational phases: Slow Start and Congestion Avoidance. When cwnd is below ssthresh, the sender is in Slow Start mode (exponential growth). When cwnd reaches or exceeds ssthresh, the sender transitions to Congestion Avoidance (linear growth).

The ssthresh serves as the sender's memory of the last known safe capacity. When congestion is detected (packet loss), ssthresh is set to half the current cwnd, establishing a new safe upper bound.

Duplicate ACK Counter:

TCP uses duplicate ACKs as an early warning system for potential packet loss. When a receiver gets an out-of-order segment, it immediately sends a duplicate ACK for the last in-order segment it received. The sender tracks consecutive duplicate ACKs—three duplicates trigger Fast Retransmit.

Despite its name, Slow Start is actually an exponentially fast algorithm for ramping up transmission rate. The name derives from its contrast with the pre-Tahoe behavior of immediately transmitting at full receiver window speed. Slow Start is "slow" only in that it doesn't start at maximum rate.

The Core Mechanism:

Slow Start begins with cwnd set to 1 segment (Initial Window, or IW). For each ACK received that acknowledges new data, cwnd is increased by 1 segment. Because each segment generates an ACK (roughly), and each ACK increases cwnd by 1, the window doubles every round-trip time (RTT).

Mathematical Analysis:

Let's analyze Slow Start's growth rate precisely. If we start with cwnd = 1 segment:

• After RTT 0: cwnd = 1 (initial)
• After RTT 1: cwnd = 1 + 1 = 2
• After RTT 2: cwnd = 2 + 2 = 4
• After RTT n: cwnd = 2^n segments

To reach a window of W segments, we need approximately log₂(W) round-trip times. For a high-bandwidth network where the optimal window might be 1000 segments, we can reach that size in just 10 RTTs—a few hundred milliseconds on typical Internet paths.

Why Not Start Faster?

A natural question is: why not start with a larger initial window? The answer involves the unknown network state. When a connection begins, the sender has no information about the path's capacity. Starting too aggressively could immediately cause congestion on a bottleneck link.

Once cwnd reaches ssthresh, the sender transitions from Slow Start to Congestion Avoidance. While Slow Start aggressively probes for available capacity, Congestion Avoidance takes a more conservative approach—growing the window linearly rather than exponentially.

The rationale is straightforward: once we've reached the threshold (which approximates the point where congestion previously occurred), we're operating in a region where we're likely near the network's capacity. Aggressive growth would probably trigger congestion; cautious probing is wiser.

The Core Mechanism:

In Congestion Avoidance, cwnd increases by 1 segment for every full window of data acknowledged—not for every ACK. This results in approximately 1 segment increase per RTT, regardless of the current window size.

AIMD: Additive Increase, Multiplicative Decrease

Congestion Avoidance embodies the AIMD principle—a cornerstone of TCP congestion control:

• Additive Increase (AI): When no congestion is detected, increase cwnd by a small, constant amount per RTT (typically 1 segment). This gentle probing gradually discovers additional capacity.

• Multiplicative Decrease (MD): When congestion is detected (packet loss), reduce cwnd by a multiplicative factor (typically halving). This dramatic reduction quickly alleviates congestion.

The asymmetry is intentional. Additive increase means we approach the congestion point slowly, minimizing overshoot. Multiplicative decrease ensures we retreat rapidly when we've exceeded capacity, preventing prolonged congestion.

Prior to Tahoe, TCP relied entirely on retransmission timeouts (RTO) to detect packet loss. When a segment was lost, the sender would wait for the RTO timer to expire before retransmitting. The problem: RTO is typically set conservatively (often several RTTs) to avoid spurious retransmissions. Waiting for timeout introduces substantial delay.

Fast Retransmit provides a mechanism for detecting loss before the timer expires, using duplicate ACKs as an early warning.

How Duplicate ACKs Arise:

When a TCP receiver gets a segment with a higher-than-expected sequence number (indicating gaps in the stream), it cannot send a normal ACK for that data—it would violate TCP's cumulative ACK semantics. Instead, it immediately sends a duplicate ACK for the last contiguous byte it received.

Why Three Duplicate ACKs?

The choice of three duplicate ACKs (four identical ACKs total) balances two concerns:

1. Robustness to Reordering: Packets can arrive out of order, especially on multi-path networks. A single out-of-order packet generates one duplicate ACK. Two out-of-order packets generate two. Three consecutive duplicates are statistically unlikely from reordering alone.

2. Timely Detection: Waiting for more duplicates would increase detection latency. Three is enough to be confident about loss without excessive delay.

The Critical Difference from Timeout:

Fast Retransmit typically triggers within one RTT after loss (the time for three subsequent packets to generate duplicate ACKs), compared to RTO which might be several RTTs. This difference is enormous for throughput.

When TCP Tahoe detects packet loss (whether via triple duplicate ACK or timeout), it responds with a full reset to Slow Start. This aggressive response is Tahoe's defining characteristic—and also its primary limitation.

The Complete Response Sequence:

Why Reset to One?

Tahoe's aggressive response stems from its conservative philosophy: when in doubt, back off completely. The reasoning is:

1. A loss indicates the network is congested
2. We don't know how badly congested
3. The safest response is to reduce load dramatically
4. Slow Start will quickly recover if the network has capacity

This approach guarantees safety but sacrifices performance. After every loss event, no matter how minor, TCP Tahoe drops its sending rate to nearly zero and must rebuild.

The Recovery Timeline:

Consider a connection with cwnd = 32 segments when loss occurs:

1. Loss detected, ssthresh set to 16, cwnd reset to 1
2. RTT 1: cwnd = 2 (Slow Start)
3. RTT 2: cwnd = 4
4. RTT 3: cwnd = 8
5. RTT 4: cwnd = 16 (reaches ssthresh, switch to CA)
6. RTT 5: cwnd = 17
7. RTT 6: cwnd = 18
8. ...
9. RTT 20: cwnd ≈ 32 (back to pre-loss level)

It takes approximately 4 RTTs to reach ssthresh and another 16 RTTs to climb back to the original window—20 RTTs total for full recovery.

Let's consolidate TCP Tahoe's behavior into a complete state machine. This unified view shows how Slow Start, Congestion Avoidance, and Fast Retransmit interact to form a coherent congestion control strategy.

Key Observations:

1. Two-Phase Operation: Tahoe has only two steady-state phases (Slow Start and Congestion Avoidance). Loss triggers a reset, not a new phase.

2. Unified Loss Response: Whether loss is detected by timeout or triple duplicate ACK, the response is identical: halve ssthresh, reset cwnd to 1, re-enter Slow Start.

3. Memory in ssthresh: The ssthresh preserves information about the network's capacity. After loss, exponential growth continues only until reaching this remembered limit.

4. Perpetual Probing: Even in steady state, Congestion Avoidance continuously probes for additional capacity by incrementing cwnd. TCP never "settles"—it always seeks more bandwidth.

Despite being superseded by more advanced variants, TCP Tahoe introduced principles that remain foundational. Its strengths justify its historical importance and explain why its core ideas persist in every subsequent TCP variant.

TCP Tahoe's conservative design, while ensuring safety, introduces significant performance limitations. Understanding these limitations is essential both for appreciating subsequent variants and for recognizing where Tahoe might still be appropriate.

Quantifying the Performance Gap:

Consider a 100 Mbps link with 100ms RTT (Bandwidth-Delay Product = 1.25 MB, roughly 850 segments). Under Tahoe:

• Optimal steady-state: cwnd ≈ 850 segments
• After loss: cwnd drops to 1, ssthresh = 425
• Time to reach ssthresh: log₂(425) ≈ 9 RTTs = 0.9 seconds
• Time to reach 850: 425 additional RTTs ≈ 42 seconds

If losses occur periodically (say, every 1000 segments), Tahoe's effective utilization could be well under 50% of the link's capacity.

TCP Tahoe represents a watershed moment in networking history—the first systematic approach to congestion control that made the Internet viable at scale. Let's consolidate the essential concepts:

What's Next:

In the next page, we explore TCP Reno, which built upon Tahoe by introducing a critical enhancement: Fast Recovery. Instead of resetting to Slow Start on triple duplicate ACKs, Reno halves the window and continues in Congestion Avoidance mode—dramatically improving throughput in the face of single-packet losses.