Subject: Re: [tcpm] Vicious or Virtuous circle? Adapting reordering window to reordering degree

From: [email-masked]
Date: Wed, 21 Mar 2018 11:46:12 +0100

Bob, Yuchung, Group,

Looking below L3 ECMP, another interesting aspect of relaxing the strict in-order delivery requirement made possible with this work might be environments with limited capabilities to do stochastic flow-based load-balancing across multiple links, e.g. Ethernet LACP, while only very few TCP sessions cross that logical link, like what you find in a typical commercial enterprise environment.

Allowing round-robin load-balancing across links which have link latency differences beyond the skew buffer (e.g. 40G vs 4x 10G LACP) can result in more effective bandwidth on such L2 technologies...

However, I'm of split opinion on this relaxation of the strict in-order delivery requirment. 

Bandwidth can be improved - in particular with situations as mentioned above - but I'm concernd that the effective delivery latency might get worse (more processing overhead in the receiver, to get the data in-order)? Or is that concern misplaced?

One datapoint I would like to see would be a comparison of the receiving tcp stack cpu cost, comparing persistent, heavy reordering at around 1/2 RTT at the same sender bandwidth as a "proper" in-order delivered datastream... 

Best regards,
  Richard

---
Ich habe diese Nachricht mit der GMX Mail App für Windows erstellt.

-----Ursprüngliche Nachricht-----
Von: "Yuchung Cheng" <[email-masked]>
Gesendet: Mittwoch, 21. März 2018 10:23
An: "Bob Briscoe" <[email-masked]>
Cc: "[email-masked] Extensions" <[email-masked]>; [email-masked]
Betreff: Re: [tcpm] Vicious or Virtuous circle? Adapting reordering window to reordering degree

On Tue, Mar 20, 2018 at 11:21 AM, Bob Briscoe <[email-masked]> wrote:
> 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
>
> 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:
>
> 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?
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
>
> On 05/03/18 23:11, [email-masked] wrote:
>
> 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/
>
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>
>
> --
> ________________________________________________________________
> Bob Briscoe                               http://bobbriscoe.net/

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

---

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

> One datapoint I would like to see would be a comparison of the receiving tcp stack cpu cost, comparing persistent, heavy reordering at around 1/2 RTT at the same sender bandwidth as a "proper" in-o…
That's a great point: extreme reordering (e.g. packet spray) today can
cause severe CPU impact
beyond protocol reactions
--> extreme reordering would effectively disable GRO
--> TCP receiver is forced to process packets in MTU unit
--> TCP receiver sends far more ACKs (GRO produces stretched ACKs)
--> TCP sender is overloaded with ACKs acking MSS-worth of bytes a time

On high speed networks (>1Gbps) with Linux, the CPU impact is far more
severe than protocol reactions (e.g. RACK or not) that bottlenecks the
throughput

In general it'd be good to maintain TSO/GRO efficiency when
constructing flowlets, IMO. There is a nice work in SIGCOMM 2015
https://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p465.pdf

---

From: Sowmini Varadhan <[email-masked]>
Date: Sun, 25 Mar 2018 07:36:28 -0400

> However, I'm of split opinion on this relaxation of the strict in-order delivery requirment.
  :
e (more processing overhead in the receiver, to get the data
in-order)? Or is that concern misplaced?
> One datapoint I would like to see would be a comparison of the receiving tcp stack cpu cost, comparing persistent, heavy reordering at around 1/2 RTT at the same sender bandwidth as a "proper" in-o…

In addition to that concern, there is another aspect to excessive re-ordering:
while RACK applies to TCP packets, there are other protocols like IPsec
where excessive re-ordering will result in packet drops as a defense against
replay-protection. Thus you would end up needing to relax your replay window
to dea with excessive reordering, and that, in turn, may not be what you want
for security.  So there are constraints.

--Sowmini

---

From: Yuchung Cheng <[email-masked]>
Date: Sun, 25 Mar 2018 17:36:58 +0100

I completely agree with Olivier and Sowmini that excessive reordering
can be harmful to TCP and non-TCP. There are various concerns beyond
loss detection such as DoS, GRO efficiencies and congestion control. I
will discuss with the co-authors to add more text to RACK draft.

1. incorporate Bob's "bigger picture" of reordering statement
2. more detailed discussion of excessive reordering
3. be very explicit and clear that RACK initially starts with a small
reordering window PLUS 3-dupack threshold (equivalent of standard fast
recovery plus early-retransmit).
4. an experiment section of the goal and what to do.