|
|
|
About Fast-Recovery Algorithm:
Fast Recovery is now the last improvement of TCP. With using only Fast Retransmit, the congestion window is dropped down to 1 each time network congestion is detected. Thus, it takes an amount of time to reach high link utilization as before. Fast Recovery, however, alleviates this problem by removing the slow-start phase. Particulary, slow-start will be used only at the beginning of a connection and whenever an RTO period is expired.
The reason for not performing slow-start after receiving 3 dup ACKs is that duplicate ACKs tell the sending side more than a packet has been lost. Since the receiving side can create a duplicate ACK only in the case that it receives an out-of-order packet, the dup ACK shows the sending side that one packet has been left out the network. Thus, the sending side does not need to drastically decrease cwnd down to 1 and restart slow-start. Moreover, the sender can only decrease cwnd to one-half of the current cwnd and increase cwnd by 1 each time it receives a duplicate ACK.
Fast Recovery algorithm has been implemented in TCP since Reno release. It collaborates with Fast Retransmit algorithm in an algorithm called "Fast Retransmit/Fast Recovery Algorithm". This algorithm is described in RFC2001 as follows:
After receiving 3 duplicate ACKs in a row:
1. set ssthresh to one-half of the current congestion window.
2. retransmit the missing segment.
3. set cwnd = ssthresh + 3.
4. Each time another duplicate ACK arrives, set cwnd = cwnd + 1. Then, send a new data segment if allowed by the value of cwnd.
5. Once receive a new ACK (an ACK which acknowledges all intermediate segments sent between the lost
packet and the receipt of the first duplicate ACK), exit fast recovery. This causes setting cwnd to ssthresh (the ssthresh in step 1). Then, continue with linear increasing due to congestion avoidance algorithm.
The diagram below portrays how 3 duplicate ACKs lead to a fast recovery:
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/fast recovery algorithm.
3. The retransmitted packet is completely received at the receiver.
Description: After receiving the 3rd dup ACK5, the sender sets its ssthresh to one-half of the current cwnd ( 6/2 = 3 ). Moreover, it sets cwnd down to ssthresh + 3 which is 3+3 = 6. The window size 6 includes from pkt5 to pkt10. Then, it retransmits pkt5 to the receiver. Due to fast recovery algorithm, cwnd increases from 6 to 7 and 8 after the sender receives the 4th and 5th dup ACK5 respectively. This makes the sender can send 2 more packets which is pkt11 and pkt12. When the sender receives new ACK which acknowledges all packets up to pkt10, the sender exits fast recovery, resets cwnd to ssthresh and follow the congestion avoidance algorithm.
The Simulation showing fast-recovery 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-recovery-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 both fast retransmit for pkt#23 and fast recovery algorithm. Particularly, pkt#23 is retransmitted at that time (don't have to wait until time-out); ssthresh = (old cwnd_/2) = 10 and cwnd_ is reset to 10+3 = 13; then cwnd++ for each dup ACK arrives at the sending side. However, cwnd cannot increase more than 20 because the max window size of this simulation is 20. - At time 2.104, the sending side receives an ACK requesting for pkt#25. This ACK triggers the sender to exit fast recovery. This means that cwnd is decreased from 20 to 10. (ssthresh = 10) - Since time 2.104, the sending side cannot send any more packets because the used window[25-42] has excessed the current cwnd [10] and no enough duplicate ACKs for triggering fast retransmit of pkt#25. Thus, the sender waits until time-out of pkt#25 - At time 2.686, time-out of pkt#25. The sender reset cwnd to 1 (ssthresh = 5) and retransmits pkt#25. Slow-start restarts. - At time 3.036, the sender retransmits pkt#27 and #28. (cwnd has been increased to 2 because the sender got a normal ACK requesting for pkt#27 before 3.036.) - At time 3.352, cwnd is increased to 3 since the sender receives one normal ACK requesting for pkt#28 and one dup ACK of pkt#28. Then, the sender retransmits pkt#29, #30 and #31. - At time 3.666, cwnd is increased to 4 since the sender receives one normal ACK requesting for pkt#39 and 2 dup ACKs of pkt#39. This makes the sender to retransmit pkt#39, #40, #41 and #42. - At time3.878, cwnd is equal to 5 because the sender receives one normal ACK requesting for a new pkt (pkt#43). This makes the sender sends pkt#43, #44, #45, #46 and #47 into the network. - At time 3.928, the sender receives 3 duplicate ACKs requesting for pkt#43 in a row. This causes cwnd increase to 8. Thus, the sender can send 3 more packets: #48, #49 and #50. - At time 4.342, the sender sends pkt#51 - #56. (current cwnd = 6) - At time 4.614, the sender sends pkt#57 - #63. - At time 4.926, the sender sends pkt#64 - #71. |