Subject: Re: [tcpm] Should draft-ietf-tcpm-sack-recovery-entry update RFC 3717 (SACK-TCP)

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 9 Nov 2009 12:57:10 -0000

Hi Alexander et al.,

This will be the first post to this group, so excuse me if I act inappropriately.

I'm curious about one little tidbit which has been bugging me for the better part of the last two monts, and which is closely related with TCP SACK operations (thus it might belong to this thread?)

The implicit assumption for TCP fast recovery is, that packet loss happens randomly (ie. to different segments each time) with low correlation between the drop events. Also, a drop event is used as a implicit signal to indicate congestion. So far, so good.

It seems to me, that the focus of most developments has been the internet environment - where statistical assumptions like the above mentioned arguably hold true.

However, certain high-speed LANs seem to exhibit characteristics, which don't play well with these implicit assumptions (uncorrelated packet loss) - the smaller the network, the more deviation from an "good seasoned" link (exhibiting some form of congestion) is likely to occur.

Also, as has been noted in prior research, many internet routers do use more "tcp-friendly" RED or WRED queue policies, over the simplistic TailDrop most often encountered in LANs (default policy of L2 switches and L3 routers).

In one extreme, I have found a (misbehaving´?) TCP stack/host, which sends out a burst of segments (4-6) @ 10GbE wirespeed, which immediately cause queue buffer overload and TailDrop in the first hop L2 Switch, when two such high performance hosts try to establish a high speed communication. With other words, the hosts themselves seem to make sure that there is a high correlation between TCP (fast) recovery and further packet loss.

But what puzzles me the most - even with SACK enabled TCP stacks, virtually no implementation can detect / act upon detection of the loss of a retransmitted segment during fast recovery. This despite the fact, that the stipulations in RFC3517 requires the receiver to make the information to detect such an event implicitly available to the sender. The first SACK option has to reflect the last segment, which triggered this SACK. 

Together with the scoreboard held at the sender, it should be rather easy to find out if the left edge of the lowest hole (relative to stream octets) closes.

If that left edge stays constant for "DupThresh" number of ACKs, which reduce the overall number of octets in holes (any one hole might close due to the retransmitted packets still received), AND the sender retransmits beginning with the lowest hole first, this would be a clear indication of another segment retransmit loss...

Even a less speedy detection logic would work for SACK-enabled sessions: once the fast recovery is finished from the sender's point of view, if the receiver still complains about missing segments (indicated by having the SACK rightmost edge - in the first slot SACK option - at a segment higher than when fast recovery started), another round of fast recovery could be invoked, rather than waiting for RTO.

Of course, the first approach would be better for low cwnd sessions with only very few segments in transit - and both could be combined with the proposed sack recovery speed-ups... (Reducing DupThresh for low cwnd sessions / when little data is being sent).

Congestion control should act to this event (it will now, but only one RTO later...), and the SACK retransmit vector (HighRxt) reset, using LimitedTransmit for sending out the retransmission segments - once cwnd + pipe allows; any retransmitted segments still in the network will close their respective SACK holes before the new HighRxt advances to them.

And, RTO should be reduce (I guess to nearly zero, between SACK-enabled hosts).

I have run numerous tests, to check the behavior of different TCP Stacks (FreeBSD 4.2 - 8.0; windows xp, vista, 7, 2003; Linux 2.6.16 and others).

All these stacks seem to exhibit this issue; What I don't know yet is the percentage of multi-loss segement events triggering RTO - but I assume that the majority of RTOs happen because of this.

In LAN environments (ie. 10 GbE over 1 km @ 2 ms latency due to the L2 hops in between) featuring relatively few streams, the effect of any single RTO can be quite tremendeous - taking considerable theoretical bandwidth away from the session (ie. 1 sec minimum RTO equals 1.2 GB; even with more recent RTO values around 0.2 - 0.4 sec, each RTO is still a few hundred MB "lost" capacity under optimal circumstances.

Nevertheless, I cann't imagine that I am the first one to bring up this issue (despite having failed to find any study of this effect). :)

One more clarification, which came up after I looked at the FreeBSD implementation of Limited Transmit; this might be a nit-pick, but when RFC 3042 is active, shouldn't ABC also be used during LimitedTransmit / FastRecovery? (FreeBSD MAIN is increasing cwnd by 1 mss for each new ACK, instead for the amount of data in that ack...

Thanks a lot!

Best regards,  

Richard Scheffenegger
Field Escalation Engineer
NetApp Global Support 
NetApp
+43 1 3676811 3146 Office (2143 3146 - internal)
+43 676 654 3146 Mobile
www.netapp.com <BLOCKED::http://www.netapp.com/>  
Franz-Klein-Gasse 5
1190 Wien 

*	To: "tcpm at ietf.org <mailto:[email-masked]>  WG Extensions" <tcpm at ietf.org <mailto:[email-masked]> >
*	Subject: [tcpm] Should draft-ietf-tcpm-sack-recovery-entry update RFC 3717 (SACK-TCP)
*	From: Alexander Zimmermann <alexander.zimmermann at nets.rwth-aachen.de <mailto:[email-masked]> >
*	Date: Wed, 21 Oct 2009 12:22:50 +0200

  _____  

Hi folks,

based on the fact that the draft "draft-ietf-tcpm-sack-recovery-entry" is adopted as WG item now and intended to be a "standards track" document, I would like to start a poll/discussion whether the draft should update RFC 3517 or not? Moreover, should we produce a separate document or an update of RFC 3517? 

a) separate document, do not update RFC 3517
b) separate document, update RFC 3517
c) RFC3517bis, obsolete RFC 3517

