Subject: [tcpm] missequenced TCP segments

From: "Sommars, Steven E (Steven)" <[email-masked]>
Date: Wed, 6 Oct 2010 10:07:19 -0500

Vern Paxson suggested this forum for discussing an RFC793 ambiguity.

RFC793 section 3.4 says:
    Reset Generation
    ...
    3.  If the connection is in a synchronized state (ESTABLISHED,
    FIN-WAIT-1, FIN-WAIT-2, CLOSE-WAIT, CLOSING, LAST-ACK, TIME-WAIT),
    any unacceptable segment (out of window sequence number or
    unacceptible acknowledgment number) must elicit only an empty
    acknowledgment segment containing the current send-sequence number
    and an acknowledgment indicating the next sequence number expected
    to be received, and the connection remains in the same state.

The problem comes with a bidirectional TCP flow (both directions carrying payload) in the presence of IP missequencing. 

Sender transmits
	Seq 1, Ack 15
	Seq 2, Ack 16
	Seq 3, Ack 17
	Seq 4, Ack 18
Due to packet reordering receiver sees
	Seq 4, Ack 18
	Seq 1, Ack 15  << Ack out of window
	Seq 3, Ack 17  << Ack out of window
	Seq 2, Ack 16  << Ack out of window

The cited RFC793 section suggests that when the Acks are out of window the accompanying data segment should not be processed.   That strategy can lead to undesirable TCP stalls. 

I cannot find a clarification in other RFCs.   Is an erratum appropriate?

---

From: Stefanos Harhalakis <[email-masked]>
Date: Wed, 6 Oct 2010 18:33:18 +0300

Hello,

>     to be received, and the connection remains in the same state.

[...]

> The cited RFC793 section suggests that when the Acks are out of window the
> accompanying data segment should not be processed.   That strategy can
> lead to undesirable TCP stalls.

While I'm not an expert, from what I understand, as you quoted, RFC states 
"unacceptable acknowledgment number" and not "out of window". It also states 
that "the connection remains in the same state" and not that it rejects the 
data. Both of those statements are valid if you just accept the data. In fact, 
assuming that all ACKs with  ACK# >= last_ack-2^31 are valid/acceptable, 
should be OK.

---

From: David Borman <[email-masked]>
Date: Wed, 6 Oct 2010 11:33:47 -0500

> The cited RFC793 section suggests that when the Acks are out of window the accompanying data segment should not be processed.   That strategy can lead to undesirable TCP stalls.

It says unacceptable ACKs, not out of window ACKs.  On page 72:
          If SND.UNA < SEG.ACK =< SND.NXT then, set SND.UNA <- SEG.ACK.
          Any segments on the retransmission queue which are thereby
          entirely acknowledged are removed.  Users should receive
          positive acknowledgments for buffers which have been SENT and
          fully acknowledged (i.e., SEND buffer should be returned with
          "ok" response).  If the ACK is a duplicate
          (SEG.ACK < SND.UNA), it can be ignored.  If the ACK acks
          something not yet sent (SEG.ACK > SND.NXT) then send an ACK,
          drop the segment, and return.
I.e., duplicate ACKs are acceptable.  The only thing that is unacceptable is an ACK for data that hasn't been sent.

I'll also take this opportunity to mention that if an out-of-order packet arrives, either due to a gap or duplicate data, the ACK field should be processed anyway.  On bi-directional connections, failure to process the ACK field in a packet that is purely duplicate data can lead to ACK wars on the connection, e.g. in crossing zero window probes.

			-David Borman

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

---

From: Alexander Zimmermann <[email-masked]>
Date: Wed, 06 Oct 2010 18:57:52 +0200

Hi David,

> I.e., duplicate ACKs are acceptable.  The only thing that is unacceptable is an ACK for data that hasn't been sent.

Hmm... IMO an DUPACK is not an acceptable ACK.
An acceptable ACK is an ACK, which acks perviously unacknowledged data.
I like the term "valid" here...

>> I cannot find a clarification in other RFCs.   Is an erratum appropriate?

//
// Dipl.-Inform. Alexander Zimmermann
// Department of Computer Science, Informatik 4
// RWTH Aachen University
// Ahornstr. 55, 52056 Aachen, Germany
// phone: (49-241) 80-21422, fax: (49-241) 80-22222
// email: [email-masked]
// web: http://www.umic-mesh.net
//

---

From: David Borman <[email-masked]>
Date: Wed, 6 Oct 2010 13:06:08 -0500

> I like the term "valid" here...

