[tsvwg] L4S vs. RFC-4774

[Jonathan Morton <[e-mail]>]

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