Subject: NewReno and the 2001 Revision

From: Mark Allman <[email-masked]>
Date: Fri, 11 Sep 1998 09:06:45 -0400

We would like to hear some feedback on what sorts of loss recovery
mechanisms the working group thinks are appropriate for inclusion in
the revision of RFC 2001.  As Sally outlined in Chicago, there are
several improvements we can make to Reno style TCP (i.e., TCP
without SACK).

Our current opinion is that some form of the NewReno changes (as was
obvious in the meeting, there are a number of permutations of
NewReno) should be included in a seperate experimental document.
However, as Sally outlined in the meeting and it her note to this
list shortly after, there is also a seperate issue of fixing a
fairly well known TCP bug (misfeature?).  The bug occurs when
multiple fast retransmits happen for multiple lost segments within a
window of data and consequently cwnd is halved multiple times for
one ``congestion event''.  We would like to hear comments on whether
or not such a bug fix should be included in the 2001 revision.

Thanks,
Mark and Vern

---

From: Tom Henderson <[email-masked]>
Date: Tue, 15 Sep 1998 13:19:27 -0700 (PDT)

I've recently been looking at this issue quite closely.  This bug fix is
very helpful in at least the following situation:  large file transfers over
GEO (600ms RTT) paths for which the initial value of ssthresh is not cached 
but is instead some large value.  Without the fix, the slow start overshoot 
typically leads to multiple packet losses, which then leads to rebuilding 
snd_cwnd linearly from a small value.  As an example of the type of 
performance difference I've seen, a 10 MB file transfer over our GEO network 
testbed consistently takes a 30% hit in throughput when SACK with Reno 
congestion avoidance is used instead of SACK with ``NewReno.''  In general,
for long transfers over a satellite path, it is very costly to unnecessarily
reduce the congestion window while in linear growth phase.

I agree with the opinion that this is a bug fix and should not be considered
experimental.  It covers a case for which the previous version of RFC 2001 
was ambiguous (what to do if the ACK is a partial ACK).  However, I also
believe that if the spec is to include this, it should fully specify the
correct behavior upon receiving a partial new ACK.  In our SACK + NewReno 
implementation, we also do the following:
	- upon receiving a partial ACK, partially deflate the current snd_cwnd 
by (the amount of new data acked minus one segment), resend the next 
highest segment that has not yet been ACKed, and call tcp_output() to see if 
a new segment can be sent.  The reason to do window inflation in Reno TCP is 
to have the correct amount of outstanding data in the network when the 
recovery ends.  If one does not deflate the window for partial ACKs, this 
amount will be incorrect (overestimated).
	- upon leaving fast recovery, set snd_cwnd to min(snd_ssthresh,
current amount of outstanding data).  Window inflation may not successfully
generate enough new transmissions for a number of reasons (e.g., sender is 
receiver window limited, dup acks are lost), leading to a burst of packets 
when the recovery phase ends.  Kevin Fall and Sally Floyd have previously 
proposed a "maxburst" parameter that limits the number of segments that can be 
sent in response to an ACK when leaving fast recovery phase.  However, we 
found that a slow receiver can generate a lot of pure window updates right 
after recovery ends, the effect of which can circumvent this maxburst 
protection.  Setting snd_cwnd to be no more than the current amount of 
outstanding data is effective in preventing this problem.
	- avoid "false fast retransmissions" after a timeout as decribed by 
Hoe in the 1996 Sigcomm paper.

--Tom Henderson

For those interested, more details on our TCP implementation and experimental
results can be found in the following paper:
http://www.cs.berkeley.edu/~tomh/papers/jsac99_abstract.html

---

From: Kacheong Poon <[email-masked]>
Date: Wed, 23 Sep 1998 19:31:22 -0700 (PDT)

> congestion avoidance is used instead of SACK with ``NewReno.''  In general,

Can you describe what you meant by SACK with Reno and SACK with NewReno? With
NewReno, upon receiving a partial ACK, the first unack'ed segment is
retransmitted immediately.  So how do you use SACK info here?  Do you
retransmit more than one segment using SACK info?  Or do you check that the
first unack'ed segment is indeed lost before retransmitting it?  And if the
first unack'ed segment is not lost, you use the SACK info to retransmit the
next lost segment?

							K. Poon.
							[email-masked]

---

From: Kacheong Poon <[email-masked]>
Date: Wed, 23 Sep 1998 19:25:13 -0700 (PDT)

> or not such a bug fix should be included in the 2001 revision.

