As per Relevance of the word congestion, we have this rfc below:
Network Working Group W.
Request for Comments: 2001
Category: Standards Track January 1997
TCP Slow Start, Congestion Avoidance
Fast Retransmit, and Fast Recovery
Status of this
This document specifies an Internet standards track protocol for
Internet community, and requests discussion and suggestions
improvements. Please refer to the current edition of the "
Official Protocol Standards" (STD 1) for the standardization
and status of this protocol. Distribution of this memo is unlimited
Modern implementations of TCP contain four intertwined
that have never been fully documented as Internet standards:
start, congestion avoidance, fast retransmit, and fast recovery. [2]
and [3] provide some details on these algorithms, [4]
examples of the algorithms in action, and [5] provides the
code for the 4.4BSD implementation. RFC 1122 requires that a
must implement slow start and congestion avoidance (Section 4.2.2.15
of [1]), citing [2] as the reference, but fast retransmit and
recovery were implemented after RFC 1122. The purpose of
document is to document these four algorithms for the Internet
Much of this memo is taken from "TCP/IP Illustrated, Volume 1:
Protocols" by W. Richard Stevens (Addison-Wesley, 1994) and "TCP/
Illustrated, Volume 2: The Implementation" by Gary R. Wright and W
Richard Stevens (Addison-Wesley, 1995). This material is used
the permission of Addison-Wesley. The four algorithms that
described were developed by Van Jacobson
1. Slow
Old TCPs would start a connection with the sender injecting
segments into the network, up to the window size advertised by
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
receiver, problems can arise. Some intermediate router must
the packets, and it's possible for that router to run out of space
[2] shows how this naive approach can reduce the throughput of a
connection drastically
Stevens Standards Track [Page 1]
RFC 2001 TCP January 1997
The algorithm to avoid this is called slow start. It operates
observing that the rate at which new packets should be injected
the network is the rate at which the acknowledgments are returned
the other end
Slow start adds another window to the sender's TCP: the
window, called "cwnd". When a new connection is established with
host on another network, the congestion window is initialized to
segment (i.e., the segment size announced by the other end, or
default, typically 536 or 512). Each time an ACK is received,
congestion window is increased by one segment. The sender
transmit up to the minimum of the congestion window and
advertised window. The congestion window is flow control imposed
the sender, while the advertised window is flow control imposed
the receiver. The former is based on the sender's assessment
perceived network congestion; the latter is related to the amount
available buffer space at the receiver for this connection
The sender starts by transmitting one segment and waiting for
ACK. When that ACK is received, the congestion window is
from one to two, and two segments can be sent. When each of
two segments is acknowledged, the congestion window is increased
four. This provides an exponential growth, although it is
exactly exponential because the receiver may delay its ACKs
typically sending one ACK for every two segments that it receives
At some point the capacity of the internet can be reached, and
intermediate router will start discarding packets. This tells
sender that its congestion window has gotten too large
Early implementations performed slow start only if the other end
on a different network. Current implementations always perform
start
2. Congestion
Congestion can occur when data arrives on a big pipe (a fast LAN)
gets sent out a smaller pipe (a slower WAN). Congestion can
occur when multiple input streams arrive at a router whose
capacity is less than the sum of the inputs. Congestion avoidance
a way to deal with lost packets. It is described in [2].
The assumption of the algorithm is that packet loss caused by
is very small (much less than 1%), therefore the loss of a
signals congestion somewhere in the network between the source
destination. There are two indications of packet loss: a
occurring and the receipt of duplicate ACKs
Stevens Standards Track [Page 2]
RFC 2001 TCP January 1997
Congestion avoidance and slow start are independent algorithms
different objectives. But when congestion occurs TCP must slow
its transmission rate of packets into the network, and then
slow start to get things going again. In practice they
implemented together
Congestion avoidance and slow start require that two variables
maintained for each connection: a congestion window, cwnd, and a
start threshold size, ssthresh. The combined algorithm operates
follows
1. Initialization for a given connection sets cwnd to one
and ssthresh to 65535 bytes
2. The TCP output routine never sends more than the minimum of
and the receiver's advertised window
3. When congestion occurs (indicated by a timeout or the
of duplicate ACKs), one-half of the current window size (
minimum of cwnd and the receiver's advertised window, but
least two segments) is saved in ssthresh. Additionally, if
congestion is indicated by a timeout, cwnd is set to one
(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
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
continues until TCP is halfway to where it was when
occurred (since it recorded half of the window size that
the problem in step 2), and then congestion avoidance takes over
Slow start has cwnd begin at one segment, and be incremented
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
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'
exponential growth. The increase in cwnd should be at most
segment each round-trip time (regardless how many ACKs
received in that RTT), whereas slow start increments cwnd by
number of ACKs received in a round-trip time
Stevens Standards Track [Page 3]
RFC 2001 TCP January 1997
Many implementations incorrectly add a small fraction of the
size (typically the segment size divided by 8) during
avoidance. This is wrong and should not be emulated in
releases
3. Fast
Modifications to the congestion avoidance algorithm were proposed
1990 [3]. Before describing the change, realize that TCP
generate an immediate acknowledgment (a duplicate ACK) when an out
of-order segment is received (Section 4.2.2.21 of [1], with a
that one reason for doing so was for the experimental fast
retransmit algorithm). This duplicate ACK should not be delayed
The purpose of this duplicate ACK is to let the other end know that
segment was received out of order, and to tell it what
number is expected
Since TCP does not know whether a duplicate ACK is caused by a
segment or just a reordering of segments, it waits for a small
of duplicate ACKs to be received. It is assumed that if there
just a reordering of the segments, there will be only one or
duplicate ACKs before the reordered segment is processed, which
then generate a new ACK. If three or more duplicate ACKs
received in a row, it is a strong indication that a segment has
lost. TCP then performs a retransmission of what appears to be
missing segment, without waiting for a retransmission timer
expire
4. Fast
After fast retransmit sends what appears to be the missing segment
congestion avoidance, but not slow start is performed. This is
fast recovery algorithm. It is an improvement that allows
throughput under moderate congestion, especially for large windows
The reason for not performing slow start in this case is that
receipt of the duplicate ACKs tells TCP more than just a packet
been lost. Since the receiver can only generate the duplicate
when another segment is received, that segment has left the
and is in the receiver's buffer. That is, there is still
flowing between the two ends, and TCP does not want to reduce
flow abruptly by going into slow start
The fast retransmit and fast recovery algorithms are
implemented together as follows
Stevens Standards Track [Page 4]
RFC 2001 TCP January 1997
1. When the third duplicate ACK in a row is received, set
to one-half the current congestion window, cwnd, but no
than two segments. Retransmit the missing segment. Set cwnd
ssthresh plus 3 times the segment size. This inflates
congestion window by the number of segments that have left
network and which the other end has cached (3).
2. Each time another duplicate ACK arrives, increment cwnd by
segment size. This inflates the congestion window for
additional segment that has left the network. Transmit
packet, if allowed by the new value of cwnd
3. When the next ACK arrives that acknowledges new data, set
to ssthresh (the value set in step 1). This ACK should be
acknowledgment of the retransmission from step 1, one round-
time after the retransmission. Additionally, this ACK
acknowledge all the intermediate segments sent between the
packet and the receipt of the first duplicate ACK. This step
congestion avoidance, since TCP is down to one-half the rate
was at when the packet was lost
The fast retransmit algorithm first appeared in the 4.3BSD
release, and it was followed by slow start. The fast
algorithm appeared in the 4.3BSD Reno release
5. Security
Security considerations are not discussed in this memo
6.
[1] B. Braden, ed., "Requirements for Internet Hosts --
Communication Layers," RFC 1122, Oct. 1989.
[2] V. Jacobson, "Congestion Avoidance and Control,"
Communication Review, vol. 18, no. 4, pp. 314-329, Aug. 1988.
ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z
[3] V. Jacobson, "Modified TCP Congestion Avoidance Algorithm,"
end2end-interest mailing list, April 30, 1990.
ftp://ftp.isi.edu/end2end/end2end-interest-1990.mail
[4] W. R. Stevens, "TCP/IP Illustrated, Volume 1: The Protocols",
Addison-Wesley, 1994.
[5] G. R. Wright, W. R. Stevens, "TCP/IP Illustrated, Volume 2:
The Implementation", Addison-Wesley, 1995.
Stevens Standards Track [Page 5]
RFC 2001 TCP January 1997
Author's Address
W. Richard
1202 E. Paseo del
Tucson, AZ 85718
Phone: 520-297-9416
EMail: rstevens@noao.
Home Page: http://www.noao.edu/~
Stevens Standards Track [Page 6]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
