Subject: [tsvwg] L4S Issue #16: Classic ECN Fall-Back: Tech Report updated ... and standby for more

From: Bob Briscoe <[email-masked]>
Date: Fri, 24 Apr 2020 03:52:18 +0100

tsvwg Folks,

We have posted a significantly expanded update to our Tech Report on 
Classic ECN AQM Fall-Back:
     https://arxiv.org/abs/1911.00710

The top level message is that, in a Classic ECN bottleneck, our proposed 
fall-back algorithm has been successfully ensuring Cubic's flow rate is 
not suppressed significantly more by Prague than it is by Cubic under 
otherwise identical traffic conditions. We're creating a visualization 
of all the results that should be usable by the morning. I haven't yet 
seen a result worse than 48% rate reduction percentage (meaning the 
Cubic rate is at worst 48% slower when competing against TCP  Prague 
than it is when against other Cubic flows in otherwise identical 
conditions).

That worst-case was with 9xPrague vs 1 Cubic plus Cubic background web 
traffic at 12Mb/s link rate and 100ms base RTT. The average "rate 
reduction percentage" so far over all link rates, base RTTs and traffic 
scenarios is 89.2%.

Some summary points:
* There's a slight update to the algorithm we described in the previous 
version last November (much longer smoothing of RTT estimate, and 
adaptive), but other than that it's been working as originally designed.
* The section on Evaluation now includes an overview of the results we 
have been getting (a snapshot before the paper was submitted to arXiv on 
Saturday).
* The extra per ACK processing of the algorithm is 2 bit-shifts, 4 adds 
and a min(); all amenable to pipelining.

And here's the tag of the code (Host Congestion Controls and Network 
AQMs) that we've been using in all the experiments:
https://github.com/L4STeam/linux/releases/tag/testing%2F08-04-2020

Also, please standby for more tomorrow...  We should then have the site 
up and running that will help you to navigate around the thousands of 
plots showing all the results of all the test scenarios, with more 
tests  being added every day, now that we've got it mostly automated.

Bob

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

---

From: Sebastian Moeller <[email-masked]>
Date: Fri, 24 Apr 2020 11:05:52 +0200

Hi Bob, hi Koen

First thanks for following up with more data, for both RFC3169 coexistence and RTT independence!

While I am thankful for more data, I do want to voice my unhappiness with the timing, though.

A) If the paper was submitted almost a week ago, why was it not also posted here immediately on the same Saturday?

B) We are effectively 3 days before the next meeting, that is rather challenging to post a revised paper that was effectively teased at the last interim meeting that late in the game and still expect people to actually read it before the meeting.

C) the RTT website just became announced today on the mailing list.

Since the date of the meeting was known well in advance at least some announcement of major new data to be dropped soon should have been mentioned on the mailing list. 
I am well aware that I risk being considered out of line here again, I would appreciate it in the future if data related to and important for a near term scheduled discussion would be posted with sufficient time to actually allow to read and digest the data. I believe this to be normal courtesy to give sufficient time nnd also generally a simple way to get higher quality feed-back.

Best Regards
	Sebastian

> On Apr 24, 2020, at 04:52, Bob Briscoe <[email-masked]> wrote:
> 
> tsvwg Folks,
> 
> We have posted a significantly expanded update to our Tech Report on Classic ECN AQM Fall-Back:
> The top level message is that, in a Classic ECN bottleneck, our proposed fall-back algorithm has been successfully ensuring Cubic's flow rate is not suppressed significantly more by Prague than it is by Cubic under otherwise identical traffic conditions. We're creating a visualization of all the results that should be usable by the morning. I haven't yet seen a result worse than 48% rate reduction percentage (meaning the Cubic rate is at worst 48% slower when competing against TCP  Prague than it is when against other Cubic flows in otherwise identical conditions).
> 
> That worst-case was with 9xPrague vs 1 Cubic plus Cubic background web traffic at 12Mb/s link rate and 100ms base RTT. The average "rate reduction percentage" so far over all link rates, base RTTs and traffic scenarios is 89.2%.
> 
> 
> Some summary points:
> * There's a slight update to the algorithm we described in the previous version last November (much longer smoothing of RTT estimate, and adaptive), but other than that it's been working as originally designed.
> * The section on Evaluation now includes an overview of the results we have been getting (a snapshot before the paper was submitted to arXiv on Saturday).
> * The extra per ACK processing of the algorithm is 2 bit-shifts, 4 adds and a min(); all amenable to pipelining.
> 
> 
> 
> And here's the tag of the code (Host Congestion Controls and Network AQMs) that we've been using in all the experiments:
> Also, please standby for more tomorrow...  We should then have the site up and running that will help you to navigate around the thousands of plots showing all the results of all the test scenarios, with more tests  being added every day, now that we've got it mostly automated.
> 
> 
> 
> Bob
> 
> --

