Subject: [tcpm] I-D Action: draft-ietf-tcpm-rack-03.txt

From: [email-masked]
Date: Mon, 05 Mar 2018 15:11:50 -0800

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the TCP Maintenance and Minor Extensions WG of the IETF.

        Title           : RACK: a time-based fast loss detection algorithm for TCP
        Authors         : Yuchung Cheng
                          Neal Cardwell
                          Nandita Dukkipati
                          Priyaranjan Jha
	Filename        : draft-ietf-tcpm-rack-03.txt
	Pages           : 25
	Date            : 2018-03-05

Abstract:
   This document presents a new TCP loss detection algorithm called RACK
   ("Recent ACKnowledgment").  RACK uses the notion of time, instead of
   packet or sequence counts, to detect losses, for modern TCP
   implementations that can support per-packet timestamps and the
   selective acknowledgment (SACK) option.  It is intended to replace
   the conventional DUPACK threshold approach and its variants, as well
   as other nonstandard approaches.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-tcpm-rack/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-ietf-tcpm-rack-03
https://datatracker.ietf.org/doc/html/draft-ietf-tcpm-rack-03

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-ietf-tcpm-rack-03

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 20 Mar 2018 18:21:13 +0000

Yuchung,

What I was trying to say at the tcpm mic just now.
This could be considered as a first draft of the text you asked me to 
write...

      The Bigger Picture

The reordering degree of a link is not a constant. It evolves (over 
years) dependent on TCP.

  *  From a link designers viewpoint, parallelizing (eg. link bonding)
    is the easiest way to get their link to go faster
      o So their main constraint on speed is reordering and there is
        huge pressure on them to relax that constraint
      o The /only/ thing that is holding them back from introducing more
        reordering is the 3 dupacks in TCP or the RTT/4 rule in RACK-02
  * It is likely RACK will become widespread
  * Given RACK-03 now adapts to the reordering window, link designers
    will introduce more reordering
  * That is GOOD (virtuous circle), but only up to a point (vicious circle).
      o We need to write down what that point is
      o We need to ensure the algorithm stops adapting at that point.

Put in IETF process terms, the draft needs to state the WG's consensus 
of what the goal of the experiment is. Otherwise:

  * we can't judge whether the experiment has succeeded.
  * we can't invent alternative algorithms to better reach the goal.

      TCP Specifics:

TCP cannot tell immediately whether a hole is reordering or loss.
It only knows in hindsight (if the hole gets filled later).

It is good (up to a point) to allow more reordering in the network, and 
repair the reordering within the receive buffer instead.
It is also good (up to a point) for TCP to be able to deem that a loss 
has occurred as quickly as possible.

However,

  * the longer the reordering window, the longer it takes to repair losses
  * the faster loss is repaired, the more spurious retransmissions

These two represent a trade-off between latency and bandwidth efficiency.

Given the reordering window could evolve to grow without bound (see 'the 
bigger picture'),...
...Where is the best trade-off point?

What assumption about the answer to this problem did you make when 
designing the algo in RACK-03?

Bob

On 05/03/18 23:11, [email-masked] wrote:
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>

-- 
________________________________________________________________
Bob Briscoehttp://bobbriscoe.net/

---

From: Joe Touch <[email-masked]>
Date: Tue, 20 Mar 2018 18:22:57 -0700

Hi, all,

Regarding the fragmentation part of this issue:

At some level, we need to understand that "fragmentation is harmful" is
fundamentally incorrect and misleading.

The reality is that "network devices that rely on transport info without
reconstituting it are harmful".

I.e., any device that forwards, filters, translates, folds, spindles, or
otherwise mutilates IP packets based on transport information needs to
either:

    a) act like the transport endpoint it becomes once it relies on
transport info, and reassemble the fragments into a full packet

or

    b) emulate the net effect of (a) by caching initial fragment state
and processing subsequent fragments in that context (perhaps including
holding non-initial fragments until that initial frag creates that state).

Devices that claim to be line-rate forwarders but can't do the above at
line rate are broken and/or lying about their performance, not
"optimized". Optimization works better than the default; the default
case still has to work.

Joe

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 21 Mar 2018 03:23:31 -0700

On Tue, Mar 20, 2018 at 11:21 AM, Bob Briscoe <[email-masked]> wrote:
> The reordering degree of a link is not a constant. It evolves (over years)
> dependent on TCP.
>
> From a link designers viewpoint, parallelizing (eg. link bonding) is the
> easiest way to get their link to go faster
>
> So their main constraint on speed is reordering and there is huge pressure
> on them to relax that constraint
> The /only/ thing that is holding them back from introducing more reordering
> is the 3 dupacks in TCP or the RTT/4 rule in RACK-02
>
> It is likely RACK will become widespread
> Given RACK-03 now adapts to the reordering window, link designers will
> introduce more reordering
> That is GOOD (virtuous circle), but only up to a point (vicious circle).
>
> We need to write down what that point is
>
> We need to ensure the algorithm stops adapting at that point.
>
> Put in IETF process terms, the draft needs to state the WG's consensus of
> what the goal of the experiment is. Otherwise:
>
> we can't judge whether the experiment has succeeded.
> we can't invent alternative algorithms to better reach the goal.
>
> TCP Specifics:
>
> It is also good (up to a point) for TCP to be able to deem that a loss has
> occurred as quickly as possible.
>
> However,
>
> the longer the reordering window, the longer it takes to repair losses
> the faster loss is repaired, the more spurious retransmissions
>
> What assumption about the answer to this problem did you make when designing
> the algo in RACK-03?
Thank you. I agree we need to clarify the degree of reordering window
TCP should/would tolerate.

