Re: [tsvwg] ECT(1) Flag Day Plausibility

[Bob Briscoe <[e-mail]>]

Jake,

On 11/05/2021 00:25, Holland, Jake wrote:
> Hi Bob,
>
> I will also cut some stuff in the interest of brevity, and respond
> to just a few points that seemed to me the most useful.
>
> This isn't meant to dismiss anything you raised as unimportant,
> just I'm first focusing on trying to clarify my meaning from the
> prior email where your response indicates I probably didn't get
> some key points across very well.
>
> On 05-09, 7:44 PM, "Bob Briscoe" <[e-mail]> wrote:
>> [BB] Whoa! Where do you get 2% from?
> Sure, let me flesh out my back of the envelope reasoning for my "this
> looks too harmful" position and speak to the 2% hand-wave.
>
> To clarify up front, I'm not really looking at an "all flows" model,
> I'm more looking for an "impact to user experience" framing, for which
> I'll try to articulate a useful straw-man scenario.
>
> Main Question:
>
> Does our lower bound on expected harm put us over our breakage budget
> already, or do we have to look to how much higher than our lower bound
> the harm prevalence would need to be before we can decide?
>
> Background modeling assumptions:
> - lower bound from deployment observations:
>    - at least 0.3% of all internet paths
>    - they might all be fq
> - breakage budget:
>    - 2% rate of "buffering" result on video for these reaches the level
>      of "unacceptable harm"

[BB] Perhaps I'm being thick, but it doesn't say 2% of what, e.g. 
whether it's 2% of flows within some time period, or 2% of videos that a 
family watches at some time during a day, or 2% of flows at each instant 
(you still have to know how long an instant is to be able to calculate 
anything, given there are continual flow arrivals and departures), or 
whatever.

And I think it still doesn't explain where the 2% comes from.

Would you mind explaining this longhand. I'm just not getting it.


>
> Suppose family members are individually watching ABR video on different
> services during their daily free time, some of which have L4S support and
> others of which are classic, and they're at one of the locations with one
> of the more common fq-codel marking AQM deployments.
>
> Sub-question 1:
> How many simultaneous ABR streams among the family will result in a 2%
> collision rate?
>
> Expected hash collisions for n elements in D hash buckets:
>    E = n-D + D((D-1)/D)**n
> (from http://matt.might.net/articles/counting-hash-collisions/)
>
> Set D = 1024 based on the default fq-codel settings in tc:
>
> def e(n):
>    return (n-1024) + 1024 * ((1023/1024.)**n)
>
> This crosses the 2% collision threshold when stepping from 6 to
> 7 active flows:
>
>>>> e(6)0.014629377978053526
>>>> e(7)0.020474466476116504
>>>>
>>>> Here's my other big questionable (but plausible and testable) assumption:
>>>> - ~30-45s+ of collision between ABR video running over L4S with TCP Prague
>>>>    and ABR video running with a classic TCP will likely result in "buffering"
>>>>    for the classic connection.
>>>>
>>>> Then I think about some of the chillaxed family evenings I've seen where
>>>> maybe someone is in their room on Youtube and someone else is in their
>>>> room on Netflix, and Hulu is on the big screen in the family room but the
>>>> 4 people mostly-watching the big screen are also scrolling thru their
>>>> feeds on Reddit, Tiktok, and Facebook and letting those ubiquitous
>>>> 30-60s video clips play.
>>>>
>>>> When that's the scene, whichever services are still on classic endpoints
>>>> are going to be seeing sporadic buffering at a 2% level based on the
>>>> activity of others that are on L4S.

[BB] If I could understand it, this might start to get to the bottom of 
why some people think hash collisions will be a massive problem and 
others don't. Thank you for continuing to try.

Let me try to read out to you all the factors I can see here, some of 
which are silently included in your model:

First, assume we confine ourselves to residential broadband for this 
email - OK willing to do that (but note that mobile doesn't have 
multiple users per access link).

Then:
a) 100% of homes in the population under study have FQ on their access 
link (by definition of the study);
b) 100% of their FQ algos use the worst-case hash algo (without 
set-associative hash);
c) 100% non-upgradeable FQ classifiers
d) Everyone has worst-case 50:50 L4S:Classic traffic mix;
e) Every home has 100% utilization of the access link continuously

All these assumptions lead to over-estimates of the harm. I believe b) 
and e) contribute most greatly to the overestimate, but I'll go through 
them all.


a) A harm metric should be across all users; but I'll be generous and 
allow you to confine the population of the study to those who have 
chosen to use FQ (given, if there is harm, they can never not use FQ to 
avoid it)