---

From: Jonathan Morton <[email-masked]>
Date: Fri, 24 Apr 2020 12:48:09 +0300

> On 24 Apr, 2020, at 12:05 pm, Sebastian Moeller <[email-masked]> wrote:
> 

> I am well aware that I risk being considered out of line here again, I would appreciate it in the future if data related to and important for a near term scheduled discussion would be posted with s…

Fortunately, we (the SCE team) noticed that some new code had appeared in the L4S repository, so we began a round of testing ourselves.  I think our results provide a useful counterpoint, even if there is not a lot of time for people to digest it before the meeting.

Briefly comparing our tests to Bob's revised paper, I think the L4S team did a deeper investigation of fewer scenarios, while we performed a lighter survey over a broader range of scenarios, particularly involving a greater variety of queue types.  I think that adequately explains the very different conclusions we draw from our respective data.

 - Jonathan Morton

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 24 Apr 2020 18:01:50 +0100

Sebastian,

Your criticism of the lateness of these results is valid - I can only 
apologise - explanations below, but they don't excuse it.

Had you read the previous version? I don't think I've seen any comments 
from you about it. I tried to help those that had read it by explaining 
that the algo is largely unchanged and pointing to the main diffs.

However, the specific criticisms that the publication of the paper was 
held back for nefarious reasons are not well-founded. Let me explain.

Unfortunately, we are between a rock and a hard place. As well as 
fending off technical criticism (which ideally requires rapid open 
development), we have to continue to use careful open publication 
practices of any new ideas to protect against patent trolls. I'm afraid 
the purpose of publishing through arXiv is to ensure the data of 
publication is verifiable. arXiv published the paper on Tuesday. It 
would have defeated the whole purpose of using arXiv to point to an 
unofficial copy of the submitted paper before then.

Then why did I wait between Tuesday and Thursday?
Well, the paper gives a small selection of the experiments we had done, 
and refers to our online results for more. We had not got all the 
visualization scripts working on that site until last night. So I didn't 
want to draw people onto a site that was broken.

See a later mail for the announcement of that site.

We had the algo working at the time of the first tsvwg interim (as I 
said during the interim). However, as you know, we always publish 
evaluations over a wide range of scenarios. The creation of an automated 
testing environment that outputs useful visualization of the large 
number of results has taken a lot longer than any of us thought it 
would. Running all the tests wasn't the problem (altho it has taken a 
huge long running time to ensure statistical significance). The main 
problem was designing then implementing the visualizations.

Again, I apologise for the lateness.

Regards

Bob

On 24/04/2020 10:05, Sebastian Moeller wrote:
>> On Apr 24, 2020, at 04:52, Bob Briscoe<[email-masked]>  wrote:
>>
>> tsvwg Folks,
>>
>> Bob Briscoehttp://bobbriscoe.net/
>>

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

---

From: Sebastian Moeller <[email-masked]>
Date: Fri, 24 Apr 2020 20:35:35 +0200

Dear Bob,
more below in-line.

> On Apr 24, 2020, at 19:01, Bob Briscoe <[email-masked]> wrote:
> 
> Sebastian,
> 
> Your criticism of the lateness of these results is valid - I can only apologise - explanations below, but they don't excuse it.
> 
> Had you read the previous version? I

	[SM] Yes, I did; I was not terribly happy about the approach though.

> don't think I've seen any comments from you about it.

	[SM] I refrained from commenting upon it to give you time to bring supportive data (I started two response mails and luckily caught myself before sending them out). In retrospect that might have been too optimistic on my side.

> I tried to help those that had read it by explaining that the algo is largely unchanged and pointing to the main diffs.

	[SM] Pretty much what I expected.