We designed RACK based on studying the current traces we collected at
Google. I see largely three kinds of reordering:
1) router parallelism. key symptom: the sub-MSS packet in the end of a
window burst arrives first. the rest follows in order. e.g.
P10,P1,P2,...P9. the reordering degree << min-RTT (except low BW)
2) wireless retransmission/burst at first/last hop: notably 802.11n
block ACK may cause out-of-order delivery of TCP packets. Despite a
reordering buffer is mandated in the spec, not all drivers implement
that. symptom: random permutation of delivery but the degree in time
is usually within the estimated RTT (e.g. SRTT) at the time of
reordering.
3) the path is significantly shorten'd due to traffic engineering -
the reordering degree is unbounded but happens infrequently (i.e. once
many RTTs).

[not observed but a bonus feature]
4) flowlet: ECMP is universally deployed. but being able to tolerate
small degree of reordering enables flowlet idea for better
load-balacning in some cases. That is an elephant flow may use
"slightly different" path at times.

We want TCP to accommodate small-degree but frequent reordering
introduced (i.e. within a round trip) in (1)(2)(4). Therefore RACK
reordering window is cap'd to SRTT. Theoretically max_RTT makes more
sense but we're concerned of bufferbloat.

Although maintaining reordering within an RTT is difficult for route
designers as they don't want to or can't know RTT. 3 DUPACKs is easier
to implement. We're open to wide discussion about this design point --
although it might be better to have a separate draft on this aspect
(similar to Joe's comments) --- and RACK is only one recovery
mechanism that honors the guidelines.

> Bob Briscoe                               http://bobbriscoe.net/

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 21 Mar 2018 10:51:44 +0000

Yuchung,

Thanks. I understand all this.
Responses inline...

> TCP should/would tolerate.
You say TCP "should/would". From your response below, it looks like an 
answer is already in the RACK code.

> sense but we're concerned of bufferbloat.
"Theoretically"? What theory? This is a tradeoff between bandwidth 
efficiency and latency. So why is the answer only related to RTT?

I think you mean "practically" rather than "theoretically". IOW, the 
implementation is constrained by a separate tradeoff that makes it hard 
to work at all, if you wait >SRTT.

But that nearly doubles the time before loss recovery starts (assuming 
link designers eventually make reordering degree expand to fill the 
space available). I think most apps would be happier with some more 
spurious retransmissions but faster recovery.

> mechanism that honors the guidelines.
I think different applications will have different answers - but I 
suspect we could make a guess in TCP and not need a socket option.

However, it's important not to punt difficult but important questions.
It's not safe for tcpm to let you drive this car, if no-one has a clue 
where the brake is.

Bob

Bob

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 21 Mar 2018 04:31:50 -0700

On Wed, Mar 21, 2018 at 3:51 AM, Bob Briscoe <[email-masked]> wrote:
>>> years)
> implementation is constrained by a separate tradeoff that makes it hard to
> work at all, if you wait >SRTT.
>
> But that nearly doubles the time before loss recovery starts (assuming link
> designers eventually make reordering degree expand to fill the space
> available). I think most apps would be happier with some more spurious
> retransmissions but faster recovery.
>
>>
> I think different applications will have different answers - but I suspect
> we could make a guess in TCP and not need a socket option.
>
> It's not safe for tcpm to let you drive this car, if no-one has a clue where
> the brake is.
RACK reo_wnd max is SRTT --> I am open to discuss alternatives but not
under such offensive tone.

How is this punting? I merely meant "how TCP should handle reordering"
may be out-of-scope of a specific loss recovery mechanism -- RACK is
not the only one and would not be the last one.

RACK can not become an RFC w/o consensus no matter what

I ask the chairs to moderate.

>>> This draft is a work item of the TCP Maintenance and Minor Extensions WG
>>> of
>>> the IETF.
>>>
>>>          Title           : RACK: a time-based fast loss detection
>>> algorithm
>>> for TCP
>>>          Authors         : Yuchung Cheng
>>>                            Neal Cardwell
>>>                            Nandita Dukkipati
>>>                            Priyaranjan Jha

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 22 Mar 2018 20:47:50 +0100

Bob,

> This could be considered as a first draft of the text you asked me to write...
> The Bigger Picture
> 
> The reordering degree of a link is not a constant. It evolves (over years) dependent on TCP.
> From a link designers viewpoint, parallelizing (eg. link bonding) is the easiest way to get their link to go faster
> So their main constraint on speed is reordering and there is huge pressure on them to relax that constraint
> The /only/ thing that is holding them back from introducing more reordering is the 3 dupacks in TCP or the RTT/4 rule in RACK-02
> Given RACK-03 now adapts to the reordering window, link designers will introduce more reordering

I agree that parallelising is a nice way to expand the capacity of links, typically in the access. However, link designers should not assume that they can parallelise whatever they want and let TCP figure out what is happening and solve any issue.

If TCP packets are sent over two parallel links that have similar characteristic, then it should work fine. However, as soon as one of these links has different characteristics (in terms of delay, bandwidth, congestion, packet losses), TCP will have difficulties to understand what is happening in the network if it cannot know which packet is sent over which link. A better approach when bonding access links is to expose them to a multipath capable transport layer and let it figure out the characteristics of the different links and use them efficiently. With IPv6, access link designers have the ability to expose multiple addresses to the endhosts and we should encourage this behaviour when those addresses correspond to links with different characteristics

Olivier
-- 

------------------------------
DISCLAIMER.
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify the system manager. 
This message contains confidential information and is intended only for the 
individual named. If you are not the named addressee you should not 
disseminate, distribute or copy this e-mail. Please notify the sender 
immediately by e-mail if you have received this e-mail by mistake and 
delete this e-mail from your system. If you are not the intended recipient 
you are notified that disclosing, copying, distributing or taking any 
action in reliance on the contents of this information is strictly 
prohibited.

