Subject: Re: [tcpm] Settling Time and RFC3517bis

From: Anthony Sabatini <[email-masked]>
Date: Fri, 3 Aug 2012 19:37:32 -0400

All -

Because of the wording of the original comment it was not clear whether the RTT referred to the generated SACK information from the receiver or the original transmission from the sender.  By definition, with respect to the sender, it is not possible to properly retransmit the message in less than one RTT plus Reordering time plus processing time.

I am sorry for this misunderstanding.

Tony

Sent from my ASUS Pad

Mark Allman <[email-masked]> wrote:

>
>This is all pretty mis-guided.  Let me say just a few quick things.
>
>> 3) STANDARD TCP can not recover in less than one RTT, 
>
>Correct.  Nor would we want it to.  If you retransmit in less than one
>RTT from the time a segment is originally sourced then you will always
>be retransmitting blind.  I.e., you'll have no indication as to whether
>that segment needs to be retransmitted or not.
>
>>    SACK TCP as written certainly can and does currently recover in
>>    less that one RTT on at least long links.  
>
>Incorrect.  At least I am aware of no TCP SACK-based loss recovery
>variant that retransmits a segment less than one RTT after it was
>originally sent.  You reference 3517bis in the subject.  The algorithm
>specified in RFC 3517 and 3517bis *does not* retransmit a segment in
>less than one RTT.
>
>>    With the changes I have been proposing nearly all errors can be
>>    recovered in less than one RTT.
>
>The only way to recover in less than one RTT is to retransmit blind.
>I.e., retransmit segments without any indication as to whether they have
>arrived at the receiver or not.  One could write such an algorithm.
>And, probably show it fixes lost segments sooner.  But, the question
>would immediately become "at what cost?".  I.e., how many needless
>retransmits are being piled into the network to accomplish this task?
>And, the answer nearly has to be proportional to the benefit you obtain.
>I.e., I bet that as you speculatively retransmit more segments you will
>also spurious retransmit more segments.  
>
>And, this is needless retransmits that we know are being piled into a
>congested network and so are using scarce network resources.  So, all
>around a bad idea.
>
>allman
>
>
>

---

From: Anthony Sabatini <[email-masked]>
Date: Sat, 11 Aug 2012 17:23:58 -0400

All -

After reviewing things a bit more I realize no one has given serious thought to Fragmentation Reassembly Timer, Reordering Time and the pseudo equivalent of three acks that is used to substitute for a more rigorous Reordering Time.

First let us examine fragmentation reassembly timer.  Since, as was pointed out, all fragments are generated at the same time if we do not consider reordering of the fragments then the timer need be no greater than the transmission delay inherent in the fragment length as it relates to link speed plus an amount for processing delay, relatively speaking a very small amount of time.  Even if we include a reroute through a satellite link that adds only 500 ms to the timer, there is NO scenario under which reordering will take over two seconds so with an abundance of caution you could set fragment reassembly time to four seconds and be done with it.  Yet EVERY IP stack sets this value to above fifteen seconds (Linux is 15), some at thirty seconds (Microsoft is 30) and the rest at SIXTY SECONDS!! (Solaris, BSD).  These numbers are unsupportable and make fragmentation a good attack vector because of it (interesting note, unlike the operating system people, Cisco who has to deal with this in the real world sets the value to 5 seconds).

Now let us look at 3517bis.  No where is there a mention of Reordering time yet by definition it has to be considered.  Indeed if we did not consider reordering time then we could simply queue the retransmission of a missing segment as soon as a SACK block arrives that implies the segment is missing.  As it is if we saved the block and then waited an amount of time equal to the reordering time, if we did not receive an ACK or SACK covering the range we could and should queue it for retransmission WHETHER WE RECEIVED ANY ACKs OR SACKs IN THE INTERIM.

