Subject: Re: Counting ACKs in NewReno

From: Kacheong Poon <[email-masked]>
Date: Sun, 14 Mar 1999 23:27:46 -0800 (PST)

Included message from [email-masked]:

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

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 infer that you think TCP should not retransmit a
segment unless 3 dup acks of the previous segment are received.  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.  

...
>The next example shows that the proposed rule for updating the dupacks
>counter doesn't prevent partial ACKs from generating retransmissions.
...

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.  And because no new acks will come back, TCP
has to time out.  This is what NewReno tries to avoid.

...
>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.

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.  And one may argue that this time out
is a good thing.  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.
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.  That is why dup ack count
is reset to 0.

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.  But there are several things you need to
clarify first.

1. You have to decide what a congestion event is.  You cannot keep on 
manipulating the dup ack count.  When should this end?  Does TCP halve its
window whenever dup ack count equals 3?
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?

Basically you need to describe the reasons behind your suggestion and then
tell us how your suggestion should be integrated into NewReno.  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]

---

From: [email-masked]
Date: Tue, 16 Mar 1999 01:41:20 -0500

Hello,

   Now for the value of the dup ACK counter at the end of fast Recovery, I
   think that here the value of this counter doesn't count a lot.

Why? Because of lost ACKs?

   Setting
   it to zero may prohibit the source from detecting some losses as you
   show in your exemple. Also taking the number of duplicate ACKs into
   account may cause a problem because we are not sure if these duplicate
   ACKs correspond to packets sent before or after the loss. A duplicate
   ACK for a packet sent before the missing packet is not a signal for the
   loss of this packet.

At the end of Fast Recovery, if you update the dup ACK counter after
each partial or full ACK as I proposed, you have a useful count of the
packets sent after the loss and received by the other end. As long as
you don't overestimate this count, any number should be more useful than zero.

Marcel

   I propose here to not count on the counter and
   instead to stretch the Fast Recovery phase to cover the new packets sent
   during Fast Recovery. Let X be the highest sequence number sent when the
   Fast Recovery phase is called, let Y be the highest sequence number sent
   when the last loss in the window is retransmitted. When an ACK for this
   loss is received, if this ACK askes for a packet less than Y than we can
   conclude that this packet is also lost without waiting for dup ACKs
   because at least one Roundtrip time has passed since its transmission.
   Now if the ACK carries a sequence number more than or equal to Y than
   dup ACK can be set to zero and normal Fast Retransmit can be used to
   detect the subsequent losses.

   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

---

From: Kacheong Poon <[email-masked]>
Date: Tue, 16 Mar 1999 00:44:25 -0800 (PST)

Included message from [email-masked]:

>----
>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.

Oops, I misunderstood yours as

dup_ack_cnt = dup_ack_cnt - segs_acked - 1.

Now, I see where that - 1 comes from.

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

Let me try another example.  Using your notation, cwnd = 5,

[1] 2 [3] 4 5

