Test Description:
This test shows the fast recovery algorithm of TCP Reno with a single packet drop.
Expected output:
  • After a packet loss, duplicate ACKs are received. When duplicate ACK count reaches the threshold of 3, fast retransmission is performed. The packet which is possibly lost is retransmitted.
  • Congestion avoidance is performed. The ssthresh is set to half of number of packets in flight (half of min(cwnd, rwnd)). In this test, ssthresh is set to 7 packets.
  • Fast recovery is performed after fast retransmission. The cwnd is set to ssthresh + 3 * MSS
  • When number of duplicate ACKs is greater than 3, cwnd increases by 1 MSS for each duplicate ACKs. Send one packet if allowed by the new cwnd value.
  • After the ACK of the retransmitted packet is received which acknowledged all outstanding packets, fast recovery is finished. The cwnd is set to ssthresh, and congestion avoidance is performed.
    • When congestion window reaches ssthresh, congestion avoidance is performed. Congestion window will increase by one packet roughly per one round-trip time.
Test Topology 
  Server .................Router.................Client

             8Mbs 5ms              800kbs 100ms
   6(0)------------------0(1)0(0)-----------------7(0)
SSF Configuration Test File: f13.dml
send window = receive window = 28 packets
SSF Tcpdump File: f13.tcpdump

Figure 1: Sequence number plot for tcpdump at router.
Zoom in plot for Figure 1

Note that in above figure, the packet is dumped at the router, there is slightly delay between the 3rd duplicate ACK and fast retransmitted packet. The same delay exists for the last duplicate ACK and the last fast recovery packet.

Server tcpdump, RTT and Congestion window plot
(EPS format plot)

Figure 2: Sequence number plot, RTT plot and cwnd plot for tcpdump at server
Zoom in plot for figure 2 (EPS format)
Note that after fast retransmission, the fast recovery does not send any packet until after a few ACKs, when the usable window becomes positive.

NS Test with the same network parameters

NS tcpdump trace file:f13.tr

Original trace

Note that at the beginning of the trace there are two additional short connections used to force the packet drop.

Zoom in on NS trace

Trace Analysis:

The output is consistent with what we expected.
  • Packet loss and fast retransmission/fast recovery:
  • From Figure 1, we can see that after 3 duplicate packets the fast retransmission/fast recovery is performed.
  • The lost packet is retransmitted, and ssthresh and cwnd are updated: 
    ssthresh = max(flight-size/2, 2*MSS) = 7 MSS
    cwnd = ssthresh + 3* MSS = 10 MSS
    • According to the send window management algorithm (see SSF TCP implementation), the usable window is: 
      D = snd_una + snd_wnd - snd_nxt
      In SSF TCP a new data packet can be sent only when D >= MSS, implying: 
      min(cwnd, rwnd) - (snd_nxt - snd_una) >= MSS
    • For Reno TCP, after fast retransmission, snd_nxt is the last value before the 3rd duplicate ACK. In most cases snd_nxt is equal to snd_max and greater than snd_una, and a new packet will be send if allowed by cwnd.
    • In this test snd_nxt = snd_max, and we find: 
      (snd_nxt - snd_una) = 15 MSS
      It means that a new packet can be sent only after cwnd > 15 MSS
  • The cwnd is increased by 1 MSS for each duplicate ACK after fast retransmission. After another 5 duplicate ACKs are received, cwnd is large enough to send a new packet. Each additional duplicate ACK triggers one new packet transmission. During the fast recovery 5 more new packets are sent before new data ACK arrives.
  • New data ACK comes, fast recovery is finished, congestion avoidance is performed:
    • cwnd is set to ssthresh, and congestion window will increase by one packet roughly per one round-trip time.