References: Peterson and Davie, the RFC1323 and the RFC2001 are used here. The experiment is from Shenker. L. Brakmo PhD Thesis can be another useful reference.
This demonstration uses the agent TCP/FullTcp.
In Applet 6.2 we saw that the Fast-Retransmit algorithm mimimizes those intervals where the pipe is emptied after a packet drop. However, it does not make them dissapear.
The problem is that the Slow-Start algorithm is invoked each time a a packet drop is detected, either by means of a timeout or by means of duplicated ACKs. But why to take a so severe recover algorithm (Slow-Start) and empty out the pipe which we know that it still contains packets? (packets are still arriving to the other side and we are getting duplicated ACKs). Jacobson realized that throughput could be improved if Slow-Start is performed only on timeouts.
The Fast-Recovery algorithm is implemented together with the Fast-Retransmit algorithm in the so-called Fast-Retransmit/Fast-Recovery algorithm
The Fast-Retransmit/Fast-Recovery algorithm was introduced in 4.3BSD Reno release and is described in the RFC 2001 as follows:
After receiving three duplicated ACKs in a row:
As it was previously said, receiving repeated acknowledgements for sequence number X provides more information than a timeout expiration. It means that a segment has not arrived at the other side, but further segments which the receiver cannot acknowledge are still arriving and being buffered. Therefore, there is still flow on the pipe that we can try to preserve.
First and second actions are performed by Fast-Retransmit. Third one sets the congestion window to the value to be set after a Fast-Retransmit (ssthresh) plus the number of segments we know that have left the pipe after the drop (the three ones that generated the duplicated acknowledgements). Fourth allows to send an extra segment to replace the one that has arrived and left the network (generating a duplicated acnowledgement), that is, this allows not to have to stop the transmission while waiting for the retransmitted packet's acknowledgement. Fifth, in the case of a single packet drop, the first non-duplicated ACK will open the window completely; there is no need to continue with the previous, artificially blown, cwnd and we set it to ssthresh and continue performing Congestion-Avoidance to find out the capacity of the line.
Applet 7.1 repeats the experiment in Applet 6.1, this time implementing the Fast-Retransmit/Fast-Recovery algorithm on the TCP source. Throughput is improved again.
Applet 7.1 |
|
|---|---|
|
|
This animation file: gzipped. The script used: fastrec.tcl Parameters for this animation: ns fastrec.tcl true Description:Link 0-1 is 1 Mb/s bandwidth, 10ms delay. Link 1-2 is 60Kb/s bandwidth, 10ms delay. The source implements the Reno TCP flavor. We will focus on what happens after t=5.0. The transient from t=0 to t=5.0 will be the starting point for a next section discussing Reno's limitations. Around t=11.6 we receive the third acknowledgment after a packet drop around t=11. We retransmit the lost packet. Around t=11.7 another duplicated acknowledgement arrives, cwnd is increases and this makes room for the retransmission of a new packet, asround t=11.8 another etc. During that time, the queue at (1) has not became empty and (2) has seen a maintained flow all the time. Plots of the transmission window, queue at the router and sequence numbers: 
|