//
// 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-22220
// email: zimmermann at cs.rwth-aachen.de
// web: http://www.umic-mesh.net
//

---

From: Arnd Hannemann <[email-masked]>
Date: Mon, 09 Nov 2009 16:21:15 +0100

Scheffenegger, Richard schrieb:

> But what puzzles me the most - even with SACK enabled TCP stacks, virtually no
> implementation can detect / act upon detection of the loss of a retransmitted
> segment during fast recovery. This despite the fact, that the stipulations in
> RFC3517 requires the receiver to make the information to detect such an event
> implicitly available to the sender. The first SACK option has to reflect the 
> last segment, which triggered this SACK. 

Some implementations actually do detect lost retransmissions.
(see Linux tcp_mark_lost_retrans())
However, currently only for FACK enabled flows. (Comments indicate,
it would be non-trivial / too-expensive for SACK enabled flows.)

> Together with the scoreboard held at the sender, it should be rather easy to
> find out if the left edge of the lowest hole (relative to stream octets) closes

> If that left edge stays constant for "DupThresh" number of ACKs, which reduce
> the overall number of octets in holes (any one hole might close due to the
> retransmitted packets still received), AND the sender retransmits beginning
> with the lowest hole first, this would be a clear indication of another segment
> retransmit loss...

Sorry, I don't understand. You mean "DupThresh" number of DupACKs? Sack-blocks?
After which point in time? After the first retransmit?
SACK-blocks higher than recovery point? (the latter would make most sense, IMO)

> Even a less speedy detection logic would work for SACK-enabled sessions: once
> the fast recovery is finished from the sender's point of view, if the receiver
> still complains about missing segments (indicated by having the SACK rightmost
> edge - in the first slot SACK option - at a segment higher than when fast
> recovery started), another round of fast recovery could be invoked, rather than
> waiting for RTO.

How can fast recovery be "finished" if the sender is missing packets?

Best regards,
Arnd Hannemann

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 9 Nov 2009 19:39:17 -0000

Hello Arnd,

Thanks for your comment; unfortunately, I'm not supposed to get
inspiration from GPL'ed code :) 

Do you know which kernel versions feature this? I've checked 2.6.16 and 
2.6.18 (commercial distributions), but none of the most recent ones...

FACK as described here
http://www.psc.edu/networking/papers/FACKnotes/current/
seems to be a sender-only algorithm; Thus if the receiver is
implementing
SACK, the sender should be able to use it, right?

I just rechecked - the trace does show the hallmark signs of FACK, but
no sign of
a retransmission of a lost retransmitted segment before a
(comparatively) long
Period (assuingly RTO) starting a limited slow start (as the slow start
ACKs
Are still SACKs for a large sequence space)...

(Using CentOS53, kernel 2.6.18 in this quick test).

Hmm... Running a 2nd check (this time with cached session parameters),
the
Linux Kernel seems to do a 2nd sack recovery - even though not optimally
so
(not at the very first possibility w/ 3 SACK-ACKs indicating that it 
would be possible...). The first trace appears to have run into a RTO
with
The very first dropped segment (and the stream took ages...)

3rd test: 237 msec delay (RTO?), with the last new segment being set 36
ms after
the 2nd drop (so, nearly exactly 200 ms after sending the last new
segment,
And receiveing about 80 uninterrupted ACKs...

So, the linux stack seems to have the capability, but it's not reliably
invoked...

Thanks for pointing this out!

Regarding the other two question - for the first one, please see
The diagram I sent earlier; I hope this clarifies what I mean.

If I am mistaken somewhere, please let me know...

And with the last statement (fastretransmission finished) I referred
To the point in time, when the sender has sent all segments being
flagged
By SACK to have been missing, before noticing (one RTT later) that
another
One might be missing; this might be a special case, though, as I assumed
That retransmission would end prior to the receiver detecting the 
2nd loss...

I guess a time-flow diagram would help :)