Ok, if you are going to wordsmith, look at it this way: an acceptable ACK is one that the TCP state machine knows how to properly process, and that includes duplicate ACKs.  It is only ACKs for data that hasn't been sent that TCP can't deal with, since that situation shouldn't occur, hence those are the unacceptable ACKs, the ones that cause the packet to be dropped, an ACK to be sent back to the other side, and the state of the connection is left unchanged.

Certainly you aren't arguing that it is unacceptable to receive duplicate ACKs. :-)

			-David Borman

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 8 Oct 2010 15:36:59 +0100

Hello members of the TCPM group, Matt, Mark,

I'm currently looking into the loss recovery behavior of TCP SACK -
especially at the end-of-stream.

End-of-stream (case 2) of the small congestion window, as per RFC5827)
is of particular interest, as there are synchronous IO loads over TCP,
that will only deliver additional data to the socket once an application
level acknowledgement has been received. To be precise, single threaded,
synchronous NFS read/write IOs. However that application layer Ack will
only be sent by the receiver, once the complete App IO was received,
thus any stalls can tremendeously delay the IO on the application. 

The analogy would be TCP (with a large MTU) within TCP (with a small
MTU) - which is known to behave sub-optimal.

It appears that RFC2018 has codified behavior, which makes TCP SACK
perform less optimal compared with TCP NewReno, when loss occurs
directly at the last segments of the stream.

"
5. Interpreting the Sack Option and Retransmission Strategy: Data
   Sender Behavior
:
:
   After the SACKed bit is turned on (as the result of processing a
   received SACK option), the data sender will skip that segment during
   any later retransmission.  Any segment that has the SACKed bit turned
   off and is less than the highest SACKed segment is available for
   retransmission.
"

This definition leaves out the range [snd_fack .. snd_nxt (at loss
recovery initiation time)]. There is no explanation as to why that
omission was done (other than snd_fack not being defined at the time). 

As RFC5827 is only concerned about detection and entering loss recovery,
it too gives no advice in this regard.

Consider a sequence of 4 Segments sent, S1 .. S4; S2 and S4 get dropped.

Early Retransmit (RFC5827) will allow entering loss recovery. 

Depending on TCP SACK, or TCP NewReno, the behavior will be different:

NewReno will retransmit S2;
The ACK for S3 will trigger retransmission of S4 (and nobody got hurt)

SACK will retransmit S2;
The ACK for S3 will *not* trigger a retransmit of S4 (it falls outside
the boundary defined in RFC2018).
Only a RTO will recover S4, and the stream might continue (as
applications resume operation).

Of course, S4 could be any number of packets, just prior to the
end-of-stream. And the same sequence of events can happen without Early
Retransmit and large cwnds...

With infinite data to send, after SACK finished loss recovery - at the
highest SACKed (snd_fack) block - the sender would resume sending
starting from snd_nxt (and most likely in slow start). As soon as 3 new
segments would be received, this missing segment chain (snd_fack ..
Former snd_nxt) could be detected and recovered. Of course, counting
this as one additional congestion event (unlike what NewReno would do).

Or are SACK implementations which silently ignore the hole between
snd_fack and snd_nxt (when loss recovery is entered) broken?

I would like to learn what you think would be the proper behavior. From
my point of view, this appears to have been a simple oversight in
RFC2018, and changing the statement to 

"
5. Interpreting the Sack Option and Retransmission Strategy: Data
   Sender Behavior
:
:
   After the SACKed bit is turned on (as the result of processing a
   received SACK option), the data sender will skip that segment during
   any later retransmission.  Any segment that has the SACKed bit turned
   off and is less than the highest sent segment at the beginning of the

   SACK recovery episode is available for retransmission.
"

The fix would be simply add an implicit hole (or an implicit SACK block)
up to snd_nxt. If none of these tailing segments was lost, they will be
covered in an SACK eventually. That would happen before the sender could
retransmit those segments, as cwnd is also reduced thus limiting the
sending rate. 

Richard Scheffenegger

---

From: Yuchung Cheng <[email-masked]>
Date: Thu, 21 Oct 2010 18:13:42 -0700

> The ACK for S3 will trigger retransmission of S4 (and nobody got hurt)

NewReno will not retransmit S4 because the ACK elicited by S3 is a
DUP-ACK, not a partial ACK (Step 5 in RFC 2582).

W/o additional intelligence, I don't think it's a good idea to
retransmit S4 because the DUP-ACK sacking S4 often come right after
the ACK of S2.

Cheers,

