Re: [L4s-discuss] Thoughts on cost fairness metric

[rjmcmahon <[e-mail]>]

Hi Sebastian, list,

I'm not sure what "wasting a mark" means. Does it matter if the short 
flows stop on their own accord vs slow down per a mark? Marks that don't 
affect transport don't seem wasted per se, just not an affecting signal. 
Not sure why that's a problem.

On "average/median time between marks/drops"

Should this be a histogram too? In general, I try to support histograms 
as well as central limit theorem (CLT) averaging in stats collections.

I'll probably start with marks - not sure how to do drops with ebpfs in 
a simple way for iperf.

Bob
> Hi Bob, list,
> 
> 
>> On Jun 19, 2023, at 01:48, Bob Briscoe 
>> <in=[e-mail]> wrote:
>> 
>> Sebastian,
>> 
>> Before responding to each point, yes, I agree that the marking 
>> algorithms have to mark 'fairly' and we have to agree how to do that 
>> and improve algorithms over time. But lack of perfection in the 
>> network doesn't stop the congestion-rate being a good metric for iperf 
>> to maintain while network marking algorithms are being improved.
> 
> 	The question is IMHO not so much "perfection" or not, as I subscribe
> to the "good enough" school of problem solving, my question is which
> out of the simple to compute harm measures is the most suitable. I am
> not yet convinced that marking/dropping rate is "it", but it might
> well be good enough...
> 
>> And if anyone quotes iperf harm metrics without knowing or defining 
>> the marking algorithm in use, then others would be right to question 
>> the validity of their results.
> 
> 	Honestly, I would prefer a harm metric that is independent of details
> as much as possible, as is this metric seems not well suited to e.g.
> compare L4S' two queues with each other... (the L-queue generally
> using a higher marking rate)...
> 
> 
>> 
>> Now pls see [BB] inline
>> 
>> On 18/06/2023 11:33, Sebastian Moeller wrote:
>>> Hi List,
>>> 
>>> 
>>>> On Jun 16, 2023, at 23:15, Bob Briscoe 
>>>> <in=[e-mail]> wrote:
>>>> 
>>>> Bob
>>>> 
>>>> That would actually be v useful as a harm metric. For the list, it's 
>>>> essentially the bit rate, but measuring only those packets that are 
>>>> ECN-marked [in units of marked-b/s].
>>> 	This primarily seems to show how much harm the flow suffered from 
>>> the AQM, not how much it actually caused. Granted there is some 
>>> correlation between the two, but no hard causality... Now, if the AQM 
>>> sits behind a min/max flow queuing scheduler the correlation will be 
>>> harder and if it sits behind a single queue "scheduler" it will be 
>>> weaker (especially if the AQM on that single queue is not looking at 
>>> a packets actual sojourn time, but at the estimated sojourn time of a 
>>> virtual packet enqueued at dequeue time, so how much queue a newly 
>>> added packet will have to wait behind). As far as I understand that 
>>> is what L4S recommends for dual queue AQMs, and in that case the 
>>> "harm" can be caused by a later burst (e.g. from a badly-paced flow) 
>>> but assigned to a perfectly well behaving low rate flow.
>>> 	That is IMHO sub-optimal :
>>> a) once congestion hits the best an AQM can do is mark a packet of 
>>> the most contributing flow not the one that has happen to have a 
>>> packet at the head of the queue
>>> b) this clearly assigns blame to the wrong flow
>> 
>> [BB] What you say at '(a)' sounds as if you are considering all the 
>> marking being done at just one point in time. An algorithm that 
>> statistically decides whether to mark each packet as it becomes the 
>> head packet should be able to produce an outcome where packets from 
>> the flow contributing most to congestion are marked more. So I don't 
>> see any basis for what you've said at '(a)'.
> 
> 	[SM] That is part of my point, by stochastically marking packets you
> will sooner or later end up marking more packets of larger flows than
> smaller flows (as in number of packets in the queue over time), but a
> node that experiences congestion now would ideally not randomly
> mark/drop packets but selectively drop packets that have the highest
> likelihood of resulting in a noticeable decrease in the offered load
> and do so as soon as possible. It is the "sooner or later" part in the
> randomly dropping that I consider open to improvements. Now, one
> obviously needs a suitable data structure, if restricted to a single
> queue there is not much one can do... (one could still keep per flow
> stats for each queue entry and consult that when dealing with the head
> of queue packet)
> Case in point, if an AQM marks say a DNS-over-TCP response in all
> likelihood it might as well not marked that packet at all, the flow
> likely is too short to ever throttle down enough for the load at the
> bottleneck to subside... same for a flow that is already at the
> minimal congestion window. From a responsiveness perspective these
> marks are wasted... (real drops at least reduce the bottleneck queue
> but marking "unresponsive" flows (there are valid reasons for a flow
> not being able to respond to marking, so that is not necessarily
> nefarious) is not going to help).
> 
> 
> 
>> 
>> There are many things we (the community) still don't understand about 
>> apportionment of blame for congestion. But one thing we can be certain 
>> of is that the best solution will not involve heaping all the blame 
>> onto a single flow.
> 
> 	[SM] I respectfully disagree, there are situations when a single flow
> monopolizes the lion's share of a bottlenecks capacity (e.g. single
> flow TCP dowwnload on a home link) so this flow will also cause the
> lion's share of the queue build-up, so heaping most of the
> responsibility on that flow seems imminently reasonable. We seem to
> agree that talking in absolutes (all the blame) makes little sense...
> 
> 
>> Where a number of flows behave the same or similarly, that would 
>> produce a very unstable outcome.
> 
> 	[SM] In my experience, having run FQ schedulers in one form or
> another (mostly fq_codel and cake) on my internet access link for over
> a decade now, the link behaves pretty well, with low
> latency-increase-under-load/ high responsineness (for those flows that
> behave well, less well behaved flows will suffer the consequence by
> higher intra-flow queuing). However, that situation, many flows at
> very similar "fatness" is in my experience rather a rare beast, normal
> traffic tends to have loads of short transient flows that never reach
> steady state and that are not in equilibrium with each other. In the
> rare case randomly selecting a flow will be a tad cheaper than
> searching for and selecting the flow with the largest immediate
> queueing contribution, but I am not sure whether it makes all that
> much sense optimizing for the rare case, while the common case is more
> a bi modal distribution with low and high contributing flows.
> 
> 
>> Despite just having said 'one thing we can be certain of', I would 
>> otherwise suggest that anyone who thinks they are certain about what 
>> the solution to the blame apportionment problem is should be very 
>> careful until they have done exhaustive analysis and experimentation. 
>> That includes the above opinions about FQ vs single queue.
> 
> 	[SM] I would call this more a hypothesis, and less an opinion, as I
> explained why the AQM sojourn estimation is designed to increase the
> "speed" of the marking action, not its targeting of relevant flows...
> 
> 
>> 
>> For instance, I myself thought I had hit upon the solution that 
>> marking ought to be based on the delay that each packet causes other 
>> packets to experience, rather than the delay each packet experiences 
>> itself (which is what sojourn delay measures).
> 
> 	[SM] That in essence would mean scaling by packet size if all one
> looks at is individual packets... not sure that would help. If the
> marking entity does not take packet size into account when marking
> then whether  64 octets were marked or ~1500 does not carry precise
> and relevant information, neither about the "magnitude" of the
> congestion, nor about the magnitude of the contribution of that flow
> to the congestion. To be able to extract that informatio from a mark
> the marking entity would need to take that into account.
> 	BTW, in a sense that is what a min/max fq-scheduler does offer, the
> flows with most packets in the queue (or rather bytes) will have a
> larger effect on the total queuing delay than flows with fewer packets
> and marking packets from that fat flow will at least solve the "does
> the marked flow contribute meaningful to the congestion" question. But
> the endpoints have still no clue about the bottleneck AQM's marking
> strategy and hence can not make robust inferences.
> 
>> In my experiments so far I turned out to be correct quite often, but 
>> not sufficiently often
> 
> 	[SM] Which is the hallmark of a correlation, not a causation...
> 
>> to be able to say I had found /the/ solution.
> 
> 	[SM] As above indicates I clearly must be misunderstanding how you
> quantify the delay an individual packet introduces, could you
> elaborate, please?
> 
> 
>> I've got a much better grasp of the problem now compared to the 
>> position that had been reached in the late 1990s (when this problem 
>> was last attacked in the research community). However, the latest 
>> results of my simulations have surprised me in one region of the 
>> parameter space. So my experiments are still telling me that I need to 
>> go round the design-evaluate loop at least one more time before I have 
>> something worthy of write-up.
> 
> 	[SM] I would love to read a decent peer-reviewed paper on that.
> 
>> 
>>> 
>>> Now, I wonder how that is going to work out:
>>> rfc3168 flows:
>>> the receiver knows the number of CE marked bytes and could accumulate 
>>> those, but the sender does not, as ECE will be asserted until CWR is 
>>> received independent of whether additional packets were marked.
>>> L4S:
>>> these flows are expected to accumulate more CE marks than classic 
>>> traffic and hence more marked bytes. (also even with accurate ECN 
>>> does the sender unambiguously know which packets where CE marked so 
>>> it can veridically track their size?)
>>> 
>>> So to make sense out of this "measure" the application needs to 
>>> collect information from both ends and aggregate these before 
>>> reporting, something that iperf2 already does, and it will need to 
>>> report ECT(0) and ECT(1) flows/packets separately (assuming that 
>>> ECT(1) means L4S signaling/AQM).
>> 
>> [BB] As I already said, this metric will not mean much if reported in 
>> isolation, without defining the test conditions. That's for peer 
>> reviewers to highlight when results of tests using iperf are reported. 
>> It's doesn't mean it would be inappropriate for iperf to be able to 
>> report this metric in the first place.
> 
> 	[SM] Indeed the best way to figure out whether a measure is useful
> (or how useful it is) seems to actually take it and correlate it with
> other measures of interest. Personally, I would also like to see
> simpler measures, like total number of marks/drops of a measurement
> flow or even average/median time between marks/drops, as I said, also,
> not instead.
> 
> 
>> 
>>> 
>>> 
>>> 
>>>> Even without ECN marking, the congestion cost of a flow could be 
>>>> reported, as the rate of bits lost [in units of lost-b/s] (except of 
>>>> course one cannot distinguish congestion losses from other causes of 
>>>> loss).
>>> 	But see above, even with ECN in practice this measure does not seem 
>>> to be precise, no?
>> 
>> [BB] See previous response.
>> 
>> Nonetheless, it's got more potential as a harm metric for 
>> characterizing dynamic scenarios than any other metric (e.g. various 
>> fairness indices, which only measure rate harm, not latency harm, and 
>> only in steady state scenarios).
> 
> 	[SM] But in non-steady state situations with e.g. the L4S recommended
> sojourn time estimator we will have considerable more mis-targeted
> markings, no? I am not satying the problem is easy to solve, but the
> proposed measure is clearly not ideal either; I am not ruling out that
> it might be an useful compromise. The advantage of looking at the rate
> is that it is a measure which is invariant to the CC-algorithm and
> will easily allow to compare e.g. L- and C-queue flows in L4S.
> 
> 
>> 
>>> 
>>> 
>>>> A specific use would be to test how well a flow could keep within a 
>>>> certain level of congestion cost. For instance, that would test how 
>>>> well a flow would do if  passed through DOCSIS queue protection 
>>>> (without needing to have a DOCSIS box to pass it through). DOCSIS 
>>>> QProt gives a flow a certain constant allowance for the rate it 
>>>> contributes to congestion, which is precisely the cost metric you 
>>>> highlight.
>>> 	[SM] On that note, how is that going to work on variable rate links?
>> 
>> [BB] That's the whole point - the steady-state congestion-rate of each 
>> of a set of scalable flows sharing a link should be invariant whatever 
>> the link rate (and whatever the number of flows).
> 
> 	[SM] A variable rate link will "actively conspire" against reaching
> steady-state...
> 
> 
>> Of course, the challenge is how rapidly a flow's controller responds 
>> when the rate is varying (because nothing ever actually reaches 
>> steady-state). This metric should give a handle on how well or badly a 
>> flow manages to track varying capacity.
> 
> 	[SM] Assuming the marks are actually assigned to the "right"
> packets... (which for flows running long enough should e true, albeit
> the mis-aaprpriation will result in a "noise-floor" for the measure).
> 
>> (Of course there are caveats, e.g. whether the congestion-rate 
>> actually is invariant in the steady state, like the theory says it 
>> should be.)
>> 
>>> 
>>> 
>>>> Other methods for policing latency might do similarly. A few years 
>>>> ago now I was given permission to reveal that a Procera traffic 
>>>> policer used the same congestion cost metric to more strongly limit 
>>>> traffic for those users contributing a higher congestion cost. 
>>>> Unlike rate policers, these policers can inherently take account of 
>>>> behaviour over time.
>>> 	[SM] Curious, does the "over time" part not require to keep per flow 
>>> state for longer?
>> 
>> [BB] A common design for per-flow congestion policers is to only hold 
>> state for badly behaving flows. For example:
>> * A common technique in flow-rate policers is to hold flow-state only 
>> on flows selected probabilistically by randomly picking a small 
>> proportion of those packets that are ECN-marked or dropped. Then the 
>> more a flow is marked, the more likely flow-state will be held on it.
> 
> 	[SM] Such sub-sampling might work for monitoring purposes, but to
> drive an actual controller on this seems more approximate than
> desirable, especially since we aim for a low-latency control loop,
> sub-sampling and averaging suffer from requiring multiple rounds
> before converging on something actionable, no?
> 
> 
>> * In the DOCSIS q-protection algo, the state decays out between the 
>> packets of a flow (freeing up memory for other flows, which also 
>> usually decays out before the next packet of that flow). See 
>> https://datatracker.ietf.org/doc/html/draft-briscoe-docsis-q-protection-06#section-2.1
> 
> 	[SM] It would be great if there were published evaluations of the
> docsis methods. I assume data was acquired and analyzed to come to the
> final design, now it would be nice if that data and analysis could be
> made available...
> 
>> In the Procera case, it held per-user state, not per-flow (a 
>> congestion cost metric aggregates well over a set of flows as well as 
>> over time).
> 
> 	[SM] Makes sense, assuming there are fewer "users" than flows, and
> "user" is a relevant grouping. Is it correct then that they kept per
> user drop/mark probability and hence used different probabilities per
> user? ("User" is a tricky concept, but in cake we use IP address as
> decent proxy and optionally do a first round of arbitration between IP
> addresses (typically "internal" IP addresses to the home network) and
> then do per-flow queueing within each IP's traffic, this takes the
> sting out of using flow-explosion to gain a throughput advantage in
> that this behaviour only affects traffic to/from the same IP while
> other hosts do not even notice; this does obviously not help against
> DOS attacks but it mitigates the simplistic, 'let's use a shipload of
> flows to monopolize the link's capacity' strategy).
> 
> 
> Regards
> 	Sebastian
> 
> 
>>> Also is there any public data showing how this affected RTT-bias?
>> 
>> [BB] In a word, no.
>> 
>> Cheers
>> 
>> 
>> Bob
>> 
>>> 
>>> 
>>>> Since then Procera merged with Sandvine, so I don't know whether 
>>>> that technology is still available.
>>>> 
>>>> Thanks
>>>> 
>>>> 
>>>> Another Bob
>>>> 
>>>> On 16/06/2023 21:20, rjmcmahon wrote:
>>>>> Hi All,
>>>>> 
>>>>> I read the below recently and am wondering if the cost fairness 
>>>>> metric is useful? I'm adding ECN/L4S support from a test 
>>>>> perspective into iperf 2 and thought this new metric might be 
>>>>> generally useful - not sure. Feedback is appreciated.
>>>>> 
>>>>> https://www.bobbriscoe.net/projects/refb/draft-briscoe-tsvarea-fair-02.html
>>>>> 
>>>>> "The metric required to arbitrate cost fairness is simply volume of 
>>>>> congestion, that is congestion times the bit rate of each user 
>>>>> causing it, taken over time. In engineering terms, for each user it 
>>>>> can be measured very easily as the amount of data the user sent 
>>>>> that was dropped. Or with explicit congestion notification (ECN 
>>>>> [RFC3168]) the amount of each user's data to have been congestion 
>>>>> marked. Importantly, unlike flow rates, this metric integrates 
>>>>> easily and correctly across different flows on different paths and 
>>>>> across time, so it can be easily incorporated into future service 
>>>>> level agreements of ISPs."
>>>>> 
>>>>> Thanks,
>>>>> Bob
>>>>> 
>>>> --
>>>> ________________________________________________________________
>>>> Bob Briscoe                               http://bobbriscoe.net/
>>>> 
>>>> --
>>>> L4s-discuss mailing list
>>>> [e-mail]
>>>> https://www.ietf.org/mailman/listinfo/l4s-discuss
>> 
>> --
>> ________________________________________________________________
>> Bob Briscoe                               http://bobbriscoe.net/
>> 
>> --
>> L4s-discuss mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/l4s-discuss