Introduction

RFC 3782, "The NewReno modification to TCP's Fast Recovery Algorithm", ([RFC3782]), defines a variant of the Fast Retransmit / Fast Recovery algorithm that is known as NewReno. The main differences of NewReno with respect to the algorithm detailed in RFC 2581 are:

•when three duplicate Acks are received some tests are performed;

•there is a new control variable called recover_;

•a different behaviour in response to partial Acks, with two variants called Slow but Steady and Impatient;

•a new step (step 6) intended to avoid multiple instances of Fast Retransmit.

After a thourough analysis of the NewRenoFullTcpAgent class, which implements the NewReno variant of TCP highlighted, we discovered two differences with respect to RFC 3782: these differences are detailed below.

1. Congestion window check after a Retransmit Timeout

RFC3782 says that, upon receiving the third duplicate Ack, the transmitter enters the Fast Recovery phase only if the Acknowledgment Number field in the received Ack is greater than the value contained in the recover_ variable. The reason is that, after a timeout happened during a Fast Recovery, the receiver keeps receiving duplicate Acks until the segment with sequence number equal to the recover_ is retransmitted.

Looking in the ns-2 class NewRenoFullTcpAgent, one sees that the transmitter, after a timeout, increases by one the transmission window for each duplicate Ack after the third one, so new segments can be transmitted. That is, the transmitter behaves as it was in Fast Recovery, even when it is not, as far as the congestion window update is concerned. This is not consistent with RFC 3782, where no provision exists about cwnd increase when duplicate Acks are received.

1.1 Code changements

We modified ns-2 in order to choose between the current behaviour and the one dictated by RFC 3782, by means of a new variable cwnd_inflation_after_timeout_ added in tcl/lib/ns-default.tcl , as follows:

diff -pu /tmp/ns-default.tcl.orig /tmp/ns-default.tcl

--- /tmp/ns-default.tcl.orig2006-01-17 14:32:16.000000000 +0100

+++ /tmp/ns-default.tcl2006-01-17 14:31:38.000000000 +0100