Best regards,

Richard Scheffenegger
www.netapp.com 
Franz-Klein-Gasse 5
1190 Wien 

-----Original Message-----
From: Arnd Hannemann [mailto:[email-masked]] 
Sent: Montag, 9. November 2009 16:21
To: Scheffenegger, Richard
Cc: [email-masked]
Subject: Re: [tcpm] Should draft-ietf-tcpm-sack-recovery-entry update
RFC 3717 (SACK-TCP)

Scheffenegger, Richard schrieb:

> But what puzzles me the most - even with SACK enabled TCP stacks, 
> virtually no implementation can detect / act upon detection of the 
> loss of a retransmitted segment during fast recovery. This despite the

> fact, that the stipulations in
> RFC3517 requires the receiver to make the information to detect such 
> an event implicitly available to the sender. The first SACK option has

> to reflect the last segment, which triggered this SACK.

Some implementations actually do detect lost retransmissions.
(see Linux tcp_mark_lost_retrans())
However, currently only for FACK enabled flows. (Comments indicate, it
would be non-trivial / too-expensive for SACK enabled flows.)

> Together with the scoreboard held at the sender, it should be rather 
> easy to find out if the left edge of the lowest hole (relative to 
> stream octets) closes

> If that left edge stays constant for "DupThresh" number of ACKs, which

> reduce the overall number of octets in holes (any one hole might close

> due to the retransmitted packets still received), AND the sender 
> retransmits beginning with the lowest hole first, this would be a 
> clear indication of another segment retransmit loss...

Sorry, I don't understand. You mean "DupThresh" number of DupACKs?
Sack-blocks?
After which point in time? After the first retransmit?
SACK-blocks higher than recovery point? (the latter would make most
sense, IMO)

> Even a less speedy detection logic would work for SACK-enabled 
> sessions: once the fast recovery is finished from the sender's point 
> of view, if the receiver still complains about missing segments 
> (indicated by having the SACK rightmost edge - in the first slot SACK 
> option - at a segment higher than when fast recovery started), another

> round of fast recovery could be invoked, rather than waiting for RTO.

Best regards,
Arnd Hannemann

---

From: Arnd Hannemann <[email-masked]>
Date: Tue, 10 Nov 2009 13:03:40 +0100

Hi,

> 2.6.18 (commercial distributions), but none of the most recent ones...

At least 2.6.24 (Ubuntu 8.04 LTS) and newer have this.

> SACK, the sender should be able to use it, right?

As far as I remember the advantage of FACK for detecting lost
retransmissions is, that you can be sure that after invoking
"Fast Retransmit" you retransmitted all holes up to RecoveryPoint
before sending any new data. Now you can use any ACK containing
a SACK block above RecoveryPoint for an indication of a
lost retransmission. But note, that FACK has serious problems
with reordering.

In my opinion SACK-TCP you would need to track a lot more.
Thinking of it, maybe it would be enough to store highest seq
sent so-far for each retransmit. And then check this for incoming
SACKs individually for each retransmit. Might be still too expensive...

[Shortened E-mail]

> That retransmission would end prior to the receiver detecting the 

Don't forget that with SACK-TCP the TCP sender will mix retransmissions
and new segments all the time during recovery.
The interesting part is: How does the TCP sender detect, that a
retransmission might be missing? Simply checking against RecoveryPoint
would not work... Or only for the "first hole".

> I guess a time-flow diagram would help :)

Yes please!

Best regards,
Arnd Hannemann

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 10 Nov 2009 13:32:52 -0000

Hi Arnd,

Let's think about what would be required to track a lost retransmitted
segment.

A) the sender can only know about this one RTT after it send out the
first 
   retransmission at the earliest.

  A1) With TSOpt, they could be used to "remember" when Retransmission
started; 
      When an ACKs with TSEcn > (TSOpt + RTT) is seen by the sender, it
can 
      re-arm the DUPACK detector.

  A2) With SACK, tracking SND.NXT and HOLEBYTES (number of octets in all
current holes) 
      can be employed to track RTT (they need to be initialized when the
first 
      retransmitted segment is sent). When an ACK contains a SACK for >=
SND.NXT, or the 
      HOLEBYTES are smaller than when retransmission started, the DUPACK
detector can 
      be re-armed.

  A3) If neither TSOpt nor SACK is used, revert to current behavior (RTO
timeout to
      detect a lost retransmit).

