Subject: Re: [tcpm] An issue in RFC3517? (Re: end-of-stream loss recovery (TCP SACK) )

From: Yoshifumi Nishida <[email-masked]>
Date: Fri, 15 Apr 2011 03:22:39 -0700

Dear folks,

I've submitted an I-D as a solution for the issue we discussed about a
month ago.
The proposed logic in the doc allows TCP to retransmit one segment per RTT
where all available data TCP has is unSACKed and not sure if it is lost.

Below is the information of the draft.
--------------------------------
Filename:        draft-nishida-tcpm-rescue-retransmission
Revision:        00
Title:           Rescue Retransmission for SACK-based Loss Recovery Algorithm
Creation_date:   2011-04-15
WG ID:           Independent Submission
Number_of_pages: 14

Abstract:
This memo describes an issue in the recovery algorithm in RFC3517 and
proposes a simple modification to avoid unnecessary timeouts for
performance improvement.
-------------------

Since it sends just one segment per RTT, I think the amount of
spurious retransmissions
will be small. Also, I believe the logic is not so complicated while it will be
useful to avoid tcp's stalling. The little trick in this logic is
sending the highest unsacked
segment and expect that the next ACK will convey some useful information.

It would be great If you could give some comments on this draft.
If I'm misunderstanding something, please let me know.

The proposed logic will work something likes this.

case: packets 1--10 are transmitted in order, but arrive at the
receiver as "2, 3, 4, 1, 5, 6, 7, 8, 9, 10

snd 1--10, cwnd = 10
rcv ack=1, sack={2-2} (via pkt 2)
rcv ack=1, sack={2-3} (via pkt 3)
rcv ack=1, sack={2-4} (via pkt 4)
rexmt 1, cwnd = 5, pipe = 7
rcv ack=5 (via pkt 1-orig), pipe = 6
rcv ack=6 (via pkt 5), pipe = 5
rcv ack=7 (via pkt 6), pipe = 4
rexmt 10, pipe = 5
rcv ack=8 (via pkt 7), pipe = 3
rcv ack=9 (via pkt 8), pipe = 2

case: packet 1,2,3,4,5,6 are transmitted in order.  1,5 6 are lost.

rcv ack=1, sack={2-2} (via pkt 2)
rcv ack=1, sack={2-3} (via pkt 3)
rcv ack=1, sack={2-4} (via pkt 4)
rexmt 1, cwnd = 3, pipe = 3
rcv ack=5 (via pkt 1), pipe = 2
rexmt 6, pipe = 1
rcv ack=5 sack={6-6} (via pkt 6) pipe = 2
rexmt 5, pipe = 1

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: Mark Allman <[email-masked]>
Date: Mon, 18 Apr 2011 13:50:32 -0400

> Filename:        draft-nishida-tcpm-rescue-retransmission

First, I must say its a nicely clever trick, Yoshifumi.  The neat
observation is that by sending one segment per loss event you can
encourage the information needed to let the standard 3517 algorithm fix
end-of-window loss.

The basic idea here is that when you're stuck and cannot send anything
according to RFC3517 (and the bis) the algorithm is extended to allow
sending the last unSACKed packet again.  This, in turn, triggers an ACK
with new SACK information that can further prod the loss recovery
process.  (Details are in Yoshifumi's draft).

Second, the proposed fix isn't quite right, IMO.  Consider the case of
sending 6 segments (cwnd=6), losing only segment #1 and having no
further data to send.  So, this is what arrives at and is sent by the
data sender:

    1.  ACK 1, SACK 2:2
        [do nothing]
    2.  ACK 1, SACK 2:3
        [do nothing]
    3.  ACK 1, SACK 2:4
        --> cwnd = FlightSize / 2 = 3, pipe = 2 (segs 5 & 6)
        --> retransmit segment 1, pipe = 3 (segs 1(rxt), 5 & 6)
    4.  ACK 1, SACK 2:5
        --> pipe = 2 (segs 1(rxt) & 6)
        --> we have no data judged as having been lost ((1) in
            NextSeg())
        --> we have no new data to send ((2) in NextSeg())
        --> we have no "last resort" data to send ((3) in NextSeg()),
            i.e., unSACKed data not judged as lost, but with SACKed data
            above it)
        --> so, we invoke the proposed (4) in NextSeg() and transmit the
            segment at the end of the window, or segment 6
    5.  ACK 1, SACK 2:6
    6.  ACK 7
    7.  ACK 7, (DSACK 6, if supported)

