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:29:17 -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 <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 <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 <http://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 <https://github.com/jridgewell/ns2/blob/master/queue/pi.cc>

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

---

From: John Leslie <[email-masked]>
Date: Mon, 26 Jan 2015 12:14:39 -0500

Vishal Misra <[email-masked]> wrote:
> <snip>
> <http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf>
>...

   I wish we'd discuss ECN more here, and state some benefit of its use;
perhaps even discuss how to route-around its misuse along the path.

   We should (IMHO) note that it's many years since its use in congestion
control could possibly be "the same as packet drop" -- and by the nature
of AQM, packets need to be ECN-marked before anything must be dropped
due to buffer overflow.

   Obviously (IMHO), an ECN-capable packet which encounters buffer
overflow needs to be dropped: not held until it can be ECN-marked and
forwarded.

--
John Leslie <[email-masked]>

---

From: Vishal Misra <[email-masked]>
Date: Mon, 26 Jan 2015 15:34:55 -0500

> overflow needs to be dropped: not held until it can be ECN-marked and

John,

Couldn't agree more.

That was sort of the whole idea behind the PI controller - something that predicts onset of congestion by observing the derivative in the queue length as well as the absolute value of the queue. One of the failings of RED that we identified in a companion paper to the PI one (http://dna-pubs.cs.columbia.edu/citation/paperfile/22/hollot01control.pdf) was that RED used _averaged_ queue length as the congestion indicator. That introduced a further delay to the feedback loop - by the time your average rose and you to decided to "mark" a packet the buffer was already close to overflowing.

With a PI(E) like scheme you can proactively ECN mark packets, keep the delays low but still keep the pipe fully utilized without needing to drop any packets. You can also use ECN marks with DiffServ and handle multiclass traffic (voice/real time streaming vs video downloads etc.) much more efficiently.

-Vishal

---

From: Dave Taht <[email-masked]>
Date: Tue, 27 Jan 2015 12:02:43 +1300

>> overflow needs to be dropped: not held until it can be ECN-marked and

Actually what happens on overflow in fq_codel is a packet from the
largest flow is dropped from
it's head, regardless of it's ecn marking. The ingress packet is
always accepted in the current implementation. It is certainly
possible to change this behavior, but as overflow is a very rare case
with the default packet limit, it does not seem to be a problem in
practice.

ecn is enabled by default in fq_codel. Some notes on actual use I've
seen are that it is entirely possible to have a fully utilized, low
latency, drop free network, and that at typical or long RTTs drop/mark
percentages decrease proportional to the rate of transmittal to
inconsequential values, while still preserving low latency and
throughput.

I would like to try a dctcp implementation against the aqms as
available today, and to compare the results against the default highly
specialized RED implementation dctcp presently requires.

> That was sort of the whole idea behind the PI controller - something that predicts onset of congestion by observing the derivative in the queue length as well as the absolute value of the queue. On…

There is not a lot of useful information in "average" queue length, yes.

http://www.pollere.net/Pdfdocs/QrantJul06.pdf page 14.

> With a PI(E) like scheme you can proactively ECN mark packets, keep the delays low but still

I note that the pie implementation in linux does, indeed, implement
ecn. (it is not enabled by default, you can enable it by specifying
the ecn parameter at instantation) However, due to the method it uses
for avoiding overflow, it will still drop ecn marked packets, when
perhaps it shouldn't, due to the randomized time it reacts within. I
have plenty of packet captures showing ecn and non ecn behaviors for
all the proposed aqm and packet scheduling schemes.

The current linux codel's ecn implementation is fully deterministic,
as is fq_codel's. I have a version under test that is also
deterministic but more explicitly handles the more dramatically out of
bounds  conditions by dropping, rather than marking ecn-marked
packets, before the overall queue limit is hit. That portion of the
revised algorithm works well, but there is another tweak that isn't
working, and no further development has been funded.

>keep the pipe fully utilized without needing to drop any packets. You can also use ECN marks with DiffServ and handle multiclass traffic (voice/real time streaming vs video downloads etc.) much more efficiently.

I look forward to seeing a diffserv enabled implementation of pie or
pie-fq. In the "sqm-scripts" package for openwrt and cerowrt, there is
the ability to test variants of a 3 tier classification scheme, with
pie, codel, fq_codel, multiple test *codel variants, sfq, sfb, and
fifo qdiscs. Extensive benchmark results are available, and you are
perfectly welcome to merely run these scripts on any linux distro
shipped in the past 2 years.

Essentially this 3 tier scheme is what has deployed in many
aftermarket home router distributions, and in netgear's dynamic QoS.
What streamboost does (partially fq_codel based) is a bit different,
attempting to provide bandwidth garuntees for various services like
netflix, and it's too confusing to describe here.

Since there seemed to be no interest in the ietf for documenting what
has deployed, I have not taken this draft any further,
http://snapon.lab.bufferbloat.net/~d/draft-taht-home-gateway-best-practices-00.html

Work proceeds slowly on "cake", which incorporates what works so far
in the above deployments in pure C, and adds full diffserv support to
multiple levels of fq_codel. Patches for that are available on
request. I am told there are several wfq + codel implementations being
developed, and there is out there somewhere, an fq-pie.

> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm

-- 
Dave Täht

thttp://www.bufferbloat.net/projects/bloat/wiki/Upcoming_Talks

---

From: Dave Taht <[email-masked]>
Date: Tue, 27 Jan 2015 12:46:10 +1300

> working, and no further development has been funded.

I think I have described that tweak here before. What happens in that version
of test codel is that if a drop happens for any reason, the very next packet is
attempted to be marked with ECT, if ECN is available. This provides an
immediate signal of congestion, while still shedding actual load.
If you only hit one flow, you've done that. If you hit two flows, all
the better.

It works,
but real differences in behavior are hard to discern at the typical rates and
RTTs I work at, with the benchmarks I have.

The same idea could be easily applied to pie.

At the moment anything that treats ECN as substantially different to
drop in the aqm layer is kind of anathema to me as the control logic
has to run very, very fast, and some folk even begrudge the needed
packet inspection and if statements required to do the ecn check at
all.

I do feel, that preserving the current ECN behavior(s) of pie or
fq_codel, and exploring different TCP variants on the endpoints to how
they react to a mark, might be fruitful more short term and further
improvements evolve in sync with the many, many improvements that have
happened in TCP over the last few years.

-- 
Dave Täht

---

From: Vishal Misra <[email-masked]>
Date: Mon, 26 Jan 2015 19:15:32 -0500

Agreed. ECN has to be a "drop in replacement" for a drop.

-Vishal

> On Jan 26, 2015, at 6:46 PM, Dave Taht <[email-masked]> wrote:
> 
> has to run very, very fast,

---

From: KK <[email-masked]>
Date: Tue, 27 Jan 2015 02:51:25 -0800

I am not a participant on this list (I should join), but was forwarded
this particular email - which was certainly of interest to me.

As described in the ECN RFC, we had constructed ECN to explicitly take
advantage of AQM mechanisms, and would indeed provide the benefits of AQM
-- reduced packet latency and loss. One of the implicit benefits of AQM is
the decoupling of loss from being the key means for congestion management,
and ECN is the means for AQM to provide the necessary indication needed
for the feedback control loop to work.

On the comment made below - when we constructed ECN, we were particularly
careful to make the scheme robust to loss of the packets carrying the
indication (whether in the packet or the Acks). The CWR provides a means
for the source taking the action (and thus completing the feedback control
loop) to provide an indication that the ECN notification has been acted
upon. We fully recognized that buffer overflows can cause ECN-marked
packets (and/or Acks) to be lost. Thus, there is no reason to set aside
ECN-marked packets for being forwarded when the buffer overflows.
Obviously, we would like this to not happen frequently (and if all the
sources were cooperating (obviously only in an ideal world) and the
AQM/ECN mechanism was working, it wouldn¹t happen frequently), but the way
ECN is constructed, it is robust to such occurrences.
Thanks,
-- 
K. K. Ramakrishnan
Professor
Dept. of Computer Science and Engineering
University of California, Riverside
Rm. 332, Winston Chung Hall
Tel: (951) 827-2480

>
>> Begin forwarded message:
>> 
>> Date: January 26, 2015 at 12:14:39 PM EST
>> From: John Leslie <[email-masked]>
>> To: Vishal Misra <[email-masked]>
>> Cc: [email-masked]
>> Subject: ECN: was Control Theoretic Analyses of PI(E)
>>

---

From: Vishal Misra <[email-masked]>
Date: Tue, 27 Jan 2015 08:30:58 -0500

> On Jan 26, 2015, at 6:02 PM, Dave Taht <[email-masked]> wrote:
> 
> 

That would be interesting. The default DCTCP AQM mechanism is RED without the averaging, which is a good thing, but it uses proportional marking. The proportional controller is the "fastest" controller you can design however the drawback is you cannot regulate (control) the delay/queue length to a fixed value. The PI controller fixes this issue.

The authors of DCTCP also tried to implement the PI controller however they found the performance was not as good. This shouldn't be a surprise as the design guidelines that the authors used for PI followed our original paper where the dynamics followed vanilla TCP. Since DCTCP follows different dynamics, the PI controller needs to be adjusted accordingly. I am happy to work with you on this if there is interest. 

> There is not a lot of useful information in "average" queue length, yes.

We have argued something stronger - average queue length actively _hurts_ a feedback loop that has significant delays.

> shipped in the past 2 years.

Our DiffServ+PI design was published here: http://dna-pubs.cs.columbia.edu/citation/paperfile/31/Chait_02.pdf - I'll take a look at the distribution and see if we can implement our scheme with openwrt.

> netflix, and it's too confusing to describe here.

Our DiffServ design did something very close to that - offered a minimum guaranteed rate (MGR) for the AF service using two-colored marking. 

-Vishal

---

From: KK <[email-masked]>
Date: Tue, 27 Jan 2015 07:55:43 -0800

Because of DCTCP¹s differences in the approach to marking and the
different control reaction at the end-system, I have wondered about 2
things:
1) How it interoperates with the flows that have to go over the WAN -
where you may have a different marking method, and end-systems that have
the traditional TCP end-system reaction
2) What are the limits for the feedback delay with the marking based on
the instantaneous queue state that is used - and the proportional
controller employed.
Thanks,
-- 
K. K. Ramakrishnan
Professor
Dept. of Computer Science and Engineering
University of California, Riverside
Rm. 332, Winston Chung Hall
Tel: (951) 827-2480