b) I thought all CAKE is deployed with the set-associative hash.
Why wouldn't there be deployments of FQ-CoDel with the set-associative 
hash in future / soon / already?
What is the % deployment of the set-associative hash likely to be by the 
time L4S is deployed?
With the set-associative hash:
* What is the probability of at least 2 flows colliding out of 6 flows 
(say)?
* What number of flows leads to 2% probability of at least 2 flows 
colliding?
(I could work that out, but not right now...!)

c) For remotely upgradeable and new FQ deployments, even without the 
set-associative hash, the measures outlined in the last email would 
solely involve classifier changes, perhaps implying they're more trivial 
to implement without resource implications than improving the hash algo, 
i.e.:
i) enabling the shallow threshold for ECT1 by default (it's stateless, 
and it's currently a config option for all ECT).
ii) and classifying on ECN + flow-ID

Bullet (i) means that, if you get a hash collision between Classic and 
L4S, the Classic flow at least dominates the L4S flow, rather than the 
other way round. {Note 1}
Bullet (ii) separates out Classic and L4S for VPNs (in normal 
circumstances, but not if there are also collisions of course). So at 
least Classic doesn't dominate L4S when they are both in the same VPN.

I suspect most ISP-supplied home gateways are remote-upgradeable, and 
would therefore pick up any such changes within a few months (depending 
how long the operator take to validate the change). On a quick search I 
haven't been able to find the percentage of gateways bought from third 
parties in each of the world's main markets, but I'm sure such stats are 
available somewhere.

{Note 1}: Note this will be true starvation of L4S by Classic, not just 
an unfair balance, because the Classic flow is blind to the shallow 
ECT(1) threshold and drives the queue over it. So it might be necessary 
to deploy this change in two stages - first slightly shallower than 
'target' for ECT(0), before going fully shallow.

d) If we assume L4S is successfully deployed, one would certainly expect 
everyone to go through a 50:50 point at some time, but not everyone at 
the same time.

e) A broadband service would be unusable if regular 'busy hour' usage 
was keeping it at 100% utilization, as you describe.
This needs a little more explanation that the previous four items, but 
it's also the most important point....

* As I said, on average /during the busy hour/ a broadband link is about 
2-3% utilized (that was the planning rule I was used to - other 
operators might work differently but not that differently). Operators 
continually grow link capacities as expectations of what people can do 
with the capacity grow. Think back to when 4Mb/s capacity was the norm. 
You wouldn't have expected to be able to run 7 video streaming sessions 
at the same time.

* Given your chillax scenario seems realistic, why isn't 100% 
utilization realistic? It's because there's very little similarity 
between how many /sessions/ seem to be proceeding, and what is actually 
happening on the link when you watch flows and packets. Typically, 
either these sessions are app-limited and not filling the link, or one 
is briefly filling the link to refill the playout buffer then it goes 
idle, so they very rarely all overlap at once.

* If the scenario you describe with these 7 foreground sessions 
continuously consuming 100% of the capacity were ever the norm for more 
than a tiny  percentile of customers, then 1/7 or capacity per flow 
would drop to 1/8 (or say 1/15) whenever another application transferred 
1 more flow (or say 8 more flows) for a few seconds. Then the videos for 
those homes would already be buffering a lot of the time today, due to 
FQ and insufficient capacity.

Note, there are two meanings of 3% utilization depending on the flow 
behaviour:
* Capacity-seeking:
     100% utilization 3% of the time, then flows run in fast but short 
trains, so it's "much less likely" that 7 flows (or whatever the limit 
is) will all coincide, relative to what you were imagining with 100% 
utilization
* App-Limited:
     3% utilization, 100% of the time, then there will never be any 
congestion and no harm
* a mix of the two behaviours:
      which would mean the chance of 7 simultaneous flows was somewhere 
between zero and "much less likely".

___________________________
So, lets go through a) to e) again, putting in variable letters where 
you had assumed 100%:
a) 100% of customers have FQ on their access link [by definition of the 
scenario];
b) b:(100-b)% of their FQ algos use the set-associative : simple hash;
c) c:(100-c)% upgradeable : non-upgradeable FQ classifiers
d) A distribution of L%:C% for the L4S:Classic traffic mix at any one time;
e) Average u% utilization of the access link, with a distribution around 
that. I say u = 2-3%, but let's hear what other operators aim for these 
days.

I suggest you say what reasonable numbers would be for the variables.
Then (assuming no correlation) a weighted average will give a 
back-of-the-envelope harm metric.

It will be orders of magnitude lower than 2%, even taking b) and e) alone.

