Subject: [aqm] Control Theoretic Analyses of PI(E) (was Gen-art LC review of draft-ietf-aqm-recommendation-08)

From: Vishal Misra <[email-masked]>
Date: Mon, 26 Jan 2015 04:20:21 -0500

On 08/01/15 01:20, Fred Baker (fred) wrote:

>> Yes. I think something like this would be good.   The buffer bloat
>> example is probably an extreme case of things not having AQM at all
>> and interacting badly.  It would maybe be worth mentioning that any
>> AQM  mechanism has also got to work in series with boxes that don't
>> have any active AQM - just tail drop. Ultimately, I would say this
>> is just a matter of control engineering principles:  You are
>> potentially making a  network in which various control algorithms
>> are implemented on different legs/nodes and the combination of
>> transfer functions could possibly be unstable.  Has anybody applied
>> any of the raft of control theoretic methods to these algorithms?
>> I have no idea! 

>Well, PIE basically came out of control theory (a basic equation that
> describes a phase-locked loop), and I believe that Van and Kathy will
> say something similar about Codel. But that’s not a question for this
> paper, it’s a  question for the various algorithmic papers.

Elwyn, 

I would like to expand on a comment that Fred made above.  He is
absolutely correct, about PIE coming out of control theory. PIE is
based on the PI AQM algorithm proposed by us back in 2001
(http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf),
where we showed the  benefits of using a PI controller to regulate queue
lengths and delays through a formal control theoretic analysis. The PI
algorithm itself came from a fluid model of TCP+AQM that we developed
(http://dna-pubs.cs.columbia.edu/citation/paperfile/27/sigcomm2000.pdf)
and the model is referenced in the IETF draft. 

When we designed PI, we took great care in designing an algorithm that
was amenable to a very simple implementation at line speeds. We could
have gone in the direction of sophisticated (non-linear/optimal)
control algorithms but we instead kept simplicity of implementation front and
center and it is great to see that the standards community has come to
appreciate the work.

The PIE update algorithm is very similar to the original PI algorithm (we
controlled queue length to a reference value whereas PIE controls
delay by dividing the queue length by measured link capacity) - Rong
Pan and the PIE team have done great work in adapting the originial
algorithm for implementation in production environments and all our
original analyses carries through to PIE. I am happy to provide
references to more control theoretic analyses (including ours) that
look at the behavior and stability of the AQM algorithms.

One thing to note though that hasn't changed all these years is if you
look at Section VII.A of our PI paper linked above, the full benefits
of AQM are realized in conjunction with ECN. On a bottlenecked link,
if you reduce delay (by controlling it via a mechanims like PI(E) or
CoDel), unless you have ECN implemented you will end up increasing
loss rates which may not be a good thing.

Lastly, I had contributed pi.cc to ns2 back in 2001 - a version seems
to have survived all these years if anyone is interested in playing with it:

https://github.com/jridgewell/ns2/blob/master/queue/pi.cc

Thanks,
-Vishal

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