About Fast-Retransmit Algorithm:
In the past, TCP detected the wrong things inside the network, such as packet loss, network congestion, etc, by using only the "timeout" mechanism. After sending a data packet, TCP sets up its own timer particularly for the sent packet. The timer is usually set to the retransmission timeout period (RTO) which is determined by some other algorithms. If TCP correctly receives an ACK corresponding to the data packet before the timer is expired, TCP assumes that everything inside the network is fine. TCP, then, automatically resets the timer of just received ACK packet and continuously waits for the other ACK packets. However, if TCP does not get the desired ACK within RTO period, this will trigger TCP to retransmit the packet whose timer is expired. In addition to retransmit the lost packet, TCP starts slow-start again by reset cwnd to 1 and set ssthresh to (old cwnd / 2) due to the congestion control algorithm.
It was soon discovered that using only the timeout mechanism led to long periods of time (RTO period) in order to react to the wrong things happened inside the network. Therefore, a new mechanism called "fast retransmit" was added to TCP. Fast retransmit is a heuristic that sometimes triggers the retransmission of a dropped packet before the RTO period is up. It is worth to make things clear that fast retransmit does not supplant timeout mechanism. The timeout mechanism actives normally for a small window size, where packets in transit are not enough to cause fast retransmit. TCP can employ fast retransmit only in a large window size to enhance its performance and link utilization.
The idea of fast retransmit is straightforward. It only adds a tiny thing to the normal operation of TCP. Every time a packet with sequence number x arrives correctly at the receiver; the receiver acknowledges the packet #x by sending an ACK packet (containing the sequence number of another packet which it is waiting for - this number may or may not be "x+1") back to the sender. Therefore, when a packet arrives out of order (for example, 1 2 3 ... 5 : "4" is missing), TCP at the receiving side resends the last ACK packet to portray the expected packet again. This causes a duplicate ACK at the sending side. ("duplicate ACK" means the second, third, fourth, ... transmission of the same acknowledgement.) Fast retransmit plays an important role here. After receiving some numbers of duplicate ACKs, TCP at the sending side retransmits the missing packet without waiting for the timer to be expired. Moreover, receiving some numbers of duplicate ACKs means that the network congestion has been occured. Thus, TCP at the sending side resets cwnd to 1 and sets ssthresh to (old cwnd / 2) due to the congestion control algorithm; then starts slow-start again. In the practical TCP, the third duplicate ACKs triggers fast retransmit.
Note ! The reason that the sending side has to wait until the third duplicate ACK is described in RFC2001 as follows:
" Since TCP does not know whether a duplicate ACK is caused by a lost segment or just a reordering of segments, it waits for a small number of duplicate ACKs to be received. It is assumed that if there is just a reordering of the segments, there will be only one or two duplicate ACKs before the reordered segment is processed, which will then generate a new ACK. If three or more duplicate ACKs are received in a row, it is a strong indication that a segment has been lost. "
The diagram below shows the situation that fast retransmit cannot occur in a small window size:
Assumptions:
1. Only one packet in a window is dropped. In this diagram, it is Pkt1.
2. TCP at the sending side implements fast retransmit algorithm.
3. The retransmitted packet is completely received at the receiver.
Description: All packets in transit are not enough to trigger fast retransmit. In the diagram, there is only 1 dup ACK caused by Pkt2.
The diagram below depicts how 3 duplicate ACKs lead to a fast retransmit:
Assumptions:
1. Only one packet in a window is dropped. In this diagram, it is Pkt5.
2. TCP at the sending side implements fast retransmit algorithm.
3. The retransmitted packet is completely received at the receiver.
Description: After detecting an out-of-order packet (Pkt6), the receiving side resends the last ACK packet which is ACK5. At this time, packets in transit are enough to trigger fast retransmit. Therefore, after receiving the third duplicate ACK5, TCP at the sending side retransmits Pkt5. Moreover, it resets cwnd to 1 and sets ssthresh to (old cwnd /2) = 6/2 = 3 due to the congestion control algorithm; then starts slow-start again.
Note! In case that there are more than one dropped packets in a window, things still go straightforward.
The diagram below portrays the situation where 2 packets in a window are dropped:
Assumptions:
1. Two packets in a window are dropped. In this diagram, they are Pkt7 and Pkt9.
2. TCP at the sending side implements fast retransmit algorithm.
3. The retransmitted packet is completely received at the receiver.
Description: For Pkt7, fast retransmit can be triggered since the sending side receives 3 dup ACK7. However, from the diagram, retransmission of Pkt9 happens because Pkt9's RTO is expired - not fast retransmit. Why? It is shown obviously in the diagram that there are no enough packets in transit for triggering the 2nd fast retransmit.
Note! In case that the retransmitted packet is dropped, things still go straightforward. Try to figure this out by drawing a diagram similar to those shown above.
The simulation showing Fast-Retransmit algorithm:
Tools:
1. Javis version 0.2 (Applet version)
2. ns version 2.1b6
Topology Desctiption: There are 4 nodes named "0","1","2" and "3" in the topology.
"0" is a sender.
"3" acts as a receiver.
"1" and "2" act as intermediate routers between the sender and receiver.
Link Description: There is three duplex-links connecting "0" & "1", "1" & "2" and "2" & "3" . The characterization of each link is:
"0" & "1" : 5Mb 20ms DropTail
"1" & "2" : 0.5Mb 100ms DropTail
"2" & "3" : 5Mb 20ms DropTail
Assumptions:
1. The initial cwnd_ is 1.
2. The maximum window size (advertised window in the real world) is 20.
3. Multiple dropped packets in a window.
File Name: fast-retransmit-out.nam.gz
Simulation Description:
- At time 0.1, the sender starts sending a packet to the receiver. The slow-start algorithm is playing a role here.
- At time 1.403, multiple packets in transit (#23 #25 #27 #29) are dropped because the queue at node "1" is full. However, the sender now does not realize that those packets are dropped in the network. The slow-start mechanism operates properly until time 1.658.
- At time 1.658, cwnd_ reaches the pre-defined maximum window size. Usually, the sender cannot send any window larger than this maximum window size.
- At time 1.697, pkt#39 gets dropped since the queue at node "1" is full.
- At time 1.768, the sending side detects the 3rd dup ACK caused by the first dropped packet (#23). This 3rd dup ACK triggers fast retransmit for pkt#23. Particularly, pkt#23 is retransmitted at that time (don't have to wait until time-out); cwnd_ is reset to 1 and ssthresh_ is set to (old cwnd_ / 2); then slow-start starts again.
- Thus, at time 2.081, cwnd_ increases from 1 to 2 because the sender receives only one normal ACK requesting for pkt#25. Therefore, the sender retransmits pkt#25 and #26.
- At time 2.382, cwnd_ at the sending side increases from 2 to 3 because the sender gets only 1 normal ACK requesting for pkt#27 and 1 dup ACK requesting for pkt#27. [ Recall, the cwnd_ is increased only when the sender receives the normal ACK, not the dup ACK. ]. Therefore, the sender retransmits pkt#27, #28 and #29.
- Again, at time 2.698, cwnd_ increases from 3 to 5 because the sending side receives 1 normal ACK requesting for pkt#29, 1 dup ACK requesting for pkt#29 and 1 normal ACK requesting for pkt#39. These 2 normal ACK and one dup ACKs cause the sending side to send pkt#29 #30 #31 #39 #40 #41 #42 #43 in the next window.
- Unfortunately, at time 2.750, pkt#43 gets dropped. There is no fast-retransmit for pkt#43. The sending side waits until time-out and starts slow-start again.