But this still depends on the questions:
* "2% of flows,... over what period?" and
* where did 2% come from?


>
> This can be a new short-lived 2% buffering event whenever one of the
> scrolling platforms opens a new flow that lasts for a bit too long and
> stabilizes at too high a bitrate, which is plausible because of the
> degree of unfairness on the co-existence problem when there's a
> collision.

[BB] An aside: The large-screen TV, with its higher definition, will be 
wanting to take much higher bit-rate than any of the phones scrolling 
past 'thumbnail' videos. If your 100% utilization model were really 
true, the FQ would be forcing them all to have the same bit-rate and the 
large-screen would be sacrificing its quality, while the FQ would be 
encouraging the small screens to rise to their highest quality. This is 
another reason why 100% utilization is always avoided in practice (and 
why FQ would not be a sensible solution if 100% utilization was common).

>
> Maybe this is too pessimistic?

[BB] I believe it is ultra-pessimistic.

But allegedly "ultra" is a hype word that has been removed from my 
permitted vocabulary. So you're not allowed to understand what I mean, 
even though most English speakers would understand it to mean "extremely 
pessimistic" which is all I was trying to say ;)

> I'm assuming here that an L4S ABR will
> basically not notice the classic flow's existence in a fq collision,
> and will reach its ABR rate based on the achievable bitrate within its
> FQ hash bucket, crowding out the classic flow almost entirely and
> stabilizing at its top rate within ~30-45s, especially given a starting
> target informed by recent history.

[BB] Why assume that? We have figures from large numbers of experiments 
for the rate ratio when the capacity per flow is reduced.
Here's results for L4S vs Cubic over CoDel with different numbers of 
flows in the same queue (without the 3168 fall-back active):
https://l4s.net/ecn-fbk/results_v2.2/baseline/codel_release/#whisker_plots

>
> To me that reaches "already borderline unacceptable" for user experience,
> at a 0.3% scale, and then we remind ourselves that we started with super-
> generous assumptions that could make the scale much worse.
>
> I mean, some people do have vpns,

[BB] That is certainly true for existing FQ systems that are unlikely to 
be upgraded.
For those with upgradeable gateways, using ECN as part of the classifier 
is intended to address that problem.

> and maybe there's some ISPs that did
> turn on shared queue marking after all,

[BB] Yes, that's always a possibility. That's where l4sops comes in.

To be clear, I do not believe the techniques in l4sops to work round 
3168 will be necessary for FQ systems. And I think you will agree once 
we get this collision model closer to reality.


> plus we have good reason to
> believe that 0.3% of paths is undercounted but we're not sure by how much,
> plus who knows when some device on the network is going to decide it
> should download an update, which would *really* crowd out a colliding flow
> if it's L4S.

[BB] Yes. E.g. some people do loads of torrents, etc.

> OTOH, maybe not all of the 0.3%+epsilon paths have 6-person
> families,

[BB] https://en.wikipedia.org/wiki/List_of_countries_by_number_of_households
Sort by number in household, or the % of households with 6+ members. I 
think you'll find you've succumbed to some exaggeration here. 
Particularly if you weight the figures by Internet penetration in each 
country.


> but then again there's also a fair few that share across
> multiple apartments, etc.  I'm taking all this fine detail as "in the
> noise", if we agree that this is scenario is sufficiently realistic
> and already problematic.

