Re: [tsvwg] L4S and the detection of RFC3168 AQMs

[Bob Briscoe <[e-mail]>]

Alex,
As I said yesterday, it was only through Richard reviving this thread 
that I saw your response, which I missed last Dec. Sorry.
See inline tagged [BB]

On 13/12/2020 21:32, [e-mail] wrote:
> Martin,Bob,
>   I'm glad you replied, Martin; firstly for your kind words, but also because Bob's reply below was in my spam folder, so I hadn't seen it. More inline [AB]
>
>
> On Friday, December 11, 2020, 8:11:23 PM GMT, Martin Duke <[e-mail]> wrote:
>
>
> Alex,
>
> Thanks for thinking outside the box like this -- it may be this sort of creativity that gets out of the box we're in.
>
>
> This falls under the "much easier to do in other transports" category, where I could just send a PING or HEARTBEAT marked ECT(0) to test the queue in mid-connection, without affecting the latency of anything that matters. But in the TCP case, I'm not sure how to resolve Bob's second objection (running ECT(0) for a long time would be unacceptable).
>
> On Wed, Dec 9, 2020 at 3:23 PM Bob Briscoe <[e-mail]> wrote:
>>    
>>    Alex,
>>
>> An interesting idea.
>>
>> You've given some pro points.
>> Here are a few con points:
>>
>> 1) Requires L4S FQ AQMs to actively remove Classic ECN support.
>> Many FQ AQMs already support Classic ECN. By this proposal, if they wanted to add L4S ECN support (which is pretty simple to do), they would have to remove Classic ECN support, dropping instead of marking ECT(0) packets. It is possible (likely?) that a number of FQ AQM implementers would vote with their feet and not remove Classic ECN support, even if the IETF published an RFC adopting your proposal. Then the certainty that your proposal is designed to create would be lost. Then we would be worse off in two directions: still no way to be certain about ECT(0) markings, while at the same time having reduced what little Classic ECN deployment there is.
> [AB] That would be a bad outcome. Perhaps the constraint could be modified to allow that FQ AQMs supporting L4S were allowed to mark ECT(0) following RFC3168, so long as they ONLY do so in buckets which have not seen ECT(1) for some period?

[BB] Good point. That would work. To keep this email unambiguous, I'll 
call that A2 (for Alex's idea #2).

It's just occurred to me that, even if an FQ AQM did not implement A2, 
the AQM would still be very unlikely to mark any ECT(0) packets if they 
were mixed into an L4S flow of ECT(1) packets, as long as...:
* the threshold for marking ECT(0) is deeper than for ECT(1);
* and particularly if ECT(1) marking is immediate, whereas ECT(0) 
marking needs persistent queuing
    (e.g. CoDel's requirement to exceed 'target' for the duration of 
'interval').
Reason: at any one time a queue can only have one length. So if the L4S 
flow's congestion control is keeping the queue mostly at the shallow 
operating point, it will hardly ever be able to persistently exceed a 
higher threshold.

I'm not saying your A2 idea wouldn't be worth implementing for stronger 
certainty. I'm just saying that the certainty that ECT(0) packets would 
not be marked by any L4S AQM would still be near-certainty, even if some 
FQ implementers didn't implement A2.


Some detailed thoughts on your A2 idea (skip if you want):

    Within one bucket, after an ECT(1) packet, it could disable ECT(0)
    for the remaining life of the bucket, rather than for a set duration.
    (This straightforward latch would be a little simpler than a timer.
    However, it would be more susceptible to an attack on Classic ECN
    support in which the attacker generates ECT(1) packets with random
    flow IDs and throws them at an FQ. Nonetheless, I'm sure attackers
    would rather spend their time mounting more harmful attacks than this.)


> I think this would also help with your 3) below.

[BB] Definitely.
[To save readers scrolling, my point (3) said Alex's original idea would 
be good for out-of-band testing, but only if it also applies to FQ 
(which it does now, given idea A2)].


> Maybe this would also help with the issues of unfairness with a) tunnels and b) L4S and normal flows hashing to the same bucket, since the queue in that bucket would build up to the point of dropping and then L4S would fall back to reno.