B) DUPACK detector would need to be enhanced over what is currently in
the RFCs (but 
   I think most of that is already in Drafts, ie. 
   http://tools.ietf.org/html/draft-jarvinen-tcpm-sack-recovery-entry-01
).

 B1) With SACK enabled, fully duplicate ACKs (ACK and SACK have been
seen before, and 
     prev_HOLEBYTES == HOLEBYTES) can be discarded; lost ACKs would
count for two 
     (prev_HOLEBYTES < HOLEBYTES - SMSS).

 B2) With TSOpt, if another RTT passes without advancing SND.UNA, 
     increase DupAcks += DupThresh 

 When DupThresh # of ACKs are received, reset HighRxt = SND.UNA, DupAcks
= 0; *)

There are two comments I would like to make:

A) Latency: if the sender first sends out the entire range of holes,
before
   reacting to a detectable lost retransmitted packet, the latency
observed
   by the application on the receiver side will increase needlessly. It
might
   take a number of RTTs under certain circumstances, before all the
holes
   have been retransmitted once... 

B) Complexity: As soon as any congestion event is encountered, TCP won't
be in
   fastpath mode any longer; the added computational complexity to
(reliably, see my
   check on FACK with Linux 2.6.18 yesterday) trigger another
retransmission
   of an already retransmitted segment is neglegible, compared to
current best
   practise (waiting for RTO), when you need to move data around as
quickly (low
   latency AND high bandwidth) as possible. As mentioned, my background
is not
   so much the global internet (with statistically valid implict
assumptions), but
   rather High-Speed, short Range, (lossy) LANs, with only very few
active TCP
   sessions at any one time. The hosts I deal with might have as few as
10-20 TCP
   sessions, of which only 1-4 are pushing data, but those might run
over dedicated
   10GbE ports (overloading L2 switches in the process, and exhibiting
Burst Loss
   (correlated packet loss) ).

Thus my view might deviate from a "typical" view in certain aspects. I
might even be 
in error and would like to hear, why some things cann't work like
depicted. However, 
I would place more emphasis on the timely recovery  of any lost (or
re-lost) segment, 
over making sure that no single segment is re-transmitted needlessly;
better retransmit 
a little (!) too much too soon, instead of waiting for RTO :) I want to
point out the 
"little" though, as overwhelming a already lossy network with too much
retransmissions 
(ie. Setting RTO = 0/1 tick, with a TCP clock runnig in msec), will only
cause more loss...

*) reducing the segment size for this generation of retransmission might
also be 
advisable; I have seen odd gear (but that's actually a long time ago),
which simply 
would choke on certain bit-patterns. Reducing the mss might break such
bit/byte 
patterns, so that the always-lost segment now looks differently and
makes it through... 

But really, this shouldn't be necessary any more, I think.

Richard Scheffenegger

-----Original Message-----
From: Arnd Hannemann [mailto:[email-masked]] 
Sent: Dienstag, 10. November 2009 13:04
To: Scheffenegger, Richard
Cc: [email-masked]; Alexander Zimmermann
Subject: Detect Lost Retransmit mit SACK

Hi,

[Shortened E-mail]

Yes please!

Best regards,
Arnd Hannemann

---

From: Arnd Hannemann <[email-masked]>
Date: Tue, 10 Nov 2009 17:43:03 +0100

Hi Richard,

>       re-arm the DUPACK detector.

This is your non-SACK scenario?
Please note that a TCP receiver will NOT echo TSVal
from out-of-order segments. So this won't work.

>       HOLEBYTES are smaller than when retransmission started, the DUPACK

You should specify what you mean with SND.NXT.
We are in recovery, so we may very well send out new segments.
I don't see why number of holes in sack scoreboard
has anything todo with RTT.

>      (prev_HOLEBYTES < HOLEBYTES - SMSS).

Now B1 is SACK enabled scenario? You try to confuse me, right?
All this makes little sense to me.

>  When DupThresh # of ACKs are received, reset HighRxt = SND.UNA, DupAcks

See above...
non-SACK is not going to work.

>    have been retransmitted once... 

Show me an example. where a lost retransmission is detectable, while
the sender did not send out retransmissions for every other hole?
Sounds weird.

>    (correlated packet loss) ).

This probably highly rates from case to case. If you have a huge
bandwidth-delay product even SACK scoreboard handling will have
computational complexity which might outweigh its benefits.
As you have seem to have the equipment at hand, you could do some
cpu load and throughput measurements with 10GbE
and SACK versus non-SACK flows.

> (ie. Setting RTO = 0/1 tick, with a TCP clock runnig in msec), will only

I think it is a good idea to detect lost retransmissions and I think
it is possible with SACK. I already proposed a potential solution ;-)
"Just" store highest seq, for each retransmission. And check incoming SACKs
on those. My main concern is, as already said, that this might get
quiet expensive. But you are free to evaluate this more deeply ;-)
Anyway, maybe we should focus on your other thread...