In this case we just don't wait long enough to re-send this rescue
packet (step 4 above) and so we really have no idea if the end of the
window has been lost or not (and, in the above example it has not and so
the retransmit is spurious).  In step 4 above we cannot possibly have
gained an understanding about the end of the window.
   
Third, this failure mode is readily fixed by forcing the rescue
retransmit to happen an RTT after loss recovery has started (i.e., to
ensure all ACKs for the window of data that experienced loss roll in
first).  This is easy enough.  When loss recovery is initiated we set
RescueRxt to the highest octet of the first retransmission.  Now, rule
(4) in NextSeg()

  (4) If the conditions for rules (1), (2) and (3) fail, but there
      exists outstanding and unSACKed data we provide the opportunity
      for a single "rescue" retransmission.  If HighACK is greater than
      RescueRxt then one segment of up to SMSS octets that includes the
      highest outstanding unSACKed sequence number SHOULD be returned.
      Further, RescueRxt MUST be set to RecoveryPoint.  Finally,
      HighRxt MUST NOT be updated.

I.e., before we can send a rescue segment the first segment
retransmitted must be ACKed (ensuring an RTT has passed).  

Finally, contrary to my usual mantra of keeping 3517bis clean and only
including well-understood things and not gooping it up, I think this
change [including the fix above] may well be OK.  I think that for
several reasons:

  (1) The change does not alter any of the *actions* or algorithms of
      RFC3517.  Rather, the change turns a current inaction into an
      action.  Therefore, the implications are easier to understand.

  (2) RFC3517 strives to fix all loss within an RTT of loss detection.
      Therefore, by pushing this rescue transmission to at least an RTT
      after the guts of the algorithm has been completed we are reducing
      the possible interactions and badness.

  (3) The scope of the proposed change is quite small.  The change
      allows for **one** additional packet transmission **per loss
      event**.  This packet is meant to then coax us into a regime where
      the already understood parts of RFC3517 take over and fix things
      up.  So, even if we needlessly retransmit this rescue packet its
      just one packet per event and at that rate cannot likely cause any
      damage to the network, competing traffic or the connection
      itself.  And, if it is spurious it isn't going to add any
      information to change the behavior of the algorithm that won't
      come along anyway.

So, I'm all for rolling this nifty little tweak in.

allman

---

From: Ethan Blanton <[email-masked]>
Date: Mon, 18 Apr 2011 15:58:46 -0400

>       information to change the behavior of the algorithm that won't

Let me add to this, per some discussion with mallman.

Not only is this one packet per loss event, this is one packet where
if we *could* have sent something different, we *would* have -- so
it's no more "aggressive" in that sense than 3517.

I do wish to note that some patterns of reordering with moderate cwnd
sizes (a cwnd of at least 8 segments is required) will trigger this
rescue retransmission reliably.  However, as mentioned above, only in
cases where 3517 would allow the sender to send a segment anyway, and
bounded to a single retransmission per loss event.  Steps (1) and (3)
of NextSeg can be coaxed into spuriously retransmitting more than one
segment in the face of reordering, under the right conditions, so I
don't think this is a big deal.

> So, I'm all for rolling this nifty little tweak in.

I want to think about this a little more before I make that
declaration.  However, I *do* like this.  It is clever and minimal,
and the implications of "messing up" are well-defined and limited (to
a constant one segment, even!).  I simply want to make sure we're not
overlooking anything before I give it my blessing (whatever that is
worth).

Ethan

---

From: Yoshifumi Nishida <[email-masked]>
Date: Mon, 18 Apr 2011 22:18:28 -0700

Hello Mark,

Thanks for the comments.
The algorithm you presented is smarter than I wrote in the draft.
you're right that my logic has a bug and it's fixed in your algorithm,
so I totally agree with this.
Since whole intention in my draft is already covered by your comments,
I don't have
any more things to add.

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: Yuchung Cheng <[email-masked]>
Date: Mon, 18 Apr 2011 22:31:14 -0700

I also think the idea + Mark's change are really neat.