[BB] I'm afraid it won't help. Remember, a single queue can only have 
one length at a time.
If ECT(0) and ECT(1) flows mix in the same bucket (due to hash collision 
or a tunnel that looks like one flow), the ECT(0) flow will not see any 
marking at the shallower threshold, so it will drive the queue to the 
deeper threshold where ECT(0) packets are dropped or marked (depending 
if A2 is implemented or not).  Then, nearly all the ECT(1) packets will 
be marked, because they all arrive at a queue that exceeds the shallower 
threshold.

So the L4S CC will continually yield until it is starved.

Thinking further about idea A2:
Starting from today's situation, with only Classic flows, hash 
collisions and tunnels are detrimental to a small proportion of Classic 
flows. For this small proportion of flows, L4S and idea A2 would add to 
this detriment by disabling ECN as well.

Given long-running flows are relatively rare, two together are more 
rare, two with different ECTs will be even rarer, and two together in a 
tunnel or hash collision are even rarer still, I think that's a 
probability most people could live with. But others might say the sky is 
falling.


> It would need some additional storage per bucket, to track those which have recently seen ECT(1), but that could be a 2 bit countdown counter.

[BB] [Detail: Can be skipped]
I'm intrigued to know how to do this with only a 2-bit counter.
Perhaps whenever a queue sees ECT(1), it sets its counter to 3 then the 
whole scheduler decrements all non-zero counters every T seconds, so 
there will be 2T to 3T duration after the last occurrence of ECT(1) in 
any queue before that queue marks ECT(0) again.

more...

>> 2) For in-band Classic ECN AQM detection, the proposal requires L4S not to be used for a long time in order to detect whether L4S can be used.
>> L4S hosts are the ones that need to check for Classic ECN AQMs. But they don't send ECT(0). So to take advantage of your proposal, they would have to send ECT(1) packets then, if they see one CE marking, they would have to switch to sending ECT(0) packets, and actively send enough ECT(0) to be sure that /lack/ of CE marking was not just lack of congestion. Given CE marking is currently very rare, how long without CE marking do they have to send ECT(0) packets until they can assume it's an L4S AQM? They don't want to alternate ECT0 & ECT1, cos if it is an L4S bottleneck, that will lead to reordering.
>>
>> So, lack of CE marking would be ambiguous. Would it mean the bottleneck is L4S? Would it mean the capacity has increased and the flow needs to increase its rate more to find the limit? If there was a loss or losses, that would also be ambiguous. Are they congestion losses?
>>
>> All the time that the L4S source is sending ECT(0) packets, the flow is losing the benefit of the low delay it could have been getting if the original CE mark was emitted from an L4S queue. This is a similar problem to an algorithm that gives false positives (like the v2 Classic ECN AQM detection that Asad & I published). It sometimes detected an L4S AQM as Classic. So it was argued that this would probably prevent people from using it. The same would surely be true of an algorithm that requires L4S not to be used in order to detect whether L4S can be used.
>>
> [AB] I was indeed assuming that the transport could send ECT(0) probe whenever it wanted, and that probes would not contain data and so would not cause an ordering problem. I admit that I hadn't realised this might be difficult in tcp, although further in the thread Mike Heard and David Black seem to have identified a possible approach.
>
> I am not sure if, supposing a probe can be sent at any time,  this completely addresses your objection. "not using L4S" could be
> a) not using ECT(1) and therefore not getting the benefit of the L queue, or
> b) initially assuming that CE marks have the RFC3168 meaning, rather than the L4S meaning.
>
> If a way is found to send ECT(0) probes without causing reordering, presumably this addresses a)?  b) is more tricky.
>
> Let me take a step back:
>   One approach to getting this WG unstuck, would be to find some fallback algorithm which could easily be shown to be safe, even if it has other deficiencies from the point of view of those who want to deploy L4S. That would remove the most serious objection to starting the experiment; and then the WG might agree that since it would now be safe, the experiment could start, so long as there is a reasonable prospect of developing some improved fallback algorithm  . Once the experiment starts, then it would be easier to test and develop better detection algorithms along side one already known to be safe.
>
> You guys are in a better position to know what kind of deficiencies are tolerable to those who want to use L4S.
>
> The reason probing seems attractive is that, once you assume L4S doesn't mark ECT(0) , if probe packets are arranged such that each RFC3168 CE mark has the same, independent probability of hitting an ECT(0) nprobe packet, then the mathematics is very simple. At the risk of teaching everyone to suck eggs, if the proportion of probe packets is P then the expected number of CE marks until detection is 1/P. For safety, the number of CE marks until detection seems to me the right metric, since if there are no CE marks it's not a problem, and the higher frequency CE marks are, the more we care about detecting.And to calculate statistics about that, we don't need any more information than P, and any more assumptions other than that the frequency of CE marks is nonzero.
>
> Making P large  causes overhead in terms of the number of probe packets, which is one deficiency . On the other hand, even the most safety-minded might be placated with a sufficiently large P, and if also reduces the length of time you might need to wait to decide there is no RFC3168 AQM.

