References: Jacobson's SIGCOMM'88 paper, section 3 and appendix D; Brakmo96, subsection 3.4.1; Peterson and Davie. The idea of introducing Congestion-Avoidance before the Slow-start Algorithm was taken from Peterson and Davie.
The Sliding Window Flow Control assures we are not going to overload the other peer, but does not take care of network congestion. That is, the bottleneck can be (and will probably be) the network, not the receiver.
The network can absorb short traffic bursts over its capacity by buffering them on the nodes. If equilibrium is reached, then self-clocking works and solves the problem. The following applet shows it:
Applet 4.1 |
|
|---|---|
|
|
This animation file: gzipped. The script used: congavd_motivation.tcl Parameters for this animation: ns congavd_motivation.tcl 100 DropTail false false 2 Description:All the links are 10Mbit/s, 10ms delay. All the hosts implement a plain RFC 793 TCP. n0 begins transmitting to n4 at t=0.1s. At t=0.5s n3 begins transmitting to n4; now link n2-n4, which is 1Mbit/s is shared by two 1Mbit/s flows, so that the queue at the node n2 begins to grow; it has a very big capacity (100 packets), and no packet is dropped. ACKs arrive now at n0 with twice the initial temporal spacing of the beginning, so that at t=0.71s n0 finishes running out of window and has to wait for new ACKs to strobe the sending of new packets; in this moment, our transmission is clocked and the queue at n2 stops growing fast. At t=1.5s n3 stops sending and a few time later ACKs begin to arrive at n0 at the original rate. |
However, if we persistenly try to deliver to the network more packets than it can absorb, we will fall on network congestion:
Resuming:
too much traffic --> net congestion --> timeouts --> have to retransmit
^ |
| V
+------------------------------------------ more traffic
If we call the total network load L and we sample it on time, so that L[i] is the i-th sample, we can express L[i] as the sum of two terms:
That is, L[i] = N + r * L[i-1]
On NO Congestion, r will be approximately 0. On Congestion, r will be big, so that L[i] will be approximately r^i * L[i-1], so that queues in the network will grow exponentially until they begin dropping packets. Applet 4.2 shows this effect..
Applet 4.2 |
|
|---|---|
|
|
This animation file: gzipped. The script used: congavd_highcong.tcl Parameters for this animation: ns congavd_highcong.tcl 100 SFQ false false 2 Description:The scenario is the same as of Applet 4.1, this time with three additional sources. Note that this time queue n2-n4 implements as SFQ Packet Scheduling discipline to avoid ugly phase effects; re-run the experiment with ns congavd_highcong.tcl 100 DropTail false false 2 to see them. Packet Scheduling Disciplines will be discussed in other document |
Let W[i] be the TCP send window sampled at the i-th instant. The Congestion-Avoidance Algorithm is as follows:
We can choose an explicit congestion signaling, where the routers send messages to the sources (e.g. ECN). However, if we think that packet losses are almost always due to network congestion, then we have an implicit congestion signal: if a packet drop is detected, then assume the network is congested and slow down the transmission.
"If the connection is in steady-state running and a packet is dropped, it's probably because a new connection started up and took some of your bandwidth. We usually run our nets with rho < 0.5 so it's probable that there are now exactly two conversations sharing the bandwidth, halving your window is conservative --- and being conservative at high traffic intensities is probably wise" <= 0.5 so it's probable that there are now exactly two conversations sharing the bandwidth, halving your window is conservative --- and being conservative at high traffic intensities is probably wise"
We define a new window that we call Congestion Window (cwnd).
swnd = min {maxwin, cwnd}
[timeout] => cwnd = swnd / 2
[new ack] => cwnd += 1/cwnd (so cwnd increases at most one pkt each RTT)
With Congestion-Avoidance, TCP adapts to different network loads and stabilizes the queues that were growing too fast. Compare Applet 4.3, where all the senders do not implement Congestion-Avoidance, with Applet 4.4 where they do. In consequence, TCP implementing Congestion-Avoidance achieves higher throughput.
Applet 4.3 |
|
|---|---|
|
|
This animation file: gzipped. The script used: congavd_motivation.tcl Parameters for this animation: ns congavd_motivation.tcl 10 SFQ false false 3 Description:The same as applet 4.1, this time implementing a SFQ discipline un the queue n2-n4 and limiting its size to 10 packets. Take a look to a plot of the transmitted sequence number vs. time. Red dots are transmitted packets. Green ones are drops.
|
Applet 4.4 |
|
|---|---|
|
|
This animation file: gzipped. The script used: congavd_motivation.tcl Parameters for this animation: ns congavd_motivation.tcl 10 SFQ true false 3 Description:The same as Applet 4.3, this time implementing the Congestion-Avoidance mechanism in all the sources. Transmitted sequence number vs. time: 
Send Window evolution: (note the instant where the timeout expires: the congestion window is set to one segment, send is allowed so that the packet is retransmitted and then the congestion window is set equal to ssthresh) 
|