Best regards,
Arnd

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 10 Nov 2009 18:28:00 -0000

See inline

Richard Scheffenegger

> Sent: Dienstag, 10. November 2009 17:43
> Cc: Alexander Zimmermann; [email-masked]
> Subject: Re: Detect Lost Retransmit mit SACK
> 
> Hi Richard,
> 
> 
::
> > 
> >   A1) With TSOpt, they could be used to "remember" when 
> >       Retransmission started;
> >       When an ACKs with TSEcn > (TSOpt + RTT) is seen by 
> >       the sender, it can
> Please note that a TCP receiver will NOT echo TSVal from 
> out-of-order segments. So this won't work.

Interesting; this doesn't seem to be what certain (most?) stacks are 
doing - they seem to always reply in the ACK Tsecr the value of
Tsopt/TS.recent 
triggering the ACK...

Or was your intention to say, that the receiver will not respond with
Tsopt, but rather TS.recent?

If so, than this makes no difference - the sender will detect the 
first ACK from the receiver, which has the same TS (well, actually TS+1
as multiple segments are likely to carry the same TS) when the
retransmission
was started. This will be the sign for the sender, that at least one RTT
has elapsed (that was the intention for having timestamps in the first
place, right?). If the returned ACK does not cover the first
retransmitted
segment by that time, it's quite reasonable to assume that it got lost
again.

Again, keep in mind that I'm looking on LANs; a TS in 10 ms increments
(100 Hz
TCP clock) is likely to be put into a few hundred or thousand packets...

If there is reason to believe the reordering can occur with delays >>
RTT, then
Yes, this simple detection logic would be fooled and falsely trigger a
retransmission.

However, IF the reordering is >> 2*RTT, then it's very likely that the 
newly retransmitted segment arrives at the receiver first (over the
faster 
path), and again this would only serve to keep the application visible
latency 
as low as possible (between the points in time, where TCP can deliver
some / any 
new data up the stack...) 

> >   A2) With SACK, tracking SND.NXT and HOLEBYTES (number of 
> >       octets in all current holes)
> >       can be employed to track RTT (they need to be 
> >       initialized when the first
> >       retransmitted segment is sent). When an ACK contains 
> >       a SACK for >= SND.NXT, or the
> >       HOLEBYTES are smaller than when retransmission started, the 
> >       DUPACK detector can be re-armed.
> 
> I don't see why number of holes in sack scoreboard has 
> anything todo with RTT.

SND.NXT is the rightmost segment which the sender has never before 
sent out to the network. Isn't that the meaning of Snd.nxt according 
to RFC793?

And I was not talking about the # of holes, but rather the amount of
Data (in sum) between FACK (defined by the rightmost offset in the SACK
Scoreboard, i.e. covering the highest ever received segment) and
SND.UNA.

Monitoring Holes will gain nothing (when there is reordering for
example);

But if the any one retransmission makes it though, the amount of
unSACKed 
data in the sum total of all holes in the scoreboard, will decrease - 
indicating when at least one RTT has passed since start of
FastRetransmit.

> 
> > 
> >   A3) If neither TSOpt nor SACK is used, revert to current behavior 
> > (RTO timeout to

I agree, it would have made sense to label points B1 and B2 the other
way
around to stay more consistent; that's one of the reasons why I like to 
discuss this :)

> >  When DupThresh # of ACKs are received, reset HighRxt = SND.UNA, 
> > DupAcks = 0; *)
> 
> See above...

See above - TSOpt is only used for the prime purpose to detect when a 
RTT has passed. It doesn't matter if Tsecr contains TSopt or
TS.recent... 
 
> >    by the application on the receiver side will increase 
> needlessly. 
> > It might
> Show me an example. where a lost retransmission is 
> detectable, while the sender did not send out retransmissions 
> for every other hole?
> Sounds weird.

Can I attach trace files on posts to this list, or shall I sent them 
to you directly? 

I assume that on the receiving side, the application is only delivered
data, which has been ACKed (not SACKed). If the sender waits until 
RTO before retrying to re-send a retransmission (sorry about these
Multiple re-s :) ), the application will at least stall (not get any 
new data) for RTO+2*RTT - and certain latency sensitive applications
will time out before that. Again: I'm not talking about internet
applications but rather LAN HPC applications with timeouts in the 
order of a few seconds at most.

Advancing (on the receiver) within that application timeout is
Usually enough to not run into the application timeout.