[BB] This all makes sense.

However, one additional consideration makes this much harder: some 
Classic AQMs reduce drop probability for smaller packets (for instance 
DOCSIS PIE [RFC8034; Sec 4.6], which is used as the Classic AQM in the 
DOCSIS dual queue alongside L4S). So the probability calculation would 
need to take into account the relative sizes on the wire of data packets 
and probes. Unfortunately an L4S sender doesn't know which sort of 
Classic AQM it might encounter, so I think it will have to assume the 
worst case.

> I had actually assumed that the L4S team's  intention was to start by assuming that there were no RFC3168 AQMs. This seems to be the behavior of the pseudocode in the paper.

[BB] That's not really a correct way to say it.
Our approach in the experiments in our report was: while a flow is 
starting to measure whether there's a Classic ECN AQM at the bottleneck 
(for perhaps 20 or 30 round trips), It can afford to /behave/ like L4S. 
That's not the same as assuming there are no 3168 AQMs. To justify this, 
as our report says, I checked the original paper onTCP Cubic, and 
convergence was still described as ’short’ when it took one or two 
hundred rounds. Anyway,from the user point of view, surely it's not 
significant if one flow outcompetes another for a few seconds after 
flow-start.

> If that is the case (and the WG accepts it) then there are no false positives at startup. The only reason then  to worry about the amount of time to wait without seeing ECT(0)->CE is if there is an RFC3168 AQM, which you previously detected, and now might no longer be the bottleneck. under those conditions it would seem reasonable to be conservative about switching back.

[BB] How and when did you "previously detect" an RFC3168 ECN AQM? I've 
read this para (and the whole thread) over and over, but I still can't 
work it out.

Whatever, as I say at (3) below, even if this approach cannot detect an 
RFC3168 ECN AQM quickly enough for in-band testing, it could still be 
useful for out-of-band testing.

still more...