> 
> However, the specific criticisms that the publication of the paper was held back for nefarious reasons are not well-founded. Let me explain.
> 
> Unfortunately, we are between a rock and a hard place. As well as fending off technical criticism (which ideally requires rapid open development), we have to continue to use careful open publication practices of any new ideas to protect against patent trolls. I'm afraid the purpose of publishing through arXiv is to ensure the data of publication is verifiable. arXiv published the paper on Tuesday. It would have defeated the whole purpose of using arXiv to point to an unofficial copy of the submitted paper before then.

	[SM] Does a non-peer reviewed article actually offer sufficient shielding against patent trolls? I guess I learned something new.
> Well, the paper gives a small selection of the experiments we had done, and refers to our online results for more. We had not got all the visualization scripts working on that site until last night. So I didn't want to draw people onto a site that was broken.

	[SM] I respectfully submit, that at last a link to the paper should have been send to the list right then with a note that details would follow. Would I have been happy? No, I probably would have commented upon that unhappily as well, but it would have been the right thing to do IMHO.

> We had the algo working at the time of the first tsvwg interim (as I said during the interim). However, as you know, we always publish evaluations over a wide range of scenarios. The creation of an automated testing environment that outputs useful visualization of the large number of results has taken a lot longer than any of us thought it would. Running all the tests wasn't the problem (altho it has taken a huge long running time to ensure statistical significance). The main problem was designing then implementing the visualizations.
> 

	[SM] Fair enough. That still leaves us in a pickle, in that we are going into a discussion on Monday without sufficient time to look at the data and results. At least a note to the mailing list that something was coming should have been possible on Saturday, I believe to allow at least to reserving some time. 

Regards
	Sebastian

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 24 Apr 2020 19:42:38 +0100

Jonathan,

> Fortunately, we (the SCE team) noticed that some new code had appeared in the L4S repository, so we began a round of testing ourselves.  I think our results provide a useful counterpoint, even if t…

[BB]
It is useful to have a "red team" that looks at an algorithm and works 
out scenarios it is likely to fail under. However, so far I'm not overly 
concerned about the cases you have found, as explained below.

Your pages essentially find the following problems, which I'll address 
quickly below for now:
1a) Failure to detect Classic AQMs that has had its AQM settings tightened.
1b) Detects a Classic AQM when it's actually L4S
1c) insensitivity to the delay variation occurring around a packet loss.
2. Insensitivity to packet loss.

The other points about ultra-low delay are general, and not related to 
this algorithm. I'll deal with them elsewhere.

1a) Of course one can make a Classic AQM undetectable by altering its 
configuration so that will evade the heuristics of this algorithm. You 
are welcome to consider this a problem with our algorithm if you want. 
This looks to me more like clutching at straws.

1b) You will see that we have not tried to fix the false positives yet, 
because they only occur in situations where a fairness problem does not 
arise from the detection failure. We do plan to address these to some 
degree, and the tech report I sent out describes how we intend to. If 
you do find genuine cases where these false positives actually affect 
the fairness goal, then we will raise the priority of this question.

1c) I couldn't find anything further in your pages to explain what you 
meant by "insensitivity to the delay variation occurring around a packet 
loss". Please elaborate. This might be related to #2 below, and 
therefore might have gone away now the bug is fixed.

2. The insensitivity to packet loss was a simple bug. Thank you for 
pointing out the symptom. There was no evil intent to ignore losses. 
Olivier has already issued a bug fix, I believe - and thank you again 
for you help on this one.

> Briefly comparing our tests to Bob's revised paper, I think the L4S team did a deeper investigation of fewer scenarios, while we performed a lighter survey over a broader range of scenarios, partic…
The difference is in the dimension of the scenario matrix we're 
exploring first. As you'll see in the mail I just posted, we've so far 
tested 3,000 traffic and parameter scenarios on two AQMs. See 
http://folk.uio.no/asadsa/ecn-fbk/

As I explained in the first tsvwg interim meeting, we planned to start 
with a worst-case AQM (CoDel) that would be hardest to distinguish from 
L4S, then work our way through other AQMs, which we're moving on to now.

I'll go into your more detailed points later, but I wanted to get this 
response out given we haven't left much time for people to track this 
important conversation.

Bob

---

From: Pete Heist <[email-masked]>
Date: Sat, 25 Apr 2020 00:13:48 +0200

Hi Bob,

