Chalmers -    
Computer Engineering

The Congestion-Avoidance Algorithm


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.

Motivation

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:

  1. It is possible that packets take so long to arrive at the other side that our timeouts will expire and we will retransmit packets unnecessarily, wasting bandwidth and increasing the congestion even more.
  2. The nodes can reach their memory limit and begin dropping packets, which we will have to retransmit (wasting bandwidth and adding extra traffic to the network that becomes even more congested). Drops are worse than they seem: when we drop a packet, the receiver cannot acknowledge further ones until the lost one arrives; therefore, we run out of send window and we have to wait for a timeout to occur, retransmit the lost packet, and wait for the cumulative acknowledgement of all the packets to continue the transmission.

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:

  1. The new traffic N offered to the network on the i-th sample .
  2. A fraction of the traffic L[i-1] from the previous sample time that has to be retransmitted.

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

Algorithm Description

Let W[i] be the TCP send window sampled at the i-th instant. The Congestion-Avoidance Algorithm is as follows:

  1. On Congestion: W[i] = d * W[i-1] with d < 1 (Multiplicative Decrease)
  2. On NO Congestion: W[i] = W[i-1] + a (Additive Increase)

Justification

Implementation

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)
       

Improvements Obtained

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)

Related Issues