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

From: Mark Allman <[email-masked]>
Date: Thu, 03 Mar 2011 10:09:23 -0500

Folks-

> I've been thinking about the issue Richard brought up and I think it's
> valid and worth for discussion.  I personally think this is a minor
> issue in RFC3517. (also in RFC3517bis)

As part of thinking about 3517bis I came back to this yesterday and
asked Ethan about it again.  Per his suggestion from a while back, and
since nobody else seems to have done so, we puzzled through this for a
bit and played around with various scenarios.  Again illustrating how
subtle this stuff is we (really Ethan) have identified an issue.  I am
leaving your email appended below because its a nice summary to remind
folks.

The problematic scenario involves reordering, not loss.  If you play out
a scenario where packets 1--10 are transmitted in order, but arrive at
the receiver as "2, 3, 4, 1, 5, 6, 7, 8, 9, 10" and there is no data
beyond 10 available.  Packet 1 will be retransmitted needlessly because
of the reordering (in 3517, 3517bis and Richard's proposal).  However,
in the proposal below that removes condition (1.b) from step (3) in
NextSeg() the TCP will also needlessly retransmit packets 7--10 whereas
3517 and 3517bis will not.  Basically, with the proposed change it looks
like this from the sender's perspective:

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 7, pipe = 5
rcv ack=8 (via pkt 7), pipe = 3
rexmt 8, pipe = 4
rexmt 9, pipe = 5
rcv ack=9 (via pkt 8), pipe = 2
rexmt 10, pipe = 3

Instead of 1 needless retransmit we end up with half the window
needlessly retransmitted.  (This holds I believe no matter how big the
window gets if the first packet is delayed to the 4th position.
Different amounts of delay will clearly result in different scenarios.) 

Of course, we have cut the sending rate (needlessly) and so in some
sense this is conservative in terms of the *amount* of traffic being
dumped into the network.  However, in terms of *useful* traffic it is
clearly suboptimal.  

So, there is a tradeoff here.  In order to make loss recovery from the
tail of a window (when there is no further data to send) more timely we
aggravate the impact of reordering.

(Note: This might not be the only issue.  This is the first one we
tripped over.)

allman

> Let's say, we have a pair of SACK TCP sender and receiver and when
> cwnd=5, sender transmits S1, S2, S3 .. S5 packets.
> Now, if we lost S1, S5, segments here, we will see the following sequence.
> 
> 1: When S2 S3 S4 arrives at the receiver side, the receiver sends back
> dupacks with SACK info to the sender.
> 2: When the sender receives the 3rd dupack, it retransmits S1 and
> enters loss recovery phase.
> 3: When S1 arrives at the receiver side, the receiver sends back a
> cumulative ACK for S4.
> 4: When the ACK for S4 arrives, the sender process this ACK by the
> following steps
>     4.1: It's not greater than RecoveryPoint, so TCP cannot exit loss
> recovery phase yet.
>     4.2: Use update() and setpipe() and find it has only 1 outstanding segment.
>     4.3: Since cwnd - pipe >= 1MSS, tcp tries to send one or more segments.
>     4.4: Use NextSeg() to find the packet to be sent
> 
> Here, I think there is one minor issue in NextSeg().
> When TCP checks if S5 can be sent with the rule (1) in NextSeg(), it
> fails. ( because (1.b) and (1.c) return false.)
> Rule (2) can be applicable "if there are available unsent data". But,
> let's think about the case where there's no available unsent data.
> Now, TCP is going to apply Rule (3) for S5, but again it fails (
> because (1.b) returns false. )
> Here, TCP cannot send any packets even though there is a chance to
> send a retransmit packet.
> 
> To summarize, I think the logic in RFC3517 can stall in some
> situations even though there are packets can be sent.
> This might cause the lost of ack clocking and unnecessary timeouts.
> 
> I think the solution would be simple. Don't apply (1.b) to the Rule
> (3) in NextSeg().
> I mean, change Rule (3) in NextSeg() from
> 
>           If the conditions for rules (1) and (2) fail, but there exists
>           an unSACKed sequence number 'S3' that meets the criteria for
>           detecting loss given in steps (1.a) and (1.b) above
>           (specifically excluding step (1.c)) then one segment of up to
>           SMSS octets starting with S3 MAY be returned.
> 
> To
> 
>           If the conditions for rules (1) and (2) fail, but there exists
>           an unSACKed sequence number 'S3' that meets the criteria for
>           detecting loss given in steps (1.a)  above
>           (specifically excluding step (1.b) and step (1.c)) then one
> segment of up to
>           SMSS octets starting with S3 MAY be returned.
> 
> I might need more time to think about this, but I think removing (1.b)
> from (3) will not be very harmful.

---

From: Yoshifumi Nishida <[email-masked]>
Date: Thu, 3 Mar 2011 22:22:11 -0800

Hello Mark, Thanks for your response.

The point you mentioned is exactly what I wanted to discuss.
I have thought several similar scenarios and here's my opinion on that.

  1: As Richard already pointed out, this redundant transmission
happens even in NewReno,
      since NewReno retransmits the first unacknowledged segment when
it receives a partial ACK.

      So, It's just as bad as NewReno but not worse than NewReno,
which might be mostly acceptable.

  2: If the problem is the amount of unnecessary transmission, we have
several ways to mitigate this.
      2a) I believe we can presume the use of delayed ACK in most cases.
            So, in your example, the amount of unnecessary