The problem is three ACKs is a very very bad way to simulate reordering time since on a busy link it will trigger too early casing duplicate transmissions and if the link goes idle it will fire way to slowly or not at all, even though it could correctly have been used for retransmission with only one occurrence.

Also for you to think about - a Reordering time of greater than .25*RTT degrades the throughput of the link in direct proportion to its value.

.Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

> Date: Fri, 3 Aug 2012 19:37:32 -0400
> From: [email-masked]
> To: [email-masked]
> CC: [email-masked]; [email-masked]; [email-masked]
> Subject: Re: [tcpm] Settling Time and RFC3517bis
> 
> All -
> 
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Joe Touch <[email-masked]>
Date: Sat, 11 Aug 2012 18:16:40 -0500

On Aug 11, 2012, at 4:23 PM, Anthony Sabatini <[email-masked]> wrote:
> First let us examine fragmentation reassembly timer.  Since, as was pointed out, all fragments are generated at the same time

Fragmentation of fragments can also occur, which is not synchronized. 

> if we do not consider reordering of the fragments

We do. 

> then the timer need be no greater than the transmission delay inherent in the fragment length as it relates to link speed plus an amount for processing delay, relatively speaking a very small amount of time.

See multipath routing. 

...
> These numbers are unsupportable and make fragmentation a good attack vector because of it (interesting note, unlike the operating system people, Cisco who has to deal with this in the real world sets the value to 5 seconds).

Implementations regularly trade compliance - and robustness sometimes - for cost. 

The resulting drops aren't well tracked, so we shouldn't assume shore reassembly timers are ok. 

Joe

---

From: Ethan Blanton <[email-masked]>
Date: Sat, 11 Aug 2012 22:01:55 -0400

Anthony Sabatini spake unto us the following wisdom:
> After reviewing things a bit more I realize no one has given serious
> thought to Fragmentation Reassembly Timer, Reordering Time and the
> pseudo equivalent of three acks that is used to substitute for a more
> rigorous Reordering Time.

MANY people have thought about this.  This means only that you are not
familiar with the literature.

    http://scholar.google.com/scholar?q=ip+fragmentation

    http://scholar.google.com/scholar?q=tcp+reordering

The second link seems to have many more useful papers on the first
page, but certainly there is a wealth of information on both.

[snip]

> Even if we include a reroute through a satellite link that adds only
> 500 ms to the timer, there is NO scenario under which reordering will
> take over two seconds so with an abundance of caution you could set
> fragment reassembly time to four seconds and be done with it.

Queuing delay.  The rest of this paragraph is invalid, before and
after this erroneous statement.

[snip]

> Now let us look at 3517bis.  No where is there a mention of Reordering
> time yet by definition it has to be considered.  Indeed if we did not
> consider reordering time then we could simply queue the retransmission
> of a missing segment as soon as a SACK block arrives that implies the
> segment is missing.  As it is if we saved the block and then waited an
> amount of time equal to the reordering time, if we did not receive an
> ACK or SACK covering the range we could and should queue it for
> retransmission WHETHER WE RECEIVED ANY ACKs OR SACKs IN THE INTERIM.

Reordering was *carefully* considered by the community, as well as
specifically by the authors of RFC 3517 and 3517bis, myself included.
I have published several papers and RFCs specifically on TCP
reordering-related issues.  You will find them in the above Google
Scholar link.  Your overly simplistic analysis fails to take into
consideration the basic nature of packet switched networks with best
effort forwarding and forwarding queues.

> The problem is three ACKs is a very very bad way to simulate
> reordering time since on a busy link it will trigger too early casing
> duplicate transmissions and if the link goes idle it will fire way to
> slowly or not at all, even though it could correctly have been used
> for retransmission with only one occurrence.

This is also a problem that has been extensively considered in the
literature.  In fact, it is the precise reason we define the 3517
algorithms in terms of DupThresh, rather than the number 3.  There are
adaptive schemes for tuning DupThresh, as well as networks that simply
use a number larger than three.  Both 5681 and 3517 permit this,
provided that the resulting algorithm is no more aggressive than the
algorithms described in 5681.  See, for example, RFC 4653.

