Subject: Counting ACKs in NewReno

From: [email-masked]
Date: Fri, 12 Mar 1999 19:25:28 -0500

Hi,

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

I believe that the NewReno draft/RFC should be more specific about the
handling of the duplicate ACKs counter (dupacks) in step 5.

For both partial and full ACKs, I propose that dupacks should be
decremented by the number of segments acknowledged minus one. This is
similar to the draft's recommendation for updating cwnd upon receiving
a partial ACK. The proposed change will only affect the retransmissions
of segments 'around' the right edge of the window, i.e., segments with
sequence numbers 'around' recover.

The draft is unclear about dupacks handling when a partial ACK is
received. If dupacks is left unchanged upon receiving a partial ACK,
unnecessary transmissions may occur (see Example 1). Instead,
decrementing dupacks, as I propose, delays the retransmission of
a segment until there is enough evidence that three segments sent
after it were received (see Examples 1 and 2).

The draft recommends dupacks to be reset upon receiving a full ACK.
Example 3 shows how resetting dupacks prevents a useful retransmision to
happen. In addition, Example 3 shows how information useful for segment
retransmission is preserved upon exiting fast recovery if dupacks
is updated as I propose.

I've checked the tcp-impl archive and didn't find any discussion on
this issue. If this has already been discussed in the WG, please let
me know.

Looking forward to your comments.
Regards,
Marcel

The partial ACK case is described first, followed by the full ACK
case. I'll assume that ACK messages are never lost. Lost ACKs will
only make the proposed scheme more conservative...

A. The partial ACKs case:
From draft-ietf-tcpimpl-newreno, February 1999, page 4, step 5:

       If this ACK does *not* acknowledge all of the data up to and
       including "recover", then this is a partial ACK.  In this case,
       retransmit the first unacknowledged segment.  Deflate the
       congestion window by the amount of new data acknowledged, then
       add back one MSS and send a new segment if permitted by the new
       value of cwnd.  This "partial window deflation" attempts to
       ensure that, when Fast Recovery eventually ends, approximately
       ssthresh amount of data will be outstanding in the network.

       >> Do not clear the counter recording the number of duplicate
       acknowledgements (i.e., do not exit the Fast Recovery procedure).<<

Should we understand that dupacks should not be changed upon receiving
a partial ACK?  If this is the case, the next example shows a situation
in which the draft recommends retransmitting a segment too early.

Example 1.
Consider the following sequence of eight segments, with an initial
congestion window (cwnd) of 8.  The 1st and the 7th segment in the
sequence are lost:
[1] 2 3 4 5 6 [7] 8    ([ ] =  lost segments)

After sending segments 1-8, the source receives three duplicate acks,
and it retransmits segment 1. Immediately before receiving the partial
ACK, which acknowledges segment 6, cwnd is 10 = 4 (initial cwnd = 8/2) +
6 (duplicate ACKs generated by segments 2-6, 8).

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?

Since only two segments sent after 7 (segment 8 and the retransmission
of 1) were acked by the destination, it is probably too early to
retransmit segment 7.

I believe that, upon receiving a partial ACK, the sender should
decrement dupacks by the number of segments acknowledged minus one.
In this example, the resulting dupacks is 1. 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.
Either way, I don't think that segment 7 shouldn't be retransmitted
at this time.

According to the draft, upon receiving the partial ack, cwnd is
deflated by 6 (the amount of data acknowledged) and inflated by 1. The
new congestion window is 5 (10 - 6 + 1). Based on the new value of
cwnd, the source will sends three new segments. It is probably closer
to the spirit of the "Fast Retransmit" algorithm to retransmit segment
7 only after (if ever) two acks (or one ack if we count the retransmission
of 1) for segment 6 are received. Alternatively, if an ACK for segments
7, 8, 9, or 10 is received before dupacks becomes 3, the proposed rule
for updating dupacks eliminates an unnecessary retransmission.

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