Yuchung

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 22 Oct 2010 03:56:13 +0100

Yuchung,

> > Consider a sequence of 4 Segments sent, S1 .. S4; S2 and S4 

sorry for the appreviated example.

A more complete example would have been S1..S6 with S2 and S6 getting lost, and a window of >=6 when recovery is triggered, to avoid any confusion.

> NewReno will not retransmit S4 because the ACK elicited by S3 
> is a DUP-ACK, not a partial ACK (Step 5 in RFC 2582).

The initial S3 will cause a DUP-ACK (of S1)

> W/o additional intelligence, I don't think it's a good idea 
> to retransmit S4 because the DUP-ACK sacking S4 often come 
> right after the ACK of S2.

The retransmission of S2 will cause a Full Ack of S3, that will trigger the retransmission of S4 (with NewReno). There won't be any ACK for S2; only S1;S1;S3 (and eventually S4).

Let me paste two traces, both between the same hosts, same network, same drop pattern (93001 (newreno)/95001(sack) and 99001 are dropped at first transmit). Only difference is NewReno vs. SACK. These were recorded on the receiver side, and timed such that the sender would end up in recovery mode until after the last segment of the stream. 

Note the time-delta when 99001 is retransmitted....

NewReno IS retransmitting the S4 in the original example, while SACK is not...

