Subject: [aqm] Fwd: ECN AQM parameters

From: Bob Briscoe <[email-masked]>
Date: Sat, 9 May 2015 18:20:27 +0100

Dave,

As promised, here's my thoughts on what PIE (and CoDel) should do 
when ECN is enabled.

There's also new info in here that I think is important: CoDel uses 
an RTT estimate in two different places. One has to be the max 
expected RTT, the other should be the (harmonic) mean of expected RTTs.

The former might be 100ms, but the latter is more likely to be 
15-20ms, given most traffic in the developed world these days comes 
from CDNs. This could make significant difference to performance.

Bob

>Date: Tue, 14 Apr 2015 19:59:47 +0100
>To: "Fred Baker (fred)" <[email-masked]>
>From: Bob Briscoe <[email-masked]>
>Subject: ECN AQM parameters (was: AQM Recommendation: last minute change?)
>Cc: Gorry Fairhurst <[email-masked]>, Richard Scheffenegger 
><[email-masked]>, "Eddy Wesley M. [VZ]" <[email-masked]>, 
>"[email-masked]" <[email-masked]>
>
>Fred,
>
>At 22:27 13/04/2015, Fred Baker (fred) wrote:
>>
>>I think w have a pregnant statement in this case. What parameters 
>>do you have in mind?
>
>The point was simply to ensure that implementers provide sufficient 
>flexibility so that /any or all/ of the AQM parameters for ECN 
>traffic could be separate instances from those for drop. But they 
>would still apply to the same queue, much like the different RED 
>curves for different traffic classes in the WRED algo.
>
>
>>With RED, the parameters available to change are min-threshold, 
>>max-threshold, the limit mark/drop rate, and (IIRC) the minimum 
>>inter-mark/drop interval.
>
>...and, importantly, the EMWA constant, which is the main parameter 
>I would change for ECN (for ECN set ewma-const = 0, assuming the 
>Cisco definition of ewma-const as
>    EWMA weight = 2^{ema-const}
>So for ECN, EWMA weight = 2^0 = 1).
>
>See also {Note 1} about inter-mark/drop interval.
>
>>With PIE, the equation is
>>      p = p + alpha*(est_del-target_del) + beta*(est_del-est_del_old).
>>meaning that we can meaningfully tune alpha, beta, and target_del, 
>>and there is an additional 'max_burst' parameter.
>
>Yes.
>Strictly, the min data in the queue before PIE measures the rate 
>('dq_threshold') is a parameter as well.
>
>>With Codel, if I understand section 4, the only parameters are the 
>>"a round-trip time metric" (100 ms by default) and the Setpoint, 
>>which they set to 5 ms based on it being 5-10% of the RTT.
>>
>>If it's not the target delay, which is essentially what Codel's 
>>setpoint is, I'm not sure what parameter you want to change.
>
>There are actually two more hidden parameters in CoDel's control 
>law, which is written in the pseudocode as :
>    t + interval / sqrt(count)
>but ought to have been written as:
>    t + rtt_ave / (count)^b
>
>These parameters have been hard-coded as
>    rtt_ave = interval
>and
>    b=1/2.
>
>'rtt_ave' in the control law is better set to a likely /average/ 
>RTT, whereas the interval used to determine whether to enter 
>dropping mode is better set to a likely /maximum/ RTT.
>
>To implement an ECN variant of CoDel I would set
>    interval = 0 (or very close to zero)
>and I would leave 'rtt_ave' (in the control law) as an average RTT, 
>decoupled from 'interval'.
>
>However, the CoDel control law was designed assuming it will remove 
>packets from the queue, so I'm not convinced that any naive approach 
>for implementing ECN will work. I suspect a CoDel-ECN doesn't just 
>need different parameters, it needs a different algo.
>
>I have no interest in solving this problem, because I wouldn't start 
>from CoDel in the first place - I would never design an AQM that 
>switches between discrete modes, and CoDel's control law assumes 
>that the e2e congestion control is NewReno which contravenes our AQM 
>recommendations anyway.
>
>
>>In saying 'in this case you might want to mess with the 
>>parameters', I'm not sure what parameters are under discussion, and 
>>in any event we're talking about the document that says 'we should 
>>have an algorithm', not the discussion of any of them in particular.
>>
>>To my mind, this begs for a new draft on your part.
>
>Certainly. We're still doing the research and evaluation tho (see 
><http://www.ietf.org/proceedings/92/slides/slides-92-iccrg-5.pdf>www.ietf.org/proceedings/92/slides/slides-92-iccrg-5.pdf 
>- I don't remember whether you were in the room for that). But, yes, 
>we will write it up.
>
>So far it's not based on RED, PIE or CoDel, but a new drop-based AQM 
>that is most similar to RED but with only 2 parameters (not 4). This 
>is because we needed the drop probability to be the square of the 
>marking probability. So it made the implementation really simple to 
>use a square curve through the origin for drop. It doesn't need 
>min_thresh, because the square curve near-enough runs along the axis 
>when it is close to the origin. For the square curve we used a 
>probability trick - we merely had to compare the queue delay with 
>the max of two random numbers. RED (especially gentle RED) can be 
>thought of as a piecewise linear approximation of a square curve.
>
>We're evaluating this as a drop AQM in its own right. The neat thing 
>about a square curve (or any convex curve) is that the increase in 
>delay wrt load reduces as load increases.
>
>I've worked out how to do a similar squaring trick with PIE, but 
>it's not a straightforward forklift of the same idea, so it needs to be tested.
>
>It would be really hard/impossible to fork-lift the idea into CoDel, 
>because it switches modes. As above, I have no interest in building 
>on CoDel anyway.
>
>Cheers
>
>
>Bob
>
>{Note 1}: The whole min inter-mark/drop interval aspect of RED is 
>just a waste of cycles. Any attempt to alter the distribution of 
>inter-mark/drop spacing in an aggregate just collapses into a 
>geometric distribution again for each flow. For proof see "Are RED 
>Markings Uniformly Distributed?" in my PhD dissertation 
><http://www.bobbriscoe.net/pubs.html#refb-dis>.
>
>
>
>> > On Apr 13, 2015, at 11:23 PM, Bob Briscoe <[email-masked]> wrote:
>> >
>> > Gorry, Fred, Richard, Wes,
>> >
>> > [Off list, because I don't want to distract people's attention 
>> if you don't want to make this change]
>> >
>> > While replying to David Lang just now, I checked with the AQM 
>> recommendation says, and the para below raised a concern:
>> >
>> > 
>> <https://tools.ietf.org/html/draft-ietf-aqm-recommendation-04#section-4.2.1>
>> > "  An AQM algorithm that supports ECN needs to define the threshold and
>> >   algorithm for ECN-marking.  This threshold MAY differ from that used
>> >   for dropping packets that are not marked as ECN-capable, and SHOULD
>> >   be configurable.
>> > "
>> > The work Koen has done since this was written has satisfied me 
>> that the threshold has to be the same (to prevent starvation), but 
>> other parameters can be different, and ought to be. So in the 
>> second sentence I think we should say:
>> >
>> > CURRENT:    "This threshold MAY differ from that used for dropping..."
>> > PROPOSED:   "The parameters MAY differ from those used for dropping..."
>> >
>> > Parameters widens it to burst size, slope, etc.
>> >
>> > If it is too late for any changes, fair enough.
>> > If this minor change can still be accommodated, then pls do 
>> whatever process is necessary to make the change.
>> >
>> > Cheers
>> >
>> >
>> > Bob
>> >
>> >
>> > ________________________________________________________________
>> > Bob Briscoe,                                                  BT
>________________________________________________________________
>Bob Briscoe,                                                  BT

________________________________________________________________
Bob Briscoe,                                                  BT

---

From: Dave Taht <[email-masked]>
Date: Sat, 9 May 2015 19:03:46 -0700

On Sat, May 9, 2015 at 10:20 AM, Bob Briscoe <[email-masked]> wrote:
> Dave,
>
> As promised, here's my thoughts on what PIE (and CoDel) should do when ECN
> is enabled.
>
>
> There's also new info in here that I think is important: CoDel uses an RTT
> estimate in two different places. One has to be the max expected RTT, the
> other should be the (harmonic) mean of expected RTTs.

I like the harmonic idea a lot, it ties in with some of my packet pair
thinking on wifi aggregation.

> The former might be 100ms, but the latter is more likely to be 15-20ms,
> given most traffic in the developed world these days comes from CDNs. This
> could make significant difference to performance.
>
>
> Bob
>
> I think w have a pregnant statement in this case. What parameters do you
> have in mind?
>
>
> flexibility so that /any or all/ of the AQM parameters for ECN traffic could
> be separate instances from those for drop. But they would still apply to the
> same queue, much like the different RED curves for different traffic classes
> in the WRED algo.
>
>
> ...and, importantly, the EMWA constant, which is the main parameter I would
> change for ECN (for ECN set ewma-const = 0, assuming the Cisco definition of
> ewma-const as
> meaning that we can meaningfully tune alpha, beta, and target_del, and there
> is an additional 'max_burst' parameter.
>
>
> Yes.
> With Codel, if I understand section 4, the only parameters are the "a
> round-trip time metric" (100 ms by default) and the Setpoint, which they set
> to 5 ms based on it being 5-10% of the RTT.
>
> If it's not the target delay, which is essentially what Codel's setpoint is,
> I'm not sure what parameter you want to change.
>
>
> There are actually two more hidden parameters in CoDel's control law, which
> is written in the pseudocode as :
> 'rtt_ave' in the control law is better set to a likely /average/ RTT,
> whereas the interval used to determine whether to enter dropping mode is
> better set to a likely /maximum/ RTT.
>
> However, the CoDel control law was designed assuming it will remove packets
> from the queue, so I'm not convinced that any naive approach for
> implementing ECN will work. I suspect a CoDel-ECN doesn't just need
> different parameters, it needs a different algo.
>
> I have no interest in solving this problem, because I wouldn't start from
> CoDel in the first place - I would never design an AQM that switches between
> discrete modes, and CoDel's control law assumes that the e2e congestion
> control is NewReno which contravenes our AQM recommendations anyway.
>
>
> In saying 'in this case you might want to mess with the parameters', I'm not
> sure what parameters are under discussion, and in any event we're talking
> about the document that says 'we should have an algorithm', not the
> discussion of any of them in particular.
>
> www.ietf.org/proceedings/92/slides/slides-92-iccrg-5.pdf - I don't remember
> whether you were in the room for that). But, yes, we will write it up.
>
> So far it's not based on RED, PIE or CoDel, but a new drop-based AQM that is
> most similar to RED but with only 2 parameters (not 4). This is because we
> needed the drop probability to be the square of the marking probability. So
> it made the implementation really simple to use a square curve through the
> origin for drop. It doesn't need min_thresh, because the square curve
> near-enough runs along the axis when it is close to the origin. For the
> square curve we used a probability trick - we merely had to compare the
> queue delay with the max of two random numbers. RED (especially gentle RED)
> can be thought of as a piecewise linear approximation of a square curve.
>
> We're evaluating this as a drop AQM in its own right. The neat thing about a
> square curve (or any convex curve) is that the increase in delay wrt load
> reduces as load increases.
>
> I've worked out how to do a similar squaring trick with PIE, but it's not a
> straightforward forklift of the same idea, so it needs to be tested.
>
> It would be really hard/impossible to fork-lift the idea into CoDel, because
> it switches modes. As above, I have no interest in building on CoDel anyway.
>
> Cheers
>
>
> Bob
>
> {Note 1}: The whole min inter-mark/drop interval aspect of RED is just a
> waste of cycles. Any attempt to alter the distribution of inter-mark/drop
> spacing in an aggregate just collapses into a geometric distribution again
> for each flow. For proof see "Are RED Markings Uniformly Distributed?" in my
> PhD dissertation < http://www.bobbriscoe.net/pubs.html#refb-dis>.
>
>
>
>> [Off list, because I don't want to distract people's attention if you
>> don't want to make this change]
>>
>> <
>> https://tools.ietf.org/html/draft-ietf-aqm-recommendation-04#section-4.2.1 >
>> The work Koen has done since this was written has satisfied me that the
>> threshold has to be the same (to prevent starvation), but other parameters
>> can be different, and ought to be. So in the second sentence I think we
>> should say:
>>
>> If this minor change can still be accommodated, then pls do whatever
>> process is necessary to make the change.
>>
>> Cheers
>>
>>
>> Bob
>>
>>

-- 
Dave Täht
Open Networking needs **Open Source Hardware**

https://plus.google.com/u/0/+EricRaymond/posts/JqxCe2pFr67

---

From: Dave Taht <[email-masked]>
Date: Sat, 9 May 2015 19:13:26 -0700

I am looking over the rest of your email. It is a lot to absorb...

but:

"I have no interest in solving this problem, because I wouldn't start
from CoDel in the first place - I would never design an AQM that
switches between discrete modes, and CoDel's control law assumes that
the e2e congestion control is NewReno which contravenes our AQM
recommendations anyway."

0) I too have trouble... particularly with the decay of codel as it stands.

1) I note we generally got better results from "cubic" than reno.