Three dup ACKs is certainly a compromise, but it is not "a very very
bad way to simulate reordering time" -- in fact, it is almost always
correct, and there are studies to show this.  There are certain
network pathologies on which it is reliably wrong, and there are
situations where it may degrade performance by a small constant
factor.  These are a trade-off for the heaps of situations where it
just Does the Right Thing without complicated timers and predictions.
I'm not actually aware of any algorithm that performs markedly better
in a wide range of network situations, but I would be shocked to see
one that is anywhere near as simple.

> Also for you to think about - a Reordering time of greater than
> .25*RTT degrades the throughput of the link in direct proportion to
> its value.

Unecessary retransmissions have a MUCH larger impact than this, as
each spurious retransmission cuts cwnd by 1/2.

You need to carefully revisit your premises, this thread indicates
that you do not understand the interactions of packet switched
networks and reliable transport protocols.  I would be happy to help
you understand these issues, but I will not reply to any more spurious
assertions that the well-studied approaches we are currently taking
are wrong unless they are accompanied by careful analysis and a clear
understanding of the subject matter.

Ethan

---

From: Yuchung Cheng <[email-masked]>
Date: Sun, 12 Aug 2012 10:33:22 -0700

On Sat, Aug 11, 2012 at 2:23 PM, Anthony Sabatini <[email-masked]> wrote:
> All -
>
> After reviewing things a bit more I realize no one has given serious thought
> to Fragmentation Reassembly Timer, Reordering Time and the pseudo equivalent
> of three acks that is used to substitute for a more rigorous Reordering
> Time.
>
> First let us examine fragmentation reassembly timer.  Since, as was pointed
> out, all fragments are generated at the same time if we do not consider
> reordering of the fragments then the timer need be no greater than the
> transmission delay inherent in the fragment length as it relates to link
> speed plus an amount for processing delay, relatively speaking a very small
> amount of time.  Even if we include a reroute through a satellite link that
> adds only 500 ms to the timer, there is NO scenario under which reordering
> will take over two seconds so with an abundance of caution you could set
> fragment reassembly time to four seconds and be done with it.  Yet EVERY IP
> stack sets this value to above fifteen seconds (Linux is 15), some at thirty
> seconds (Microsoft is 30) and the rest at SIXTY SECONDS!! (Solaris, BSD).
> These numbers are unsupportable and make fragmentation a good attack vector
> because of it (interesting note, unlike the operating system people, Cisco
> who has to deal with this in the real world sets the value to 5 seconds).
>
> Now let us look at 3517bis.  No where is there a mention of Reordering time
> yet by definition it has to be considered.  Indeed if we did not consider
> reordering time then we could simply queue the retransmission of a missing
> segment as soon as a SACK block arrives that implies the segment is missing.
> As it is if we saved the block and then waited an amount of time equal to
> the reordering time, if we did not receive an ACK or SACK covering the range
> we could and should queue it for retransmission WHETHER WE RECEIVED ANY ACKs
> OR SACKs IN THE INTERIM.
Hi Anthony,

RFC 5827 suggests a lower dupthresh and similar reordering time logic in the
appendix. I implemented RFC 5827 with features suggested in Appendix A.1 and A.3
 in Linux 3.5. Coincidentally the imlementation waits .25 RTT to
trigger ER as well.