transmission will be 1/4 of the window.
      2b) We might be able to presume the use of DSACK,
            Once the sender finds out spurious retransmission, it can
stop unnecessary transmission immediately.
      2c)  I believe it's possible to implement a certain simple logic
to reduce the amount of unnecessary transmission.
            For example, I think we can apply this special rule every
other time by having one flag in NextSeg().

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: "Ilpo Järvinen" <[email-masked]>
Date: Fri, 4 Mar 2011 11:51:04 +0200 (EET)

> transmission will be 1/4 of the window.

True.

> stop unnecessary transmission immediately.

That will be only after all of the unnecessary retransmissions were made 
so it is of no use here.

> other time by having one flag in NextSeg().

I don't think your 2c) has any logical basis... this here is more or less 
just a tradeoff in a case where ambiguity exists. ...Instead the algorithm 
should try to break out from the ambiguities using something similar to 
FRTO xmit ordering (but that's hardly a thing that belongs to 3517bis 
now).

Yet, in theory, the delayed ACK double cumulatives could be used as a flag 
to distinguish between rexmit/original data generated ACKs: ~"If more than 
the retransmitted one was cumulatively ACKed, do nothing." ...But that 
depends on the receiver doing delayed ACKs.

-- 
 i.

---

From: Mark Allman <[email-masked]>
Date: Fri, 04 Mar 2011 08:17:12 -0500

> So, It's just as bad as NewReno but not worse than NewReno, which
> might be mostly acceptable.

I understand the sentiment.  But, lets be clear that both are
suboptimal. 

> transmission will be 1/4 of the window.

Actually that isn't true.  It probably is for NewReno, but RFC3517 tries
quite hard to work based on the amount of data SACKed and ACKed and
*not* the *number* of SACKs/ACKs that arrive.  So, you can play through
my scenario with delayed ACKs and you'll see that a cumack for two
segments would open more room in the pipe than a cumack for one segment
and so you'd see the same number of needless retransmits.

Therefore, the claim of "just as bad as NewReno" is likely not right and
RFC3517 without (1.b) in rule (3) is something like twice as bad.

> stop unnecessary transmission immediately.

Look at my scenario.  By the time the DSACK gets to the sender it has
already strobed out all the unnecessary retransmits because the DSACK
comes in the next RTT.  This is the basic problem with DSACK.  You can
use it to figure out you have made a mistake after the fact, but you can
make a bunch more mistakes before you find out because of the RTT lag.

> to reduce the amount of unnecessary transmission.

I am certainly willing to believe that there is additional complexity
that could be added to address this case.  The first question is whether
the cost of the required complexity is worth the benefit it provides.
The second question is whether the complexity interferes with the rest
of the algorithm in ways that break it.

allman

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sat, 5 Mar 2011 12:43:10 -0000

[hopefully this arrives at the list too... also expanded over the private emails.]

Mark,

You and Ethan have clearly a point here.

Do you see a way to address this? Ie. If RecoveryPoint is 10 in your example, and loss of the last segment running up to the end of stream would require a RTO with SACK, while not so with NewReno.

In fact, NewReno would exhibit the same behavior (unnecessary retransmitting up to 1/2 window on a reorder event > DupThresh).

Thinking about the cost (latency of in-order delivered data on the receiver side) of the RTO vs the cost of possibly retransmitting data unnecessary (while reducing cwnd shortly before end of stream), I believe the latter is less hard to the network, while the first can have a more problematic impact on the timeliness of your application (typically, the RTO is >> RTT)...

(I think I have mentioned that some vendors appear to prefer NewReno over SACK for latency sensitive applications/environments. Insofar they appear to have choosen the lesser of the two bads for their enironments.)

OTOH, a more optimal approach could be to identify if the partial Ack 5 was due to the retransmitted segment 1, or the original segment 1 - for example by using timestamp information (akin to eifel detection). Depending on the result, a partial Ack due to a delayed segment 1 could be identified and addressed (similar to eifel response)....

Would that be a workable solution for that scenario?

Of course, TCP stacks that want to use the improved end-of-stream behavior may only be allowed to do so, if the session has negotiated for SACK+TS...