NewReno:
0.000009 A -> B TCP  93001 1    5888 48709 > 5001 [ACK] Seq=93001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736607 [drop]
0.000005 A -> B TCP  94001 1    5888 48709 > 5001 [ACK] Seq=94001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736607
0.000012 B -> A TCP  1 93001  990528 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=990528 Len=0 TSval=15736608 TSecr=375481555
0.000029 A -> B TCP  95001 1    5888 48709 > 5001 [ACK] Seq=95001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736607
0.000012 B -> A TCP  1 93001  990528 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=990528 Len=0 TSval=15736608 TSecr=375481555 [TCP Dup ACK 150#1]
0.000044 A -> B TCP  96001 1    5888 48709 > 5001 [ACK] Seq=96001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736607
0.000011 B -> A TCP  1 93001  990528 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=990528 Len=0 TSval=15736608 TSecr=375481555 [TCP Dup ACK 150#2] 
0.000078 A -> B TCP  97001 1    5888 48709 > 5001 [ACK] Seq=97001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736608
0.000012 B -> A TCP  1 93001  990528 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=990528 Len=0 TSval=15736608 TSecr=375481555 [TCP Dup ACK 150#3] 
0.000029 A -> B TCP  98001 1    5888 48709 > 5001 [ACK] Seq=98001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736608
0.000011 B -> A TCP  1 93001  990528 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=990528 Len=0 TSval=15736608 TSecr=375481555 [TCP Dup ACK 150#4] 
0.000029 A -> B TCP  99001 1    5888 48709 > 5001 [FIN, PSH, ACK] Seq=99001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736608 [drop]
0.000099 B -> A TCP  1 93001  998720 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=998720 Len=0 TSval=15736608 TSecr=375481555 [TCP Window Update]
0.000151 B -> A TCP  1 93001 1006912 5001 > 48709 [ACK] Seq=1 Ack=93001 Win=1006912 Len=0 TSval=15736608 TSecr=375481555 [TCP Window Update] 
0.000126 A -> B TCP  93001 1    5888 48709 > 5001 [ACK] Seq=93001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736608 [TCP Out-Of-Order]
0.000017 B -> A TCP  1 99001 1000960 5001 > 48709 [ACK] Seq=1 Ack=99001 Win=1000960 Len=0 TSval=15736609 TSecr=375481555
0.000116 B -> A TCP  1 99001 1009152 5001 > 48709 [ACK] Seq=1 Ack=99001 Win=1009152 Len=0 TSval=15736609 TSecr=375481555 [TCP Window Update]
0.000151 B -> A TCP  1 99001 1017344 5001 > 48709 [ACK] Seq=1 Ack=99001 Win=1017344 Len=0 TSval=15736609 TSecr=375481555 [TCP Window Update]
0.000119 A -> B TCP  99001 1    5888 48709 > 5001 [FIN, PSH, ACK] Seq=99001 Ack=1 Win=5888 Len=1000 TSval=375481555 TSecr=15736609 [TCP Out-Of-Order]
0.000016 B -> A TCP 1 100002 1016320 5001 > 48709 [ACK] Seq=1 Ack=100002 Win=1016320 Len=0 TSval=15736609 TSecr=375481555
0.000125 B -> A TCP 1 100002 1024512 5001 > 48709 [ACK] Seq=1 Ack=100002 Win=1024512 Len=0 TSval=15736609 TSecr=375481555 [TCP Window Update] 
0.000150 B -> A TCP 1 100002 1032704 5001 > 48709 [ACK] Seq=1 Ack=100002 Win=1032704 Len=0 TSval=15736609 TSecr=375481555 [TCP Window Update] 
0.000148 B -> A TCP 1 100002 1040896 5001 > 48709 [ACK] Seq=1 Ack=100002 Win=1040896 Len=0 TSval=15736609 TSecr=375481555 [TCP Window Update] 
0.000166 B -> A TCP 1 100002 1048960 5001 > 48709 [ACK] Seq=1 Ack=100002 Win=1048960 Len=0 TSval=15736610 TSecr=375481555 [TCP Window Update] 
0.000206 B -> A TCP 1 100002 1048960 5001 > 48709 [FIN, ACK] Seq=1 Ack=100002 Win=1048960 Len=0 TSval=15736610 TSecr=375481555
0.001338 A -> B TCP 100002 2    5888 48709 > 5001 [ACK] Seq=100002 Ack=2 Win=5888 Len=0 TSval=375481556 TSecr=15736610

SACK:

0.000006 A -> B TCP  95001 1    5888 60934 > 5001 [ACK] Seq=95001 Ack=1 Win=5888 Len=1000 TSval=367716224 TSecr=3613608261 [drop]
0.000006 A -> B TCP  96001 1    5888 60934 > 5001 [ACK] Seq=96001 Ack=1 Win=5888 Len=1000 TSval=367716224 TSecr=3613608261
0.000005 A -> B TCP  97001 1    5888 60934 > 5001 [ACK] Seq=97001 Ack=1 Win=5888 Len=1000 TSval=367716224 TSecr=3613608261
0.000006 A -> B TCP  98001 1    5888 60934 > 5001 [ACK] Seq=98001 Ack=1 Win=5888 Len=1000 TSval=367716224 TSecr=3613608261
0.000066 A -> B TCP  99001 1    5888 60934 > 5001 [FIN, PSH, ACK] Seq=99001 Ack=1 Win=5888 Len=1000 TSval=367716224 TSecr=3613608261 [drop]
0.003322 B -> A TCP  1 90001 1046976 5001 > 60934 [ACK] Seq=1 Ack=90001 Win=1046976 Len=0 TSval=3613608265 TSecr=367716224
0.000078 B -> A TCP  1 92001 1044992 5001 > 60934 [ACK] Seq=1 Ack=92001 Win=1044992 Len=0 TSval=3613608265 TSecr=367716224
0.000032 B -> A TCP  1 94001 1042944 5001 > 60934 [ACK] Seq=1 Ack=94001 Win=1042944 Len=0 TSval=3613608265 TSecr=367716224
0.000032 B -> A TCP  1 95001 1041984 5001 > 60934 [ACK] Seq=1 Ack=95001 Win=1041984 Len=0 TSval=3613608265 TSecr=367716224 SLE=96001 SRE=97001
0.000032 B -> A TCP  1 95001 1041984 5001 > 60934 [ACK] Seq=1 Ack=95001 Win=1041984 Len=0 TSval=3613608265 TSecr=367716224 SLE=96001 SRE=98001 [TCP Dup ACK 163#1] 
0.000032 B -> A TCP  1 95001 1041984 5001 > 60934 [ACK] Seq=1 Ack=95001 Win=1041984 Len=0 TSval=3613608265 TSecr=367716224 SLE=96001 SRE=99001 [TCP Dup ACK 163#2] 
0.000032 B -> A TCP  1 95001 1048960 5001 > 60934 [ACK] Seq=1 Ack=95001 Win=1048960 Len=0 TSval=3613608265 TSecr=367716224 SLE=96001 SRE=99001 [TCP Window Update] 
0.000434 A -> B TCP  95001 1    5888 60934 > 5001 [ACK] Seq=95001 Ack=1 Win=5888 Len=1000 TSval=367716225 TSecr=3613608265 [TCP Retransmission] 
0.003328 B -> A TCP  1 99001 1044992 5001 > 60934 [ACK] Seq=1 Ack=99001 Win=1044992 Len=0 TSval=3613608269 TSecr=367716225
0.000084 B -> A TCP  1 99001 1048960 5001 > 60934 [ACK] Seq=1 Ack=99001 Win=1048960 Len=0 TSval=3613608269 TSecr=367716225 [TCP Window Update] 
0.202595 A -> B TCP  99001 1    5888 60934 > 5001 [FIN, PSH, ACK] Seq=99001 Ack=1 Win=5888 Len=1000 TSval=367716277 TSecr=3613608269 [TCP Retransmission]
0.003322 B -> A TCP 1 100002 1048000 5001 > 60934 [ACK] Seq=1 Ack=100002 Win=1048000 Len=0 TSval=3613608475 TSecr=367716277
0.000078 B -> A TCP 1 100002 1048960 5001 > 60934 [FIN, ACK] Seq=1 Ack=100002 Win=1048960 Len=0 TSval=3613608475 TSecr=367716277
0.000473 A -> B TCP 100002 2    5888 60934 > 5001 [ACK] Seq=100002 Ack=2 Win=5888 Len=0 TSval=367716277 TSecr=3613608475

Richard Scheffenegger
Storage Infrastructure Architect
Area Deutsche Telekom 
NetApp
[email-masked]
+43 1 3676811 3146 Office (2143 3146 - internal)
+43 676 654 3146 Mobile
www.netapp.com 

EURO PLAZA
Gebäude G, Stiege 7, 3.OG
Am Euro Platz 2
A-1120 Wien

> -----Original Message-----
> From: Yuchung Cheng [mailto:[email-masked]] 
> Sent: Donnerstag, 21. Oktober 2010 21:14
> To: Scheffenegger, Richard
> Cc: [email-masked]; Matthew Mathis; [email-masked]
> Subject: Re: [tcpm] end-of-stream loss recovery (RFC2018 SACK errata?)
> 
> NewReno will not retransmit S4 because the ACK elicited by S3 
> is a DUP-ACK, not a partial ACK (Step 5 in RFC 2582).
> 
> W/o additional intelligence, I don't think it's a good idea 
> to retransmit S4 because the DUP-ACK sacking S4 often come 
> right after the ACK of S2.
> 
> Cheers,
> 
> Yuchung
>

---

From: Yoshifumi Nishida <[email-masked]>
Date: Fri, 22 Oct 2010 01:43:25 -0700

Hello Richard,

I think this discussion should be based on rfc3517 since it describes
a loss recovery algorithm for TCP SACK.

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 22 Oct 2010 19:25:41 +0100

Thank you Yoshifumi-san,

I agree; it's the combination of SACK signalling (as defined in
RFC2018), which segments are elegibe for SACK-based retransmission, and
RFC3517 (how to actually behave during SACK loss recovery).

Unfortunately, neiter of which covers the corner case of loosing the
last segment(s) of a stream [while already in loss recovery].

With NewReno, every FullAck below SND.MAX causes the retransmission of
one segment (after the ACK), before continuing with the next segment
after SND.MAX...

But my findings so far indicate, that such a FullACK (no SACK entries)
below SND.MAX doesn't trigger the retransmission of the next segment.

Obviously, with a continous stream of data, this is not a big issue, as
eventually you will have a SACK entry again, making the lost, previously
last, segment elegible for retransmission under RFC2018/3517.

Would there be any support by the group for an I-D, which addresses this
particular corner case? 

Richard Scheffenegger

> From: Yoshifumi Nishida [mailto:[email-masked]] 
> Sent: Freitag, 22. Oktober 2010 04:43
> Cc: [email-masked]
> I think this discussion should be based on rfc3517 since it 
> describes a loss recovery algorithm for TCP SACK.
> 
> Thanks,
> --
> Yoshifumi Nishida
> [email-masked]
>

---

From: Matt Mathis <[email-masked]>
Date: Fri, 22 Oct 2010 12:21:56 -0700

I think it would be better to try to get it into 3517bis, but if that
doesn't work, a separate ID will do.

My rational:  If the very last segment is lost, the partial ACK for
the preceding segment will not include a SACK block because the
receiver mistakenly thinks the data is complete.  I would characterize
this situation as leaving SACK recovery prematurely, which why it
should be in scope for 3517bis.

Thanks,
--MM--
The best way to predict the future is to create it.  - Alan Kay

---

From: Yuchung Cheng <[email-masked]>
Date: Fri, 22 Oct 2010 14:14:14 -0700

The example Richard gave makes lots of sense; it should improve loss
recovery latency for web traffic as well. I also suggest revising RFC3517
about this case. My rational is simply TCP has too many RFCs on similar
subjects. It's nightmare for developers (at least me) to follow up.

but I disagree it's receiver's mistake: the receiver has no way to tell in
this case! unless we put SND_NXT in the sender packets.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sat, 23 Oct 2010 00:08:23 +0100

Hi Ethan, Mattis, Yuchung and Yoshifuma,
 
Let me state the conclusion of the below thoughts first:
 
A Full ACK (no SACK blocks) of SND.FACK should be a strong enough
trigger to start retransmit of all segments between SND.FACK and
SND.MAX. With the nice side effect that no additional state needs to be
kept or saved in the senders TCP when entering SACK loss recovery... 

 
Some thoughts w.r.t. conservation of packets when such a problem
happens; please correct me, if any of these assumptions don't hold:
 
o) worst case scenario would be making one window minus 4 (initial loss,
3 delivered to trigger sack loss recovery, remaining segments heavily
delayed) segments elegible for retransmissions.
 
o) would require delay (reordering) of all of these segments for at
least one RTT (delivery after S2 is received on the receiver side).
 
o) due to the loss of the ACK clock, no more than at most dupthresh
segments would be sent spurious after receiving an FullACK, while the
remaining segments are
still delayed.
 
o) depending on implementation details, up to (cwnd-4)*7/12 segments may
be retransmitted unneccessarly, but nicely clocked out by ACKs. (With
delayed ACKs, that might only be (cwnd-4)*3/12 segments).

However, if the reordering delay would be higher than 1 RTT, even RTO
based loss recovery would sent spurious retransmits.... but potentially
even more than allowing SACK loss recovery to continue: (cwnd-4) - and
by doing a slow start.

Overall, for low RTT environment, I would argue that the benefit of
addressing this RTO far outweights the potential, worst case cost. 
 
For high RTT environment, the current behavior can already be worse
(slow-starting (bursts) after RTO, bursting out potentially delayed
segments) than the worst case behavior of addressing this corner case -
provided my back of the envelope sketch above holds any merit.
 
The scenario to end up with worst case violation of conservation of
packets seem pretty extreme (LIFO delivery, exactly timed, adjusted to
the cwnd....), so in a normal heavy reordering scenario, only very few
segments may be retransmitted unnecessarily...

A Full ACK (no SACK blocks) of SND.FACK should be a strong enough
trigger to start retransmit of all segments between SND.FACK and
SND.MAX. With the nice side effect that no additional state needs to be
kept or saved when entering SACK loss recovery... 
 
ACKs with (higher) SACK entries received after starting the
retransmission of that SND.FACK ..  SND.MAX range may only cause a
reduction of unnecessarily transmitted segments (IIRC, ACKs with SACK
entries that don't ack any previously unacked segment, are not counting
against the rate-halving scheme, or the rfc3517 pipe calculation...).

Richard Scheffenegger

________________________________

	From: Yuchung Cheng [mailto:[email-masked]] 
	Sent: Freitag, 22. Oktober 2010 17:14
	To: Matt Mathis
	Cc: Scheffenegger, Richard; [email-masked]
	Subject: Re: [tcpm] end-of-stream loss recovery (RFC2018 SACK
errata?)

	The example Richard gave makes lots of sense; it should improve
loss recovery latency for web traffic as well. I also suggest revising
RFC3517 about this case. My rational is simply TCP has too many RFCs on
similar subjects. It's nightmare for developers (at least me) to follow
up. 

	but I disagree it's receiver's mistake: the receiver has no way
to tell in this case! unless we put SND_NXT in the sender packets.

	On Fri, Oct 22, 2010 at 12:21 PM, Matt Mathis
<[email-masked]> wrote:

		I think it would be better to try to get it into
3517bis, but if that
		doesn't work, a separate ID will do.
		
		My rational:  If the very last segment is lost, the
partial ACK for
		the preceding segment will not include a SACK block
because the
		receiver mistakenly thinks the data is complete.  I
would characterize
		this situation as leaving SACK recovery prematurely,
which why it
		should be in scope for 3517bis.
		
		Thanks,
		--MM--
		The best way to predict the future is to create it.  -
Alan Kay

---

From: Ethan Blanton <[email-masked]>
Date: Fri, 22 Oct 2010 21:42:00 -0400

> doesn't work, a separate ID will do.

See my response to the 3517bis thread for my response to this, too.
;-)  I prefer to see this in separate ID.