---

From: Praveen Balasubramanian <[email-masked]>
Date: Mon, 26 Mar 2018 15:45:32 +0000

There are a lot of assumptions in not just host TCPIP stacks but in networking stack in general that reordering is not the common case. We put in a lot of work to make the common in order case work blazingly fast all the way from the hardware to the software stack. Yes the stack needs to tolerate some reordering but we are not ready for a world where networks build in reordering as a common case. Any such behavior will cause severe performance issues.

How about if the draft specify a minimum reordering threshold in time (RTT/4) and number of packets (3) and leaves the further extension of increasing the threshold as an optional improvement to handle bad network behavior? Without doing tests I cannot determine the memory and CPU impact of allowing it to grow to SRTT worth in time domain. Also I worry about what Bob is saying that this could become a vicious cycle with increasing reordering -- and even if we fix RACK the rest of hardware and software stack will not be ready for it. Deliberate reordering is not an acceptable network behavior, it should only happen during rare events like route flaps or ECMP flaps.

Thanks

From: tcpm [mailto:[email-masked]] On Behalf Of Olivier Bonaventure
Sent: Thursday, March 22, 2018 12:48 PM
To: Bob Briscoe <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [tcpm] Vicious or Virtuous circle? Adapting reordering window to reordering degree

Bob,

  *   From a link designers viewpoint, parallelizing (eg. link bonding) is the easiest way to get their link to go faster

     *   So their main constraint on speed is reordering and there is huge pressure on them to relax that constraint
     *   The /only/ thing that is holding them back from introducing more reordering is the 3 dupacks in TCP or the RTT/4 rule in RACK-02

  *   It is likely RACK will become widespread
  *   Given RACK-03 now adapts to the reordering window, link designers will introduce more reordering
  *   That is GOOD (virtuous circle), but only up to a point (vicious circle).

     *   We need to write down what that point is
     *   We need to ensure the algorithm stops adapting at that point.

If TCP packets are sent over two parallel links that have similar characteristic, then it should work fine.. However, as soon as one of these links has different characteristics (in terms of delay, bandwidth, congestion, packet losses), TCP will have difficulties to understand what is happening in the network if it cannot know which packet is sent over which link. A better approach when bonding access links is to expose them to a multipath capable transport layer and let it figure out the characteristics of the different links and use them efficiently.. With IPv6, access link designers have the ability to expose multiple addresses to the endhosts and we should encourage this behaviour when those addresses correspond to links with different characteristics

Olivier

________________________________
DISCLAIMER.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the system manager. This message contains confidential information and is intended only for the individual named. If you are not the named addressee you should not disseminate, distribute or copy this e-mail. Please notify the sender immediately by e-mail if you have received this e-mail by mistake and delete this e-mail from your system. If you are not the intended recipient you are notified that disclosing, copying, distributing or taking any action in reliance on the contents of this information is strictly prohibited.

---

From: Yuchung Cheng <[email-masked]>
Date: Mon, 26 Mar 2018 09:15:28 -0700

On Mon, Mar 26, 2018 at 8:45 AM, Praveen Balasubramanian
<[email-masked]> wrote:
> There are a lot of assumptions in not just host TCPIP stacks but in
> networking stack in general that reordering is not the common case. We put
> in a lot of work to make the common in order case work blazingly fast all
> the way from the hardware to the software stack. Yes the stack needs to
> tolerate some reordering but we are not ready for a world where networks
> build in reordering as a common case. Any such behavior will cause severe
> performance issues.
>
>
>
> How about if the draft specify a minimum reordering threshold in time
> (RTT/4) and number of packets (3) and leaves the further extension of
> increasing the threshold as an optional improvement to handle bad network
> behavior? Without doing tests I cannot determine the memory and CPU impact
Praveen: thanks for the feedback.

The current draft is already similar to what you described
a) initially reo_wnd=min_RTT/4 and/or dupthresh=3
b) optionally extend reo_wnd up to SRTT based on DSACK.

<quote>
section 5.2
[snip]

Extension 1: Optionally size the window based on DSACK Further, the
   sender MAY leverage DSACK [RFC3708] to adapt the reordering window to
   higher degrees of reordering. ...

Extension 3: Optionally size the window with the classic
   DUPACK threshold heuristic The DUPACK threshold approach in the
   current standards [RFC5681][RFC6675] is simple, and for decades has
   been effective in quickly detecting losses, ....

RACK_update_reo_wnd:
    RACK.min_RTT = TCP_min_RTT()
    If RACK_ext_TCP_ACK_has_DSACK_option():
        RACK.dsack = true

    If SND.UNA < RACK.roundtrip_seq:
        RACK.dsack = false  /* React to DSACK once within a round trip */

    If RACK.dsack:
        RACK.reo_wnd_incr += 1
        RACK.dsack = false
        RACK.roundtrip_seq = SND.NXT
        RACK.reo_wnd_persist = 16 /* Keep window for 16 loss recoveries */
    Else if exiting loss recovery:
        RACK.reo_wnd_persist -= 1
        If RACK.reo_wnd_persist <= 0:
            RACK.reo_wnd_incr = 1

    If in loss recovery and not RACK_ext_TCP_seen_reordering():
        RACK.reo_wnd = 0
    Else if RACK_ext_TCP_dupack_threshold_hit(): /* DUPTHRESH emulation mode */
        RACK.reo_wnd = 0
    Else:
        RACK.reo_wnd = RACK.min_RTT / 4 * RACK.reo_wnd_incr
        RACK.reo_wnd = min(RACK.reo_wnd, SRTT)

</quote>

There are two action items
1) clarify the reo_wnd policy further
2) incorporate the reordering detection algorithm based on SACK