In any case, at the very least, 3517bis should document this corner case, albeit I would still think that SACK should not be less timely under any circumstances than NewReno. But I would agree, that a proper fix (as sketched above) is beyond the scope of 3517bis.

(Actually, synergy between SACK and TS would allow improvements in other areas as well).

Best regards,
   Richard

-----Original Message-----
From: Mark Allman [mailto:[email-masked]] 
Sent: Donnerstag, 03. März 2011 16:09
To: Yoshifumi Nishida
Cc: Scheffenegger, Richard; [email-masked]
Subject: Re: [tcpm] An issue in RFC3517? (Re: end-of-stream loss recovery (TCP SACK) ) 

Folks-

> issue in RFC3517. (also in RFC3517bis)

As part of thinking about 3517bis I came back to this yesterday and asked Ethan about it again.  Per his suggestion from a while back, and since nobody else seems to have done so, we puzzled through this for a bit and played around with various scenarios.  Again illustrating how subtle this stuff is we (really Ethan) have identified an issue.  I am leaving your email appended below because its a nice summary to remind folks.

The problematic scenario involves reordering, not loss.  If you play out a scenario where packets 1--10 are transmitted in order, but arrive at the receiver as "2, 3, 4, 1, 5, 6, 7, 8, 9, 10" and there is no data beyond 10 available.  Packet 1 will be retransmitted needlessly because of the reordering (in 3517, 3517bis and Richard's proposal).  However, in the proposal below that removes condition (1.b) from step (3) in
NextSeg() the TCP will also needlessly retransmit packets 7--10 whereas
3517 and 3517bis will not.  Basically, with the proposed change it looks like this from the sender's perspective:

snd 1--10, cwnd = 10

Instead of 1 needless retransmit we end up with half the window needlessly retransmitted.  (This holds I believe no matter how big the window gets if the first packet is delayed to the 4th position.
Different amounts of delay will clearly result in different scenarios.) 

Of course, we have cut the sending rate (needlessly) and so in some sense this is conservative in terms of the *amount* of traffic being dumped into the network.  However, in terms of *useful* traffic it is clearly suboptimal.  

So, there is a tradeoff here.  In order to make loss recovery from the tail of a window (when there is no further data to send) more timely we aggravate the impact of reordering.

(Note: This might not be the only issue.  This is the first one we tripped over.)

allman

> fails. ( because (1.b) and (1.c) return false.) Rule (2) can be 
> applicable "if there are available unsent data". But, let's think 
> about the case where there's no available unsent data.
> because (1.b) returns false. ) Here, TCP cannot send any packets even 
> though there is a chance to send a retransmit packet.
>

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 4 Mar 2011 07:43:05 -0000

Mark,

You and ethan have clearly a point here.

Do you see a way to address this? Ie. If recoverypoint is 10 in your example, and loss of the last segement running up to the end of stream would require a rto with sack, while not so with newreno.

In fact, newreno would exhibit the same behaviour (unnecessary retransmitting up to 1/2 window on a reorder event > dupthresh).

Thinking about the cost (latency of in-order delivered data on the rx side) of the rton vs the cost of possibly retransmitting data unnecessary (and reducing cwnd shortly before end of stream unnecessary), I beliefe the latter is less hard to the network...

(I think I have mentioned that some vendors appear to prefer newreno over sack for latency sensitive applications/environments. Insofar they appear to have choosen the lesser of the two bads for their environments.)

Otoh, a more optimal approach could be to identify if the cumulative ack 5 was due to the retransmitted seg 1, or the original seg 1 - I.e. By using timestamp information. Depending on the result, a cumack due to delayed seg1 could be identified and adressed (similar to eifel detection/response)....

Of course, tcp stacks that want to use the improved end-of-stream behavior may only be allowed to do so, if the session has negotiated for sack+ts...

(Actually, synergy between sack and ts would allow improvements in other areas as well).

Best regards,
   Richard

-----Original Message-----
From: Mark Allman [mailto:[email-masked]] 
Sent: Donnerstag, 03. März 2011 16:09
To: Yoshifumi Nishida
Cc: Scheffenegger, Richard; [email-masked]
Subject: Re: [tcpm] An issue in RFC3517? (Re: end-of-stream loss recovery (TCP SACK) ) 

Folks-

snd 1--10, cwnd = 10

allman

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 6 Mar 2011 19:25:40 -0800

Hello Mark,

Thanks for your insightful comments.
The points you mentioned are quite right and thanks for pointing out
my misunderstanding.
I also agree with you that there'll be additional complexity to
address this issue,
but I still personally think there might be a certain good balance
between efficiency and complexity.
I'll need to think about it more carefully and hopefully get back soon.

I really appreciate Ethan and you spending some time to check this.
Thank you so much.
--
Yoshifumi Nishida
[email-masked]