>
> On the other hand if L4S transports should start in 'RFC3168  safe mode' and only switch to L4S if it decides that there is no RFC3168 AQM on the bottleneck, or if it is important to switch quickly back when the bottleneck changes, then you do need to make some assumptions about the frequency of marking  (of this stream). Unfortunately I don't have enough knowledge  of tp  (or tcp-prague) to devise such an assumption. Given some worst-case assumption of the rate at which an actually-marking AQM would mark, it would be straightforward to calculate the probability P(we should have seen ECT(0)->CE by now) by standard bayesian reasoning, and the expected number of packets before this probability would fall below a given threshold. But, I do not know if this would be a number that you would like.
>
> Unfortunately I don't have much  spare effort to develop this, but  I hope that has provided food for thought.
>
> Alex
>
>
>
>
>
>> 3) Could be used for Out-of-band Classic AQM detection, but...:
>> The proposal would help server operators who wanted to run pre-L4S-deployment tests to check for the presence of Classic ECN AQMs. Then ehy could run saturating ECT(0) flows for long enough to be sure that lack of CE meant absence of Classic ECN bottlenecks. But only if all L4S implementers complied (see item #1). The fact that this proposal is only really useful for pre-deployment testing would surely make FQ implementers even less keen on removing Classic ECN support.

[BB] I still think out-of-band is where the real merit of the idea lies. 
Especially, because we have your 'A2' idea.

The server could use it as a pre-L4S-deployment check. And/or servers 
could use it to infrequently check different paths in order to check 
whether Classic ECN AQMs have appeared, or to check where they are.

Then all the problems I raised about "not using L4S in order to use L4S" 
would melt away.

Cheers



Bob


>>
>> Perhaps this conversation will spark a variant of your idea. However, in its present form, unless I'm missing something, it doesn't seem to stand up to scrutiny.
>>
>> Cheers
>>
>>
>> Bob
>>
>>
>> On 08/12/2020 19:37, Greg White wrote:
>>
>>
>>>    
>>>    
>>> Hi Alex,
>>>
>>>   
>>>
>>> This does seem worth considering.  FWIW in Low Latency DOCSIS the implementation will be as you describe.  ECT(0) packets will not be marked CE.  This was done for practical reasons, since the classic AQM re-uses the DOCSIS-PIE AQM which is implemented in hardware in many devices, and does not support ECN.  For consistency, any ECT(0) traffic that were to make its way somehow (e.g. DSCP marked as NQB) into the LL queue, will also not be CE marked.
>>>
>>>   
>>>
>>> -Greg
>>>
>>>   
>>>
>>>   
>>>
>>>    
>>> From: "[e-mail]" <[e-mail]>Reply-To: "[e-mail]" <[e-mail]>Date: Monday, December 7, 2020 at 3:44 PMTo: ""[e-mail]"" <[e-mail]>, ""[e-mail]"" <[e-mail]>, Greg White <[e-mail]>Cc: ""[e-mail]"" <[e-mail]>Subject: L4S and the detection of RFC3168 AQMs
>>>
>>>
>>>    
>>>   
>>>
>>>
>>>    Hi all,  At present the DUALQ draft leaves it to implementers to decide if traffic in the classic queue (IE, ECT(0) traffic that uses currently standard congestion controllers) should be dropped or marked (except, apparently, when an ECT(0) packet for some reason turns up in the L queue?). Perhaps it would be wise to specify that during the experiment, deployments of L4S AQMs (whether DUALQ or the other alternatives mentioned in draft-ietf-tsvwg-l4s-arch) SHOULD NOT (or maybe even MUST NOT) mark ECT(0) traffic, and only drop. This would be to preserve the fact that, as currently, those RFC3168 AQMs which are unaware of L4S, can be identified by the fact that they mark ECT(0) packets with CE. If L4S AQMs are required not to mark ECT(0) as CE, then if an endpoint (or other monitoring method) sees a CE mark on an otherwise ECT(0) flow, then it knows with more or less 100% confidence that an RFC3168-only AQM is on the path. Presumably this is safe, since L4S nodes are required to be able to support Not-ECT traffic, and ECT(0) traffic is required to be able to cope with drop.  At present the only definitive way for endpoints identify an RFC3168 AQM in use, is to observe CE marks on an ECT(0) marked flow.Bob's paper [1] gives various other methods, but this seems to be a research project at present. If any of these approaches were found to be reliable, then the above requirement could be relaxed fairly easily; the reverse is not so easy. There are, as is probably obvious, a number of reasons for wanting to identify RFC3168 AQMS: - Current efforts to gather statistics on the number of RFC3168 AQMs which might encounter problems when L4S traffic passes through them. - The the ops draft (sec 3.1)  envisages that CDN operators should test for the presence of RFC3168 AQMs, but doesn't yet specify how this should be achieved - Within a L4S transport protocol, in order to fall back to RFC3168 behavior All of these would presumably be assisted by being able to classify observed ECT(0)->CE transitions unambiguously being the result of an L4S-unaware node. Unless I'm missing something it seems very much worth considering to restrict L4S marking behavior of ECT(0) for the time being? I am not sure which drafts would need updating; DUALQ at least, but presumably the ops draft and maybe L4S-arch. regards, Alex [1] https://arxiv.org/pdf/1911.00710.pdf
>>>
>>>
>> -- 
>> ________________________________________________________________
>> Bob Briscoe                               http://bobbriscoe.net/
>>

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/