One nit: since rescue-retransmit does not update HighRxt, the HighRxt
definition may need some update or clarification.

On Mon, Apr 18, 2011 at 10:18 PM, Yoshifumi Nishida
<[email-masked]>wrote:

> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 19 Apr 2011 12:21:05 +0100

Yoshifumi, Mark,

I really like that idea about only sending the very last segment anew very much! 

As Mark and Yuchung pointed out, my original idea about the partial ACK would clock out the *suspected* (but unproven) lost data segement only at 1 per RTT, while this new proposal is even better suited (when 3 or more consecutive segments are lost, a few RTTs are saved on recovery as the full RFC3517 algorithm, including pipe, comes into play!).

I'm glad to have sparked this discussion about end-of-stream loss recovery!

Richard Scheffenegger

> -----Original Message-----
> From: Yoshifumi Nishida [mailto:[email-masked]]
> Sent: Dienstag, 19. April 2011 07:18
> To: [email-masked]
> Cc: [email-masked]"
> Subject: Re: [tcpm] An issue in RFC3517? (Re: end-of-stream loss
> recovery (TCP SACK) )
> 
> Hello Mark,
> 
> Thanks for the comments.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sat, 30 Apr 2011 10:11:03 +0100

Hi,

I have been thinking about this a little bit more.

There may be one peculiar corner case with the new Rule 4; I believe it's probably out-of-scope for 3517bis, but would like to point it out nevertheless.

>       HighRxt MUST NOT be updated.

The issue revolves around the observation, that with tail-drop there are often periods of burst loss (a number of consecutive packets of a session get lost). During a good fraction of these events, a number of retransmitted packets are still encountering the network condition that led to the loss, and are lost too... The very first retransmitted packet (which would change HighAck) is particularly vulnerable to encounter such a condition, unfortunately. The senders sharing the bottleneck may have not yet reacted to reduce their sending rate enough, when the sender(s) with the lowest RTT is staring the retransmission.

Given the following events (segments sent/lost),

S0 XX S2 S3 S4 XX S6 XX XX |(end of stream)
   XX          S5 

Rule 4 would not trigger even when another retransmitted segment (S5) was successfully received (and S1, S7, S8 would require a RTO to recover).

Anyway, lost retransmissions themselves are out-of-scope for 3517 (and at the root of this corner case is a lost retransmission). So I don't think addressing this particular instance has to be done there. However, if someone implements the Rule 4 above in a stack that does lost-retransmission recovery (ie. Linux), the statement "HighACK is greater than RescueRxt" may need to be expanded to include SACKed octets. For example, if a newly arrived ACK SACKs bytes below FACK, but doesn't advance FACK (some hole closes at least partially in the senders SACK datastructure), that could also be a valid trigger for Rule 4. Just using SACK information alone, such a heuristic would still be prone to be triggered by delayed original segments as well as true retransmissions. But the case has been made, that a single retransmission (of S8 in the above example) would be acceptable...

Richard Scheffenegger

> From: Mark Allman [mailto:[email-masked]]
> Sent: Montag, 18. April 2011 19:51
> To: Yoshifumi Nishida
> Cc: [email-masked]"
> window has been lost or not (and, in the above example it has not and
> so the retransmit is spurious).  In step 4 above we cannot possibly
> have gained an understanding about the end of the window.
>

---

From: Mark Allman <[email-masked]>
Date: Sat, 30 Apr 2011 22:10:21 -0400

> Anyway, lost retransmissions themselves are out-of-scope for 3517

Exactly.

> (and at the root of this corner case is a lost retransmission). So I
> don't think addressing this particular instance has to be done
> there. However, if someone implements the Rule 4 above in a stack that
> does lost-retransmission recovery (ie. Linux), the statement "HighACK
> is greater than RescueRxt" may need to be expanded to include SACKed
> octets. For example, if a newly arrived ACK SACKs bytes below FACK,
> but doesn't advance FACK (some hole closes at least partially in the
> senders SACK datastructure), that could also be a valid trigger for
> Rule 4. Just using SACK information alone, such a heuristic would
> still be prone to be triggered by delayed original segments as well as
> true retransmissions. But the case has been made, that a single
> retransmission (of S8 in the above example) would be acceptable... 

Yes, if you do something different then you'll have to do something else
different, too.

allman