Subject: [tsvwg] L4S vs. RFC-4774

From: Jonathan Morton <[email-masked]>
Date: Wed, 16 Feb 2022 13:28:39 +0200

In light of tonight's interim meeting, I'd like to clarify ahead of time my previously stated position regarding L4S' conformance (or lack thereof) with RFC-4774.  L4S claims to comply with RFC-4774's Option 3 for an alternate ECN semantics deployment.  My concern is that this compliance claim has been chosen to maximise L4S' freedom of deployment, without proper regard for the responsibilities that Option 3 places on an alternate-ECN proposal.  Neither does L4S properly comply with the requirements of the other two Options available under RFC-4774.

Section 4.3, which describes Option 3 in detail, begins with a quote from RFC-3168 laying out the standard ECN semantics that an existing ECN-compliant router will expect:

   "Upon the receipt by an ECN-Capable transport of a single CE packet,
   the congestion control algorithms followed at the end-systems MUST be
   essentially the same as the congestion control response to a *single*
   dropped packet.  For example, for ECN-Capable TCP the source TCP is
   required to halve its congestion window for any window of data
   containing either a packet drop or an ECN indication."

It then specifically calls out standards-track TCP congestion control algorithms (currently Reno and CUBIC) and TCP-Friendly Rate Control as exemplar instances of these semantics.  Both of these have the same response to single ECN marks and single packet losses, and are designed to compete fairly with each other for resources at a bottleneck.

RFC-8511 relaxes these requirements slightly, but still requires single CE marks to trigger a Multiplicative Decrease in the congestion window or send rate, merely to a lesser minimum degree than standards-track TCP requires for single packet losses.  L4S does not claim compliance with RFC-8511.

