Subject: [aqm] draft-ietf-aqm-pie-01: review

From: Bob Briscoe <[email-masked]>
Date: Fri, 8 May 2015 11:08:03 +0100

Richard, Wes, (and Rong plus all the PIE authors),

In Dallas you 'volunteered' me to review draft-ietf-aqm-pie-01

First, thanks to the draft authors for developing this, writing it 
up, evaluating it and maintaining it.

I read an early draft when it just described the basics and it was 
fine. However, now we have the pseudocode and enhancements, I have a 
number of concerns...

My full review is here:
<http://www.bobbriscoe.net/projects/latency/piervw_tr.pdf>

My technical points run to 15 pages. I could have turned it into I-D 
format, but I chose to use PDF for a tech report format, 'cos the 
review includes charts and maths. I've put significant work into this 
over the past couple of weeks, particularly preparing charts to 
justify my technical points in the body of the review. So I hope it 
gets read thoroughly.  The review ends with a 7 page tailpiece of 
editorial nits, references, etc.

Over the next few days I may break it down, by pasting the important 
points into manageable bite-sized emails to the list. But I recommend 
the tech report format for a proper read.

==Exec Summary==

The PIE draft ends with two assertions in the Discussion section:
    "PIE is simple to implement"
    "PIE does not require any user configuration"
I am afraid I have to say that I do not believe either statement is 
warranted any more. PIE has lost its way a bit. The implementation 
has not retained the elegance of the theory. The performance benefit 
from so-called `enhancements' is questionable or non-existent, 
whereas the added complexity is very apparent. Also PIE now contains 
a large number of hard-coded constants (I counted 20) that ought to 
be scenario-dependent configuration variables.

==Main concerns==

This is a table of contents of the technical part of the review:
    * Proposed Standard, but no normative language
        *   work needed to distinguish between design intent and 
specific implementation
        *   unclear how strongly the enhancements are recommended
    * Has PIE been separately tested with and without each 
enhancement, to justify each?
    * Needs to enumerate whether it satisfies each AQM Design Guideline
        * If not, say why or fix.
        * Particular concerns:
            * No spec of ECN behaviour
            * No autotuning of the two main parameters
            * Transport specific (Reno-based?) autotuning of alpha & beta
    * Rationale for a PI controller not properly articulated
    * Technical flaws/concerns
        * Turning PIE off
        * So-called `autotuning' of alpha & beta parameters
        * Averaging problems
        * Burst allowance unnecessary?
        * Needs a Large Delay to Make the Delay Small
        * Derandomization: a waste of cycles
        * Bound drop probability at 100% --> DoS vulnerability?
        * Avoiding Large Packet Lock-Out under Extreme Load.
    * Numerous magic numbers
        * ~20 constants, 13 of which are not in the header block.
        * About half ought to be made to depend on other constants
        * Need to state how to set the remaining constants for 
different environments
    * Implementation suggestion for Autotuning alpha & beta

Bob

________________________________________________________________
Bob Briscoe,                                                  BT

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 8 May 2015 19:26:12 +0000

Bob,

Wow, really detailed review. Thank you so much for looking into all the details. We will definitely read them thoroughly and address them properly and revise the draft. This might take some time, please be patient :-).

Thanks,

Rong

From: Bob Briscoe <[email-masked]<mailto:[email-masked]>>
Date: Friday, May 8, 2015 3:08 AM
To: Richard Scheffenegger <[email-masked]<mailto:[email-masked]>>, "Eddy Wesley M. [VZ]" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Cc: AQM IETF list <[email-masked]<mailto:[email-masked]>>
Subject: [aqm] draft-ietf-aqm-pie-01: review

First, thanks to the draft authors for developing this, writing it up, evaluating it and maintaining it.

I read an early draft when it just described the basics and it was fine. However, now we have the pseudocode and enhancements, I have a number of concerns...

My full review is here:
< http://www.bobbriscoe.net/projects/latency/piervw_tr.pdf>

My technical points run to 15 pages. I could have turned it into I-D format, but I chose to use PDF for a tech report format, 'cos the review includes charts and maths. I've put significant work into this over the past couple of weeks, particularly preparing charts to justify my technical points in the body of the review. So I hope it gets read thoroughly.  The review ends with a 7 page tailpiece of editorial nits, references, etc.

Over the next few days I may break it down, by pasting the important points into manageable bite-sized emails to the list. But I recommend the tech report format for a proper read.

==Exec Summary==

The PIE draft ends with two assertions in the Discussion section:
   "PIE is simple to implement"
   "PIE does not require any user configuration"