> On Apr 24, 2020, at 8:42 PM, Bob Briscoe <[email-masked]> wrote:
> 
> Jonathan,
> 
> It is useful to have a "red team" that looks at an algorithm and works out scenarios it is likely to fail under. However, so far I'm not overly concerned about the cases you have found, as explained below.
> 
> Your pages essentially find the following problems, which I'll address quickly below for now:
> The other points about ultra-low delay are general, and not related to this algorithm. I'll deal with them elsewhere.
> 
> 1a) Of course one can make a Classic AQM undetectable by altering its configuration so that will evade the heuristics of this algorithm. You are welcome to consider this a problem with our algorithm if you want. This looks to me more like clutching at straws.

This issue is important to us, so hopefully we can make some progress on it. Now that we’ve shown that changing AQM parameters can lead to false negatives with classic queue detection in place, what’s the constructive path forward here? Here are a few questions I can think of:

1) How much tolerance for starvation do we have?

2) Are we willing to accept that misconfiguring an AQM may lead to starvation?

3) Are we willing to accept that setting shorter latency targets or lower queue limits may lead to starvation?

4) Is it ok if, when starvation occurs due to #2 or #3, that the cause might not be readily apparent to those working on troubleshooting it, or users experiencing it?

5) Are we aware of any common AQM config changes that would trigger a false negative?

Rather than try to answer these myself, it would be great if others interested in this issue could make an attempt. But, I’d also be interested to hear your stance on any of those questions as well, if you feel it would move things forward.

> 1b) You will see that we have not tried to fix the false positives yet, because they only occur in situations where a fairness problem does not arise from the detection failure. We do plan to address these to some degree, and the tech report I sent out describes how we intend to. If you do find genuine cases where these false positives actually affect the fairness goal, then we will raise the priority of this question.
> 
> 1c) I couldn't find anything further in your pages to explain what you meant by "insensitivity to the delay variation occurring around a packet loss". Please elaborate. This might be related to #2 below, and therefore might have gone away now the bug is fixed.
> 
> 
> 2. The insensitivity to packet loss was a simple bug. Thank you for pointing out the symptom. There was no evil intent to ignore losses. Olivier has already issued a bug fix, I believe - and thank you again for you help on this one.
> 
> 
> 
>> 
> The difference is in the dimension of the scenario matrix we're exploring first. As you'll see in the mail I just posted, we've so far tested 3,000 traffic and parameter scenarios on two AQMs. See http://folk.uio.no/asadsa/ecn-fbk/
> 
> As I explained in the first tsvwg interim meeting, we planned to start with a worst-case AQM (CoDel) that would be hardest to distinguish from L4S, then work our way through other AQMs, which we're moving on to now.
> 
> I'll go into your more detailed points later, but I wanted to get this response out given we haven't left much time for people to track this important conversation.
> 
> 
> Bob
>> 
>>  - Jonathan Morton
> 
> --

---

From: Jonathan Morton <[email-masked]>
Date: Sat, 25 Apr 2020 01:49:04 +0300

> On 24 Apr, 2020, at 9:42 pm, Bob Briscoe <[email-masked]> wrote:
> 

You may notice that the plot we illustrated this point with features RED - an old AQM that is notoriously difficult to configure correctly, but widely implemented in hardware.  An AQM that is difficult to configure correctly will, in practice, often be configured incorrectly - and entirely by accident, that is what we initially did.

These are actually the very first settings we tried with RED, *before* we stepped back and realised that a 150KB hard limit at 50Mbps corresponds to just 25ms, and that the default parameters then cause marking to begin at only about 2ms.  It was then that we added a second RED configuration with a 400KB limit, taking the latter from the example in
the tc-red man page.  Incidentally, the man page provides no practical guidance on choosing the limit value correctly.

What's interesting about this is that conventional flows (and SCE ones) were perfectly happy with the 150KB configuration.  A network engineer could easily set this up, run some measurements, and be quite satisfied with the results.  It's also easy to imagine a 100Mbps device with a 256KB buffer that was configured more or less similarly, simply because 256KB was the amount of memory available at the right speed and the right price at the time of manufacture.  So this is a configuration you should expect to encounter in the wild, at least occasionally.

The 400KB configuration begins marking at 5.5ms, which is similar to Codel's default target.  However, if we closely examine those plots, we can see that TCP Prague is basically on the edge of its detection parameters, and still exhibits some L4S-type responses.  The easiest to spot is the roughly 35 seconds it takes to switch into classic fallback mode on the 160ms path, well beyond the 20-second failure criterion mentioned in your paper.  For reference, 160ms corresponds to a Europe to West Coast USA path.

All of which brings mildly into question your initial assumption that Codel would be the "most difficult" AQM to distinguish from L4S.  Assumptions such as these often lead to spherical cows.