After fast retransmitting seg 1, partial ack for seg 2 comes back.  Then
dup_ack_cnt -= 2 - 1 = 2.  (I hope I get it right this time (-:)  So
using your idea, since dup_ack_cnt < 3, seg 3 will not be retransmitted.
cwnd is set to 5 - 2 + 1 = 3.  So no new segment can be sent.  TCP has
to time out.

>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 think we can separate your modification into 2 cases.  Using NewReno's
terms, partial ack and ack covers recover.  Firstly, I don't believe that it
is "risky" at all in retransmitting the first unack'ed segment after getting
a partial ack.  Fast retransmit is triggered because of 3 dup acks.  We
assume that there is no reordering, thus the segment is really dropped.  This
means that no partial ack or complete ack can be sent back until this
dropped segment is retransmitted and received by the receiver.  Thus
retransmitting a segment because of a partial ack is as "risky" as the first
fast retransmission.  They are all linked together.

Suppose for the moment, we just apply half of your idea, do the dup_ack_cnt
calculation but relax the dup_ack_cnt >= 3 rule.  If after leaving fast
retransmit phase, dup_ack_cnt is still > 0, can we infer that some of the
new segments sent during fast retransmit phase are also dropped?  I'll say
probably.

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

If the network is very congested, what is not good for a connection can be
the best way to prevent network collapse.

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

The dup_ack_cnt is just an implementation detail in NewReno which is used to
identify when fast retransmit start and ends.  Reseting it to 0 just means
it is the 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.
>No. The congestion window should be handled as in the current draft.

Actually, my intention is to ask when you stop the fast retransmit phase.
Do you stop only when dup_ack_cnt becomes 0 or a time out happens?  The
reason I ask is that a fast retransmit phase covers a single congestion
event.  If cwnd is adjusted as in the draft, the loss of a new segment sent
during fast retransmit phase is treated as the same congestion event.  I'd
suggest cwnd needs to be decremented when recovering for segments sent
beyond recover.

>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?

As I described above, it is as "safe" as the first fast retransmission
of seg 1, especially in this example.

							K. Poon
							[email-masked]

---

From: Kacheong Poon <[email-masked]>
Date: Tue, 16 Mar 1999 01:10:42 -0800 (PST)

Included message from "Chadi M. BARAKAT" <[email-masked]>:

>----
>[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.

Actually, after getting partial ack of seg 3, cwnd is set to 5-3+1 = 3.
That means a new seg can be sent, assuming there is new data.  This
new seg 6 will in turn elicit another dup ack, which will increase cwnd
by 1 and dup_ack_cnt by 1.  Another new seg 7 can be sent, which will
elicit another dup ack.  After getting this dup ack, dup_ack_cnt will
be equal to 3, thus seg 4 is retransmitted according to Marcel's
suggestion.

>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 I want to know is if you retransmit a segment because of this ack,
should cwnd be decremented?  I think you agree that it should.  Another
question is should this retransmission be the start of another fast
retransmit?  If it should, then maybe your T will become recover of the next
phase.  And because cwnd and ssthresh are getting smaller, this extension
will eventaully end.  

As I stated in my previous mail, if the window is relatively large, your
dropped U can be recovered by another fast retransmit.  Your extension
mechanism can recover it faster and for smaller windows.  You have a 

							K. Poon
							[email-masked]

---

From: [email-masked]
Date: Tue, 16 Mar 1999 23:18:04 -0500

.........

   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??

   ......

   What do you think?

   Chadi

I'm not sure your argument is correct.

Lets assume that U = T. What if Z is retransmitted immediately after U?
On their way to the receiver, Z and U get reordered, Z is received first and
an ACK asking for U is send back to the source. Immediately after that,
U is acked in a separate ACK message. The two acks are received by the source
in the order they were sent. Upon receiving the first of the two ACKs, U is
retransmitted unnecessarily.

In the following, U != T.
I believe you can use your idea only to fast retransmit the packets beyond Y
that were sent before V, where V is the packet with the highest sequence
number between X and Z, that was lost. In other words, you can fast
retransmit U if T is the highest new packet sent before the retransmision
of V, where X [V] [Z] Y [U] T.

A second case when it is safe to fast retransmit U is when there are at
least two packets between U and T. In this case, there are three packets
between U and the retransmission of Z and it is safe to ignore packet
reordering.
(This second case will be handled correctly by Reno/NewReno and U will be
fast retransmitted because dupacks >= 3 when the ACK asking for U is received).

Please correct me if I'm wrong.

If my understanding of NewReno is correct, the first retransmission is protected
by the first three duplicate ACKs, while the next retransmissions are protected
by the "at least one roundtrip" argument. Once you exit the window, you are
protected by the "at least one roundtrip" argument only in the special case
described above. Otherwise, you need to wait for the three dup acks.

In my proposal, you fast retransmit only when protected by three dup ACKs,
when you're inside or outside the window.

Marcel