Slow Start: Exponential Probing and the Initial Window Problem

A connection that has just completed its handshake knows three things: the peer’s address, the peer’s advertised receive window, and the maximum segment size. It knows nothing about the path. It does not know how many bytes per second the bottleneck can forward, how deep the bottleneck’s queue is, or how many other flows share it. Every estimate it will use later has to be constructed from the acknowledgements it has not yet received.

The problem is that the first window is also a guess, and the guess is a commitment. Whatever the sender puts on the wire before any feedback arrives will be delivered into a path whose capacity is unknown, and if the guess is too large the excess is dropped. Slow start is the procedure for starting from a deliberately small guess and expanding it geometrically until the path pushes back.

Why doubling, and why it is called slow

Start with a window of one segment. Send it, wait a round trip, receive one acknowledgement, and increase the window by one segment. Now two segments may be sent. They generate two acknowledgements, so the window grows by two, then four, then eight. The window doubles once per round trip, and the number of segments sent after k round trips is 2^k - 1.

The growth is exponential in round trips and therefore linear in time on a log scale. To find a window of 1024 segments takes ten round trips: 1, 2, 4, 8, …, 1024. To find a window of one million segments takes twenty. That is the entire justification for the shape of the curve. The sender has no idea whether the right window is ten segments or ten thousand, so it spends the first few round trips resolving the order of magnitude, and exponential search does that in log₂ probes. A linear search from one segment would take a thousand round trips to reach a window of a thousand.

The name is a historical artifact. Jacobson’s 1988 paper introduced the algorithm as the counterpart to congestion avoidance, and “slow” refers to the contrast with the previous behaviour, which was to send the receiver’s entire advertised window immediately. Relative to that, doubling from one segment is slow. Relative to additive increase it is fast, and the naming has confused readers ever since.

The doubling is implemented by increasing the window by one segment per acknowledgement, not by one segment per round trip. In this phase the two are equivalent in effect because the number of acknowledgements per round trip equals the window, and the sum of those increments over a round trip is the window itself. This equivalence is exactly what stops holding once acknowledgements are delayed or compressed, which is why implementations credit bytes rather than packets.

The threshold and the exit condition

Slow start does not run until loss. It runs until the window reaches a remembered value, ssthresh, which stands for slow start threshold. On exit the sender switches to congestion avoidance and its growth changes from doubling to roughly one segment per round trip.

ssthresh starts unset, effectively infinite, so the first slow start is bounded only by loss or by the receive window. After a loss, ssthresh is set to half the window at the time of loss, so the next slow start stops at approximately the window that the path was last known to sustain. That is the memory in the algorithm: the path’s capacity estimate survives the connection’s loss events as a single number.

The transition is a comparison, not a state flag that persists independently:

/* Per-ACK window update, with the slow-start threshold as the boundary. */
if (cwnd < ssthresh) {
    /* Slow start: credit at most two segments per ACK (RFC 3465, L = 2). */
    cwnd += acked < 2 * smss ? acked : 2 * smss;
} else {
    /* Congestion avoidance: about one SMSS per RTT. */
    cwnd += (smss * smss) / cwnd;
}

Two details are worth noting. The cap of two segments per acknowledgement bounds how much a receiver can inflate the growth by acknowledging one segment several times; RFC 5681 itself recommends a cap of one segment per ACK, and the two-segment variant comes from the experimental appropriate byte counting of RFC 3465, which trades a small amount of that protection for faster growth under delayed ACKs. And the comparison is < rather than <=, so a window exactly equal to the threshold is treated as congestion avoidance; RFC 5681 permits either reading at equality, and implementations differ.

Initializing ssthresh to infinity is correct for a fresh connection but interacts badly with persistent connections that have been idle. A sender that has sent nothing for several round trips has no evidence that the path is still as it was, and the window it remembers may be far too large for a path that has since become congested. RFC 5681 addresses this by requiring that after an idle period exceeding a retransmission timeout, the congestion window be reduced to the restart window, which is min(IW, cwnd). The connection then re-probes rather than resuming at a stale rate.

What the first window should be

The initial window is the one number in the algorithm that has been revised by standards track documents more than once, and the revisions track changes in the web’s traffic mix.

The original specification allowed one segment. That is safe for the network and disastrous for short transfers: a connection that sends one segment, waits a round trip, sends two, waits, sends four, needs three round trips before it has sent seven segments. For a transfer small enough to fit in a handful of segments, those round trips are the entire cost. The latency cost of the small initial window is paid on every connection, and it is paid in round trips, which is the currency that matters.