But returning to Codel, the default settings are tuned for "typical" Internet paths, whose median is often quoted at 80ms.  Supposing someone had little interest in the world beyond their home state and their ISP's local CDNs, and decided to tune Codel to match that philosophy.  Cake (which uses a version of Codel internally) actually includes a preset keyword for that purpose; "regional" selects 30ms interval, 1.5ms target.  Only a minority of users will bother to change the default, but this alternative setting serves a legitimate use case.

Here is how L4S reacts, predictably:

http://sce.dnsmgr.net/_archive/ect1-2020-04-25T001927/l4s-s2-twoflow/l4s-s2-twoflow-ns-cubic-vs-prague-cake_regional_-20ms_tcp_delivery_with_rtt.svg

Obviously, the behaviour is much better if we leave Cake's FQ features switched on, but that is not the point of the present discussion.

> 1b) You will see that we have not tried to fix the false positives yet, because they only occur in situations where a fairness problem does not arise from the detection failure. We do plan to addre…

But the false positives *would* result in a fairness problem, as mentioned in the text, if a second L4S flow were added which was not subject to the added jitter.  This second flow would squeeze out the one experiencing the false-positive detection, in exactly the same way as it would squeeze out any other conventional-behaving flow.

Granted, this is not a situation directly relevant to friendly coexistence on *existing* networks.  We included false-positive results mainly to point out that there is little if any margin for merely adjusting parameters of the heuristic to include the false-negative cases identified elsewhere.

> 1c) I couldn't find anything further in your pages to explain what you meant by "insensitivity to the delay variation occurring around a packet loss". Please elaborate. This might be related to #2…

We simply mean that TCP Prague apparently did not switch into classic fallback mode, despite the presence of a very strong delay variance signal, when there were also a lot of packet drops.  This was visible also on one of the PIE runs that *did* have ECN marking enabled, but had a hard limit low enough to also cause tail loss on slow-start.  This is of course worth re-testing with the bugfix.

> 2. The insensitivity to packet loss was a simple bug. Thank you for pointing out the symptom. There was no evil intent to ignore losses. Olivier has already issued a bug fix, I believe - and thank…

Nevertheless, I think it is very much worth pointing out that such a serious (if easily solved) bug made it past your test suite, however extensive you say it is.  I think our decision to go for a broad rather than deep approach to testing was the right one.

In the meeting, the discussion over ECT(1) will most likely centre on how each proposal copes with traversing a conventional network.  We think SCE is in an excellent position here, as RFC-3168 compliant behaviour is built into the design.  It is up to you to prove that L4S is just as good - but we have counterexamples, such as the one I linked above.

Ultimately I think what L4S will need to detect with its heuristic is not the latency-controlling behaviour of the AQM, but the presence of competing conventional flows.  It is precisely in the latter case that the potential for starvation exists.  The delay-variance heuristic is a rather poor substitute.

 - Jonathan Morton

---

From: Sebastian Moeller <[email-masked]>
Date: Sat, 25 Apr 2020 11:25:35 +0200

Hi Bob,

more below in-line.

> On Apr 24, 2020, at 20:42, Bob Briscoe <[email-masked]> wrote:
> 
> Jonathan,
> 

	[SM] That or proof that your heuristic is just that, a heuristic that relies an assumptions, and fails if those assumptions are not met. I would feel better if safety mechanisms like the RFC316 fallback, would work reliably and robustly instead. The point being, this RFC3168 failure mode is a direct consequence of the current L4S design and implementation, expecting a robust and reliable work-around seems like a reasonable request. The alternative is to change the L4S design to avoid the failure mode completely, I understand you are loath to do that, but then please make sure that what you propose as cure for the side-effects of your design decision is actually robust and reliable and does not enshrine arbitrary assumptions like a fixed lower bound for rfc3168 introduced RTT variance.

> because they only occur in situations where a fairness problem does not arise from the detection failure. We do plan to address these to some degree, and the tech report I sent out describes how we intend to. If you do find genuine cases where these false positives actually affect the fairness goal, then we will raise the priority of this question.
> 

	[SM] This, similar to the other TCP Prague bug around the interpretation of the signal when to leave slow start, indicates that TCP Prague pretty much is still an active research vehicle with loose nuts and bolts. I would feel better, when the L4S-reference transport implementation would be allowed to reach maturity and stability before trying to unleash the whole thing into the wider internet.