TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms
obsoleted by
- rfc-2581 — TCP Congestion Control
Extracted elements (20)
Fast recovery avoids slow start after fast retransmit because duplicate ACKs indicate that data is still flowing and segments are buffered at the receiver. Invoking slow start would abruptly reduce throughput unnecessarily; congestion avoidance at half the previous rate is sufficient.
Slow start is named counterintuitively: it starts with cwnd=1 but grows exponentially. The name reflects that it is slower than the original TCP behavior of immediately injecting a full window of segments, which could overwhelm intermediate routers with limited queue space.
TCP waits for three (not one or two) duplicate ACKs before triggering fast retransmit because one or two duplicates can result from simple segment reordering rather than loss. Three consecutive duplicates are a strong indicator that a segment has been lost.
The assumption underlying congestion avoidance is that packet loss caused by damage is very small (much less than 1%), so packet loss is treated as a signal of congestion in the network rather than a transmission error.
Early TCP implementations only performed slow start when the destination was on a different network. Current implementations always perform slow start, regardless of whether the other host is on the same LAN.
Fast retransmit first appeared in the 4.3BSD Tahoe release (followed by slow start), while fast recovery was introduced in the 4.3BSD Reno release. Implementations without fast recovery will fall back to slow start after a fast retransmit.
Many implementations incorrectly add a small fraction of the segment size (typically segsize/8) to cwnd during congestion avoidance. This is wrong and should not be emulated in future releases.
A duplicate ACK generated upon receipt of an out-of-order segment SHOULD NOT be delayed; it must be sent immediately to inform the sender of the missing sequence number.
RFC 1122 requires that a TCP MUST implement slow start and congestion avoidance (Section 4.2.2.15 of RFC 1122).
The TCP output routine MUST never send more than the minimum of cwnd and the receiver's advertised window.
When congestion occurs (indicated by timeout or duplicate ACKs), one-half of the current window size (min of cwnd and advertised window, but at least two segments) MUST be saved in ssthresh. If congestion is indicated by a timeout, cwnd is additionally set to one segment.
During fast recovery, each additional duplicate ACK increments cwnd by one segment size (reflecting another segment that has left the network), potentially allowing new data to be transmitted if cwnd permits.
Fast recovery algorithm: on the third duplicate ACK, set ssthresh to max(cwnd/2, 2*segsize), retransmit the missing segment, and set cwnd to ssthresh + 3*segsize to account for segments that have left the network and are buffered at the receiver.
Fast recovery exits when the next ACK acknowledging new data arrives; cwnd is then set to ssthresh (the halved value from step 1), transitioning directly into congestion avoidance rather than slow start.
Fast retransmit: when three or more duplicate ACKs are received in a row, TCP retransmits the apparently missing segment immediately without waiting for a retransmission timer to expire.
Slow start adds a congestion window (cwnd) to the sender's TCP. The cwnd is initialized to one segment when a new connection is established with a host on another network. The sender transmits up to the minimum of cwnd and the receiver's advertised window.
Slow start increments cwnd by one segment for every ACK received, producing exponential growth. Congestion avoidance increments cwnd by segsize*segsize/cwnd per ACK received, yielding at most one segment of growth per round-trip time (linear growth).
Two per-connection variables are required: congestion window (cwnd) and slow start threshold (ssthresh). Initialization sets cwnd to one segment and ssthresh to 65535 bytes.
Security considerations are explicitly not discussed in this memo. Implementers should refer to other sources for TCP security considerations.
TCP alternates between slow start and congestion avoidance based on cwnd vs ssthresh: if cwnd <= ssthresh, TCP is in slow start (exponential growth); otherwise it is in congestion avoidance (linear growth). Congestion events reset cwnd and halve ssthresh.