On 1/27/15, 5:30 AM, "Vishal Misra" <[email-masked]> wrote:

>That would be interesting. The default DCTCP AQM mechanism is RED without
>the averaging, which is a good thing, but it uses proportional marking.
>The proportional controller is the "fastest" controller you can design
>however the drawback is you cannot regulate (control) the delay/queue
>length to a fixed value. The PI controller fixes this issue.
>
>The authors of DCTCP also tried to implement the PI controller however
>they found the performance was not as good. This shouldn't be a surprise
>as the design guidelines that the authors used for PI followed our
>original paper where the dynamics followed vanilla TCP. Since DCTCP
>follows different dynamics, the PI controller needs to be adjusted
>accordingly. I am happy to work with you on this if there is interest.
>
>
>> 
>>> That was sort of the whole idea behind the PI controller - something
>>>that predicts onset of congestion by observing the derivative in the
>>>queue length as well as the absolute value of the queue. One of the
>>>failings of RED that we identified in a companion paper to the PI one
>>>(http://dna-pubs.cs.columbia.edu/citation/paperfile/22/hollot01control.p
>>>df) was that RED used _averaged_ queue length as the congestion
>>>indicator. That introduced a further delay to the feedback loop - by
>>>the time your average rose and you to decided to "mark" a packet the
>>>buffer was already close to overflowing.
>> 
>We have argued something stronger - average queue length actively _hurts_
>a feedback loop that has significant delays.
>
>> keep the pipe fully utilized without needing to drop any packets. You
>>can also use ECN marks with DiffServ and handle multiclass traffic
>>(voice/real time streaming vs video downloads etc.) much more
>>efficiently.
>> 
>Our DiffServ+PI design was published here:
>http://dna-pubs.cs.columbia.edu/citation/paperfile/31/Chait_02.pdf - I'll
>take a look at the distribution and see if we can implement our scheme
>with openwrt.
>
>Our DiffServ design did something very close to that - offered a minimum
>guaranteed rate (MGR) for the AF service using two-colored marking.
>> -- 
>> Dave Täht
>>

---

From: Dave Taht <[email-masked]>
Date: Wed, 28 Jan 2015 09:04:29 +1300

> the traditional TCP end-system reaction

It is finally easy to test that!

Long held in outdated, hard to use, out of tree patches, DCTCP entered
the linux mainline kernel recently:
http://www.ietf.org/mail-archive/web/aqm/current/msg00804.html

And related support infrastructure for finer grained per-route ecn
landed shortly thereafter:

http://comments.gmane.org/gmane.linux.network/337395

Given the fragility of the needed infrastructure configuration (need
ecn on, need dctcp enabled, need the routers and switches on the path
configured properly) it is a certainty that someone will accidentally
test dctcp in the wan scenario, and it would be good to get an idea
for what happens non-accidentally.

There is at least one patch, I think, still out of tree, that improved
tcp ecn fallbacks for syns.

DCTCP also is now available in freebsd:
http://lists.freebsd.org/pipermail/freebsd-net/2014-February/037915.html

> controller employed

On short RTTs... with TSO enabled... with GRO enabled... with
incast... with short flows... with long flows... with competing
traffic....

-- 
Dave Täht