@@ -1039,6 +1039,8 @@ if [TclObject is-class Agent/TCP/FullTcp

Agent/TCP/FullTcp set nopredict_ false; # disable header prediction code?

Agent/TCP/FullTcp/Newreno set recov_maxburst_ 2; # max burst dur recov

+Agent/TCP/FullTcp/Newreno set newreno_changes1_ 1;

+Agent/TCP/FullTcp/Newreno set cwnd_inflation_after_timeout_ 1;

Agent/TCP/FullTcp/Sack set sack_block_size_ 8; # bytes in a SACK block

Agent/TCP/FullTcp/Sack set sack_option_size_ 2; # bytes in opt hdr

In the NewRenoFullTcpAgent class, the constructor uses the cwnd_inflation_after_timeout_ variable, wich is linked to the equally named C++ variables by the bind method. The default value is 1, which is the unpatched behaviour, that is, the congestion window is incremented after the third duplicat Ack even when not in Fast Recovery.

All other modifications are relevant to the tcp/tcp-full.h and tcp/tcp-full.cc files.
When a segment is received, ns calls the recv method, which in turn, after three duplicate Acks, calls the method dupack_action of NewReno, which does the right thing. If highest_ack_ <= recover_, ns takes the else branch. If cwnd_inflation_after_timeout_ is 0 (not the default) ns follows the logic described in step 1 of the NewReno algorithm (RFC3782, Section 3). If cwnd_inflation_after_timeout_ is 1 (the current behaviour) dupacks_ is not changed and, for each subsequent dplicate Ack, the transmitter enters the extra_ack method in tcp/tcp-full.h, where cwnd is increased.

+void

+NewRenoFullTcpAgent::dupack_action()

+{

+ printf("---> %f recover %d highest %d cwnd_inflation %d dupacks %d\n",now(),

+ (int)recover_,(int)highest_ack_,(int)cwnd_inflation_after_timeout_,

+ (int)dupacks_);

+int recovered = (highest_ack_ > recover_);

+if (recovered) {

+firstpartial_ = TRUE;

+FullTcpAgent::dupack_action();

+} else {

+// After a timeout, we may receive dupacks before we get

+// to retransmit the highest seqno we transmitted before

+// the timeout (stored in recover_).  RFC 3782 says

+// (3.1B) not to enter Fast Retransmit.  By reducing the

+// dupack count by 1 we remember that we received dupacks.

+if (!cwnd_inflation_after_timeout_) {

+printf("-->>>>> %f dupacks %d\n",now(),(int)dupacks_);

+dupacks_ -= 1;

+}

+}

+}

1.2 Testbed for cwnd inflation after timeout

In order to test the different behaviors of ns-2 for different values of cwnd_inflation_after_timeout_, we defined a testbed (Scenario A) with two nodes connected by a link with 1 Mbit/s bandwidth and 100 ms latency; the testbed is implemented in cwnd_inflation_after_timeout.tcl. Segments are 256 byte long, buffer size is 48 segments; notice, however, that buffer dimension is irrelevant in this scenario. Using the ErrorModel/List error model we listed the lost segments, that is id number 62 (with seq number 13177) and its retransmission. When the transmitter receives the third duplicate Ack relative to segment id 62, it retransmits that segment. The retransmission happens at t=1.42 s, and it is lost too, causing a timeout. After an RTO, the transmitter sends the same segment for the third time, and the subsequent segments that had been already got by the receiver, which sends a total of 30 duplicate Acks: starting from the fourth, each causes an increment of cwnd, up to the value of 28. For each cwnd increment, a new segment can be sent, for a total of 27 segments, as shown in the figure below.

When the Ack relative to the retransmitted segment is received, cwnd is increased by one, up to the value of 29. Since at this point the transmitter has received an Ack for every segment sent, it can send at once 29 segments, as shown in the figure below.

This strong increase of the congestion window does not happen in a NewReno implementation that is conformant with RFC 3782. Such an implementation would increase cwnd only when the last Ack is received, that is, the one relative to the lost segment (see figure below), because when the dupacks_ variable reaches 3, it is decreased by 1 (see next figure).

 

In scenario A, the cwnd increment due to the reception of duplicate Acks causes the transmission of a higher number of segments with respect to those sent according to RFC 3782. As far as performance is concerned, the ns-2 implementation is faster than that of RFC 3782: with a simulation time of 5 s, the ns-2 implementations sent about 1400 segments, versus about 1000 sent using the RFC 3782 algorithm. The ratio behind RFC 3782's approach is the packet conservation priciple: while it is true that each time an Ack is received, sending a new packet does not worsen the existing congestion condition, it is true that, after a timeout, even already acked packets are resent, so this principle shoud not hold after a timeout, and ns-2 implementation is more aggrssive than needed, and could lead to buffer overflow, that is, to reduced performance for all connections traversing the overflowed buffer.

2. The Impatient variant

Section 4 of RFC 3782 describes two possible different behaviours during Fast Recovery in response to a partial ack: the Slow but Steady variant, where the retransmission timer is reset at each received partial Ack, and the impatient variant, where the retransmission timer is reset at the reception of the first partial Ack only. There are situtations where many segments are lost during a single transmission window, where the Impatient variant is the winner. However, there is also the case for the Slow but Steady variant, when few segments are lost and RTO is small enough that the rimer expires. In 2.2, two scenarios are depicted that illustrate both cases.

Ns-2 contains NewReno Tcl classes for both one-way TCP (Agent/TCP/Newreno) and two-way TCP (Agent/TCP/FullTcp/Newreno). While both variants are implemented for one-way TCP, only Slow but Steady is implemented for FullTcp.

2.1 Patches

Adding the Impatient variant to FullTcp required adding a new newreno_changes1_ variable:

--- orig/ns-default.tcl2006-01-17 14:32:16.000000000 +0100+++

ns-default.tcl 2006-01-17 14:31:38.000000000 +0100

@@ -1039,6 +1039,8 @@ if [TclObject is-class Agent/TCP/FullTcp

Agent/TCP/FullTcp set nopredict_ false; # disable header prediction code?

Agent/TCP/FullTcp/Newreno set recov_maxburst_ 2; # max burst dur recov

+Agent/TCP/FullTcp/Newreno set newreno_changes1_ 1;

+Agent/TCP/FullTcp/Newreno set cwnd_inflation_after_timeout_ 1;

Agent/TCP/FullTcp/Sack set sack_block_size_ 8; # bytes in a SACK block

Agent/TCP/FullTcp/Sack set sack_option_size_ 2; # bytes in opt hdr

In the constructor of the NewRenoFullTcpAgent class, newreno_changes1_ is linked to the C++ variable with the same name using the bind method. If set to 1, the Imaptient variant is used. This variable is named after the one in Agent/TCP/Newreno with the same purpose.

Other modifications are in tcp-full.h and tcp-full.cc.
When a segment is received, ns-2 calls the recv method which, after three duplicate Acks, enters the method dupack_action. If not in Fast Recovery and recovered_ is true, firstpartial_ is set to true. This variable is central to the rest of the algorithm.

@@ -2668,6 +2670,56 @@ dupack_action:

+void

+NewRenoFullTcpAgent::dupack_action()

+{

+ printf("---> %f recover %d highest %d cwnd_inflation %d dupacks %d\n",now(),

+(int)recover_,(int)highest_ack_,(int)cwnd_inflation_after_timeout_,

+(int)dupacks_);

+int recovered = (highest_ack_ > recover_);

+if (recovered) {

+firstpartial_ = TRUE;

+FullTcpAgent::dupack_action();

+} else {

+// After a timeout, we may receive dupacks before we get

+// to retransmit the highest seqno we transmitted before

+// the timeout (stored in recover_).  RFC 3782 says

+// (3.1B) not to enter Fast Retransmit.  By reducing the

+// dupack count by 1 we remember that we received dupacks.

+if (!cwnd_inflation_after_timeout_) {

+printf("-->>>>> %f dupacks %d\n",now(),(int)dupacks_);

+dupacks_ -= 1;

+}

+}

+}

After the duplicate ack test, in the recv method, ns-2 checks for partial Acks, with the pack method. As shown in the following lines, an Ack can be partial only during Fast Recovery:

--- tcp-full.cc.2.27 2005-05-09 21:21:57.584520792 +0200

+++ tcp-full.cc 2005-05-09 21:21:23.963631944 +0200

@@ -2108,7 +2108,7 @@ process_ACK:

* of newack()

*/

-int partial = pack(pkt);

+int partial = fastrecov_ && pack(pkt);

if (partial)

pack_action(pkt);

In this way, pack_action, which retransmits the first unacknowledged segment, is only called during, Fast Recovery.
Here are the mods to the newack method, which manages the retransmission timer and the Ack numer advancement, which include an accessory method calles reset_rtx_timer_after_ack.

--- tcp-full.cc.2.27 2005-05-09 21:21:57.584520792 +0200

+++ tcp-full.cc 2005-05-09 21:21:23.963631944 +0200

@@ -1236,7 +1236,7 @@ FullTcpAgent::newack(Packet* pkt)

if (ackno == maxseq_) {

cancel_rtx_timer();// all data ACKd

} else if (progress) {

-set_rtx_timer();

+reset_rtx_timer_after_ack(pkt);

}

// advance the ack number if this is for new data

When the Impatient variant is selected, the reset_rtx_timer_after_ack method resets the retransmission timer only after the first partial Ack, that is, when firstpartial_ is true. The timer is reset at every partial Ack if Slow but Steady is selected.

+/*

+ * do a reset of the RTO timer after receiving an ACK

+ */

+

+void

+FullTcpAgent::reset_rtx_timer_after_ack(Packet* pkt)

+{

+set_rtx_timer();

+}

+

+/*

+ * Newreno, when the impatient variant is used (RFC 3782), does not

+ * reset the RTO timer in Fast Recovery after the first partial ACK.

+ */

+

+void

+NewRenoFullTcpAgent::reset_rtx_timer_after_ack(Packet* pkt)

+{

+if (newreno_changes1_) {

+hdr_tcp *tcph = hdr_tcp::access(pkt);

+register int ackno = tcph->ackno();

+// This is the "impatient" version of NewReno

+int partial = (fastrecov_ && ((ackno > highest_ack_) &&

+      (ackno < recover_)));

+int do_not_reset_timer = (partial && !firstpartial_);

+firstpartial_ = FALSE;

+if (do_not_reset_timer) {

+return;

+}

+}

+FullTcpAgent::reset_rtx_timer_after_ack(pkt);

+}

2.2 Testbeds for NewReno variant

The scenarios for this testbed have been obtained by modifying tcl/test/test-suite-newreno.tcl to use FullTcp. Each variant has better performance than the other in one of the two scenarios:

1.in scenario B, Slow but Steady performs better than Impatient: the Tcl program is called with arguments slow2 and impatient2;

2.in scenario C, Impatient performs better than Slow but Steady: the Tcl progrma is called with arguments slow4 and impatient4.

Scenarios B and C differ as far as the lost segments are concerned. They share the same topology, depicted below:

n1 is the sending node, n4 the receiving one. The buffer associated to the n3-n4 link has size 8. The link uses ErrorModel/Periodic, which loses K segments after having seen N; the error model is used together with a flow-based classifier to obtain losses only in selected flows.

Scenario B: Slow but Steady prevails over Impatient

In this scenario segments with id 14, 15, 16, 17, 18 are lost. cwnd's value is 15 when the loss happens. The transmitter enters Fast Recovery after receiveing three duplicate Acks, it retransmits the lost segment (id 14), sets ssthresh to t and cwnd to 10. Fast Recovery lasts about 2 s, during which a segment per RTT is retransmitted. At time t=5.08 s the transmitter receives the first full Ack and exits Fast recovery with cwnd=7. It then sends 7 segments, as shown below.

Even though Fast Recovery lasts for about 2 seconds, performance of Slow but Steady is better than Impatient, as shown below.

When using Impatient, in fact, the transmitter sends segment id 14 when the first loss happens. When the first partial Ack is received, it resets the retransmission timeout; at this point, 4 segments must be retransmitted, but the timeout expires after 1 s, before receiving a full Ack. After the timer expirations, at t=4.46 s, it retransmits the first unacknowledged segment (id 17), sets cwnd to 1 and ssthresh to 3. Because of the timeout, some segments are sent that had already been received.

The tradeoff is between Slow but Steady, which waits in order to retransmit the lost segments while not giving up with an already big transmission window, and Impatient, which prefers not to wait too much. in this scenario, Slow but Steady wins because the transmission window was big enough to be worth waiting for the few lost segments.

2.2.2 Scenario C: Impatient prevails over Slow but Steady

This scenario illustrates the opposite case, where Impatient wins over Slow but Steady because the transmission window was not big enough to be worth waiting the many lost segments. Here we lose the 26 segments with id between 29 and 54. With Slow but Steady, the transmitter enters Fast Recovery after the third duplicate Ack, retransmits the first lost segment and sets ssthresh to 15 and cwnd to 18. Since only one segment is retransmitted per RTT, the transmitter receives the first complete Ack only at t=14,09 s, after which 14 new segments can be sent at once, as shown below.

The Impatient variant performs better, because the transmitter resets the retransmission timeout after receiveing the first partial Ack, at t=3.92 s. After one second, the timer expires, and the transmitter sends the first unacknowledged segment (id 32), sets ssthresh to 7 and cwnd to 1. In about 2 s all segments are transmitted and the relative Acks received, as shown below.

2.3 Verifying the three scenarios with both patches applied

Three scenarios have been examined as testbeds for the modifications to ns-2:

1.Scenario A shows the difference between the native ns-2 implementation of FullTcp/NewReno and the one described in RFC 3782 as far as increasing the congestion window after a timeout is concerned;

2.Scenario B and Scenario C show the differences between the two variants of NewReno (Slow but Steady and Impatient) regarding the management of the retransmission timeout in the presence of partial Acks.

In the following, we show that ns-2 behaves correctly when both changes are applied: increasing the congestion window after a timeout as commanded by RFC 3782 and using the Impatient algorithm.

2.3.1 Scenario A

This scenario is not relevant, because partial Acks are never received, so there is no difference between the way Slow but Steady and Impatient behave.

2.3.2 Scenario B

Same as above: since cwnd is updated per RFC 3782, after the timeout the duplicate Acks are less than three, so dupack_action is never entered.

2.3.3 Scenario C

With this scenario, Impatient behaves differently if cwnd after a timeout is managed per RFC 3782.
At t=7.19 s the transmitter receives the third duplicate Ack, with Ack number 31089. In fact, this segment number has not yet been sent after the timeout, and the duplicate Acks are in response to segments sent before the timeout. The transmitter calls dupack_action and decrements dupacks_, thus preventing increasing cwnd by the extra_ack method. cwnd is subsequently increased when two more duplicate Acks are received.

In the end, using the native ns-2 approach of increasing cwnd aftear a timeout, the transmitter sends 822 segments versus 798 which are sent using the RFC 3782 algorithm.
The following graph illustrates the behaviour obtained in the latter case. The picture below shows the Impatient variant with congestion window updated per RFC 3782.

Patch Sources