Example 2.
Consider an initial cwnd of 10, message 1 and 7 are lost, messages
2-6, 8-10 are received. If dupacks is decremented upon receiving a partial
ack (for segment 6), then dupacks is updated to 8 - 5 = 3. You can think
of the new value of dupacks as representing the three duplicate ACKs
generated by the receipt of segments 8, 9, and 10. As the new value
of dupacks is >= 3, segment 7 is retransmitted immediately.

B. The full ACK case:
From draft-ietf-tcpimpl-newreno, February 1999, page 4, step 5:

       If this ACK acknowledges all of the data up to and including
       "recover", then the ACK acknowledges all the intermediate
       segments sent between the original transmission of the lost
       segment and the receipt of the third duplicate ACK.  Set cwnd to
       either (1) min (ssthresh, FlightSize + MSS); or (2) ssthresh,
       where ssthresh is the value set in step 1; this is termed
       "deflating" the window.  (We note that "FlightSize" in step 1
       referred to the amount of data outstanding in step 1, when Fast
       Recovery was entered, while "FlightSize" in step 5 refers to the
       amount of data outstanding in step 5, when Fast Recovery is
       exited.) If the second option is selected, the implementation
       should take measures to avoid a possible burst of data, in case
       the amount of data outstanding in the network was much less than
       the new congestion window allows [HTH98].  >> Clear the counter
       recording the number of duplicate acknowledgements, exiting the
       Fast Recovery procedure. <<

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)

The sender receives two additional ACKs for segment 6 (dupacks == 4),
retransmits 7, and gets an ACK for segment 9. As recover is 9, this last
ACK is a full ACK.

According to the draft, upon receiving a full ACK, the source sets
dupacks to zero. In addition, the source sets cwnd to ssthresh (= 4)
and it sends a new data segment, 13. The receipt of segment 13 generates
a second ACK for segment 9 and dupacks is incremented from 0 to 1.

Clearing dupacks erases all the information the source has recorded
on segments 10, 11, and 12. Ideally, dupacks should be reset to 2
in order to count for segments 11 and 12.

If we apply the proposed rule for updating dupacks and decrement it
by the number of segments acknowledged minus one, the resulting value
is 2 (= 4 - 2).  After the second ACK for 9 is received (the ACK generated
by segment 13), segment 10 can be retransmitted.

Please correct me if I am wrong.

---

From: "Chadi M. BARAKAT" <[email-masked]>
Date: Mon, 15 Mar 1999 11:01:11 +0100

Hello,

The idea with the three duplicate ACKs of the fast retransmit algorithm
is to eliminate any possibility for packet reordering. It is supposed
that the receipt of three packets after the missing one is a good signal
of the loss of this packet. So it is retransmitted without waiting for a
timeout. Now, in New Reno, the first loss in a window required three
duplicate ACKs, but once a partial ACK is received, the source can
conclude directly that this packet is lost and it doesn't need the wait
for any additional dup ACK, for this reason it doesn't change its dup
ACKs counter. Why? because a partial ACK is sent most probably in
response to the retransmission of the previous loss in the same window,
so at least one Roundtrip time has passed since the first transmission
of the missing packet. This roundtrip is enough to take a decision that
the packet is lost. You can consider that the three dup ACKs counted at
the begining of Fast Recovery is used by the source to fast retransmit
any further loss in the same window.

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. 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. 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: Mon, 15 Mar 1999 11:51:14 -0800 (PST)

> because at least one Roundtrip time has passed since its transmission.

Should cwnd be adjusted for this kind of ack?  Should new segments be sent
during this "extension" period?  If yes, should the fast retransmit phase
keep on extending?  As I menioned in a previous mail, NewReno treats this
kind of drops as another congestion event.  And depending on the number of
segments in flight, another fast retransmit can be triggered to recover
this kind of drops.  I think you need to clarify your suggestion in the
context of idea 1, as stated in my previous mail, of NewReno.

							K. Poon.
							[email-masked]