> should be in scope for 3517bis.

I largely agree with this characterization.  There may be some
potential for confusion if the segment immediately preceding the
incoming cumulative ACK was retransmitted, where loss recovery is
indeed complete and the next segment *should not* be retransmitted.
Due to this and other possible issues, I'd much rather see this
hammered out carefully and integrated later, while 3517bis is pushed
through and finished in the meantime.

It sounds to me like there's room for a document (or maybe two
documents) which says:

1) There's a corner case where a specific loss pattern which involves
   at least two segment losses in a single window of data separated by
   at least three intervening segments causes SACK to perform worse
   than NewReno.

2) There is a related set of corner cases with general losses at the
   end of the window where, under some circumstances, it may be
   beneficial to retransmit a packet a bit "early".

--- possible document break

3) There are better ways to handle SACK data on RTO than flushing it
   blindly.  In particular, Josh Blanton documented as part of his
   Masters thesis a scheme which reliably disambiguates reneging on
   SACK information from other behaviors.

Then, at some later point in time, it may make sense to roll these
algorithms into the RFC 3517 lineage.  In particular, I believe that
points 1) and 2) are more subtle than this thread suggests.  I think
3) is probably more straightforward.

Ethan

---

From: Ethan Blanton <[email-masked]>
Date: Sat, 23 Oct 2010 09:25:27 -0400