RFC 3390 raised the initial window to min(4*SMSS, max(2*SMSS, 4380 bytes)). The 4380 figure is three segments of 1460 bytes, a common Ethernet MSS, so the rule grants four segments when the MSS is small and roughly three when it is large. The asymmetry exists because the risk of a large initial burst is proportional to the burst’s byte count, not its segment count.

RFC 6928 raised it again, to min(10*SMSS, max(2*SMSS, 14600 bytes)). Ten segments of 1460 bytes is 14600 bytes, so for common Ethernet the rule is exactly ten segments. The document’s argument rests on summaries of large-scale experiments showing lower latency for web traffic at the larger window, and on the observation that a ten-segment burst is likely to fit in the queue space available at a broadband access link. Both claims are about a traffic mix and a deployment rather than about the protocol, which is why the value is a recommendation with an explicit scope rather than a constant.

The trade is straightforward and worth stating in the direction it runs. A larger initial window reduces the number of round trips needed to deliver a small object, which improves latency for short flows. It also increases the size of the first burst, which increases the probability that the burst overflows a shallow buffer and loses a segment, and a loss in the first window is expensive because the sender has no ssthresh estimate and must fall back to a timeout. The optimum depends on the distribution of object sizes and on the depth of the bottleneck queue, both of which are properties of the deployment rather than of TCP.

The burst problem

Slow start’s exponential growth is also a burst generator, and the burst is the mechanism’s real cost. At the moment the window doubles from W to 2W, the sender has W acknowledgements arriving and responds to each by sending new data. If the acknowledgements arrive compressed — which happens whenever the bottleneck has been draining a queue — the sender emits 2W segments in a compressed interval rather than spread over a round trip. The instantaneous rate at that moment can be many times the average rate, and the excess lands in the bottleneck’s queue at once.

Two mechanisms exist to bound this. Pacing spreads the window’s transmissions over the round trip instead of emitting them on ACK arrival, which removes the burst without changing the average rate; that is the subject of model-based control and pacing. Limited slow start, from RFC 3742, caps the growth rate for very large windows: once the window exceeds a threshold, the increase per round trip is limited to a fixed number of segments rather than being proportional to the window. The cap matters only on paths where the window is large enough that doubling represents a megabyte-scale burst, which in practice means high-bandwidth long-delay paths.

There is a subtler issue with the exponential phase that no cap fixes. The sender discovers capacity only after exceeding it, so the window at the moment of the first loss is necessarily larger than the sustainable window, and the amount by which it overshoots is proportional to the window itself. On a path with a 100 ms round trip and a 1 Gbit/s bottleneck, the bandwidth-delay product is 12.5 MB, and a slow start that reaches it will have overshot by up to the same amount. The queue must absorb that overshoot or the loss rate during startup is severe. This is the reason the buffer-sizing rule of thumb is stated in terms of the bandwidth-delay product rather than in packets, and the reason starting after a loss is expensive even when the loss itself was cheap.

Measuring the exit instead of waiting for loss

Waiting for a loss to end slow start means the first loss is unavoidable. A sender that could detect the onset of queueing before the queue overflows would exit slow start at the right window and avoid the loss entirely. That is the motivation for delay-based exit heuristics, which compare the current round-trip time against the minimum observed and leave slow start when the difference exceeds a threshold.

The difficulty is that the minimum RTT is itself an estimate that improves over time. A connection whose first measurements happened to be taken while a queue was already present will have an inflated minimum and will therefore tolerate more queueing than intended. The heuristic also cannot distinguish a growing queue from a path change that legitimately increased the propagation delay, such as a route change to a longer path. Both failure modes produce the same symptom: slow start continues past the correct window and the sender learns the truth from a loss, which is what the heuristic was meant to avoid.

The state machine in one place

Putting the pieces together, a sender’s window behaviour is a three-state cycle. In slow start the window doubles per round trip until it reaches ssthresh or a loss occurs. In congestion avoidance it grows by about one segment per round trip. On a loss indication it halves, sets ssthresh to the halved value, and either stays in congestion avoidance (for a duplicate-ACK loss) or collapses to one segment and re-enters slow start (for a timeout).

The transition that costs the most is the timeout, because it discards the capacity estimate entirely rather than halving it, and the re-entry is a full exponential probe from one segment. On a path with a large bandwidth-delay product, that probe takes many round trips, and the connection spends most of its recovery time re-learning something it already knew. This asymmetry, between the cheap halving and the expensive collapse, is what selective acknowledgement and the recovery algorithms of the next stage were designed to avoid.