>
> The problem is three ACKs is a very very bad way to simulate reordering time
> since on a busy link it will trigger too early casing duplicate
> transmissions and if the link goes idle it will fire way to slowly or not at
> all, even though it could correctly have been used for retransmission with
> only one occurrence.
>
> Also for you to think about - a Reordering time of greater than .25*RTT
> degrades the throughput of the link in direct proportion to its value.
>
> .Tony
>
> Anthony Sabatini
> 200 West 20th Street
> Apt. 1216
> New York, NY 10011
>
> Phone: (212) 867-7179
> Mobile: (917) 224-8388
>
>
>
>
>> Because of the wording of the original comment it was not clear whether
>> the RTT referred to the generated SACK information from the receiver or the
>> original transmission from the sender. By definition, with respect to the
>> sender, it is not possible to properly retransmit the message in less than
>> one RTT plus Reordering time plus processing time.
>>

---

From: Anthony Sabatini <[email-masked]>
Date: Tue, 14 Aug 2012 14:16:20 -0400

Yuchung -

Thank you for your reference to RFC5827 appendix, it speaks to the issue at hand.

My point has been if you are cleaning up RFC3517 then reference should be made to this in the "bis" draft.  The truth has always been no matter how many ACKs you have seen, if a SACK hole has not been filled in Reordering Time, then the packet can be safely assumed lost.  Obviously this makes you more vulnerable to lost ACKs but the only way to truly fix that would be to adopt my token strategy.  This is why I proposed sending another ACK at .25*RTT if the link goes idle.  This fixes both the Last ACK lost problem and kills a duplicate retransmit if that ACK filled a hole (obviously we would adjust the two times to not collide, probably setting the safety ACK to .20*RTT and the delay before considering a hole valid to .30*RTT for example).

Also as a personal comment 3517bis has a "first read" problem.  You know what you mean but a casual reader does not.  You need to be careful to spell things out and not use words and expressions common to the working group but which may be misunderstood by people lacking that context.

Now with respect to those who say I know nothing and have read nothing - let us get back to the whole theoretical underpinning of the "three ACK" rule, Vern Paxson's 1999 paper "End-to-End Internet Packet Dynamics", which discusses in great detail that at the time the rule is a great substitute for a fixed delay of between 20 ms and 85 ms.  He noted rater pointedly that those numbers were selected based on current link speeds of 56 kbps and 1,544 kbps (T1).  The reason for avoiding short fixed delays in TCP were outlined in RFC791, the fact that timers of that era were based on 60 cycle power line frequency or 33 ms minimum resolution (two ticks since that could be anywhere from 17 to 33 ms).  Obviously all of these assumptions are invalid today when average high speed internet is 4 mbps and we are progressing toward 10 mbps and microsecond timing services are available and wide spread.  As pointed out to me rather forcefully queueing delays are a major issue, which was rather unneccessary as I have been dealing with the issue for the last 40 years, so "three ACKs" is no longer a very useful measure in the real world.  I would, however, point out that there is no router in common use that has enough memory to buffer more than 5 seconds worth of high speed traffic, nor would it want to as the information then delivered would be highly irrelevant. 

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

> From: [email-masked]
> Date: Sun, 12 Aug 2012 10:33:22 -0700
> Subject: Re: [tcpm] Reordering Time and RFC3517bis
> To: [email-masked]
> CC: [email-masked]
>

---

From: Mark Allman <[email-masked]>
Date: Tue, 14 Aug 2012 15:45:26 -0400

Bottom line ...

> so "three ACKs" is no longer a very useful measure in the real world.

Show us.  In other words, make your case empirically.  I have looked at
(ahem) a few traces in my life and read (ahem) a few papers on the
subject and it seems to me the empirical evidence is that three dupacks
is actually pretty useful.  It provides for reasonably timely
retransmission and it is generally able to disambiguate loss from
reordering.  If you have some empirical observation to the
contrary---rather than hand waves---I think we'd all like to see it.

There are known issues with three dupacks in that there are cases when
you don't or can't get three dupacks back.  We have dealt with that in
3517bis, in RFC 3042, in RFC 5827 and the current rtorestart is also
aiming to help that situation.  So, we know it isn't perfect.

So, write down the problem you see, this real world evidence of the
problem and your proposed solution.

allman