I am afraid I have to say that I do not believe either statement is warranted any more. PIE has lost its way a bit. The implementation has not retained the elegance of the theory. The performance benefit from so-called `enhancements' is questionable or non-existent, whereas the added complexity is very apparent. Also PIE now contains a large number of hard-coded constants (I counted 20) that ought to be scenario-dependent configuration variables.

==Main concerns==

     *     work needed to distinguish between design intent and specific implementation
  *   Has PIE been separately tested with and without each enhancement, to justify each?
     *   Need to state how to set the remaining constants for different environments

Bob

---

From: Dave Taht <[email-masked]>
Date: Fri, 8 May 2015 16:51:44 -0700

Dear Bob:

 I now understand the linux codebase for pie a lot better, as well as
some of the experimental data I have. It  looks like I could make
several of the changes you describe and put them in my next series of
tests, and based on your parameters I should be able to exercise some
edge cases across those changes. Wow, thx!

I have not actually read the latest pie draft, but would like to make
a few comments on your comments quickly:

re: 3.1: in linux, params->ecn is presently a boolean, and could
easily be modified to mean anything and compare anything you want.
What would be a good default?

The ECN support in the linux code on enqueue looks like:

        if (!drop_early(sch, skb->len)) {
                enqueue = true;
        } else if (q->params.ecn && (q->vars.prob <= MAX_PROB / 10) &&

                   INET_ECN_set_ce(skb)) {

                /* If packet is ecn capable, mark it if drop probability

                 * is lower than 10%, else drop it.

                 */
                ....

Re: 5.0: will look over that code

re: 5.1,  linux code:

        /* Non-linear drop in probability: Reduce drop probability quickly if
         * delay is 0 for 2 consecutive Tupdate periods.
         */

        if ((qdelay == 0) && (qdelay_old == 0) && update_prob)
                q->vars.prob = (q->vars.prob * 98) / 100;

re: 5.2: strongly agree that the lookup table doesn't scale properly.
The linux code appears to differ from the draft also, here, with a
smaller lookup table, and some other smoothing functions. I am going
to stop pasting now and just point at:
https://github.com/torvalds/linux/blob/master/net/sched/sch_pie.c#L334

Will await more feedback from y'all on that.

Codel also has a similar undershoot problem for which I proposed we
try a fixed point fractional count variable in a recent post to the
cake mailing list.

re: 5.3.1: In the environments i work in it is extremely hard to get
timers to reliably fire in under 2ms intervals, particularly on vm'd
systems. Also as you fire the timer more rapidly the current
calculations in pie now done out of band of the packet processing have
a couple divides in them which tend to be processor intensive... both
things said, i figure this and other implementations could fire faster
than the default 16ms...

re: 5.3.2: I like what you are saying but I gotta go work it out for
myself. which will take a while. patches wanted.

re: 5.4: linux and all my tests have always been against:
           /* default of 100 ms in pschedtime */
           vars->burst_time = PSCHED_NS2TICKS(100 * NSEC_PER_MSEC);

5.5: explains a lot. Probably. Will think on it.

5.6: :chortle: heats_this_room() indeed! Derandomization always looked
to me like an overly complex solution to a non-problem.

5.7: don't think this problem exists in the linux code but will step through.

But: in one of my recent (450 rrul_50_up tcp flows) tests neither
codel or pie got to a sane drop rate in under 60 seconds, and pie
stayed stuck at 10000 packets outstanding, i did not try more - on
gigE local links. I think a lot of pie tests were run by others with a
very low outside packet limit (200 packets) and thus the tail drop
kicked in before pie itself could react.

5.8:  I think this is a quibblish change not relevant for any
reasonable length of queue measured in packets.

but I do note that we switched from packet limits to byte limits in
cake but that was for other reasons - primarily due to the extreme
(1000x1) dynamic range of a modern "packet".

6: I do wish the draft and the code I have still lined up, and the
constants clearly defined.

7: exp(p) is not cheap, and there aint no floating point in the kernel either.

8. Haven't read the draft, can't comment on the nits.

One quick note on:

"4.1 Random Dropping s/Like any state-of-the-art AQM scheme, PIE would
drop packets randomly/ /PIE drops packets randomly/ Rationale: The
other scheme with a claim to be state-of-the-art doesn’t (CoDel). I
would agree if the draft had said “A state of the art scheme should
introduce randomness into packet dropping in order to desynchronize
flows,” but maybe it was decided not to introduce such underhand
criticism of CoDel. Whatever, the draft needs to be careful about
evangelising random drop, given it attempts to derandomize later."

I don't buy the gospel that randomness is needed to avoid tcp global
synchronization. I would prefer that whatever evangelicalization of
randomness exists in any draft here or elsewhere be dropped in favor
always of discussing the real problem of tcp global sync instead...

... which as near as I can tell both codel and fq_codel avoid just
fine without inducing a random number generator. I welcome evidence to
the contrary.

---

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

Dave,

>edge cases across those changes. Wow, thx!

I'd like to allow the authors a chance to think 
and respond before anyone does any changes to 
implementations - they may have their reasons that I didn't understand.

>                  * is lower than 10%, else drop it.

Next mail I'll send an email I sent to Fred offlist on this subject.

>Re: 5.0: will look over that code

My review didn't have a section 5.0
:?

>                 q->vars.prob = (q->vars.prob * 98) / 100;

Ooh joy. The great thing about open source is 
that it allows everyone to assert their human 
right to add their own made-up numbers.
<http://dilbert.com/strip/2008-05-08>

Looking at the Linux code, I just found another magic number has been added:
<https://github.com/torvalds/linux/blob/master/net/sched/sch_pie.c#L368>
/* to ensure we increase probability in steps of no more than 2% */
:-!

There really is no point in employing control 
theory experts to work out the stability limits 
for how fast a control algorithm can respond, if 
implementers then add in extra arbitrary limits 
on the responsiveness like this.

>Will await more feedback from y'all on that.

The factors I used in my review were added to the 
PIE draft when the pseudocode was added in Oct'14.
The numbers in the Linux code you point to above 
match the original HPSR'13 paper on PIE.
We need to wait to hear the answer from the 
authors about why the numbers were changed.

>try a fixed point fractional count variable in a recent post to the

Back in 2013 I pointed out that the CoDel 
square-root control law ends up increasing drop 
probability linearly with time. See my points 3 & 4 here:
<http://www.ietf.org/mail-archive/web/aqm/current/msg00376.html>

>things said, i figure this and other implementations could fire faster

My point was that an RFC should say what the 
algorithm is trying to achieve, not solely what a 
particular implementation for a particular 
environment might have to do as a compromise.

>myself. which will take a while. patches wanted.

I'm not sure whether the inaccuracy is 
significant. I tried to find cases where it might 
be, but gave up wasting time using trial and 
error - I need to think about it analytically.

>            vars->burst_time = PSCHED_NS2TICKS(100 * NSEC_PER_MSEC);

I think it could be zero, given the alpha/beta 
formula already significantly filters out bursts. 
But again, wait for the authors to answer my 
question about whether they chose this value based on experiments.

>5.7: don't think this problem exists in the linux code but will step through.

It does:
<https://github.com/torvalds/linux/blob/master/net/sched/sch_pie.c#L383>

>kicked in before pie itself could react.

That's the opposite to my concern in 5.7 - I'm 
sure tail drop will often kick in before PIE can 
react (see my points 5.3.1 , 5.4 & 5.5).

I'm talking about contriving an attack that 
drives PIE to 100% drop /before/ it reaches tail 
drop (because 100% drop is pathological, whereas 
tail drop is only mildy irritating by comparison).

>(1000x1) dynamic range of a modern "packet".

I've think you've misunderstood (i.e. I've explained it badly).

I merely meant that, if PIE has to fall back to 
tail drop, at least it should always stop 
enqueuing packets when there's <1MTU free at the 
tail, which ensures there will be no bias against large packets.

>7: exp(p) is not cheap, and there aint no floating point in the kernel either.

Sorry, again I've explained badly. I had defined 
p as a double, and I meant "extract the integer 
held in the exponent of the floating point representation".

I should have described this for integer 
arithmentic, as "lg(p) in integer arithmetic".
On Intel Architecture it's the bsr instruction in 
assembler, which returns the position of the 
highest set bit in an unsigned integer.

I've clarified this point and 5.8 above in my 
review. I've updated it to issue 01A and uploaded it at the same URL:
<http://www.bobbriscoe.net/projects/latency/piervw_tr.pdf>

>fine without inducing a random number generator. I welcome evidence to

Dropping single packets at a time (like CoDel and 
PDPC) should prevent global synch.
Global synch is caused if a spike in one flow can 
induce a sequence of drops that hit other flows.

Theoretically, there could be a problem with 
dropping in a deterministic pattern as CoDel does 
(a flow could game it by avoiding sending around 
the times it knows drops will occur). But it's a 
lot easier to just send faster by ignoring drop signals anyway.

CoDel's determinism might become problematic if 
unresponsiveness to congestion became a serious 
problem, so that it became necessary to police congestion responsiveness.

IOW, when you're putting algorithms in a network 
that could be there for decades, don't not use 
randomness lightly. Randomness has nice security properties.

Bob

---

From: Greg White <[email-masked]>
Date: Tue, 12 May 2015 22:44:12 +0000

Bob,

I haven't had a chance to fully read your review (though what I've read
looks to be insightful), but there was one comment in the email thread
that compelled me to respond.

You wrote:  There really is no point in employing control

I would personally truncate/modify that statement to something more like:
There really is no point in employing control theory experts to work out
the stability limits for how fast an AQM control algorithm can respond.  :)

Real networks aren't LTI systems, and I actually think it is disingenuous
to present classical control theoretical analyses of AQMs that are
intended to be deployed in real networks.  PIE borrows from classical
control theory, and that is fine, but I think that is about as far as one
should take it. 

To me PIE has always seemed like a "steampunk" AQM in that there are a lot
of knobs, gears and wires that make it look arcane.  All of those
knobs/gears/wires were added for a reason, and they do make for a system
that works well* in comparative testing.  But, is all of the algorithmic
complexity needed?  Maybe not.  Is there a more streamlined version that
would work equally well (or better)?  Probably.  One of the most
compelling arguments in favor of PIE for the cable industry was that
nearly all of the control-law functions could be done in CPU as opposed to
being burned into gates (in a cost-constained high-performance mass-market
chip). So, it is relatively easy to make changes if further studies point
out improvements that can be made.  I'm happy that it is getting another
set of smart eyes looking at it and suggesting improvements.  I would be
especially pleased if we could show equivalent or better performance
across a broader range of scenarios with a simplified algorithm.

*works well when integrated with the DOCSIS MAC layer, in simulation.
We'll have real equipment at some point to do validation testing with.

Note, some of the comments in your review are arising from a few
errors/omissions in the pseudocode that were pointed out by others and
that Rong will have fixed in the next draft (e.g. status_update() runs
every 16ms regardless of packet arrivals, the T_UPDATE check was probably
not the best way to explain this. In DOCSIS the updates are suppressed
when in sleep mode, and resume with initialized state upon exit from
sleep).  But in my view many of the others look like good suggestions that
would warrant further study.

Your comment on queue sampling comes close to one of my lingering mental
issues with PIE.  CoDel's insight was that it isn't the current queue
latency (or moving average queue latency) that matters as much as the
minimum queue latency over a recent window. PIE doesn't take advantage of
this insight.  (CoDel, however, misses that it probably does matter how
big that minimum queue latency is and how fast it is growing/shrinking).

-Greg

On 5/9/15, 11:13 AM, "Bob Briscoe" <[email-masked]> wrote:

>>other scheme with a claim to be state-of-the-art doesnâ€™t (CoDel). I
>>would agree if the draft had said â€œA state of the art scheme should
>>flows,â€ but maybe it was decided not to introduce such underhand
>_______________________________________________
>aqm mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/aqm

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 13 May 2015 02:31:17 +0100

Greg,

>the stability limits for how fast an AQM control algorithm can respond.  :)

I disagree in this respect: the control theory 
analysis gave the designer of the algorithm 
(Rong) a feel for what autotuning would be 
needed, to keep it far enough away from 
instability (given the idealised assumptions, 
i.e. only TCP Reno etc.) That's the whole point 
of a gain and phase /margin/. Not gospel, but a 
better insight into how much 'margin of error' 
there is under idealised conditions that are 
something close to those expected to be common.

My comment was in response to discovering an 
arbitrary limit had been added to the Linux 
implementation: "Limit the change in p per 
T_UPDATE to 2%". The whole point of the rest of 
the PIE algorithm is to automatically limit how 
rapidly p changes, by steering a mid-course far 
enough away from two cliffs known to be out there 
somewhere (probably not where the theory says 
they are, but at least it gives a feel).

So to write in a hard-coded limit that completely 
overrides all the autotuning is IMO just plain 
ignorant (I'll eat my words if someone like Rong 
wrote that code!). It will make PIE unnecessarily 
sluggish when conditions are changing fast and 
the rest of the code has judged that it will be quite safe to react fast.

And, I should add here that 'safe' only means 
'unlikely to harm utilisation'. Even if PIE 
becomes unstable, the oscillations only hurt 
utilisation. It's not like we're dealing with nitroglycerin or something.

No. Actually, I will push back harder. This 
community needs skilled mathmaticians, skilled 
designers, skilled evangelists and skilled 
implementers. And we all need humility, to listen 
carefully to the others. And yes, agreed, we also 
need to be wary that someone who sounds like an 
expert could be pushing inapplicable theory.

>control theory, and that is fine, but I think that is about as far as one

I'm not sure what you're saying. How can it be fine, but not be taken?

I found reading the stability analysis in the 
HPSR paper on PIE useful for understanding how to 
improve PIE autotuning over a wide range. I think 
you're criticism assumes the analysis is trying 
to claim something about the solution. Whereas I 
saw it as providing insight for those who 
designed it, and for those wanting to understand (and improve) the design.

As long as you know how much weight to give such 
analysis and what it's limits are, it is much 
much better than the Dilbert rule of thumb: "87% 
of made up numbers are better than those derived 
from analysis". I assume whoever wrote that 2% 
limit in the Linux code must live by Dilbertisms like this.

>complexity needed?  Maybe not.

And when you read my review (pls do) you will get 
a feel for my assessment of PIE: it looks to me 
like the implementation (by which I mean the 
pseudocode on which other implementations are 
based) has failed to realise the intent of the 
design. In places this is because there are still 
holes in the design, and the implementation has 
made a mess of filling them. But it's often 
because the implementation has introduced a lot 
of bad practices (e.g. abitrary constants). Most 
importantly, too little deep thought and care has gone into the pseudocode.

>Is there a more streamlined version that
>would work equally well (or better)?  Probably.

We are nearly finished testing a very simple AQM 
that doesn't use any of theose steampunk PI 
controls. But only having understood the control 
stuff could we build up the confidence and 
intuition to understand where it's probably not necessary.

It's aimed at cost-reduction more than perfection 
for very large numbers of low stat-mux queues 
within a larger scheduling hierarchy. Not really 
your scenario (cable modems), but it's possible 
it could be retargeted at residential gateways 
and be as good as PIE, or maybe so slightly worse that it wouldn't matter.

>One of the most

OK. I suspected that might be the case. Happy to 
turn that criticism into an editorial nit.

>this insight.

Altho you're right to point out that the min over 
a window is a useful insight, the way it's done 
in CoDel leaves me cold. All the decisions in 
CoDel are either-or and switching into and out of 
modes. I would have been happier if the closer 
the min was to being over the target, and the 
more often the mins came close to the target in 
recent time (e.g. by an EWMA), then the more 
likely it would drop. GIven no magic number will 
be correct, it's better to use a continuous 
approach, rather than when you're one side of a 
threshold you're fine and the other you're dead.

Bob

>(CoDel, however, misses that it probably does matter how
> >>other scheme with a claim to be state-of-the-art doesnÃ¢€™t (CoDel). I
>I
> >>would agree if the draft had said Ã¢€œA state of the art scheme should
>
> >>flows,Ã¢€Â but maybe it was decided not to introduce such underhand

---

From: Dave Taht <[email-masked]>
Date: Wed, 13 May 2015 07:43:26 -0700

On Tue, May 12, 2015 at 6:31 PM, Bob Briscoe <[email-masked]> wrote:
> I disagree in this respect: the control theory analysis gave the designer of
> the algorithm (Rong) a feel for what autotuning would be needed, to keep it
> far enough away from instability (given the idealised assumptions, i.e. only
> TCP Reno etc.) That's the whole point of a gain and phase /margin/. Not
> gospel, but a better insight into how much 'margin of error' there is under
> idealised conditions that are something close to those expected to be
> common.

A minimal amount of tachyons and infinitely precise mathematics is needed
for any implementable algorithm.

> My comment was in response to discovering an arbitrary limit had been added
> to the Linux implementation: "Limit the change in p per T_UPDATE to 2%". The
> whole point of the rest of the PIE algorithm is to automatically limit how
> rapidly p changes, by steering a mid-course far enough away from two cliffs
> known to be out there somewhere (probably not where the theory says they
> are, but at least it gives a feel).
>
> So to write in a hard-coded limit that completely overrides all the
> autotuning is IMO just plain ignorant (I'll eat my words if someone like
> Rong wrote that code!). It will make PIE unnecessarily sluggish when
> conditions are changing fast and the rest of the code has judged that it
> will be quite safe to react fast.

I assumed that the code I was given and helped polish had been thoroughly
reviewed by the authors, and had hoped it had been more reviewed by others
concerned with it long before now.

Certainly time and benchmarkings can improve all things.

http://www.bufferbloat.net/projects/codel/wiki/Cake

It is important to recognize (and remember) that we are in an iterative
process. I recently (I'll put up a graph) took apart what dslreports was
doing to make sure it was reporting real stuff, and along the way
measured how CMTSes behaved today in particular compared to
what we could do now - it is *way better*...

but not idea.

> And, I should add here that 'safe' only means 'unlikely to harm
> utilisation'. Even if PIE becomes unstable, the oscillations only hurt

Well, it is certainly feasible someone could still break the net. Did anyone
imagine how ntp was recently used for ddos attacks?

> No. Actually, I will push back harder. This community needs skilled
> mathmaticians, skilled designers, skilled evangelists and skilled
> implementers.

+10!

EEs making hardware in fpgas, coders coding, theorists theorizing
experimenters experimenting, all in the same building would be nice.

It could also use a "red team" and a "blue team" - skeptics attacking,
defenders defending...

and a much higher cycle time between idea/attempt/testing than
what is allowed by classic academic publication.

and way better test tools.

As much as these personality types and skill sets (including mine) tend to
fight I am glad we are all locked in this virtual room together...

(well... some of the time. :) )

>And we all need humility, to listen carefully to the others.

+100

And funding! However, my government, having lost the war on drugs
seems to be reluctant or unable to start one on internet congestion.

The eu seems to be doing better in this regard. I'm tired of having nothing
but canvas over my head and my enlistment was up 2 years ago.

> And yes, agreed, we also need to be wary that someone who sounds like an

This field is new to me. I brought my background in real time control systems
(principally audio) to the table as well as mods to one algorithm I
had been using for
a decade....

http://www.bufferbloat.net/projects/cerowrt/wiki/Wondershaper_Must_Die

...

and everything since then has been kind of a wonderful learning experience.

>> control theory, and that is fine, but I think that is about as far as one

Agree

Also I kvetch that few statistical methods that are commonly understood
apply. This is why I am excited about the tracy widom stuff - it is not that
it is different than a std distribution that is the important part, but that it
implies other methods could be derived.

> I found reading the stability analysis in the HPSR paper on PIE useful for
> understanding how to improve PIE autotuning over a wide range. I think
> you're criticism assumes the analysis is trying to claim something about the
> solution. Whereas I saw it as providing insight for those who designed it,
> and for those wanting to understand (and improve) the design.
>
> As long as you know how much weight to give such analysis and what it's
> limits are, it is much much better than the Dilbert rule of thumb: "87% of
> made up numbers are better than those derived from analysis". I assume
> whoever wrote that 2% limit in the Linux code must live by Dilbertisms like
> this.
>
>

In recent months multiple episodes of "girl genius" have oddly been appropo
for exactly what was going on on these mailing lists.

My favorite:

http://www.girlgeniusonline.com/comic.php?date=20150406#.VVNghnU4l4s

>
> And when you read my review (pls do) you will get a feel for my assessment
> of PIE: it looks to me like the implementation (by which I mean the
> pseudocode on which other implementations are based) has failed to realise
> the intent of the design. In places this is because there are still holes in
> the design, and the implementation has made a mess of filling them. But it's
> often because the implementation has introduced a lot of bad practices (e.g.
> abitrary constants). Most importantly, too little deep thought and care has
> gone into the pseudocode.
>
> We are nearly finished testing a very simple AQM that doesn't use any of
> theose steampunk PI controls. But only having understood the control stuff
> could we build up the confidence and intuition to understand where it's
> probably not necessary.
>
> It's aimed at cost-reduction more than perfection for very large numbers of
> low stat-mux queues within a larger scheduling hierarchy. Not really your
> scenario (cable modems), but it's possible it could be retargeted at
> residential gateways and be as good as PIE, or maybe so slightly worse that
> it wouldn't matter.
>
>> One of the most
> OK. I suspected that might be the case. Happy to turn that criticism into an
> editorial nit.
>
>
>> issues with PIE.

My own kvetch was that the sampling interval was a fixed constant and
(as you pointed out) too high for lower rates.

and in the code and API untunable.

>> CoDel's insight was that it isn't the current queue
> Altho you're right to point out that the min over a window is a useful
> insight, the way it's done in CoDel leaves me cold. All the decisions in
> CoDel are either-or and switching into and out of modes. I would have been
> happier if the closer the min was to being over the target, and the more
> often the mins came close to the target in recent time (e.g. by an EWMA),
> then the more likely it would drop. GIven no magic number will be correct,
> it's better to use a continuous approach, rather than when you're one side
> of a threshold you're fine and the other you're dead.

Tend to agree.

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

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

---

From: Greg White <[email-masked]>
Date: Wed, 13 May 2015 17:02:29 +0000

On 5/12/15, 7:31 PM, "Bob Briscoe" <[email-masked]<mailto:[email-masked]>> wrote:

Greg,

I don't know the origin of the 2% limit, but IMO it could very reasonably be that actual (simulated) traffic pointed out that the control theory prediction (based on linearized models of steady-state Reno IIRC) really wasn't the best guidance in all cases.  In fact, I really can't think of another reason why it would have been added.  To me your reaction precisely points out the danger of assuming that a bit of theory should be taken as guidance when the assumptions underlying the theory are known to only approximate reality in a constrained set of scenarios.  I did control theory and control system design for a while (e.g. ‎www.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf<http://www.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf>).  I don't claim to be an expert anymore, but I know from experience that incorrect system modeling will result in incorrect controller design, and even in simple systems, reality needs to be considered strongly over theory.  In my testing of PIE, the algorithm (with the 2% limit) works.  I don't have simulation results with and without the limit, but I'm going to believe (until shown otherwise) that it was added for a real reason.

I agree 100%.   Precise feedback control of non-LTI systems gets *really* hard *really* fast.   It is even harder when you don't have a complete system model.

What I meant is that utilizing a classical linear controller (PI in this case), and even doing some basic control theory analysis is ok as a starting point for an AQM design, but you really shouldn't take that theory as guidance that needs to be adhered to.

I think the piece that is missing is that we don't really know what the limits of the analysis are, so we don't know how much weight to give it.  The analysis uses simplified approximations of steady-state behavior.    If we did, and if we had a solid theoretical reason for limiting the growth of p, that would definitely be preferred, but I think we're a long way from such precision.

[snip]

You stated it better than I did below, but that is more-or-less what I was thinking. CoDel is a coarse controller*, but uses a better control input.  PIE uses a less precise control input, but provides a more capable control response.

*I'd characterize CoDel as an auto-tuning bang-bang controller.  It autotunes using the linear increase in drop probability over time as you had pointed out some time ago, and then uses that drop probability value in a bang-bang fashion.

I'm guessing if the PIE logic were changed to use the minimum queuing latency over the 16ms window, rather than an instantaneous sample of the queueing latency every 16ms, we'd get a bit better result.  The question then would be, is the additional complexity justified?

Bob

-Greg

I

>[email-masked]<mailto:[email-masked]>

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Thu, 21 May 2015 21:15:51 +0000

Sorry that I have not fully read Bob's report so I have been hesitating of speaking up. Let me just comment on the following thread. I will spend more time on Bob's detailed comments and give feedback later.  For now, please see inline…

Thanks,

Rong

From: Greg White <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, May 13, 2015 10:02 AM
To: Bob Briscoe <[email-masked]<mailto:[email-masked]>>
Cc: Richard Scheffenegger <[email-masked]<mailto:[email-masked]>>, "Eddy Wesley M. [VZ]" <[email-masked]<mailto:[email-masked]>>, Dave Taht <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, AQM IETF list <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] draft-ietf-aqm-pie-01: review

Greg,

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: It is designed to help in the one single TCP test during slow start phase. In this case, queue could quickly goes up during slow start and demands high drop probability. In Cable Modem SpeedTest environment, one could not afford triggering timeout and lose throughput as throughput is shown to customers who are testing his/her connection speed. TCP is not a good test for this, but that is what we do now. As Bob mentioned in his previous emails, we need to distinguish what are MUST, SHOULD, and MAY items of PIE. I consider this as SHOULD, not MUST.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Rong: I believe in the control theoretical analysis to study the basis of the design. The analysis does help give the guidelines of how to choose the parameters: it may not need to be accurate to the hundredth decimal point, but we can not be order of magnitude off. If one does change alpha and beta parameters (and their relative weight) in PIE by an order of magnitude, I am sure the system will be off. This is the value that control theory brings us. Of course, there are real system challenges that we have to deal with like the above comment.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: Bob has a question of why choosing PI. I like the PI controller because AQM naturally has proportional (rate) and integral (queue length) components to it. It is the best fit for our setup. I see it as AQM providing two knobs for us to control it :-), what a waste not to take advantage of it!

[snip]

Bob

-Greg

I

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 22 May 2015 17:38:34 +0100

Rong,

I've snipped inline...

At 22:15 21/05/2015, Rong Pan (ropan) wrote:
>Content-Language: en-US
>Content-Type: multipart/alternative;
>         boundary="_000_D183961BF09Cropanciscocom_"
>
>Sorry that I have not fully read Bob's report so 
>I have been hesitating of speaking up. Let me 
>just comment on the following thread. I will 
>spend more time on Bob's detailed comments and 
>give feedback later.  For now, please see inline…
>
> >
>Thanks,
>
>Rong
>
>
>From: Greg White <<mailto:[email-masked]>[email-masked]>
>To: Bob Briscoe <<mailto:[email-masked]>[email-masked]>
>Cc: Richard Scheffenegger 
><<mailto:[email-masked]>[email-masked]>, "Eddy 
>Wesley M. [VZ]" 
><<mailto:[email-masked]>[email-masked]>, 
>Dave Taht 
><<mailto:[email-masked]>[email-masked]>, 
>"<mailto:[email-masked]>[email-masked]" 
><<mailto:[email-masked]>[email-masked]>, 
>AQM IETF list <<mailto:[email-masked]>[email-masked]>
>On 5/12/15, 7:31 PM, "Bob Briscoe" 
><<mailto:[email-masked]>[email-masked]> wrote:
>
>[Greg] I don't know the origin of the 2% limit, 
>but IMO it could very reasonably be that actual 
>(simulated) traffic pointed out that the control 
>theory prediction (based on linearized models of 
>steady-state Reno IIRC) really wasn't the best 
>guidance in all cases.  In fact, I really can't 
>think of another reason why it would have been 
>added.  To me your reaction precisely points out 
>the danger of assuming that a bit of theory 
>should be taken as guidance when the assumptions 
>underlying the theory are known to only 
>approximate reality in a constrained set of 
>scenarios.  I did control theory and control 
>system design for a while (e.g. 
><http://www.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf>â€Žwww.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf). 
>I don't claim to be an expert anymore, but I 
>know from experience that incorrect system 
>modeling will result in incorrect controller 
>design, and even in simple systems, reality 
>needs to be considered strongly over theory.  In 
>my testing of PIE, the algorithm (with the 2% limit) works.

Any AQM 'works'. As you say below, the important 
test is whether it 'works' better without the 
limit? And if so under what assumptions and what definition of 'works'?

>I don't have simulation results with and without 
>the limit, but I'm going to believe (until shown 
>otherwise) that it was added for a real reason.
>
> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: It is 
> designed to help in the one single TCP test 
> during slow start phase. In this case, queue 
> could quickly goes up during slow start and 
> demands high drop probability. In Cable Modem 
> SpeedTest environment, one could not afford 
> triggering timeout and lose throughput as 
> throughput is shown to customers who are 
> testing his/her connection speed. TCP is not a 
> good test for this, but that is what we do now. 
> As Bob mentioned in his previous emails, we 
> need to distinguish what are MUST, SHOULD, and 
> MAY items of PIE. I consider this as SHOULD, not MUST.

[Bob] AFAICT, limiting the change in beta to no 
more than 2% will prevent PIE reacting fast to 
slow-start. Are you saying you intended to make 
PIE delay its response to a slow start? If so, ... eh? what? why?

Once a slow start has reached capacity, and is 
heading towards twice capacity in the next RTT 
(remembering the AQM doesn't know what a RTT is), 
an AQM could take a bet on whether the flow will 
finish before it gets to twice capacity, or not.
* If yes, then in hindsight the AQM wouldn't have needed to drop a packet.
* If no, then in hindsight the AQM should have 
dropped a packet (in hindsight ideally when the queue first started to grow).

By arbitrarily clamping the increase at 2%, it's 
making a judgement on the risk of each of these, 
and on the harm that would ensue if it makes the wrong call either way.

Delaying a drop improves performance of the flow 
in question if its going to end anyway (as you 
say), but it certainly means the slow-start will 
spike other flows harder (if the flow doesn't end of its own accord).

Good practice is for a host to use HSS (hybrid 
slow-start) or a similar technique to detect the 
end of slow start so it can stop SS just as it 
reaches capacity, not one RTT later. By putting 
off the drop that would end SS, you are rewarding 
flows that do not use HSS, which is the wrong incentive.

You are also potentially confusing HSS. From 
packet spacings, it thinks it's detected the 
approach of the end of SS. If the drop it expects 
doesn't actually appear, there's a strong danger 
that the sender will reverse its guess that SS is 
about to end, and move back into full SS. Then 
slam into the buffers, which are actually right where it thought they were.

> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 
>  >> Rong: I believe in the control theoretical 
> analysis to study the basis of the design. The 
> analysis does help give the guidelines of how 
> to choose the parameters: it may not need to be 
> accurate to the hundredth decimal point, but we 
> can not be order of magnitude off. If one does 
> change alpha and beta parameters (and their 
> relative weight) in PIE by an order of 
> magnitude, I am sure the system will be off. 
> This is the value that control theory brings 
> us. Of course, there are real system challenges 
> that we have to deal with like the above comment.

Yup.

> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 
>  >>>>Rong: Bob has a question of why choosing 
> PI. I like the PI controller because AQM 
> naturally has proportional (rate) and integral 
> (queue length) components to it. It is the best 
> fit for our setup. I see it as AQM providing 
> two knobs for us to control it :-), what a waste not to take advantage of it!

I think I must have phrased one of my comments 
badly (altho perhaps you're solely responding to a heading).

I didn't mean that you need to justify better why 
you chose a PI controller. I said you need to 
"Articulate the Rationale for a PI Controller". I 
meant (and said) that you do not actually even 
say what the aim of a PI controller is  - i.e. to 
keep queuing delay at the same level under a wide range of loads.

It wasn't a criticism of the choice of a PI 
controller, it was intended to be a helpful hint 
that you haven't explained your rationale well, 
for someone reading this who doesn't know the background.

Bob

---

From: Vishal Misra <[email-masked]>
Date: Fri, 22 May 2015 11:01:53 -0700

Bob, Rong

Let me present our rationale for choosing the PI controller (hope it will be helpful to present the rationale for PIE).

When we were working on the issue in 2001-2001, RED had been deployed everywhere but also disabled everywhere. People had trouble understanding and tuning RED. Our fluid modeling and control theoretic analysis showed that RED was a classical Proportional Controller with a delay element (the queue averaging mechanism. We identified the following flaws with RED

1. The “Proportional” control meant that RED could not control the queue length to a specified value, it is an inherent limitation of Proportional control. RED always controlled the queue (and hence delay) to some value between min_thresh and max_thresh depending on the load.

2. The delay element (queue averaging) introduced an additional instability to the control loop making it more difficult to control (and as Bob has said, the instability is  oscillations causing jitter and loss of some link throughput due to the oscillations).

We decided to redesign the controller but since RED was already implemented, create a controller that could use the same deployment with some minor modifications. So what we did to fix the issues was:

1. In classical control theory Integral control drives the steady state error to zero, so we changed the Proportional Control to Proportional Integral, or PI control which lets you control the buffer queue length to a specific, target value independent of the load.
2. We simply removed the queue averaging mechanism.

The resultant controller could work with existing RED implementations with a slight modification to the update equation.

-Vishal
--
http://www.cs.columbia.edu/~misra/

> On May 22, 2015, at 9:38 AM, Bob Briscoe <[email-masked]> wrote:
> 
> 
> I didn't mean that you need to justify better why you chose a PI controller. I said you need to "Articulate the Rationale for a PI Controller"

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 22 May 2015 20:49:19 +0000

>>[Bob] AFAICT, limiting the change in beta to no more than 2% will prevent PIE reacting fast to slow-start. Are you saying you intended to make PIE >>delay its response to a slow start? If so, ... eh? what? why?

>>Once a slow start has reached capacity, and is heading towards twice capacity in the next RTT (remembering the AQM doesn't know what a RTT is), >>an AQM could take a bet on whether the flow will finish before it gets to twice capacity, or not.
>>* If no, then in hindsight the AQM should have dropped a packet (in hindsight ideally when the queue first started to grow).

[RONG]: because the queue is filling up very fast during TCP's slow start, dropping too quickly would cause a timeout. As you mentioned, hopefully they will finish. In CableModem SpeedTest scenarios, however, we need to show the speed in the fast 10sec or so. The test flow is very long and we can not afford to incur a time out. In generic access link scenarios when flow multiplexing is low, this twist should help. Clapping it makes the convergences time slower. However, the drop probability should eventually catch up. Maybe changing this to "MAY" is more appropriate?

Thanks,

Rong

From: Bob Briscoe <[email-masked]<mailto:[email-masked]>>
Date: Friday, May 22, 2015 9:38 AM
To: rong <[email-masked]<mailto:[email-masked]>>
Cc: Richard Scheffenegger <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, Dave Taht <[email-masked]<mailto:[email-masked]>>, Greg White <[email-masked]<mailto:[email-masked]>>, AQM IETF list <[email-masked]<mailto:[email-masked]>>, "Eddy Wesley M. [VZ]" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] draft-ietf-aqm-pie-01: review

Rong,

I've snipped inline...

Thanks,

Rong

From: Greg White <[email-masked]<mailto:[email-masked]> >
Date: Wednesday, May 13, 2015 10:02 AM
To: Bob Briscoe <[email-masked]<mailto:[email-masked]>>
Cc: Richard Scheffenegger <[email-masked]<mailto:[email-masked]>>, "Eddy Wesley M. [VZ]" <[email-masked]<mailto:[email-masked]> >, Dave Taht <[email-masked]<mailto:[email-masked]>>, " [email-masked]<mailto:[email-masked]>" < [email-masked]<mailto:[email-masked]>>, AQM IETF list <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] draft-ietf-aqm-pie-01: review

[Greg] I don't know the origin of the 2% limit, but IMO it could very reasonably be that actual (simulated) traffic pointed out that the control theory prediction (based on linearized models of steady-state Reno IIRC) really wasn't the best guidance in all cases.  In fact, I really can't think of another reason why it would have been added.  To me your reaction precisely points out the danger of assuming that a bit of theory should be taken as guidance when the assumptions underlying the theory are known to only approximate reality in a constrained set of scenarios.  I did control theory and control system design for a while (e.g. â€Žwww.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf<http://www.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf> ).  I don't claim to be an expert anymore, but I know from experience that incorrect system modeling will result in incorrect controller design, and even in simple systems, reality needs to be considered strongly over theory.  In my testing of PIE, the algorithm (with the 2% limit) works.

Any AQM 'works'. As you say below, the important test is whether it 'works' better without the limit? And if so under what assumptions and what definition of 'works'?

I don't have simulation results with and without the limit, but I'm going to believe (until shown otherwise) that it was added for a real reason.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: It is designed to help in the one single TCP test during slow start phase. In this case, queue could quickly goes up during slow start and demands high drop proba…

[Bob] AFAICT, limiting the change in beta to no more than 2% will prevent PIE reacting fast to slow-start. Are you saying you intended to make PIE delay its response to a slow start? If so, ... eh? what? why?

Once a slow start has reached capacity, and is heading towards twice capacity in the next RTT (remembering the AQM doesn't know what a RTT is), an AQM could take a bet on whether the flow will finish before it gets to twice capacity, or not.
* If yes, then in hindsight the AQM wouldn't have needed to drop a packet.
* If no, then in hindsight the AQM should have dropped a packet (in hindsight ideally when the queue first started to grow).

By arbitrarily clamping the increase at 2%, it's making a judgement on the risk of each of these, and on the harm that would ensue if it makes the wrong call either way.

Delaying a drop improves performance of the flow in question if its going to end anyway (as you say), but it certainly means the slow-start will spike other flows harder (if the flow doesn't end of its own accord).

Good practice is for a host to use HSS (hybrid slow-start) or a similar technique to detect the end of slow start so it can stop SS just as it reaches capacity, not one RTT later. By putting off the drop that would end SS, you are rewarding flows that do not use HSS, which is the wrong incentive.

You are also potentially confusing HSS. From packet spacings, it thinks it's detected the approach of the end of SS. If the drop it expects doesn't actually appear, there's a strong danger that the sender will reverse its guess that SS is about to end, and move back into full SS. Then slam into the buffers, which are actually right where it thought they were.

Yup.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: Bob has a question of why choosing PI. I like the PI controller because AQM naturally has proportional (rate) and integral (queue length) com…

I think I must have phrased one of my comments badly (altho perhaps you're solely responding to a heading).

I didn't mean that you need to justify better why you chose a PI controller. I said you need to "Articulate the Rationale for a PI Controller". I meant (and said) that you do not actually even say what the aim of a PI controller is  - i.e. to keep queuing delay at the same level under a wide range of loads.

It wasn't a criticism of the choice of a PI controller, it was intended to be a helpful hint that you haven't explained your rationale well, for someone reading this who doesn't know the background.

Bob