> 
> 
> > 
> > B) Complexity: As soon as any congestion event is encountered, TCP 
> > won't be in
> >    latency AND high bandwidth) as possible. As mentioned, my 
> > background is not
> >    sessions at any one time. The hosts I deal with might 
> have as few 
> > as 10-20 TCP
> This probably highly rates from case to case. If you have a 
> huge bandwidth-delay product even SACK scoreboard handling 
> will have computational complexity which might outweigh its benefits.
> As you have seem to have the equipment at hand, you could do 
> some cpu load and throughput measurements with 10GbE and SACK 
> versus non-SACK flows.

Well, I was doing some test like this:

http://www.ibm.com/developerworks/linux/library/l-tcp-sack/index.html

But the CPU impact (on top of what is required for 10G) was neglegible.

But I have to admit, I didn't had the time yet to test a SACK scoreboard
with every other byte marked mission (which could mean some 0,5 mio
entries).

But it seems that most implementations feature sorted scoreboards of
limited
(16/128) size.

Traversing those is - again in my case of 10G LANs - still many orders
of 
magnitude faster then waiting for RTO. 

I personally consider RTOs to be harmful (when there are other means to 
recover with). :) (perhaps once I have worked through all the issues
raised
here, I submit a draft with "TCP RTO considered harmful" next April? :)

> > might even be in error and would like to hear, why some 
> things cann't 
> > work like depicted. However, I would place more emphasis on 
> the timely 
> > recovery  of any lost (or
> > re-lost) segment,
> > better retransmit a little (!) too much too soon, instead 
> of waiting 
> > for RTO :) I want to point out the "little" though, as 
> overwhelming a 
> > already lossy network with too much retransmissions (ie. 
> Setting RTO = 
> > 0/1 tick, with a TCP clock runnig in msec), will only cause more 
> > loss...
> > 
> 
> I think it is a good idea to detect lost retransmissions and 
> I think it is possible with SACK. I already proposed a 
> potential solution ;-) "Just" store highest seq, for each 
> retransmission. And check incoming SACKs on those. My main 
> concern is, as already said, that this might get quiet 
> expensive. But you are free to evaluate this more deeply ;-)

---

From: Alexander Zimmermann <[email-masked]>
Date: Wed, 11 Nov 2009 09:34:11 +0100

Hi Richard,

it is done. I'm completely lost in the double threaded tread. I really suggest we stop
this ping-pong discussion, since IHMO nobody can follow us....
My suggestion is that you

* start to write a little ID with at least a pseudo code algo
* and a lot of *well indented* examples like Ilpo does in his ID
	=> Basic Case, multiple (burst) loss, ACK loss, reordering, packet duplication,...

With such a document,  it will be much more easier to follow your thoughts.
What do you think?

Alex

//
// email: [email-masked]

---

From: Arnd Hannemann <[email-masked]>
Date: Wed, 11 Nov 2009 09:45:49 +0100

Hi Richard,

> doing - they seem to always reply in the ACK Tsecr the value of

Please clarify, is this non-SACK scenario?
The only lost retransmission we could be talking about then,
is the retransmission of SND.UNA.
And the TCP receiver will NOT adjust TS.recent for any
out-of order packets (RFC 1323).
It will continue to echo the timestamp of the last segment which
advanced the window (SND.UNA -1p).

> Tsopt, but rather TS.recent?

Yes, it will not respond with TSVal but with TS.recent.

> as multiple segments are likely to carry the same TS) when the

There won't be an ACK if the retransmission is lost in non-SACK
case, only dupACKs.
(Only retransmission is retransmission of SND.UNA)
TS.Recent will not get updated.

> again

> Again, keep in mind that I'm looking on LANs; a TS in 10 ms increments

If you are searching for something which is not intended for general use,
why not just set MIN_RTO to say 10 ms?

> sent out to the network. Isn't that the meaning of Snd.nxt according 

Hmm, I would interpret RFC793 differently.
I would call it SND.MAX (see RFC4015) or HighData (RFC3517) the
rightmost segment which the sender has never sent before. But now you
have to clarify how it would be possible to receive a
SACK block > SND.MAX. Even SACK block == SND.MAX will be rarely seen.
But before taking this discussion even further, maybe take some time
and write some preliminary draft of your algorithm.

> indicating when at least one RTT has passed since start of

This is not true.
Consider a 100 packet in flight, you get 3 dupacks, do  a retransmission.
This is in your words "start of FastRetransmit". After this the sum total
of all holes between SND.UNA and FACK can only increase for one RTT.
Due to Limited Transmit and Fast Recovery, it might be possible that
even the sum total of all holes between SND.UNA and SND.MAX will
increase.
You know when the first Retransmit is lost when a SACK
covers RecoveryPoint (RFC3517). But this is only true for first hole.
To detect lost retransmissions of the other holes, you would
need to store a separate HighData (RFC3617) for every retransmission.
Maybe this is after all what you are trying to express?
Perhaps it would be helpful if you could cook up some pseudo code,
of your proposed algorithm.