I'd suggest putting the bug fix in the 2001 revision but leave out NewReno. 
IMHO, we should come up with a draft on the use of SACK in recovery instead of
spending effort on experimental documents describing NewReno and other
variants.  As Sally pointed out in the IETF meeting, we can easily come up
with scenarioes where NewReno and its variants work badly or too aggressively. 
But with SACK, we can do better.  As of now, there is no internet draft on how
to make good use of SACK.  I think in 1 year's time, SACK should be widely
deployed.  So we should focus on how to make good use of SACK info, and also
how to avoid abusing it.

							K. Poon.
							[email-masked]

---

From: Tom Henderson <[email-masked]>
Date: Wed, 23 Sep 1998 22:45:24 -0700 (PDT)

> Can you describe what you meant by SACK with Reno and SACK with NewReno? With

First, let me define NewReno for the purpose of this discussion.  NewReno is 
Reno with the following changes:
i) define a variable (snd_recover) that is set to snd_max upon entering fast
recovery.  When snd_una reaches snd_recover, the fast recovery phase is 
considered to be over.
ii) if a partial cumulative ack is received (ti_ack < snd_recover), retransmit
the next segment beyond ti_ack, deflate snd_cwnd by the amount of new
data acknowledged, add back one segment to snd_cwnd, and send a new segment
if permitted.
iii) if a new ack is received with (ti_ack >= snd_recover), set snd_cwnd to
min(snd_ssthresh, amount of outstanding data in the network + 1 segment)
and otherwise exit fast recovery as in Reno.
iv) do not reset snd_recover upon a rtx timeout.  If three dupacks are received 
and (ti_ack < snd_recover), do not perform fast retransmit/fast recovery but 
instead just advance snd_cwnd by one segment and send the next segment 
(snd_nxt).  This is avoidance of false fast retransmission after a timeout.

When combining SACK with NewReno, the SACK information may permit you to
identify segments that need to be retransmitted before you receive the 
partial cumulative ack.  In our implementation, if the SACK information 
indicates that the receiver is holding a segment sent at least 3 segments 
beyond a given segment that is not SACKed, the given segment is eligible for 
retransmission.  If we send such a retransmission ``early'' (i.e., before 
partial cumulative ack), we decrement the inflated snd_cwnd by one segment to 
account for this (in essence, we trade sending a new segment
off the top of the window for the early retransmission).  If we later get a 
partial cumulative ack, but the next segment has already been retransmitted,
snd_cwnd is inflated by one segment.  In summary, in our implementation, SACK 
information permits the substitution of an early retransmission for inflating 
snd_cwnd by one segment, in a manner consistent with the allowable amount
of outstanding data in the network under NewReno rules.  This reordering of
retransmissions and new transmissions allows recovery to occur in fewer RTTs.

SACK with Reno also allows you to send retransmissions early (as defined 
above), but suffers from the multiple window reductions in one window of data
and false fast retransmission problems.

Tom

p.s.  I'd like to hear if my outline of what I called NewReno above is 
consistent with the ``bug fix'' people had in mind, as I know the term 
NewReno can mean different things to different people.

---

From: "David S. Miller" <[email-masked]>
Date: Wed, 23 Sep 1998 22:56:41 -0700

Date: Wed, 23 Sep 1998 22:45:24 -0700 (PDT)
   From: Tom Henderson <[email-masked]>

   p.s.  I'd like to hear if my outline of what I called NewReno above
   is consistent with the ``bug fix'' people had in mind, as I know
   the term NewReno can mean different things to different people.

To remove confusion I usually refer to it as "Hoe style retransmits",
to directly reference the retransmit strategy changes suggested by
Janie Hoe's paper.

I think this bug fix is useful in the case where SACK is not being
used.  There are going to be many non-SACK stacks still around even
when SACK is moderately prevalent and deployed.  (I still see a packet
trace involving a KA9Q stack from time to time even today :-)

SACK is in my experience of implementation more powerful with other
techniques such as FACK, so much so that any benefits the newreno
changes give you are lost in the noise.

Later,
David S. Miller
[email-masked]

---

From: Rick Jones <[email-masked]>
Date: Thu, 24 Sep 1998 09:52:46 -0700

> and otherwise exit fast recovery as in Reno.

I'll have to ask the guys currently supporting MPE/iX, but I think that
the behaviour described in i has been present in the MPE/XL (now iX) TCP
stack since we implemented congestion control and avoidance. ii has been
present in that the next segment after the ACK would be sent, but I do
not recall new data being allowed. that stack would then start from a
cwnd of 1 upon iii.

At the time (89-90ish) it worked pretty well for aggregate file
transfers over 9600 baud dial-ups.

rick jones
-- 
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to email, or post, but please do not do both...
my email address is raj in the cup.hp.com domain...