The Slow-Start Algorithm

References: Jacobson's SIGCOMM'88 paper, section 1; Peterson and Davie; RFC 2001

Motivation

TCP, as seen until the moment, sends a full window of information at the begining of the transmissions. In the same way, when a packet is dropped, the destination cannot acknowledge further segments until the lost packet arrives; therefore the source will probably run out of window and will have to wait until a timeout halves the send window and forces a retransmission; after that, a cumulative acknowledgement will be received which will free space on the send window (probably opening it completely), so that we will transmit a full window together, as in the first case.

The previously described behavior is dangerous: we do not know the state of the network, which maybe cannot absorb an entire window (or even half a window), and we risk to lose most of the window.

Applet 5.1
	This animation file: gzipped. The script used: slowstart_motivation.tcl Parameters for this animation: `ns slowstart_motivation.tcl 10 ca 2` Description: Links n0-n1 and n4-n5 are 10Mbit/s, 2ms. Links n1-n2 and n3-n4 are 256Kbit/s, 10ms. Link n2-n3 is 1Mbit/s, 5ms. Queue in n1 has been limited to 10 packets. The TCP used in n0 implements the plain congestion avoidance algorithm and has a maximum send window of 40 packets. n0 has a window large enough to face the pipe; the problem is that n1 cannot buffer an initial 40-packet burst, so we lose most of the window when we start transmitting at t=0.1s. Around t=0.57s we begin receiving duplicated ACKs (you will notice that they do not trigger the transmission of a new packet), and finally around t=0.71 a timeout expires and we retransmit the lost packet; when its acknowledgement arrives around t=0.88, we set the congestion window to half the previous send window and continue the transmission, sending a 20-packet burst, which is again too much for n1. Take a look to a plot of the transmitted sequence number vs. time. Red dots are transmitted packets. Green ones are drops.

Applet 5.1

This animation file: gzipped.

The script used: slowstart_motivation.tcl

Parameters for this animation: ns slowstart_motivation.tcl 10 ca 2

Description:

Links n0-n1 and n4-n5 are 10Mbit/s, 2ms. Links n1-n2 and n3-n4 are 256Kbit/s, 10ms. Link n2-n3 is 1Mbit/s, 5ms. Queue in n1 has been limited to 10 packets. The TCP used in n0 implements the plain congestion avoidance algorithm and has a maximum send window of 40 packets. n0 has a window large enough to face the pipe; the problem is that n1 cannot buffer an initial 40-packet burst, so we lose most of the window when we start transmitting at t=0.1s. Around t=0.57s we begin receiving duplicated ACKs (you will notice that they do not trigger the transmission of a new packet), and finally around t=0.71 a timeout expires and we retransmit the lost packet; when its acknowledgement arrives around t=0.88, we set the congestion window to half the previous send window and continue the transmission, sending a 20-packet burst, which is again too much for n1.

Take a look to a plot of the transmitted sequence number vs. time. Red dots are transmitted packets. Green ones are drops.

It would be desired to implement an slower, less aggressive start; first we could think in performing the linear increase of Congestion-Avoidance at the beginning and after timeouts, but it results in a too slow start. Applet 5.2 shows it.

During the discussion of the Congestion-Avoidance algorithm we discarded using a multiplicative increase the congestion window after a drop because it was too fast for that purpose; maybe we can use it here.

Algorithm Description

[At the beginning of the transmission or after a timeout]:

Start sending one packet
For each ACK we receive, send two packets

Justification

If the network can transmit fast, slow-start does actually not slow-down the start considerably: it takes RTT * log2(MaxWin) to reach the maximum window size (MaxWin

If the network is congested, then ACKs will take long to arrive back to the source, and slow-start will be actually slow

Implementation

Slow-Start uses to be implemented together with Congestion-Avoidance in the so-called Slow-Start with Congestion-Avoidance algorithm, which is implemented as follows:

We define a new varianle called ssthresh, the Slow-Start threshold, which is initialized to the maximum window size.

Each time we receive a new ACK,

               if (cwnd < ssthresh) cwnd += 1;  /* Multiplicative Increase */

               else cwnd += 1/cwnd;             /* Linear Increase */

If a timeout occurs,

               ssthresh=swnd/2; cwnd=1

Each new acknowledgement frees space for a segment in the window, so a new packet can be sent to substitute the one which has left the network. Additionally, cwnd grows, allowing to send a segment more. That is, we are allowed to send two segments for each received acknowledgement. This can be illustrated with a graph:

To illustrate that increasing cwnd one segment each time a new ack is received yields to an exponential growth of the window, the following graph is proposed:

             |                            ... [1] 
           {1|2|3|4|5|6|7}8|9         --------------------> 
             |           ^  
         cwnd=1      maxwnd=7
                
                 |                             AK2 ...
            1{2|3|4|5|6|7|8}9         <------------------- | cwnd=cwnd + 1; transmit more; | ... [3][2] 1{2|3|4|5|6|7|8}9 --------------------><-------------------
                 |         ^  
               cwnd     maxwnd

               (TO BE DRAWN WITH CARE)

Applets 5.3-5.5 introduce a resume of the three alternatives seen.

Improvements obtained

Applet 5.6 reproduces the experiment shown in applet Applet 5.1, this time implementing the Slow-Start with Congestion-Avoidance algorithm.

Applet 5.6
	This animation file: gzipped. The script used: slowstart_motivation.tcl Parameters for this animation: `ns slowstart_motivation.tcl 10 ss/ca 8` Description: The scenario is the same shown in Applet 5.1: Links n0-n1 and n4-n5 are 10Mbit/s, 2ms; links n1-n2 and n3-n4 are 256Kbit/s, 10ms; link n2-n3 is 1Mbit/s, 5ms; queue in n1 has been limited to 10 packets. This time the TCP used by n0 implements Slow-Start with Congestion Avoidance. First, we notice that now we have half of the drops at the beginning of the connection of Applet 5.1; second, we eliminate the second round of packet drops after noticing the drop. Transmitted sequence number vs. time (red dots are transmitted packets, green ones are drops):

Applet 5.6

This animation file: gzipped.

The script used: slowstart_motivation.tcl

Parameters for this animation: ns slowstart_motivation.tcl 10 ss/ca 8

Description:

The scenario is the same shown in Applet 5.1: Links n0-n1 and n4-n5 are 10Mbit/s, 2ms; links n1-n2 and n3-n4 are 256Kbit/s, 10ms; link n2-n3 is 1Mbit/s, 5ms; queue in n1 has been limited to 10 packets. This time the TCP used by n0 implements Slow-Start with Congestion Avoidance.

First, we notice that now we have half of the drops at the beginning of the connection of Applet 5.1; second, we eliminate the second round of packet drops after noticing the drop.

Transmitted sequence number vs. time (red dots are transmitted packets, green ones are drops):

On the other hand, if the line is fast so that the acknowledgements arrive quickly, Slow-Start is not that slow, as shown in *). When cwnd >= ssthresh, then we stop increasing cwnd 1 unit each time we receive an ACK and we begin increasing it 1/cwnd instead. Thus, to make the window grow 1 unit, we have to receive cwnd ACKs: we are increasing cwnd one unit each time we correctly sent an entire window of packets.