> Can I attach trace files on posts to this list, or shall I sent them 

Never mind, does not actually matter.

> here, I submit a draft with "TCP RTO considered harmful" next April? :)

Better submit a draft to mitigate the problems with it ;-)

Best regards,
Arnd

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sun, 15 Nov 2009 02:15:19 -0000

Hi Arnd,

Sorry for the late response. I did some further investigations 
lately, and this is what I came up with.

Of course, the majority of work and thoughs have been done by 
others (most notably, I want to cite [[1]] "Lost Retransmission 
Detection for TCP Part 2: TCP Using SACK Option" by 
B. Kim et al (2004), but also by some ideas from [[2]] M. Mathis 
(dated) RateHalving NetBSD based code found here 
http://www.psc.edu/networking/projects/rate-halving/ 
(which did something similar but only for a single segment  
for the SACK recovery generation, if I can tell...)

First, the following prerequisites are required:

1) TCP Session must be SACK-enabled
2) TCP Sender has to have FACK implemented 
3) TCP Sender has to have a scoreboard implementation to 
   track the state of the receiver, working with a sorted 
   list of SACK-Holes rather than positive SACK-Ranges.

The fix might not be mathematically perfect in tracking each single 
segment, but in it's simplest incarnation, it's about 8 lines of 
code, adding minimal constant time (!) during ACK-processing. 

The idea is basically, not to track every sent out segment 
individually, but rather all holes in the scoreboard at once.

The implicit assumption here is, that retransmissions get sent out
in order (and are received with little to no reordering, or not 
at all).

When the sender transmits the last segment to "close a hole" in the 
sender's representation of the scoreboard, represented by a data 
structure holding start, end and rxmit vector, ie. When rxmit == end, 
rxmit will be assinged the current value of snd.max. (In the simple 
form, a separate variable iskept, but for the purpose of this 
algorithm, the condition of rxmit <= end vs rxmit > end can be used 
to differentiate between the two uses (current retransmission vector 
in a hole, vs. segment number by which the hole should be reported 
closed by the receiver) of rxmit.

So, after the retransmission of the last segment of a hole, it's 
rxmit will show the expected snd.fack value when that hole is ought 
to have been properly ACKed by the receiver.

In SACK processing, some precautions have to be made during hole-
splitting (to keep the higher than sackhole.end rxmit vector). 

Normal SACK processing will remove any fully closed holes before 
snd.fack becomes greater than sendhole.rxmit, except when one of 
the segments within that hole is never seen by the receiver. While 
processing a normal SACK, check the condition of 
snd.fack > sackhole[0].rxmit; 

In the worst case (1 segment hole), when some reordering occurred, 
this will yield one superfluous segment; with larger holes, the 
intrinsic reordering grace period granted is n-m segments (with n 
the size of the hole, and m the segment within the hole).

If that condition is met, reset sackhole[0].rxmit to 
sackhole[0].start, and also update the shortcut lookup pointer 
(sackhint.nexthole to sackhole[0]).

Extended periods of heavy loss are not dealt with. According to 
[[1]], these should be counted as additional congestion events, 
reducing ssthresh and cwnd accordingly; but this method needs a 
constant stream of at least some new segments to leave the 
Network).
Thus, RTO + slow start is required for recovery of such severe
Events.

Also, when there is no more data from the socket to transmit, 
to never exceed snd.max recorded for that hole, it will not 
work. (Again, RTO to the rescue).

But, it will update the rxmit vector for each fully retransmitted 
hole - as long as it keeps going. This yields a maximum number or 
RTO/RTT retries, before "usual" recovery sets in, and should 
cover the common case.

You could say it's more of a quick hack, but I think the 
simplicity, intrinsic properties and near no overhead (processing 
time or variable overhead) are well balanced, but if my assumptions
are incorrect or short sighted, please say so.

The simple version without any tweaks in existing checks of 
sackhole[]->rxmit (requiring one more tcp_seq var in sackhole[]):

Tcp_sack_doack:

