Subject: Re: Counting ACKs in NewReno

From: [email-masked]
Date: Tue, 16 Mar 1999 01:23:32 -0500

Thank you very much for your comments.

   Included message from [email-masked]:

   >----
   >I've a question regarding your draft (draft-ietf-tcpimpl-newreno-02):

First, let me clarify my proposal: upon receiving a partial or full ack, dupacks
should be
decremented by (the number of segments acknowledged - 1), i.e.,
dupacks -= #segs_acked -1.

Second, I don't think your counterexample is correct because the algorithm I
propose retransmits
if dupacks >= 3, even if the dup acks counted don't ack the previous segment:

   Let's consider a simpler example. Using your notation, with cwnd = 5,
   the following segments are sent.

   [1] [2] 3 4 5

   If we use the implementation suggested by the draft, seg 1 is fast
   retransmitted as with the old algorithm.  If the retransmitted seg 1
   is not lost, the partial ack of 1 will trigger the retransmission of seg 2.
   Note that because of the small cwnd, no new segments are sent during
   the fast retransmit phase.  But with your suggestion about dup ack count,
   seg 2 will not be retransmitted.

No. If you count dupacks as I suggested, segment 2 will be retransmitted
upon receiving the partial ack of 1.

Reason: before retransmitting 1, dupacks is 3. Upon receiving
the partial ack of 1, dupacks is decremented by 0, i.e. dupacks remains 3
and segment 2 is retransmitted immediately.

A segment is retransmitted if dupacks is >= 3. The duplicate acks don't
have to ack the previous segment.

   And because no new acks will come back, TCP has to time out. This is what
   NewReno tries to avoid.

If you decrement dupacks upon receiving a full or partial ack, as I suggested,
you don't always
need new acks in order to retransmit.  For segments close to the left edge of
the sender window
(the window when fast retransmit is initiated) both 'old' and 'new' algorithms
have the same
behaviour. For segments close and beyond the right edge of the sender window,
the two algorithms
behave differently.

   The following is my understanding of NewReno and its variants. The 2 basic
   ideas behind NewReno are stated in the draft.  They are:

   1. Multiple drops of TCP segments in a window should be treated as a
   single congestion event.
   2. It is safe to infer from a partial ACK during fast retransmit phase
   that the next unack'ed segment is lost, retransmit it immediately.

   Note that there is no mention of dup ack count in the above 2 ideas.  The
   count is an implementation detail about when to start the fast retransmit
   phase.

   Reading from what you suggested, it seems to me that you did not agree that
   2 above is a good idea.

I didn't say that 2 is not a good idea. What I'm saying is that within
the window, counting dupacks more carefully will get you about the same
results as the old algorithm but with less risk. Furthermore, as you advance
beyond the right edge of the window, the new algorithm preserves "hard
to collect info" (# of dupacks) and having this info helps you avoid timeouts
when segments immediately to the right of the window are lost.

   I infer that you think TCP should not retransmit a segment unless 3 dup acks
   of the previous segment are received.

Sorry for the confusion. I propose that TCP should not retransmit
unless dupacks >= 3. The dup acks that are counted don't have to ack
the previous segment or even the same segment. Lets go back to example 1.

   While this may be a good idea, but I think it has its shortcomings.
   Let's look at your example.

   >Example 1.
   ...
   >[1] 2 3 4 5 6 [7] 8    ([ ] =  lost segments)

   >When the partial ack arrives, dupacks is 6 and the draft says only
   >that it shouldn't be reset.  As dupacks >= 3, should segment 7 be
   >retransmitted immediately?

   Idea 2 says that it should.

Segment 8 generates a dup ack for segment 1.
The retransmission of 1 generates a partial ack for 6 and segments
9 and 10 are transmitted. The dupacks counter is decremented by 5,
from 6 to 1. Segments 9 and 10 generate two acks for 6, which are both
duplicate acks. The dupacks counter is incremented twice by one,
it becomes 3 and  segment 7 is retransmitted.