But: Whatever people call cubic is not what has been in linux, and is
certainly not what is in it now after umpteen revisions and bug fixes
over the past 4 years. It is not what is in QUIC, and it is not how
tcp with sch_fq behaves, and I have tried to document each
major change to tcp in every talk I give, with things like hystart
being modified, etc.

As a baseline reference reno was useless 6+ years ago.

Tracking the continuous changes and bugfixes to linux tcp and the
driver subsystems over the past 4 years has been one of my biggest headaches.

I sometimes wish I was tracking something stable and obsolete like
windows or ns2.

2) It is good to know your honest opinion of why you would not start
with codel as a base for an AQM, and also good to know your lines of
inquery.

3) I really hope that it is clear to everyone that my own main
objective is to fix bufferbloat, and I really don't care what
algorithms we use to do that - the parts that I care about are getting
good data, working clean code, stuff that won´t break the internet,
clear rfcs, and all the solutions "out there" before the heat death of
the universe.

Obviously I think highly of fq as a big means to get there in many
circumstances.

I got really good results from fq_pie btw, published them in a dataset
that I thought others would find interesting (apparently nobody looks
at my data sets, no matter how fast you can fly through them now with
netperf-wrapper)

http://snapon.lab.bufferbloat.net/~d/cake3-fixed/baseline.png

