TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms (RFC2001)
Original Publication Date: 1997-Jan-01
Included in the Prior Art Database: 2019-Feb-15
Internet Society Requests For Comment (RFCs)
Modern implementations of TCP contain four intertwined algorithms that have never been fully documented as Internet standards: slow start, congestion avoidance, fast retransmit, and fast recovery. [STANDARDS-TRACK]
Network Working Group W. Stevens Request for Comments: 2001 NOAO Category: Standards Track January 1997
TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms
Status of this Memo
This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.
Modern implementations of TCP contain four intertwined algorithms that have never been fully documented as Internet standards: slow start, congestion avoidance, fast retransmit, and fast recovery.  and  provide some details on these algorithms,  provides examples of the algorithms in action, and  provides the source code for the 4.4BSD implementation. RFC 1122 requires that a TCP must implement slow start and congestion avoidance (Section 18.104.22.168 of ), citing  as the reference, but fast retransmit and fast recovery were implemented after RFC 1122. The purpose of this document is to document these four algorithms for the Internet.
Much of this memo is taken from "TCP/IP Illustrated, Volume 1: The Protocols" by W. Richard Stevens (Addison-Wesley, 1994) and "TCP/IP Illustrated, Volume 2: The Implementation" by Gary R. Wright and W. Richard Stevens (Addison-Wesley, 1995). This material is used with the permission of Addison-Wesley. The four algorithms that are described were developed by Van Jacobson.
1. Slow Start
Old TCPs would start a connection with the sender injecting multiple segments into the network, up to the window size advertised by the receiver. While this is OK when the two hosts are on the same LAN, if there are routers and slower links between the sender and the receiver, problems can arise. Some intermediate router must queue the packets, and it’s possible for that router to run out of space.  shows how this naive approach can reduce the throughput of a TCP connection drastically.
Stevens Standards Track [Page 1]
RFC 2001 TCP January 1997
The algorithm to avoid this is called slow start. It operates by observing that the rate at which new packets should be injected into the network is the rate at which the acknowledgments are returned by the other end.
Slow start adds another window to the sender’s TCP: the congestion window, called "cwnd". When a new connection is established with a host on another network, the congestion window is initialized to one segment (i.e., the segment size announced by the other end, or the default, typically 536 or 512). Each time an ACK is received, the congestion window is increased by one segment. The sender can transmit up to the minimum of the congestion window and the advertised window. The congestion window is flow control imposed by the sender, while the advertised window is flow control imposed by the receiver. Th...