> of allowing it to grow to SRTT worth in time domain. Also I worry about what
> Bob is saying that this could become a vicious cycle with increasing
> reordering -- and even if we fix RACK the rest of hardware and software
> stack will not be ready for it. Deliberate reordering is not an acceptable
> network behavior, it should only happen during rare events like route flaps
> or ECMP flaps.
>
>
>
> Thanks
>
>
>
> I agree that parallelising is a nice way to expand the capacity of links,
> typically in the access. However, link designers should not assume that they
> can parallelise whatever they want and let TCP figure out what is happening
> and solve any issue.
>
>
>
> If TCP packets are sent over two parallel links that have similar
> characteristic, then it should work fine.. However, as soon as one of these
> links has different characteristics (in terms of delay, bandwidth,
> congestion, packet losses), TCP will have difficulties to understand what is
> happening in the network if it cannot know which packet is sent over which
> link. A better approach when bonding access links is to expose them to a
> multipath capable transport layer and let it figure out the characteristics
> of the different links and use them efficiently.. With IPv6, access link
> designers have the ability to expose multiple addresses to the endhosts and
> we should encourage this behaviour when those addresses correspond to links
> with different characteristics
>
>
>
>
>
> Olivier
>
>
>
>
>
> immediately by e-mail if you have received this e-mail by mistake and delete
> this e-mail from your system. If you are not the intended recipient you are
> notified that disclosing, copying, distributing or taking any action in
> reliance on the contents of this information is strictly prohibited.

---

From: Joe Touch <[email-masked]>
Date: Mon, 26 Mar 2018 22:40:25 -0700

> On Mar 26, 2018, at 8:45 AM, Praveen Balasubramanian <[email-masked]> wrote:
> 
> Deliberate reordering is not an acceptable network behavior,

Reordering, dropping, and repeating packets are all valid IP network phenomena. 

There is no need to infer intent to decide otherwise. 

Joe

---

From: Praveen Balasubramanian <[email-masked]>
Date: Tue, 27 Mar 2018 15:24:52 +0000

Agreed they are all valid events and I alluded to some examples in email but they are very rare events and most connections are unaffected. A lot of systems development is about trade-offs and optimizing for the common case is one of the most commonly applied trade-offs. No need to infer intent, but just making TCP loss recovery more resilient to reordering will not address the performance issues across the entire ecosystem if reordering became more prevalent.

-----Original Message-----
From: Joe Touch [mailto:[email-masked]] 
Sent: Monday, March 26, 2018 10:40 PM
To: Praveen Balasubramanian <[email-masked]>
Cc: Olivier Bonaventure <[email-masked]>; Bob Briscoe <[email-masked]>; Yuchung Cheng <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: [tcpm] Vicious or Virtuous circle? Adapting reordering window to reordering degree

Joe

---

From: Joe Touch <[email-masked]>
Date: Tue, 27 Mar 2018 09:29:47 -0700

> On Mar 27, 2018, at 8:24 AM, Praveen Balasubramanian <[email-masked]> wrote:
> 
> just making TCP loss recovery more resilient to reordering will not address the performance issues across the entire ecosystem if reordering became more prevalent

Agreed but we should not be making TCP more brittle or performance-punished as a trade for “blue sky” performance. 

Joe

---

From: Praveen Balasubramanian <[email-masked]>
Date: Tue, 27 Mar 2018 16:46:21 +0000

It has been this way for years. The dup thresh was defined as 3 packets a long time ago. There is no good answer for what the max threshold should be in terms of packets or time. RACK draft is proposing RTT worth but we will need a lot more data. There is trade off between CPU and memory usage here and many implementations can choose to stick to 3 packets or RTT/4. The problem with time domain is that reordering is defined as a function of RTT which is variable so you cannot design for any correct limit. If the RTT is seconds, on a high BDP link this may mean thousands of packets. I think we still need to define a threshold for max packets which is absolute. Nothing in RACK precludes having a max reordering threshold in number of packets.

-----Original Message-----
From: Joe Touch [mailto:[email-masked]] 
Sent: Tuesday, March 27, 2018 9:30 AM
To: Praveen Balasubramanian <[email-masked]>
Cc: Olivier Bonaventure <[email-masked]>; Bob Briscoe <[email-masked]>; Yuchung Cheng <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: [tcpm] Vicious or Virtuous circle? Adapting reordering window to reordering degree

Joe

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 28 Mar 2018 23:52:53 +0100

Yuchung,

> 1) clarify the reo_wnd policy further

At present the draft largely just states the algo without much 
rationale. Now I understand the DSACK-based algo, I have realized it 
contains subtleties that I try to articulate below (pls use as text if 
you want).

Correct me if I'm wrong, but over the years I have detected a (perhaps 
unstated) presumption from some in the TCP community that their aim is 
to eliminate all spurious retransmissions. The DSACK algo doesn't fall 
into that trap, but superficially it looks as if it does.

The subtle part is that it starts off with the 3 DUPACK rule {Note 1}, 
then grows the reordering window from there as long as at least one 
{Note 2} spurious retransmission per RTT is detected. So, for short 
flows (or the beginning of long flows), even if the degree of reordering 
is high:

  * losses will be repaired fast, which is important for short-flow latency
  * and spurious retransmissions will be tolerated, which is OK for a
    few RTTs

If a flow lasts longer, and if the reordering degree is high, the 
reordering window will grow, so:

  * losses will take longer to repair, which is not such a concern for
    elephants {Note 3}
  * spurious retransmissions will be reduced, because the bandwidth
    efficiency of elephants dominates overall bandwidth efficiency.

I think it's important for the draft to explain that it deliberately 
starts by tolerating more spurious retransmissions to keep repair delay 
low for short flows. IOW, it would not be entirely appropriate to cache 
the reordering window learned from prior connections over the same path.