Richard, I'm pulling this back to the list, because I suspect you're
not the only reader who didn't follow ... my original example was too
terse.

Scheffenegger, Richard spake unto us the following wisdom:
> Unfortunately, I'm afraid I am not following what you wanted to describe
> here:

It requires three losses, and your change of rules.

> > through and finished in the meantime.

[snip your example]

S1 ... S7 are sent.  S1, S6, and S7 are lost.  The sender retransmits
S1, gets a cumulative ACK for S6, retransmits S6, then gets a
cumulative ACK for S7.  Should it retransmit S7?  Did the original
transmission or the retransmission trigger the cum ACK for S7?
Consider the case were S6 was not lost in the first place, but delayed
in the network for ~1RTT.  Now consider interaction with timestamps,
DSACK, etc. where this potentially *can* be disambiguated.

My point isn't that this is the end of the world, or that it's the
only potential problem, or even that it's a problem worth worrying
about (it might just be a corner case), it's simply that someone needs
to sit down and carefully think about all of the scenarios, and I
don't think this rev of 3517 is the time to do it. It took more than
two years to get 3517 published, and (for which I take some blame)
poor Ilpo and Markku have been sitting on their sack-entry draft for
many months now already.  This change to 3517 is small, easily
understood, has been understood and "approved" by many involved
parties since the time that 3517 was originally published, and
represents a real benefit.