In summary, 7 is retransmitted because dupacks is >= 3. One of the three
dup acks counted is for 1, the other two for 6.
   ...
   >Example 3.
   >Consider an initial cwnd of 9, message 1 and 7 are lost, messages 2-6,
   >8, and 9 are received. recover is set to 9 and ssthresh to 4. If we update
   >dupacks as in example 1, upon receiving a partial ack for segment 6,
   >segment 7 is not retransmitted immediately because the new value of
   >dupacks is 2. However, the new cwnd is 6 and three new  data segments
   >(10, 11, 12) are sent. Lets assume segment 10 is dropped:
   >[1] 2 3 4 5 6 [7] 8 9 [10] 11 12 13   ([ ] = lost segments)

   NewReno will retrasnmit seg 7 immediately after getting a partial ack for
   seg 6 because TCP is still in fast retransmit phase.  It seems to me that
   you are mixing your suggestion with NewReno.

Again, sorry for mixing the two. Example 3 argues against clearing the
dupacks counter upon receiving a full ack.

   Let's look at what NewReno will do in your example more closely.  Note the
   differences from the description in your mail.

   1. Seg 1 is fast retransmitted after getting dup acks elicited by segs 2, 3,
   and 4.  cwnd is set to 9/2 + 3 = 7.
   2. Dup acks elicited by segs 5, 6, 8, and 9 increases cwnd to 11.  Segs 10
   and 11 are sent.
   3. Partial ack for 6 is received, seg 7 is retransmitted.  cwnd is set to 11
   - 6 + 1 = 6.  Seg 12 can be sent.
   4. Dup ack elicited by seg 11 is received, cwnd is set to 7.  Segs 13 can be
   sent.
   5. "Complete" ack for seg 9 is received, cwnd is set to 4.  Fast retransmit
   phase ends.  No new seg can be sent.
   6. Dup ack elicited by segs 12, 13 are received.  Dup ack count is 2, no
   fast retransmit will happen.  TCP has to time out.

   Although the end result is the same as you described, there are some subtle
   differences in the sequence of events.

You're right, there are differences in the behaviour of the two algorithms
for the segments inside the window, i.e., 1 to 9. But these differences are
minor: the algorithm I suggested will retransmit 7, although a little later
than the NewReno

But there is also an important difference: the algorithm I suggested will
retransmit 10 without a timeout while NewReno timeouts because it drops all
the info on the dup acks generated by the segments outside of the window,
i.e., segments 11, 12, and 13.

   And one may argue that this time out is a good thing.

Due to my limited experience, I can't agree or disagree with you. I thought
that timeouts and unnecessary retransmissions are always bad.

   In fast retransmit phase, the sender has already slowed
   down.  Seg 10 is sent in this phase.  If segment loss is solely because of
   congestion, the loss of seg 10 indicates that the network is congested even
   after the sending rate is dropped.  It is good for TCP to slow down further.

Agree.

   This conforms to the idea that multiple drops in a window should be treated
   as one single congestion event.  Seg 10 is outside the original window.  It
   should be treated as another congestion event.

I think that reducing the congestion window is the best way to slow down TCP.

   That is why dup ack countis reset to 0.

I don't see the benefit of clearing the dupacks counter. Please elaborate.

   Note that NewReno does not try to recover all segment drops.  It just tries
   "harder" than the original fast retransmit algorithm.  Can your suggestion
   be added to NewReno?  May be.

In its simplest form, I believe that it can be added to NewReno without
increasing NewReno's complexity or overhead significantly.

   But there are several things you need to clarify first.

I agree.

   1. You have to decide what a congestion event is.  You cannot keep on
   manipulating the dup ack count.  When should this end?

When there are no losses, the dupacks counter will go to zero rapidly.
Because of lost acks, there will be attempts to decrement the counter
below zero. Anyway, dupacks should always be >= 0.

   Does TCP halve its window whenever dup ack count equals 3?

No. The congestion window should be handled as in the current draft.

   2. I think idea 2 of NeReno is pretty safe and very helpful when drops happen
   in a burst.  Do you agree that we should not change it?  If no, why?

I'm not sure idea 2 is always safe. For instance,
consider an initial window of 5, with segments 1 and 5 lost:
[1] 2 3 4 [5].
How safe is to retransmit 5 upon receiving a partial ack for 4?

Let me know what you think.