Cheers

Bob

{Note 1}: Alternative initial rules
This could be replaced with a duration in units of time, e.g. SRTT/4, 
but I understand that you wanted to start with traditional behaviour, so 
as not to trigger intrusion detection systems or protocol compliance 
checkers that might punish non-traditional behaviour.

{Note 2}: At least one?
Rather than counting the existence of at least one spurious 
retransmission per RTT, I think it would be preferable to count their 
extent. Then the algo would be collecting the metrics it needs to trade 
off a residual rate of spurious retransmissions against longer delay to 
repair losses. Instead, it keeps on extending the reordering window in 
response to even one spurious retransmission per RTT, whatever the cost 
in delayed loss-recovery (up to the arbitrary hard limit of 1 SRTT).

{Note 3}: Not all elephants are the same.
If an elephant is a single bulk file download, the delay repairing 
losses has negligible effect on performance. However, what looks like an 
elephant from the outside might actually by numerous multiplexed small 
streams (e.g. http2). Then delay repairing losses remains significant, 
potentially holding back a small object with potential collateral damage 
to latency delivering other objects stuck behind the loss (HoL 
blocking). Conclusion: TCP still needs to trade off delay repairing 
losses against spurious retransmissions, even for elephants.

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 29 Mar 2018 00:09:47 +0100

Yuchung,

> I ask the chairs to moderate.

1) Sorry if the way I wrote this caused offence - none intended.
"...if no-one has a clue" was not aimed just at you, it was aimed at the 
whole WG.

I am saying that we are entering dangerous territory if we know we are 
creating a vicious cycle, but we don't know where to stop it. Just 
guessing a max limit (1 SRTT) isn't enough. So IMO we should not proceed 
until someone can give at least some sort of credible reasoning for the 
choice of number (I'm afraid I can't).

Intuitively, a ceiling of 1 SRTT seems of the right order for a 
long-running flow. And starting at RTT/4 seems about right for short 
flows. But I haven't studied the tradeoffs enough to give a reasoned 
argument. I have a feel for the user trade off here (delay recovering 
losses vs. bandwidth efficiency), but I don't know how to factor in 
Praveen's concerns about memory and CPU performance as well.

To be clear, I think RACK is very important, and I want it deployed 
quickly. But if we punt on this question, there will never be a point 
later at which we are forced to find an answer. In the longer term, the 
potential harm could grow to be greater than the benefit of RACK. (Akin 
to the square root scaling in TCP that was punted in 1988, even tho it 
was known to be unscalable and gradually came back to bite us.)

2) Altho the last line of the pseudocode for step 3 in the draft 
implements an upper limit to RACK.reo_wnd, there's nothing in the 
English description (Extension 1 under section 5.2) about this limit. I 
believe it is important that the draft says:

  * there "MUST" be an upper limit to RACK's adaptation to the network's
    reordering degree.
  * why this is necessary - to break the potential vicious cycle
  * why the particular value of the upper limit (currently 1 SRTT) has
    been chosen

Bob

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 29 Mar 2018 01:06:07 +0100

Praveen,

On 27/03/18 17:46, Praveen Balasubramanian wrote:
> It has been this way for years. The dup thresh was defined as 3 packets a long time ago. There is no good answer for what the max threshold should be in terms of packets or time. RACK draft is proposing RTT worth but we will need a lot more data. There is trade off between CPU and memory usage here and many implementations can choose to stick to 3 packets or RTT/4. The problem with time domain is that reordering is defined as a function of RTT which is variable so you cannot design for any correct limit. If the RTT is seconds, on a high BDP link this may mean thousands of packets.
If memory is limited, or if there is a processing performance limit due 
to the scale of the reordering buffer at the receiver, wouldn't the 
correct way to control that be with rwnd?

Then, it occurs to me that RACK is likely to lead to much more buffering 
at the receiver and consequently, the connection more often being 
limited by rwnd.

So, the RACK algo will need to be conditioned on whether the connection 
is cwnd-limited or rwnd-limited (I can't find anything about this in the 
draft).

If the sender is rwnd-limited, I think RACK would need to reduce the 
reordering window, otherwise the cost of avoiding spurious 
retransmissions would not just be retransmission delay, but potentially 
a severe limit to throughput merely because of the large reordering 
window behind any hole in the receive buffer.

> I think we still need to define a threshold for max packets which is absolute. Nothing in RACK precludes having a max reordering threshold in number of packets.
I'm not sure I agree. I think the configured max receive buffer gives 
you the control you need over memory usage and over the performance of 
the reordering process at the receiver. As long as we can work out a 
good way for rwnd to influence the sender's reordering window, I think 
that should be sufficient.

Bob

---

From: Matt Mathis <[email-masked]>
Date: Thu, 29 Mar 2018 04:32:50 +0000

>
> I believe it is important that the draft says:
>
>    - there "MUST" be an upper limit to RACK's adaptation to the network's
>    reordering degree.
>    - why this is necessary - to break the potential vicious cycle
>    - why the particular value of the upper limit (currently 1 SRTT) has
>    been chosen
>
> Yes, however I would amend this s/MUST/SHOULD/ and add text qualifying the
SHOULD (which I volunteered to write).

One of my goals (for years) has been to enable more parallelism in the
network by further relaxing the operational/performance constraint that
packets be in order.   In the aftermath of  the Juniper M160 debacle [1]
one of the comments from the hardware guys was that the market enforced
operational requirement that high speed gear use per flow ECMP (vs per
packet ECMP) roughly doubles the cost of all modern high speed routing
hardware, due to of the complexity of the hashing and extra "routing" step
within the chassis to pin each flow to a single routing engine.  (All
modern high end routers/switches shard the route processing across multiple
processors/chips, but either use an extra hash and routing stage up front
or a post processing resequencing stage to preserve packet order).