I would very much prefer to see you explore the options for this
end-of-window loss scenario, including situations where it fails and
where the retransmission should be stifled (if any).  I think you'll
find that it's *not* as easy as looking for a cumulative ACK for the
highest SACKed octet + 1.  (Or, rather, it may be that it *is* that
simple for the *first* retransmission, but possibly not later
retransmissions.)

Ethan

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sat, 23 Oct 2010 19:31:29 +0100

Thank you Ethan!

I'll skip the discussion about whether it should be in 3517bis or a
seperate document.

Obviously, if S6 + S7 are lost, the sender should retransmit, right?
(But the sender and receiver lack the information to be 100% sure about
that). 

If S6 (or S7 for that matter) are delayed by more than 1 RTT, RTO would
also trigger the resending of those frames - potentially prematurely
[assuming RTT > RTO(min)]. 
This scheme would only cause the sending of one of the segments earlier,
than RTO may have done.

If either one is delayed by less than RTT, an ACK with a SACK entry
would move SND.FACK forward, preventing undue retransmissions in time.

Some goes if we are not at the end of stream, and new (S8) segments are
injected that are not delayed.

Regarding the timing/ordering of the retransmissions: A cumulative ACK
(with no SACK entries) should trigger the retransmission of only a
single further packet presumed lost at the end of stream. In your
example, the sender could fill the pipe by immedately sending S6 + S7. A
conservate sender should however still wait a little more for S7 to
arrive, if it was heavy delayed by the network. Thank you for bringing
up that point.

That way, the sender is allowing for 1 RTT reordering delay for S6, but
2 RTT reordering delay for S7 (and so forth). Assuming, of course, RTT <
RTO(min). If RTT is larger than RTO(min), and reordering delay larger
than 1 RTT, RTO will trigger retransmission of segments sooner than the
cumulative ACK for S6 could cause sack loss recovery to retransmit under
that scheme. Since this would also happen currently, we end up no worse
than without the modification.

And yes, I'm quite sure that there will be corner cases, where simply
using cumulative ACK for the highest SACKed octet + 1 may cause
superfluous retransmits. I use superfluous here in order to discreminate
from spurious retransmits, which are preceeded by an undue entering of
loss recovery. Here we are always in loss recovery.