[BB] Certainly, IMO, the 100% utilization aspect is far more important. 
But even if we set utilization aside (and we really shouldn't) the no. 
of members per household is not just fine detail. Because birthday 
analysis is sensitive to small changes in the number of simultaneous 
sessions.

For instance, a weighted avg of the above wikipedia table is 3.9 members 
per household worldwide.{Note 2} And, even with your continuously 100% 
utilization scenario and with a simple hash, 4 sessions instead of 6-7 
brings the collision probability down from 2% to below 0.6%. With a 
sensible utilization level, the number of simultaneous sessions drops 
much lower, so I'm sure the collision probability will fall an order of 
magnitude lower, if not two orders.

{Note 2} I suspect if members per household were also weighted by 
Internet penetration, it would tip towards the no. of members per 
household in more affluent countries. For instance, in the top third of 
countries by affluence, 20-40% of households have 1 member. But let's 
not get hung up on these arguments, because it's the utilization figure 
that's critical.



>
> This kind of thinking is what pushes me toward wanting a solid harm
> reduction strategy that doesn't rely on operators' monitoring, especially
> when I think about how they'll be tuning the alert thresholds to whatever
> is easiest on them.

[BB] The idea is that operators analyse their monitoring data to 
/exclude/ all the cases where the CE-marking was due to FQ, because 
operators only need to act on the non-FQ cases.

...because, once we get the utilization model closer to reality, I'm 
convinced the hash collision problem will be tiny (without even needing 
code changes to be deployed, except probably for the VPN case).

>
> I mean sure, Facebook *could* tune it so that they'll get lots of false
> positives and very few false negatives so that they don't crowd out Hulu
> and cause buffering for Dad's Hulu show, but how likely is that?  How are
> they going to respond to the high rate of false positives?  How many
> operators won't just point a finger at someone else?  How will they even
> see the complaints, when it's their competitors that experience the
> buffering video?  Those chillaxed family evenings get a lot less calm
> when people start screaming at each other to stop using the internet so
> they can watch their movie in peace, in my experience.
>
> NB: I'm using recognizable names here by way of example, but I think the
> problem gets worse again when you consider the long tail of niche content
> providers who maybe don't have a dedicated player-optimization team, in
> place of any one of the more famous services.

[BB] I think there's a huge misunderstanding here. I working on the 
basis of no expectation that CDN operators will need to do anything 
about the FQ cases. The monitoring is to find the non-FQ cases.

>
> Maybe I have some importantly wrong assumptions baked in there, but I
> hope it might be possible to at least use it as a basis for some testable
> observables that could resolve the concerns one way or the other.
>
> If this kind of scenario can be shown to be too pessimistic by a couple
> orders of magnitude, I could see changing my mind if we find a way to get
> a handle on the scale of the VPN and shared queue questions.
>
> And similarly, I hope that if these estimates bear out as roughly not-that-
> far-out-of-line, that people will get more concerned about avoiding this
> level of harm as part of an experimental rollout.

[BB] Yes, understanding whether we're looking for
     A) solely non-FQ, or
     B) (non-FQ) AND (cases of FQ where collisions might lead to harm)
is why it's important to get the mental model right. Once it's right, 
I'm sure FQ collisions will be a tiny factor that operators don't have 
to act on (case A).

>
> Anyway, that's my strawman model for the envelope calculation on where
> I'm seeing a potential user experience problem.  I hope it's helpful to
> have it written out.
>
> I've cut a big section adjacent to the "What Use is Top Speed without
> Acceleration?" reference here, in hopes that clarifying the model I was
> using was the thrust of the needed response, but if you'd like me to
> answer more on that, I'll have to leave it to another thread.
>
>>> If you're
>>> unclear, maybe this will help you as it helps me sometimes, 20s
>>> further into this video where she brings the network briefly into
>>> the state under discussion:
>>> https://www.youtube.com/watch?v=g9VfnNTDv-I&t=8m45s )
>> [BB] Do you mean 20 mins not 20s? Even then, I don't see what you're
>> seeing. Perhaps @18 mins?
>> Can you just say what condition you've noticed.
>> Also bear in mind that demo was done before the RTT-independence code
>> was added to Prague.
> Sorry.  I've attached screenshots highlighting the before/after that I
> saw when the queue changed from dualpi2 to pie, in the expectation this
> emulates roughly what we'd see from sharing a queue (either from fq
> collision or otherwise).
>
> This is just one an example of the "extreme unfairness" coexistence
> behavior problem we've discussed many times, I just wanted to
> provide an easy illustration because from some of the comments I
> wasn't sure people had a sense of the scale.
>
> To me this looks like "you probably can't watch ABR video with those
> classic flows", but from some of the discussion I'm not sure everyone
> agrees, so I wanted to point to an example that demonstrated why I'm
> starting there.

[BB] OK, I can see the event in the video you're referring to now: at 
9:04 from the start. Yes - and obviously we have much more data on the 
distribution of that effect for all different link rates and RTTs, 
rather than relying on just one brief instant in a video. In fact the 
same link as before:
https://l4s.net/ecn-fbk/results_v2.2/baseline/codel_release/#whisker_plots