Anyway, unless my comment on your "[1] [2] 3 4 5" example is incorrect,
I believe the algorithm I suggested handles a burst of lost messages as
well as NewReno.

   Basically you need to describe the reasons behind your suggestion and then
   tell us how your suggestion should be integrated into NewReno.

Reasons behind my suggestion:
         1. avoid unnecessary retransmissions of segments inside and
close to the right edge of the window, and
         2. avoid timeouts on segments outside and close to the right
edge of the window.

The integration, if considered useful, should be relatively easy.

   As mentioned in the draft (isn't it an RFC now?), there are many
   variations to NewReno. You are encouraged to describe yours.
   >----

                                    K. Poon
                                    [email-masked]

Thank you again for your comments,
Marcel

---

From: "Chadi M. BARAKAT" <[email-masked]>
Date: Tue, 16 Mar 1999 09:04:50 +0100

All you said Marcel is correct, the problem is one a loss appears at the
end of the window (before the end by less than three packets) and you
don't send enough new segments during Fast Recovery to make dupacks more
than 3. Take this counterexemple

If the source transmits packets 

[1] 2 3 [4] 5

I use the same notation for lost packets. The source receives first
three dup acks that correspond to the receipt of packets 2, 3 and 5.
dupacks is then 3 and the source retransmits packet 1, sets its window
to 2 and adds three to cwnd which becomes 5. Here no new segments are
transmitted. When packet 1 arrives at the destination, an ack asking for
packet 4 is transmitted. According to your proposal, when the source
receives this ACK, it decrements dupacks by two which becomes 1. Here
packets 4 cannot be retransmitted and a timeout is required. However
with the current version of New Reno it is retransmitted directly. I
think that it must be retransmitted because one Round trip time has
passed since its transmission and it is very probable that it is lost.

Now for my proposal about stretching the Fast Recovery phase, I don't
mean by stretching try to recover the new packets sent during the Fast
Recovery phase without reducing further the window, I just want to
profit from the information that these packets are sent long time ago
(at least one Round trip time). As in current New Reno Fast Recovery
must always end when all the packets in the window when it is called are
acknowledged. Any loss in another round trip time is another congestion
signal and the window must be reduced again. 

Let X and Y the lowest and the highest sequence numbers transmitted when
Fast Recovery is called. X is lost. 

Let Z be the highest sequence number between X and Y that is also lost.
When the source receives the partial ACK asking for packet Z, it has
transmitted new packets until T whith T>Y. 
Here it retransmits Z and may be some new packets beyond T. Packet Z
arrives at the destination which must ack all the packets till T if they
are correctly received of course. Suppose that a packet between Y and T
is also lost, call it U, we have the following figure

X  [Z]  Y  [U]  T    

Here the source receives an ACK asking for packet U. If it resets the
dupacks counter after leaving fast recovery and if the number of
segments sent after T is less than three, the detection of the loss of U
requires a timeout. Recall that all the dupack of segments X till T have
been already received when the ack asking for segment U arrived. However
if the source uses the dupack counter as proposed by Marcel, it will
consider the dup acks of packets sent between U and T with any dup ack
for a packet sent after T. This may also cause a failure of Fast
Retransmit if the number of these dup acks is less than three. However
this proposition is better than resetting the counter because it takes
account of dup acks for packets between U and T.

I propose here that the source should retransmit directly packet U
without waiting for three dupack or timeout. At least one round trip
time has passed since the transmission of U and it is very probable that
it is lost. How to do this??

The source stores in a variable the highest sequence number sent and it
updates this variable when it receives a partial ACK (less than Y). When
it leaves Fast Recovery and receives an ACK asking for a packet less
than this variable (T in our exemple), it retransmits this packet
directly.

What do you think?

Chadi

-- 
                    **  Chadi Mohamad BARAKAT  **
           http://www.inria.fr/mistral/personnel/Chadi.Barakat
                                  /\
PhD Student - MISTRAL - INRIA    /  \   [email-masked]
2004, Route des Lucioles BP 93   \  /   Phone : + 33 4 92 38 71 99
06902 Sophia Antipolis - France   \/    Cell  : + 33 6 10 42 36 30