(If I may, being interested primarily in low-latency, high bandwidth
environment where boundary synchronized traffic is encountered, the
timely recovery (few RTT) is of more criticality than absolute
conservation of packets. There are other means in TCP to address
environments, where heavy reordering is dominant, and I would argue that
once loss recovery started, this is out of scope.)

I think the above arguments can be interpreted such that

o) If RTT > RTO(min), and reordering delay >= RTT:
	No change in the way the sender behaves (all these delayed
segments may end up retransmitted unnecessarily, under both schemes, due
to RTO)

o) If RTT < RTO(min), and reordering delay between RTT and RTO(min):
	Some few superfluous retransmits can happen. This is bounded,
however, by (cwnd-4)*7/12 segments, if my calculations yesterday were
correct; with delayed ACK enabled, the upper bound can be as low as
(cwnd-4)*3/12, even under pathological worst case scenarios (such as
LIFO reordering and exact timing).

o) If reordering delay < RTT:
	The sender will not see a cumulative ACK without SACK entries,
thus not prematurely retransmit delayed segments.

If there is indeed loss, and RTT < RTO(min), full recovery will takes
n*RTT with n the number of segments lost prior to end-of-stream. Even
that "lengthy" recovery time will typically beat RTO by orders of
magnitude in local networks. If more then (cwnd-3)/2 is lost, the ACK
clock will eventually stall, and only a RTO + slow start can get the
flow going again. 

Obviously, the above statements are not as thorough as you probably
would like them to be. I tried to flesh out a scenario yesterday, which
would result in the *most* superfluous retransmissions possible -
excluding additional information such as DSACK, delayed ACKs,
Timestamps, but taking the reduction of the congestion window into
account (and the variants of rate halving, that seem to be running in
the lastest BSD and Linux stacks).

Best regards,

Richard Scheffenegger

> From: Ethan Blanton [mailto:[email-masked]] 
> Sent: Samstag, 23. Oktober 2010 09:25
> Richard, I'm pulling this back to the list, because I suspect 
> you're not the only reader who didn't follow ... my original 
> example was too terse.
> 
> S1 ... S7 are sent.  S1, S6, and S7 are lost.  The sender 
> retransmits S1, gets a cumulative ACK for S6, retransmits S6, 
> then gets a cumulative ACK for S7.  Should it retransmit S7?  
> Did the original transmission or the retransmission trigger 
> the cum ACK for S7?
> Consider the case were S6 was not lost in the first place, 
> but delayed in the network for ~1RTT.  Now consider 
> interaction with timestamps, DSACK, etc. where this 
> potentially *can* be disambiguated.
> 
> My point isn't that this is the end of the world, or that 
> it's the only potential problem, or even that it's a problem 
> worth worrying about (it might just be a corner case), it's 
> simply that someone needs to sit down and carefully think 
> about all of the scenarios, and I don't think this rev of 
> 3517 is the time to do it. It took more than two years to get 
> 3517 published, and (for which I take some blame) poor Ilpo 
> and Markku have been sitting on their sack-entry draft for 
> many months now already.  This change to 3517 is small, 
> easily understood, has been understood and "approved" by many 
> involved parties since the time that 3517 was originally 
> published, and represents a real benefit.
> 
> I would very much prefer to see you explore the options for 
> this end-of-window loss scenario, including situations where 
> it fails and where the retransmission should be stifled (if 
> any).  I think you'll find that it's *not* as easy as looking 
> for a cumulative ACK for the highest SACKed octet + 1.  (Or, 
> rather, it may be that it *is* that simple for the *first* 
> retransmission, but possibly not later
> retransmissions.)
> 
> Ethan
>

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sat, 23 Oct 2010 23:41:00 -0700

> DSACK, etc. where this potentially *can* be disambiguated.

In my feeling, this depends on the pipe size.
if cwnd - pipe >= 1 SMSS, we can send at least 1 packet.
In this example, S8 will be sent. ( rule (2) in NextSeg() will be applied)
If S8 can arrive at the receiver successfully, the sender can get good
estimation for lost packets by the ACK for S8. Then, it can retransmit
proper packets.

However, as Richard already pointed out, if this is the end of
transmission, there is no S8.
In this case, I think retransmitting S7 will not be harmful so much.

If this is not the end of transmission (e.g. application stall), I'm
not very sure whether we should retransmit a packet.

Thanks,
--
Yoshifumi Nishida
[email-masked]