>
>> [BB] The possibility of shared queue Classic AQMs is definitely an
>> unknown...
>>
>> But setting that to one side, and taking your estimate of the likelihood
>> of harm assuming mostly FQ, it seems seriously incorrectly calculated.
>> If this has been the cause of people talking past each other, I don't
>> know how it's gone so spectacularly unnoticed.
> +1, if this is the crux of our misunderstandings, then by all means
> let's stop talking past each other and get this sorted out.
>
> But with that said, I think a lot of people have been talking instead
> about the harm in the unknown scope of the shared queue deployments,
> and this discussion doesn't really speak to those points.
>
> Here I'm mostly trying to point out that that we might not even need
> to debate those points if we have substantial harm scenarios just from
> the FQ collisions, which I think might be able to cut a lot of wheel-
> spinning debate if it holds up.
>
> If it doesn't hold up, I'm not sure it answers the rest of the concerns,
> though it'll be helpful to me to have the point clarified, since I
> think this has been mostly ignored on the list since it was first raised
> as a concern some time ago (I think by Pete?  But it was a while back
> and I'm sure easily lost in the sea of messages.)

[BB] Yes, I have been interpreting concerns about unfairness /within/ FQ 
(resulting from hash collisions) as contrived for the sake of debate. 
Whereas I see now that such concerns can be due to how people understand 
how flow arrivals, departures and congested periods relate to the 
sessions we see at the human level.


>
>> [BB] Only now do I see that the thing you're describing as a 'flag-day'
>> is "treat ECT1 as NECT". Why? It doesn't need to happen on a 'day',
>> because there's no usage of ECT(1) at present. It could happen over
>> time, starting ASAP.
> Compatible changes that don't cause harm can be rolled out without a
> flag day.
>
> However, incompatible changes that do cause harm need to give fair
> warning and make reasonable attempts to get upgrades rolled out at
> a scale appropriate to avoid a significant amount of harm occurring
> in practice.  This is, to me, what the flag day suggestion is about.
>
> The harm comes when L4S traffic (specifically TCP Prague) starts flowing,
> but the harm caused by those flows comes as a result of today's network
> treatment of ECT(1).
>
> The idea is that if we intend to start rolling out an incompatible
> change that will cause harm, we need to give people (including people
> who do not intend to deploy experimental specs without a well-defined
> rollback option) a safe alternative behavior, and ensure that it's
> rolled out at a suitable scale prior to rolling out any new and harmful
> usage.
>
> I agree that queues could be upgraded with L4S support as part of the
> change without harm, and the flag day can be geared around deprecating
> the 3168 behavior of "Treat ECT(1) as ECT(0)", as opposed to specifying
> which specific ECT(1) behavior should be adopted.  Again, the harm
> doesn't actually start until the traffic starts flowing.
>
> However, if the harm concerns are well-founded, before any TCP Prague
> endpoints can be safely enabled, all (or at least almost-all) previously
> existing queues need to be upgraded with *some* change to how they
> interpret ECT(1).  And many (perhaps most?) of these, for their own
> policy reasons, need to have a standards-track option deployed.  And
> as standards-reviewers, it's our role to make sure that option is
> known to be safe in the presence of L4S traffic by the time L4S
> traffic starts flowing.
>
> This is why I'm saying this approach could use a "treat ECT(1) as NECT"
> document as a prerequisite to a flag day, with L4S traffic to start
> no earlier than the date of the flag day under the presumption (and
> some degree of confirmation) that almost all deployed 3168 queues have
> been upgraded to some kind of safe behavior.
>
> "Treat ECT(1) as NECT" is an option 1 (of RFC 4774) change to RFC 3168
> that could be shipped as a standards-track document and would be safely
> upgradeable from there to L4S behavior, thus the suggestion that it's a
> useful part of making a safely-deployable change.  (Obviously this would
> be instead of the also-safe but not upgradeable to L4S alternative of
> using an ECT(1)->ECT(0) transition as a congestion signal, since it
> has the intractable performance issues you've outlined.)

[BB] I can understand how you're thinking now, and I hope you can see 
that, if a more realistic utilization model leads to a vanishingly small 
likelihood of collisions in FQ, the question of a flag-day is moot, 
unless there are large numbers of shared queue RFC3168 AQMs out there.

>
>> At the same time, it would make sense to classify ECT1 as part of the
>> hash, as I said earlier in this email.
>> That will need some debate.
> /and/
> I'm starting skeptical on this as a solution.
>
> I think this doesn't really avoid hash collisions, it just puts them in
> different places and adds some funny ordering issues.  But if it's worth
> discussing in more depth, that's definitely a topic for another thread.

[BB] Sorry, I didn't explain well. Including ECN in the flow classifier 
is primarily to address the VPN case.
On the assumption that a shallow ECT(1) threshold is also being rolled 
out (which inverts the unfairness problem in Classic's favour).

>> And a debate can be had on other ways to update an FQ-CoDel or CAKE AQM
>> to support L4S, but not here and now.
> Sure, I'm just saying that a known-safe standards track behavior for
> the treatment of ECT(1) in a world with TCP Prague endpoints rolling out
> needs to be an option, if the safety concerns on coexistence are
> legitimate issues.

[BB] We're inexorably converging towards improved mutual understanding.


Bob

>
> Best regards,
> Jake
>
>

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