Focusing on the technical requirements for compatibility between existing and alternate-ECN traffic in the presence of an existing router, we come to the following paragraph, which seems tailor-made for the situation that L4S introduces:

   A second requirement for compatibility with routers using default ECN
   is that the end-nodes respond to packets that are marked with the ECN
   codepoint "11" in a way that is friendly to flows using IETF-
   conformant congestion control.  This requirement is needed because
   the "11"-marked packets might have come from a congested router that
   understands only the default ECN semantics, and that expects that
   end-nodes will respond appropriately to CE packets.  This requirement
   would ensure that the traffic using the alternate semantics does not
   `bully' competing traffic that it might encounter along the path, and
   that it does not drive up congestion on the shared link
   inappropriately.

It is obvious prima facie that L4S differs markedly from this behaviour, because its response to a single CE mark is negligible, and certainly much less than its response to a single packet drop.  This has, in fact, been the root cause of much of the controversy in TSVWG over the past three years.

Thus, if an L4S flow ends up in the same queue at an ECN-marking bottleneck as existing TCP traffic, the existing TCP traffic will be "bullied" out of the way - potentially achieving only de-minimis goodput - while the L4S traffic barely even notices its presence.  This analysis, predicted by Sally Floyd many years ago, is borne out by empirical testing under laboratory conditions.

RFC-4774 is an Informational document in the Best Current Practice series.  As such, it does not make normative requirements; uses of "must" and "required" (and similar language) are not capitalised and do not carry normative-requirements meanings.  Nevertheless, the advice it offers is sound, and must not be discarded lightly.

The current version of the l4s-id draft (draft-ietf-tsvwg-ecn-l4s-id-24) includes Section 4.3.1, which purports to justify its status with respect to RFC-4774.  These arguments, though verbosely stated in the draft, boil down to:

1: L4S competes fairly with Classic flows in drop-tail queues.

2: L4S-compliant queues distinguish L4S traffic from Classic traffic and handle them separately.

3: RFC-3168 ECN deployments with shared queues, which RFC-4774 discusses, are rare enough to ignore.

4: RFC-3168 ECN deployments with flow-isolation mechanisms will actively manage L4S flows down to a fair competition rate versus Classic flows, and are the usual method of ECN deployment at present.  RFC-4774 does not discuss this case.

5: Failures of the flow-isolation mechanism in point 4 would cause behaviour equivalent to point 3, but are rare enough to ignore.  These failures can be caused by hash collisions (a fault of the flow-isolation mechanism) or by VPN tunnels actively hiding the distinction between flows from that mechanism.

Point 1 in the above is uncontroversial.  Point 2 has garnered some debate over the effectiveness of the reference L4S qdisc's handling of the two traffic flows, and whether it is sufficiently fair - but at least in principle, it is capable of becoming RFC-4774 compliant, given some focused attention to this detail.  It is in Points 3-5 where serious contention arises, especially in the assertion (paraphrased for brevity) that the dangerous cases are rare enough to ignore, and in the further assertion that the deleterious effects thereof are mild enough to tolerate.

Even if existing RFC-compliant shared-queue ECN routers cannot readily be found, there is no reason whatsoever that such devices could not be deployed in future, since they would still be in compliance with RFC-3168.  It is this *future* deployment of RFC-3168 compliant devices which RFC-4774 intends to protect, as well as existing deployments of RFC-3168 at the present time.  What is more, reliance on the assertion that shared-queue ECN routers are not deployed is at odds with the reference L4S qdisc itself offering shared-queue ECN to non-L4S traffic, and a second shared queue to L4S traffic.  I thus find Point 3 unconvincing.

Compliance with RFC-4774 Option 3 would also take care of Point 5.  As it stands, most deployments of ECN AQM in the Internet are using some version of fq_codel, which performs a simple hash function over 1024 buckets.  By the birthday theorem, this is expected to result in at least one hash collision at half the bottlenecks which have 32 flows passing through them.  Larger numbers of flows result in a still higher rate of hash collisions, while smaller numbers of flows still have some risk of hash collisions.  Mechanisms exist to reduce this prevalence, eg. the set-associative hash function in the Cake qdisc, but even this would result in endemic collisions at Internet scale.

Hash collisions resulting in queue-sharing between conventional flows are tolerable, because conventional flows then merely compete on the usual basis for a share of the reduced capacity that the flow-isolation mechanism allocates collectively to them.  If one of those flows is L4S, however, the non-L4S flows would be bullied out of the way by L4S' much lower sensitivity to CE marks.  Moreover, it would be difficult for the L4S flow to detect that this has occurred, just as it is difficult for it to detect that it is going through a shared-queue ECN AQM of the conventional type.  The conventional flows would be extremely aware that something bad has happened due to their sharply reduced throughput, but are not necessarily aware of L4S' existence, and in any case are almost powerless to avoid the damage.

Ultimately, the L4S draft authors rely on Point 4 to persuade the WG that L4S complies with RFC-4774 Option 3.  This ignores the fact that RFC-4774 itself does not even discuss flow-isolation mechanisms as a possible method of compliance.  If it did, there is every possibility that the problem of hash collisions would also have been discussed, and a warning about specially handling these cases issued.  Instead, RFC-4774 restricts itself to discussing the raw ECN response, which if properly designed, would be *sufficient* to handle the absence or failure of a flow-isolation mechanism.  As noted above, this is not the case for L4S.

I thus conclude that L4S is *not* specified to be compliant with RFC-4774 Option 3, and must therefore justify its compatibility with existing traffic over existing networks by other means.

One such possibility is RFC-4774 Option 2, which requires an alternate-ECN transport to actively verify that the path it traverses supports the alternate-ECN semantics:

   The second option specified above is for the alternate-ECN traffic to
   include a mechanism for ensuring that all routers along the path
   understand and agree to the use of the alternate ECN semantics for
   this traffic.  As an example, such a mechanism could consist of a
   field in an IP option that all routers along the path decrement if
   they agree to use the alternate ECN semantics with this traffic.

	[...]

   Such a mechanism should be robust in the presence of paths with
   multi-path routing, and in the presence of routing or configuration
   changes along the path while the connection is in use.  In
   particular, if this option is used, connections could include some
   form of monitoring for changes in path behavior and/or periodic
   monitoring that all routers along the path continue to understand the
   alternate ECN semantics.

L4S does not specify any mechanism, similar to that described, to explicitly verify that all hops on the path support L4S semantics.  Instead, it relies on the deployment of heuristic detection methods.  This requires evidence that the heuristics are sufficiently robust, at least to reliably detect the most common ECN AQMs currently deployed on the Internet.  Note that the inclusion of these heuristics in the L4S specification could be viewed as a tacit admission that RFC-4774 Option 3 is not an accurate characterisation, but that Option 2 would be more appropriate.

I have tested one of the suggested heuristics and found it to have insufficient discriminatory power, yielding high rates of both false-positives and false-negatives under various tested network conditions.  I have not had the opportunity to test the other suggested heuristics, so I cannot offer any opinions on their actual performance, whether positive or negative.

This record does not fill me with confidence, especially since the reference implementation of L4S does not enable any of these heuristics by default, and thus it is safest to assume that most deployments would de-facto end up using no heuristic at all.  This latter condition would be entirely non-compliant with RFC-4774 Option 2.

The only other possibility under RFC-4774 is Option 1, which requires isolating the alternate-ECN traffic to a network which is *administratively* known to support it.  This is essentially the current situation with DCTCP deployments, which are restricted mainly to the internal traffic of certain datacentres.

The L4S authors have stated clearly that Option 1 is unacceptable to them - which is understandable given that L4S was intended to extend the deployability of something very like DCTCP *beyond* its existing confines.  However, achieving this aim requires showing that such deployment will not harm the existing Internet, and mere assertions are unconvincing.

I believe the above analysis is sufficiently well established and discussed to warrant inclusion in the Shepherd Writeup, in the unfortunate event that the L4S drafts are forwarded to the IESG.

 - Jonathan Morton

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 18 Feb 2022 00:22:26 +0000

Jonathan,

> The current version of the l4s-id draft (draft-ietf-tsvwg-ecn-l4s-id-24) includes Section 4.3.1, which purports to justify its status with respect to RFC-4774.  These arguments, though verbosely st…

[BB] The word count of this review is more than 50% greater than the 
section it reviews, even though it only reviews the first half.

> Even if existing RFC-compliant shared-queue ECN routers cannot readily be found, there is no reason whatsoever that such devices could not be deployed in future, since they would still be in compliance with RFC-3168.  It is this *future* deployment of RFC-3168 compliant devices which RFC-4774 intends to protect, as well as existing deployments of RFC-3168 at the present time.

[BB] The draft says this succinctly: "rarity need not imply small 
numbers, nor that there will be rarity in future." So why does your 
review need to say the above para at all? I think you've stopped reading 
the draft at this point, and started just repeating arguments that 
you've already made (that the draft records if you were to read it).

> What is more, reliance on the assertion that shared-queue ECN routers are not deployed is at odds with the reference L4S qdisc itself offering shared-queue ECN to non-L4S traffic, and a second shared queue to L4S traffic.  I thus find Point 3 unconvincing.

[BB] Eh? L4S and Classic do not share the Classic queue in a DualQ. 
Surely you know this? And the text you are reviewing (quoted here) says 
'single queue', not 'shared queue' anyway:

             The members of the Transport
             Working group are not aware of any current deployments of
             single-queue Classic ECN bottlenecks in the Internet.

> Compliance with RFC-4774 Option 3 would also take care of Point 5.  As it stands, most deployments of ECN AQM in the Internet are using some version of fq_codel, which performs a simple hash functi…

[BB] I've already explained that this incorrect application of the maths 
will grossly overestimate the probability of a collision: See thread: 
"ECT(1) Flag Day Plausibility"
https://mailarchive.ietf.org/arch/msg/tsvwg/Cr_3XbvUIqtSyucGxQAPp2b7p9w/
The birthday paradox gives the probability of at least one collision 
from a static set of N (in your example N=32). But about 99.8% of the 
flows arriving at each bottleneck last for less than a second.

To extend the birthday analogy, rather than the probability that there 
is at least one pair of children sitting in a static class that share a 
birthday, you need to consider random children running through the 
classroom, some staying longer than others but the vast majority running 
straight out again, then calculate the chance that any two that happen 
to both be in the room together share a birthday. Even then, in the flow 
hash case, both flows have to remain in the 'room' for long enough for 
convergence on a fair share of capacity to matter.

For instance, using your example, you have to first calculate the chance 
that 32 flows are all active at the same time in the same bottleneck and 
stay active long enough for coexistence to matter. That is truly 
vanishingly small. Then half of these vanishingly small occasions will 
involve at least one collision. You then have to do the same for 31, 30, 
29... 3, 2, 1 flows (I suspect higher numbers will make very little 
difference to the answer 'cos they will be so unlikely). Taking 3 as an 
exmaple of a low number, the probability that 3 flows coincide for long 
enough is higher, but still small. However, the probability of a hash 
collision between 3 flows is far smaller than between 32 (it's 0.0046% 
in fact, which then has to be multiplied by the low probability of 3 
flows coinciding). Then you add all these products of two tiny numbers 
together and get a bigger, but still tiny sum. Yes, collisions between 
long-running flows /will/ happen, but nothing like as often as you are 
saying.

> Hash collisions resulting in queue-sharing between conventional flows are tolerable, because conventional flows then merely compete on the usual basis for a share of the reduced capacity that the f…

[BB] Rather than checking whether the arguments you have made are 
recorded in the draft, you seem to have stopped reading the draft and 
switched into lecturing mode.

>
> Ultimately, the L4S draft authors rely on Point 4 to persuade the WG that L4S complies with RFC-4774 Option 3.

[BB] If you had continued to read this section of the draft, you would 
have reached the point where it says that L4S will not always comply 
with RFC-4774 (whether Option 3 or any option), and what the approach is 
to remedy this. Quoting (with emphasis added):

    *  Therefore the third bullet inSection 4.3  <https://datatracker.ietf.org/doc/html/draft-ietf-tsvwg-ecn-l4s-id-24#section-4.3>  above allows a
       compromise where coexistence could diverge from the requirements
       in the RFC Series briefly, but mandatory monitoring is required,
       in order to detect such cases and trigger remedial action.  This
       approach*tolerates a brief divergence from the RFCs*  given the
       likely low prevalence and given harm here means a flow progresses
       more slowly than otherwise, but it does progress.
       [I-D.ietf-tsvwg-l4sops  <https://datatracker.ietf.org/doc/html/draft-ietf-tsvwg-ecn-l4s-id-24#ref-I-D.ietf-tsvwg-l4sops>] outlines a range of example remedial
       actions that include alterations either to the sender or to the
       network.  However, the final normative requirement in the third
       bullet ofSection 4.3  <https://datatracker.ietf.org/doc/html/draft-ietf-tsvwg-ecn-l4s-id-24#section-4.3>  above places ultimate responsibility for
       remedial action on the sender.  If coexistence problems with a
       Classic ECN AQM are detected (implying they have not been resolved
       by the network), it says the sender "MUST" revert to a Classic
       congestion control."

> This ignores the fact that RFC-4774 itself does not even discuss flow-isolation mechanisms as a possible method of compliance.  If it did, there is every possibility that the problem of hash collisions would also have been discussed, and a warning about specially handling these cases issued.  Instead, RFC-4774 restricts itself to discussing the raw ECN response, which if properly designed, would be *sufficient* to handle the absence or failure of a flow-isolation mechanism.  As noted above, this is not the case for L4S.

[BB] You seem to have switched out of reading mode and stopped referring 
to anything in the draft or in the WG discussions.
Nonetheless, I've noted that the draft omits that RFC 4774 was written 
before flow isolation became a way to mitigate coexistence problems. We 
can add that.

However, that's solely an omission in the draft - everyone is very much 
aware that FQ is an important isolation technique for L4S that RFC 4774 
did not foresee. Indeed, I pointed out to David that when RFC 4774 uses 
Diffserv as the only example isolation solution, one shouldn't take it 
literally, because it predated the first appearance of FQ-CoDel by over 
5 years. I suggested that RFC 4774 is worth following when it describes 
potential problems, or gives general requirements; but it is unlikely to 
be up to date where solutions are concerned.

(BTW, we can all imagine what RFC 4774 would have said about hash 
collisions, but that would be rather like a king claiming to speak the 
word of God, which conveniently happens to agree with the king. Let's 
please just have the discussion on its own merits, rather than claiming 
what RFC 4774 would have said if it had been written today.)

> I thus conclude that L4S is *not* specified to be compliant with RFC-4774 Option 3, and must therefore justify its compatibility with existing traffic over existing networks by other means.

[BB] As above, the draft doesn't claim that L4S is compliant with Option 3.
indeed, we don't have to slavishly pick one of three outdated options. 
We can allow a mix of approaches, some of which weren't invented back in 
2006, which you would find is explained in this section of the draft 
(and its references), if you had continued reading it.

> I have tested one of the suggested heuristics and found it to have insufficient discriminatory power, yielding high rates of both false-positives and false-negatives under various tested network co…

[BB] Just to bring you back to the task at hand, I thought you were 
reading the draft, which also explains the failings of this algorithm.

> I believe the above analysis is sufficiently well established and discussed to warrant inclusion in the Shepherd Writeup, in the unfortunate event that the L4S drafts are forwarded to the IESG.

[BB] This email demonstrates that you aren't following what the WG is 
doing, or writing. You can't stay focused on reading the WG outputs, 
which state nearly everything you've said here as part of the logic for 
the WG's chosen approach. You've implied that the approach ought to 
include many things that the draft already describes. You've obviously 
stopped reading before you got to the nub of the approach (which the WG 
has been discussing and working on for nearly 2 years now, so the draft 
shouldn't have been the first time you heard it). This has been the way 
the WG chose to resolve your concerns. That is, we're recommending a 
combination of either immediate detection if it can be made to work, or 
live monitoring but offline detection which will involve a brief period 
of non-compliance to RFC 4774. The draft explains why a brief period of 
non-compliance is tolerable, given the degree of harm.

There's no need to reply.

Regards

Bob

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