Subject: Re: Counting ACKs in NewReno

From: [email-masked]
Date: Wed, 17 Mar 1999 01:12:25 -0500

Included message from [email-masked]:

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

Yes, you're right...
However, in my original message, under Example 1, I say:
"....If we want to be more aggressive and count the retransmission of
segment 1 as a segment sent after 7 but acked before 7, then the new
value of dupacks should be 2...."

I was trying to say that you can be more aggressive for the second
retransmission. The more aggressive algorithm won't timeout on
"[1] 2 [3] 4 5".

Here is a better way to count fast retransmissions as messages sent after X
but acked before X:

Enter in fast retransmit phase and retransmit if dupacks >= 3.
Upon receiving a partial ACK, always decrement dupacks by (# segs_acked - 1)
and:
if this would be the 2nd fast retransmit, then retransmit if dupacks >= 2,
or if this would be the 3rd fast retransmit, then retransmit if dupacks >= 1,
otherwise, retransmit unconditionally.

I believe that you can prove that the shortest three examples for which the
aggressive algorithm timeouts are the following: [1] 2 3 4 [5] [6] 7,
[1] 2 3 4 [5] 6 [7], and [1] 2 3 4 [5] [6] [7]. The main observation is that
while in the fast retransmit phase, cwnd is always >= cwnd0/2, where cwnd0
is the initial congestion window (before the congestion event).

Using the same observation, you can prove that the aggressive algorithm
timeouts after the first retransmit only if 1/2 of the window or more is
lost (in the examples above, at least 3 messages are lost for a window of 7).
NewReno won't timeout if 1/2 window or more is 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.

   .......

OK, lets separate my proposal in two cases and apply only part of the idea.
In the fast retransmit phase upon receiving a partial ACK, adjust dupacks as
I proposed and retransmit unconditionally (because it is safe to assume
the segment was lost after at least one roundtrip).
Upon receiving a full ACK, adjust dupacks as I proposed. If dupacks > 0, use
it to determine the start of a new fast retransmit phase.

I believe that if you filter window updates correctly, a positive value
of dupacks upon leaving the fast retransmit is a pretty safe indication of
a lost segment.
If ACKs are lost on their way back to the source, dupacks underestimates
the number of segments received out of order.
Why do you say 'probably'?

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

Comparing against the current value of the 'recover' variable will do the same.
I assume that 'recover' is never cleared; only set when fast retransmit starts.

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

You stop the current retransmit phase upon receiving a full ACK. Adjust cwnd
as the draft says and adjust dupacks as I suggested. If updated dupacks >= 3,
start a new retransmit phase; follow steps 1 and 2 in the draft. Clear dupacks
only if negative (if ACKs are lost, my algorithm for adjusting dupacks can
yield negative values).

   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.

Upon receiving a full or partial ACK, cwnd should be adjusted as specified in
the draft.

   >----

                                    K. Poon
                                    [email-masked]

Looking forward to your comments,
Marcel

---

From: Kacheong Poon <[email-masked]>
Date: Wed, 17 Mar 1999 20:09:37 -0800 (PST)

> otherwise, retransmit unconditionally.

It seems to me that you agree that applying your idea during fast retransmit
phase is probably "too safe."  Note that when implementors add code to the
common path of TCP, we want the benefits outweigh the complexity.  Let's skip
this part and look more closely at the other part, and from an implementation
point of view.

> Why do you say 'probably'?

The question here is how you are going to implement it.  We can think in terms
of distinct segments.  But in implementation, we cannot do that.  While we can
keep track of dup acks, we don't really know how many segments a partial or
complete ack acknowledges.  TCP does not need to send full MSS size segments.
(Look at recent thread of modifying Nagle algorithm in tcp-impl.)   That means
an ack for 2920 bytes may actually ack 3 segments, 1 1460 bytes large and 2
730 bytes large.  What an implementation can do efficiently is to guess.  If
MSS is 1460 byes and TCP gets an ack for 2920 byes, assume that it is for 2
segments.  This means that when doing the subtraction in your idea, TCP is
probably going to subtract fewer than it actually should.  Thus a positive
dup_ack_cnt may not really indicate a drop.

If you have an idea of how your counting can be achieved efficiently, please
send it to the mailing list and we can discuss it.  The above is just what I
think your idea can be implemented.  It does not mean that it has to be done
this way.

> Comparing against the current value of the 'recover' variable will do the
> same. I assume that 'recover' is never cleared; only set when fast
> retransmit starts.

As I said repeatedly, dup_ack_cnt is just an implementation detail.  Note that
TCP cannot just compare recover with any ack.  TCP needs to know that it
really needs to compare an ack with recover.  The variable dup_ack_cnt serves
this purpose.  If dup_ack_cnt is >= 3, it means that TCP is in fast retransmit
mode and the seq number stored in recover is valid.  TCP needs to compare the
ack number with recover.  Reseting dup_ack_cnt means that TCP does not need to
do any comparison.  Note that you can introduce a state variable to indicate
that TCP is in fast retransmit mode and need to check recover.  Or using
various other methods.  They are just implementation details.

> start a new retransmit phase; follow steps 1 and 2 in the draft. Clear
> dupacks only if negative (if ACKs are lost, my algorithm for adjusting
> dupacks can yield negative values).

This is what I like you to specify clearly.  Now you've done that, we can look
further to see how this can be implemented.

							K. Poon.
							[email-masked]