There is a 3 way trade off between reordering tolerance, avoiding spurious
retransmissions and fast loss recovery.   Today TCP implementations have
limited reordering tolerance and as a consequence limited ability to
balance the other two.   RACK  makes TCP vastly more tolerant of
reordering.   It also means that we have an opportunity to explicitly
choose the balance between avoiding spurious retransmissions and fast loss
recovery.   Even if RACK can avoid spurious retransmissions for segments
that are a full SRTT late, that is probably not optimal.

The balance between the cost of spurious retransmissions and cost of longer
recovery times is a separate engineering optimization problem, that is at
the heart of your Vicious vs Virtuous circle question.   My answer (and the
text I volunteered to contribute) is that this is a distinct  engineering
problem that is sure to change over time and is out of scope for  the RACK
algorithm document.   For one thing this is actually a very complicated
global Internet optimization problem.  I predict that in the long time
horizon it is far cheaper to fix reordering in the end system than the
switching fabric (data rates are lower, no cache thrashing from interleaved
irrelevant flows, etc), but the transition has to be gradual because in the
short term reordering will badly break some end-systems (as Juniper found
out).

The RACK document should suggest an interim bound on reordering tolerance
(SHOULD) and outline some of the tradeoffs on that bound but make it
explicit that this bound needs to evolve over time.

BTW The Internet would be a whole lot better off if it was ok to do packet
level ECPM "within the chassis" and for "channel bonded interfaces".  I
believe that a 1 ms reordering window would enable this level of reordering
and make a huge difference to the Internet as a whole.   Let me say that
more explicitly: making end-systems tolerate  packets 1 ms out of order,
(would/should) permit us to disable and eventually remove all of the
hardware to support per flow ECMP pinning, and probably save us more than
$1B...

[1] https://en.wikipedia.org/wiki/Juniper_M_Series#M160

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

We must not tolerate intolerance;
       however our response must be carefully measured:
            too strong would be hypocritical and risks spiraling out of
control;
            too weak risks being mistaken for tacit approval.

On Wed, Mar 28, 2018 at 4:09 PM Bob Briscoe <[email-masked]> wrote:

> creating a vicious cycle, but we don't know where to stop it. Just guessing
> a max limit (1 SRTT) isn't enough. So IMO we should not proceed until
> someone can give at least some sort of credible reasoning for the choice of
> number (I'm afraid I can't).
>
> long-running flow. And starting at RTT/4 seems about right for short flows.
> But I haven't studied the tradeoffs enough to give a reasoned argument. I
> have a feel for the user trade off here (delay recovering losses vs.
> bandwidth efficiency), but I don't know how to factor in Praveen's concerns
> about memory and CPU performance as well.
>
> quickly. But if we punt on this question, there will never be a point later
> at which we are forced to find an answer. In the longer term, the potential
> harm could grow to be greater than the benefit of RACK. (Akin to the square
> root scaling in TCP that was punted in 1988, even tho it was known to be
> unscalable and gradually came back to bite us.)
>
>
> implements an upper limit to RACK.reo_wnd, there's nothing in the English
> description (Extension 1 under section 5.2) about this limit. I believe it
> is important that the draft says:
>
>    - there "MUST" be an upper limit to RACK's adaptation to the network's
>    reordering degree.
>    - why this is necessary - to break the potential vicious cycle
>    - why the particular value of the upper limit (currently 1 SRTT) has
>    been chosen
>
>
>
>
> Bob
>
> --

---

From: Michael Welzl <[email-masked]>
Date: Thu, 29 Mar 2018 08:20:09 +0200

+1 to this really good rwnd idea!

cheers
michael

Sent from my iPhone