In the next year I hope to finally buckle down down to writing
some papers with all the needed math and results while we ramp up on
the very difficult problems wifi represents...

but now, damn it, I have to go re-run thousands of tests with whatever
version of pie emerges from your analysis and the new draft (pie v8 as
far as I am concerned, I have been tracking the code for far too long
and they kept changing stuff all over the place, where *codel has
stayed stable).

I have a bunch of ideas queued up for cake which is going to be a test
vehicle for also testing enhancements to codel if some more folk were
willing to help implement:

https://lists.bufferbloat.net/pipermail/cake/2015-April/000002.html

Particularly the cake_drop_monitor bits seem very useful to basically
import over from ns3 and try on real traffic on real machines.

tc qdisc add dev whatever root cake flowblind # is the codel only test

and i totally welcome new attempts at the problem as you allude to
below and will gladly fix up, polish, and test *anything*.

But I would like to be able to test stuff in the 3 testbeds I have,
the dozens of routers that i have - or the 10s of thousands we can
quickly muster by leveraging the openwrt effort, and in the 10 servers
I have over the world, and so on, and all the other testbeds now out there,
so we can lock the theorists in the
same room with the experimenters, coders, and EEs making hardware, so
we all line up in the same place(s) at the end. Implementations DO
require tradeoffs from ideal circumstances (like fixed point) and
sometimes those are significant and not understood by the
implementers. So I would like very much for the linux pie code that I
have so many results on to also be subject to the same scrutiny as you
subjected the draft to and drew plots of in the hope that some of the
experimental data will line up fully with your analysis.

And I really want to be creating and providing data people can use.

Which I don't feel like I am doing right now.

Highest on my list is
webrtc behaviors, followed by a stack of wifi related issues so high that I dont
think 2 years will be enough to get all the coding done... I have been
delightfully distracted by debugging the dslreports tests of late....

4) So I really liked very much you identifying edge cases in
particular in that document, and much else besides. That yields
testable concepts instead of having to explore the whole parameter
space. thank you thank you thank you! I really understood pie, codel,
and aqm behavior overall a lot better after reading that critique!

5) One thing I really gotta do is test the "drop on overload even if
ecn marked, then mark the next packet" idea out more full and commit
that to mainline (and look over the tcp scoreboard) and also figure
out what to do with pie ecn.

High on my list is producing some results showing the existing ecn
and drop behaviors in all these algos on the table.

6) There is no.... 6!