RFC 2001 (rfc2001) - Page 3 of 6

TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms

RFC 2001                          TCP                       January 1997


   Congestion avoidance and slow start are independent algorithms with
   different objectives.  But when congestion occurs TCP must slow down
   its transmission rate of packets into the network, and then invoke
   slow start to get things going again.  In practice they are
   implemented together.

   Congestion avoidance and slow start require that two variables be
   maintained for each connection: a congestion window, cwnd, and a slow
   start threshold size, ssthresh.  The combined algorithm operates as
   follows:

   1.  Initialization for a given connection sets cwnd to one segment
       and ssthresh to 65535 bytes.

   2.  The TCP output routine never sends more than the minimum of cwnd
       and the receiver's advertised window.

   3.  When congestion occurs (indicated by a timeout or the reception
       of duplicate ACKs), one-half of the current window size (the
       minimum of cwnd and the receiver's advertised window, but at
       least two segments) is saved in ssthresh.  Additionally, if the
       congestion is indicated by a timeout, cwnd is set to one segment
       (i.e., slow start).

   4.  When new data is acknowledged by the other end, increase cwnd,
       but the way it increases depends on whether TCP is performing
       slow start or congestion avoidance.

      If cwnd is less than or equal to ssthresh, TCP is in slow start;
      otherwise TCP is performing congestion avoidance.  Slow start
      continues until TCP is halfway to where it was when congestion
      occurred (since it recorded half of the window size that caused
      the problem in step 2), and then congestion avoidance takes over.

      Slow start has cwnd begin at one segment, and be incremented by
      one segment every time an ACK is received.  As mentioned earlier,
      this opens the window exponentially:  send one segment, then two,
      then four, and so on.  Congestion avoidance dictates that cwnd be
      incremented by segsize*segsize/cwnd each time an ACK is received,
      where segsize is the segment size and cwnd is maintained in bytes.
      This is a linear growth of cwnd, compared to slow start's
      exponential growth.  The increase in cwnd should be at most one
      segment each round-trip time (regardless how many ACKs are
      received in that RTT), whereas slow start increments cwnd by the
      number of ACKs received in a round-trip time.






Stevens                     Standards Track