> On 29 Mar 2018, at 02:06, Bob Briscoe <[email-masked]> wrote:
> 
> Praveen,
> 
> If memory is limited, or if there is a processing performance limit due to the scale of the reordering buffer at the receiver, wouldn't the correct way to control that be with rwnd?
> 
> Then, it occurs to me that RACK is likely to lead to much more buffering at the receiver and consequently, the connection more often being limited by rwnd.
> 
> So, the RACK algo will need to be conditioned on whether the connection is cwnd-limited or rwnd-limited (I can't find anything about this in the draft).
> 
> If the sender is rwnd-limited, I think RACK would need to reduce the reordering window, otherwise the cost of avoiding spurious retransmissions would not just be retransmission delay, but potentially a severe limit to throughput merely because of the large reordering window behind any hole in the receive buffer.
> 
> I'm not sure I agree. I think the configured max receive buffer gives you the control you need over memory usage and over the performance of the reordering process at the receiver. As long as we can work out a good way for rwnd to influence the sender's reordering window, I think that should be sufficient.
> 
> 
> Bob
> 
> 
> --

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 29 Mar 2018 10:05:19 +0100

Matt,

On 29/03/18 05:32, Matt Mathis wrote:
>       * there "MUST" be an upper limit to RACK's adaptation to the
>         network's reordering degree.
>       * why the particular value of the upper limit (currently 1 SRTT)
>         has been chosen
>
> Yes, however I would amend this s/MUST/SHOULD/ and add text qualifying 
> the SHOULD (which I volunteered to write).
>
> network by further relaxing the operational/performance constraint 
> that packets be in order.   In the aftermath of  the Juniper M160 
> debacle [1] one of the comments from the hardware guys was that the 
> market enforced operational requirement that high speed gear use per 
> flow ECMP (vs per packet ECMP) roughly doubles the cost of all modern 
> high speed routing hardware, due to of the complexity of the hashing 
> and extra "routing" step within the chassis to pin each flow to a 
> single routing engine.  (All modern high end routers/switches shard 
> the route processing across multiple processors/chips, but either use 
> an extra hash and routing stage up front or a post processing 
> resequencing stage to preserve packet order).
>
> There is a 3 way trade off between reordering tolerance, avoiding 
> spurious retransmissions and fast loss recovery.   Today TCP 
> implementations have limited reordering tolerance and as a consequence 
> limited ability to balance the other two.   RACK makes TCP vastly more 
> tolerant of reordering.   It also means that we have an opportunity to 
> explicitly choose the balance between avoiding spurious 
> retransmissions and fast loss recovery.   Even if RACK can avoid 
> spurious retransmissions for segments that are a full SRTT late, that 
> is probably not optimal.
It's a 3-way trade off, but reordering tolerance is the independent 
variable, not one of the three *user-experience* impairments that are 
the dependent variables:

 1. bandwidth inefficiency
 2. loss recovery delay
 3. delivery delay (without loss)

Each of these depends on reordering tolerance as follows:

 1. bandwidth inefficiency depends on spurious retransmissions, which
    *reduce* as reordering tolerance increases
 2. loss recovery delay *increases* as reordering tolerance increases
    {Note 1}
 3. delivery delay *reduces* as reordering tolerance increases {Note 2}

That's a trade off that the sender can do on behalf of the end-user. 
It's challenging, cos the three metrics are in different units 
(bandwidth & delay), so it depends on the user's utility for each. But 
at least it's not politically challenging - the end-user buys and 
controls the sending host, which is in control of the trade off.

However, as I said in a previous posting, this doesn't address the 
*cost* trade off in processing and memory terms:

 1. increasing reordering tolerance increases *receiver* memory &
    processing costs
 2. reducing reordering tolerance increases *network* memory and
    processing costs (consequently capping network throughput)

That's a politically challenging trade off: it's a tussle between 
vendors of receivers (typically bought by consumers) and vendors of 
network gear (bought by network operators).

{Note 1}: There are other ways to remove losses, e.g. FEC, ECN. In an 
ideal world, if they were 100% successfully employed, there would be no 
trade off - increasing reordering tolerance would be wholly beneficial.

{Note 2}: Shifting reordering to the end-system reduces head-of-line 
blocking of one stream when another has suffered a loss because it's the 
receiver's job to demultiplex between microflows, which naturally 
removes intra-flow HoL blocking. Also, if there are streams within an 
encrypted microflow (e.g. http2, quic), only the receiver can 
demultiplex the streams to resolve any HoL blocking.

>
> The balance between the cost of spurious retransmissions and cost of 
> longer recovery times is a separate engineering optimization problem, 
> that is at the heart of your Vicious vs Virtuous circle question.   My 
> answer (and the text I volunteered to contribute) is that this is a 
> distinct  engineering problem that is sure to change over time and is 
> out of scope for  the RACK algorithm document.   For one thing this is 
> actually a very complicated global Internet optimization problem.  I 
> predict that in the long time horizon it is far cheaper to fix 
> reordering in the end system than the switching fabric (data rates are 
> lower, no cache thrashing from interleaved irrelevant flows, etc), but 
> the transition has to be gradual because in the short term reordering 
> will badly break some end-systems (as Juniper found out).
I agree with this para...
>
> The RACK document should suggest an interim bound on reordering 
> tolerance (SHOULD) and outline some of the tradeoffs on that bound but 
> make it explicit that this bound needs to evolve over time.
...but I think the way to write this is: "a RACK implementation MUST 
implement an explicit bound", and "it SHOULD be set to value X".

If you want to only say "SHOULD implement an explicit bound", you have 
to be able to give a scenario where it make sense not to have a bound at 
all.

Admittedly, this still allows an implementer to set a stupidly high 
bound, which is no better than not having one. But it allows the doc to 
explain why an explicit bound is essential (which will not be obvious to 
all implementers, unless they understand the bigger picture).

Cheers

Bob

>
> BTW The Internet would be a whole lot better off if it was ok to do 
> packet level ECPM "within the chassis" and for "channel bonded 
> interfaces".  I believe that a 1 ms reordering window would enable 
> this level of reordering and make a huge difference to the Internet as 
> a whole.   Let me say that more explicitly: making end-systems 
> tolerate  packets 1 ms out of order, (would/should) permit us to 
> disable and eventually remove all of the hardware to support per flow 
> ECMP pinning, and probably save us more than $1B...
>
>             too strong would be hypocritical and risks spiraling out 
> of control;
> On Wed, Mar 28, 2018 at 4:09 PM Bob Briscoe <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Yuchung,
>
>     "...if no-one has a clue" was not aimed just at you, it was aimed
>     at the whole WG.
>
>     I am saying that we are entering dangerous territory if we know we
>     are creating a vicious cycle, but we don't know where to stop it.
>     Just guessing a max limit (1 SRTT) isn't enough. So IMO we should
>     not proceed until someone can give at least some sort of credible
>     reasoning for the choice of number (I'm afraid I can't).
>
>     long-running flow. And starting at RTT/4 seems about right for
>     short flows. But I haven't studied the tradeoffs enough to give a
>     reasoned argument. I have a feel for the user trade off here
>     (delay recovering losses vs. bandwidth efficiency), but I don't
>     know how to factor in Praveen's concerns about memory and CPU
>     performance as well.
>
>     To be clear, I think RACK is very important, and I want it
>     deployed quickly. But if we punt on this question, there will
>     never be a point later at which we are forced to find an answer.
>     In the longer term, the potential harm could grow to be greater
>     than the benefit of RACK. (Akin to the square root scaling in TCP
>     that was punted in 1988, even tho it was known to be unscalable
>     and gradually came back to bite us.)
>
>
>     English description (Extension 1 under section 5.2) about this
>     limit. I believe it is important that the draft says:
>
>       * there "MUST" be an upper limit to RACK's adaptation to the
>         network's reordering degree.
>       * why the particular value of the upper limit (currently 1 SRTT)
>         has been chosen
>
>
>
>
>     Bob
>
>     -- 
>     [email-masked] <mailto:[email-masked]>

---

From: Michael Welzl <[email-masked]>
Date: Thu, 29 Mar 2018 13:42:20 +0200

Hi all,

I was just about to propose a socket option for the upper limit on reordering (e.g. as a function of the RTT) - to convey whether an application is latency-critical or not. However, some of what Bob wrote below throws me off… I keep only the relevant bits and reordering them slightly for better context:

> On Mar 29, 2018, at 11:05 AM, Bob Briscoe <[email-masked]> wrote:
> 
> Matt,
> bandwidth inefficiency depends on spurious retransmissions, which reduce as reordering tolerance increases
> loss recovery delay increases as reordering tolerance increases {Note 1}
> delivery delay reduces as reordering tolerance increases {Note 2}
[snip]
> 
> {Note 1}: There are other ways to remove losses, e.g. FEC, ECN. In an ideal world, if they were 100% successfully employed, there would be no trade off - increasing reordering tolerance would be wholly beneficial.

The second sentence here confuses me: undoubtedly, for an application that needs to get stuff in order, reordering can cause delay (considering only one connection). That is, if it is produced e.g. by in-network load balancing that sends some data over a longer-latency path, that delay affects everything. E.g. ECN can’t help that?!

> {Note 2}: Shifting reordering to the end-system reduces head-of-line blocking of one stream when another has suffered a loss because it's the receiver's job to demultiplex between microflows, which naturally removes intra-flow HoL blocking. Also, if there are streams within an encrypted microflow (e.g. http2, quic), only the receiver can demultiplex the streams to resolve any HoL blocking.

But we’re talking about TCP here, and generally I find this paragraph hard to parse. You seem to have a multi-flow scenario in mind that isn’t fully described. To begin with, without Minion’ish trickery, a single TCP connection can only deliver data that arrives in order up to the application, and hence reordering (when some data arrive later, not earlier, because they use a longer-latency path) can cause delay for that application.

A separate thing:

> However, as I said in a previous posting, this doesn't address the cost trade off in processing and memory terms:
> increasing reordering tolerance increases receiver memory & processing costs
> reducing reordering tolerance increases network memory and processing costs (consequently capping network throughput)
About 1, isn’t this perhaps solved by your rwnd idea (your email to Praveen)?
If it is, then the answer to 2 is: fine, we can increase reordering tolerance anyway.

Generally, I agree with the pro-reordering musings in this thread, e.g. from Matt - we have a silly situation in the network today, where TCP acts as if it was a connection oriented network and in-network devices jump through various hoops to maintain this illusion. In fact, the Internet is a packet oriented network, and if we can tweak things a little in a direction that allows people to tune the network in a more packet oriented fashion (instead of TCP-connection-oriented), then that’s a good thing.

Looking at the draft, RACK asks for Experimental status. Couldn’t we see "finding out how much reordering is acceptable” as part of the experiment?  I mean, some version of RACK is in Linux already, and things haven’t broken badly as far as I know.  This experiment would at least let us uncover how severe the processing / memory costs above really are.

Cheers,
ichMael   (Michael, reordered)

---

From: Michael Welzl <[email-masked]>
Date: Thu, 29 Mar 2018 13:44:56 +0200

> On Mar 29, 2018, at 1:42 PM, Michael Welzl <[email-masked]> wrote:
> 
> Hi all,
> 

First, that was a typo - should be “reorder”. Second, I almost missed the irony of this… making things *more* understandable by reordering...

Cheers,
Michael

---

From: Yuchung Cheng <[email-masked]>
Date: Thu, 29 Mar 2018 10:48:04 -0700

Bob Matt Michael Praveen,

I agree most of your points, and will include the excellent texts you
suggested. Here is authors' big plan

1. A new whole big section on the design rationale on reordering
handling in RACK. The current draft is missing or fragmenting this.

2. Exactly document how reordering is and will be detected (instead of
citing another draft). There are caveats in those mechanisms too.

Details:
a. reo_wnd max. SHOULD or MUST. IMO reo_wnd MUST be bounded but the
actual value is RECOMMENDED to be X. X is TBD.

b. rwnd limit. I have to think through this. rwin-limit is very common
during high reordering due to how rwin autotuning is implemented.
restricting reo_wnd (to allow more spurious rtx) during rwin-limit
seems an adverse move. but I do get your points about potential
latency risk.

---

From: [email-masked]
Date: Thu, 29 Mar 2018 17:03:03 -0400

Hi, all, 

Setting the receive window is exactly the way to control both reordering
and loss recovery capability. The two can't be decoupled because they're
basically the same thing - loss is just reordering that hasn't happened
yet. 

Because they're coupled and because loss is more likely to drive the
larger receive window value (i.e., multiple RTTs to allow for
retransmission), what is the point in trying to limit receiver
reordering otherwise? 

As others have noted, IMO the goal here ought to be to figure out how to
make TCP less impacted by reordering - not to try to engineer the
network to do otherwise. 

Bob also noted: 

> ideal world, if they were 100% successfully employed, there would be
> no trade off - increasing reordering tolerance would be wholly
> beneficial.

Not to those who care about latency, not to mention that the increased
latency then drives larger RWIN too. 

In-network reordering trades ordering for delay, which is the wrong
trade-off when delay is more important OR when downstream re-reordering
is possible. 

Joe