(after sanity checks about the new SACK blocks, BEFORE new snd.fack 
has been calculated (one additional ACK grace period):
 
	if (((temp = TAILQ_FIRST(&tp->snd_holes)) != NULL) && //###
	     (SEQ_GT(tp->snd_fack, temp->limit))) {           //###
			temp->rxmit = temp->start;                //###
			temp->limit = tp->snd_max;                //###
			tp->sackhint.nexthole = temp;             //###
		}
//###

Tcp_sack_doack:

When splitting a hole in two:

		temp = tcp_sackhole_insert(tp, sblkp->end,
				    cur->end, cur);
				if (temp != NULL) {
					if (SEQ_GT(cur->rxmit,
temp->rxmit)) {
						temp->rxmit =
cur->rxmit;
	
tp->sackhint.sack_bytes_rexmit
						    += (temp->rxmit
						    - temp->start);
					}
					temp->limit = cur->limit;
//###
					cur->end = sblkp->start;
					// RS: SACK+ mod?
					cur->rxmit = SEQ_MIN(cur->rxmit,
					    cur->end);
				}

Tcp_output:

(when in Retransmit && SACK mode):

If (sack_rxmit == 1) {
		th->th_seq = htonl(p->rxmit);
		p->rxmit += len;
		if (SEQ_GEQ(p->rxmit, p->end))
//###
			p->limit = tp->snd_max;
//###
		tp->sackhint.sack_bytes_rexmit += len;
}

Tcp_var.h:
struct sackhole {
	tcp_seq start;		/* start seq no. of hole */
	tcp_seq end;		/* end seq no. */
	tcp_seq rxmit;		/* next seq. no in hole to be 
                                 retransmitted */
	tcp_seq limit;          /* ### for lost retransmission 
                                 detection - should be rolled 
                                 into rxmit */
	TAILQ_ENTRY(sackhole) scblink;	/* scoreboard linkage */
};

Richard Scheffenegger

> Sent: Mittwoch, 11. November 2009 09:46
> To: [email-masked]
> Subject: Re: [tcpm] Detect Lost Retransmit mit SACK
> 
> Hi Richard,
> 
> > Tsopt/TS.recent triggering the ACK...
> 
> And the TCP receiver will NOT adjust TS.recent for any out-of 
> order packets (RFC 1323).
> It will continue to echo the timestamp of the last segment 
> which advanced the window (SND.UNA -1p).
> 
> 
> > first ACK from the receiver, which has the same TS (well, actually 
> > TS+1 as multiple segments are likely to carry the same TS) when the 
> > retransmission
> 
> There won't be an ACK if the retransmission is lost in 
> non-SACK case, only dupACKs.
> (Only retransmission is retransmission of SND.UNA) TS.Recent 
> will not get updated.
> 
> 
> > was started. This will be the sign for the sender, that at 
> least one 
> > RTT has elapsed (that was the intention for having 
> timestamps in the 
> > first place, right?). If the returned ACK does not cover the first 
> > retransmitted segment by that time, it's quite reasonable to assume 
> > that it got lost again
> >   
> 
> If you are searching for something which is not intended for 
> general use, why not just set MIN_RTO to say 10 ms?
> 
> anything todo 
> >> with RTT.
> I would call it SND.MAX (see RFC4015) or HighData (RFC3517) 
> the rightmost segment which the sender has never sent before. 
> But now you have to clarify how it would be possible to 
> receive a SACK block > SND.MAX. Even SACK block == SND.MAX 
> will be rarely seen.
> But before taking this discussion even further, maybe take 
> some time and write some preliminary draft of your algorithm.
> 
> > Data (in sum) between FACK (defined by the rightmost offset in the 
> > SACK Scoreboard, i.e. covering the highest ever received 
> segment) and 
> > SND.UNA.
> >
> > unSACKed data in the sum total of all holes in the scoreboard, will 
> > decrease - indicating when at least one RTT has passed 
> since start of 
> > FastRetransmit.
> 
> This is not true.
> This is in your words "start of FastRetransmit". After this 
> the sum total of all holes between SND.UNA and FACK can only 
> increase for one RTT.
> Due to Limited Transmit and Fast Recovery, it might be 
> possible that even the sum total of all holes between SND.UNA 
> and SND.MAX will increase.
> You know when the first Retransmit is lost when a SACK covers 
> RecoveryPoint (RFC3517). But this is only true for first hole.
> Perhaps it would be helpful if you could cook up some pseudo 
> code, of your proposed algorithm.
> 
> >>     
> >>> holes
> detectable, while 
> >> As you have seem to have the equipment at hand, you could 
> do some cpu 
> >> load and throughput measurements with 10GbE and SACK 
> versus non-SACK 
> >> flows.
> >>     
> >
> > But I have to admit, I didn't had the time yet to test a SACK 
> > scoreboard with every other byte marked mission (which 
> could mean some 
> > 0,5 mio entries).
> >
> > of magnitude faster then waiting for RTO.
> >
> > I personally consider RTOs to be harmful (when there are 
> other means 
> > to recover with). :) (perhaps once I have worked through all the 
> > issues raised here, I submit a draft with "TCP RTO 
> considered harmful" 
> > next April? :)
> 
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>