This section introduces the last of the algorithms that led to the Tahoe release of TCP, the Fast-Retransmit algorithm. It was implemented, as the Slow-Start/Congestion-Avoidance and the RTT Variance Estimation, by Van Jacobson.
Peterson and Davie and the RFC1323 are used here. The experiment is from Shenker. Brakmo, subsection 3.4.2.
In previous sections we have seen that if a packet is dropped, then the destination TCP cannot acknowledge further ones; therefore, the source runs out of window, stops and has to wait for a timeout to occur; then the lost packet is retransmitted and when its acknowledgement arrives, probably acknowledging all the previous window, then the transmission continues.
Applet 6.1 |
|
|---|---|
|
|
This animation file: gzipped. The script used: fastrtx.tcl Parameters for this animation: ns fastrtx.tcl false Description:Link 0->1 is 1Mbit/s, 10ms delay; Link 1->2 is 50Kbit/s, 10ms delay. We have several drops around t=1.6; around t=3.3 we send the last packet allowed by the window and we have to wait for a timeout to occur around t=5.3s, retransmit the lost packets and wait for their acknowledgements to open the window again. This fact can be seen in the send-window plot as a flat region in the graph; its ultimate effect is that the pipe is emptied, as shown in the plots below. Plots of the transmission window, queue at the router and sequence numbers:   
|
We can appreciate that the effect of this packet loss makes the throughput decrease noticeably. In the animation we can see as well that we are receiving duplicated acknowledgements in the interval of time where the destination cannot acknowledge further packets; Jacobson realiced that this could be interpreted as an implicit Negative-ACK, and implemented it in the so-called Fast-Retransmit algorithm.
If three repeated acknowledgements for sequence number X are received, do not wait for a timeout and retransmit sequence number X immediately.
The reason for using duplicated acks as NACK signal was partially explained before. Choosing exactly three duplicated ACKs as NACK signal is a heuristic rule.
Applet 6.2 repeats the experiment in Applet 6.1, this time with a source which implements the Fast Retransmit Algorithm. It shows that the source implementing the algorithm achieves a faster response to packet losses which yields to a improved throughput.
Applet 6.2 |
|
|---|---|
|
|
This animation file: gzipped. The script used: fastrtx.tcl Parameters for this animation: ns fastrtx.tcl true Description:We have again several drops around t=1.6; around t=3.3 we send the last packet allowed by the window but this time we are not waiting for any timeout to occur; around t=3.72s we receive the third duplicated ACK for sequence number 20 and we retransmit it immediately. The problem is that the Fast-Retransmit algorithm does not work with multiple packet drops, and that is what we have this first time. More specifically, we lose packet 20, 22, 24.. we received three duplicated ACKs asking for packet 20 and we have retransmitted it at t=3.88s; it is put as the last packet on the queue, it is delivered, and another duplicated ACK, asking this time for packet 22 is issued. It is received at t=5.16. The problem is that there are no more packets on the pipe to trigger more duplicated ACKs, so Fast-Retransmit will not work; we have to wait for a timeout to expire. Despite this first inconvenience, Fast-Retransmit performs very well during the rest of the transmission; we have reduced the waiting time after drops and so the time the pipe gets completely empty; this can be seen comparing the plots of the queue size evolution. The effect is a noticeable increase in the throughput: at the end of the experiment, the source implementing the Fast Retransmit algorithm has transmitted succesfully about 20 segments more than the one not implementing it, about a 13 per cent improvement. Plots of the transmission window, queue at the router and sequence numbers:  
|