Subject: [aqm] the cisco pie patent and IETF IPR filing

From: Dave Taht <[email-masked]>
Date: Tue, 3 Mar 2015 22:07:43 -0800

Two items:

A) The IETF IPR filing   http://datatracker.ietf.org/ipr/2187/ points
to the wrong patent: 13/874,500. A google search for that patent
number brings up http://www.google.com/patents/US20130239255"

 It is ironically relevant to the discussions at hand, as that one concerns:

Abstract:

"Provided are methods of increasing the tolerance of a plant to
abiotic stresses and/or increasing the biomass and/or increasing the
yield of a plant by expressing within the plant an exogenous
polynucleotide homologous to SEQ ID NO:13."

... As I consider myself a near-vegetable, and am 40 pounds heavier,
and not responding particularly well to antibiotics, after
participating for the past several years on all the ietf mailing lists
I just got off of. I am sure that upon acceptance of pie in the ietf,
that making that particular patent more generally available for all to
use would probably have similar effects on others.

The correct patent number for PIE, 13/874,600, is here:

http://www.google.com/patents/US20140328175

I would appreciate that the IPR filing be corrected.

In the meantime, here's some more great NSFW george carlin routines!

https://www.youtube.com/watch?v=tVlkxrNlp10

B) Vishal Misra (author of PI) gave me pointers to his PI papers
recently (and he had NO idea at all his work was used for pie! - he
got his marketing department to issue a press release about it:
http://engineering.umass.edu/news/got-bufferbloat-umass-amherst-research-behind-fix
)

I usually have a pretty strict policy about never reading patents, but
I read all those papers [1], and both! patents above. I had not fully
realized that the PI-AQM work went as far back as 2001. The PI update
equation and the PIE update equation, look pretty darn similar, just
the meanings of two variables, changed.

C) I am kind of curious if any working code for the original PI
algorithm exists for linux?

D) oh, never mind, I will blog about the rest one day.

[1] still prefer fq_codel.

-- 
Dave Täht
Let's make wifi fast, less jittery and reliable again!

https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb

---

From: Vishal Misra <[email-masked]>
Date: Wed, 4 Mar 2015 03:17:11 -0500

Hi Dave,

Thanks for your email. A few quick points:

- I have actually sent a note already to someone on the Cisco PIE team
about the error in the IETF IPR filing and am sure they will get it
corrected. You have helpfully dug out the actual patent application
and it appears that one digit got inadvertently changed in the Cisco
IETF IPR declaration of the patent application.

- I wish I had a "marketing department" that would do stories for me
:-). I work at Columbia University and that story that you point out
was done by a writer at the UMass-Amherst engineering school as an
example of academic research having practical impact. There is an
urgent need to support more academic research and I think stories like
this one support the cause.

- Indeed neither me nor any of the other PI authors had any idea of
the PIE work. I discovered it accidentally when I was at MIT giving a
talk on Network Neutrality and Dave Clark mentioned Cisco's PIE and
DOCSIS 3.1 to me. I later read up on PIE and was pleasantly surprised
that our PI work from more than a decade back evolved into it.

- I had contributed the PI code to Sally Floyd back in 2001 and it has
been part of ns2 for the longest time (pi.cc). It shouldn't be
difficult to adapt that for a Linux implementation and I am happy to
help anyone who wishes to try it. Maybe that might affect your loyalty
to fq_codel.

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

> On Mar 4, 2015, at 1:07 AM, Dave Taht <[email-masked]> wrote:
>
> Two items:
>

---

From: KK <[email-masked]>
Date: Wed, 04 Mar 2015 01:01:19 -0800

I think a combination of PI/PIE/fq_codel with ECN would enable us
a) be less dependent of the physical amount of buffering that is
implemented on the intermediate devices
b) allow us to use buffering for what it is meant to do - ride out
transient variations in traffic, at points where there is a mismatch in
available capacity
c) allow us to support different types of links, including wireless lossy
links
d) as we wrote in the ECN RFC, allow even short-lived transfers to not
suffer
Thanks,  
-- 
K. K. Ramakrishnan
Professor
Dept. of Computer Science and Engineering
University of California, Riverside
Rm. 332, Winston Chung Hall
Tel: (951) 827-2480
Web Page: http://www.cs.ucr.edu/~kk/

On 3/4/15, 12:17 AM, "Vishal Misra" <[email-masked]> wrote:

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

---

From: David Lang <[email-masked]>
Date: Wed, 4 Mar 2015 01:42:45 -0800 (PST)

On Wed, 4 Mar 2015, KK wrote:

> Date: Wed, 04 Mar 2015 01:01:19 -0800
> From: KK <[email-masked]>
> To: Vishal Misra <[email-masked]>, Dave Taht <[email-masked]>
> Cc: "[email-masked]" <[email-masked]>, bloat <[email-masked]>
> Subject: Re: [aqm] the cisco pie patent and IETF IPR filing
> 

The question is how much of a burst should the buffer be able to handle? Right 
now buffers routinely hold 10+ seconds worth of traffic (and Dave T showed the 
airline system buffering 10+ MINUTES of traffic)

The problem is that if you buffer too much, you break the TCP link speed 
probing, and if you buffer even more you end up with the sender genrating a new 
packet to deliver while you still are buffering the old one.

Buffers need to hold less than one second worth of traffic, and emperical 
testing is showing that much less is desirable (Others can post more exact 
numbers, but I belive that somewhere between 1/100 of a second and 1/10 of a 
second is a reasonable range)

> c) allow us to support different types of links, including wireless lossy

If a retry is fast and has a very high probability of succeding, then it may be 
worth holding it and doing a link-level retry. But the existing mess that is 
wifi is hardly a good example of this being the right thing to do in a congested 
environment.

David Lang

---

From: KK <[email-masked]>
Date: Wed, 04 Mar 2015 11:49:01 -0800

>second is a reasonable range)
I agree with what you¹re saying. Excessive buffers and the resultant
queueing is indeed bad and undesirable. And I am glad all are recognizing
that this needs to be overcome and the efforts for AQM and Bufferbloat are
appreciated.

Once you have mechanisms that provide a signal when the queue builds up,
rather than the buffer filling up, this helps tremendously. And under good
circumstances, having loss is just as good an indicator because that loss
can be overcome by all the associated mechanisms we have built around it
to recover and mitigate its impact. ECN provides the same benefit, except
that it also continues to work when circumstances aren¹t all that ideal
(start of a flow, small windows etc.).

Once we have these (AQM, feedback) mechanisms, vendors can make a more
sensible judgement of how much buffer to put in, and more than likely
reduce buffering (and cost)...
>wifi is hardly a good example of this being the right thing to do in a
Exactly. If you have good recovery mechanisms for loss (and not
necessarily interpreting it as congestion), then you don¹t have to make
link layer mechanisms work Œovertime¹ to keep retrying and avoid that
loss. Decoupling indications for congestion from loss seems to me a good
thing - unless you know that there are un-intended consequences to this.

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Wed, 4 Mar 2015 22:08:06 +0000

The correct Cisco IPR is http://datatracker.ietf.org/ipr/2540/.

Vishal has done pioneering work in TCP modeling and in bringing in the
classical PI controller into the AQM space. I have certainly learned a lot
from him. We referenced their paper in our draft and paper, we even
mentioned his name in our PIE paper.

PIE and PI equations are similar because they are all classical
Proportional Integral controller (PI) based. We have never claimed the
ownership of classical PI controller that works like a charm. PI AQM's
design: Equation (8) in the original paper is a direct z-domain transfer
of the classical PI controller: K*(s/wg+1)/s. Our designs share a lot of
the good features inherited directly from the classical PI controller.

However, PIE is not equivalent to PI AQM:

----------------------

1) Our design is more than just a z-transform of the classical PI
controller.
Beyond math, any engineering problem has implementation and parameter
sensitivity issues associated with them. In our form of the PI controller,
we control the offset to the reference level and second moment of the
latency
independently by alpha and beta. They are often orders of magnitude apart.
This makes PIE a lot easier to tune.

2) PIE adopted the classical PI controller for latency. The latency
measurement through rate estimation turns out to be more challenging than
expected. We have ideas on how to determine when we
can have a rate sample, etc. We have to make the rate calculation work in
a robust way for real network scenarios.

3) PIE's auto-tuning:
if (PIE->drop_prob_ < 0.1%) {
	alpha'= alpha/128 and beta' = beta/128;
      } else if (PIE->drop_prob_ < 1%) {
	alpha'= alpha/16 and beta' = beta/16;

      } else if (PIE->drop_prob_ < 10%) {
	alpha'= alpha/2 and beta' = beta/2;

      } else {
	alpha'= alpha and beta' = beta;
      }

Self-tuning enables PIE to cover various network conditions.

4) We have improved the single TCP flow's performance dramatically by
reducing bursty drops and adopting bursty protection regions. We can
provide good performance for one single TCP session within seconds.

------------------------

Vishal's pioneer work certainly is an important step in advancing our
knowledge in AQM. PIE is a solid step forward given the requirements of
current challenging environments. Both PIE and PI AQM stand on the giant
shoulders of the classical PI controller.

Regards,

Rong

---

From: Dave Taht <[email-masked]>
Date: Wed, 4 Mar 2015 15:37:57 -0800

> The correct Cisco IPR is http://datatracker.ietf.org/ipr/2540/.

Thank you very much for the pointer to the correct IPR filing.

I apologize for being grumpy.

---

From: David Collier-Brown <[email-masked]>
Date: Thu, 05 Mar 2015 08:14:00 -0500

On 03/04/2015 04:42 AM, David Lang wrote:
>
> The question is how much of a burst should the buffer be able to 
> handle? Right now buffers routinely hold 10+ seconds worth of traffic 
> (and Dave T showed the airline system buffering 10+ MINUTES of traffic)
>
> The problem is that if you buffer too much, you break the TCP link 
> speed probing, and if you buffer even more you end up with the sender 
> genrating a new packet to deliver while you still are buffering the 
> old one.
>
> Buffers need to hold less than one second worth of traffic, and 
> emperical testing is showing that much less is desirable (Others can 
> post more exact numbers, but I belive that somewhere between 1/100 of 
> a second and 1/10 of a second is a reasonable range)

I'd suggest that buffers are there to hold unexpected bursts of traffic 
above the steady state maximum.  This can happen for several reason:
1)  due to the sender sending an unexpected wodge, either at startup or 
due to a bug, or
2) after a period of non-transmission, due to something in the pipe 
slowing us down momentarily.

Either case of (1)  should be throttled, so bugs and 
super-fat-start-eats-the-network can be avoided (;-))
Case of (2) need to be buffered, in an amount that handles either the 
average/expected burstyness of the link, or handles the predictable 
burst when one stream on the link slows down and then catches up.

Let's say the link varies by +/- 1 packet/second: we should have 
buffering for 2, probably for 3 and definitely not for any bigger sigma.

--dave

-- 
David Collier-Brown,         | Always do right. This will gratify
System Programmer and Author | some people and astonish the rest
[email-masked]           |                      -- Mark Twain

---

From: Dave Taht <[email-masked]>
Date: Thu, 5 Mar 2015 05:58:26 -0800

> this one support the cause.

Well, yes and no. One thing I have tried really hard to do throughout
this project is give credit where credit is due, at every talk for
example, always mentioning pie, even before I actually had any data on
it's performance.- I try to give every individual that has contributed
something to this "stone soup" project, as here at uknof -

https://plus.google.com/u/0/107942175615993706558/posts/immF8Pkj19C

praise - for what they did to help out. There have been an amazing
level of details to sort out along the way here at every level in the
OS stack, and in the hardware and there is simply no one individual or
company I would single out as truly key, except maybe George P.
Burdell!

A lesson I have learned is that folk in marketing are not particularly
good at correctly distributing credit, and I assume that is how they
are taught to write, to not look at any facts outside of their
immediate objectives. [1]

http://newsroom.cisco.com/feature-content?type=webcontent&articleId=1414442

and 'course nobody in the press has shown up with a photographer to
write puff pieces about the overall effort except, well, cringely's
work is not puffy enough by marketing standards:  (
http://www.cringely.com/tag/bufferbloat/ )

I admit to a great deal of frustration when nick weaver writes an
otherwise *excellent* piece in forbes,
http://www.forbes.com/sites/valleyvoices/2015/02/27/this-one-clause-in-the-new-net-neutrality-regs-would-be-a-fiasco-for-the-internet/

 and expends 3+ paragraphs explaining bufferbloat, but never gives the
reader a link back *to the word* so that maybe, some CTO or CEO that
reads that rag would have some context and clue when an engineer comes
up to him asking for permission to go implement a fix that is now,
basically, off the shelf.

*I* am going to keep giving credit to everyone I can, in every talk
and presentation I do, and there are quite a few core contributors
that I wish I had called out by name more - for example, I would have
mentioned felix feitkau's contribution towards fixing wifi at the
nznog talk if I could correctly pronounce his name! I struggled for
years to be able to pronounce juliusz's!

At the very least, I hope we can do more from a SEO perspective - and
all *pull together* to get the message out - that bufferbloat is
fixed, that solutions are being standardized in the ietf, and the code
is widely available on a ton of platforms already - and move to
somehow get to where ISPs are announcing settings for things like
openwrt + sqm-scripts, and more importantly - schedules for rolling
out fixes (like docsis 3.1 and better CPE) to their customers.

everyone:

What else more can we do here to cross the chasm?

> help anyone who wishes to try it. Maybe that might affect your loyalty

I let the data take me where it may. I (not) always have, but reformed
about 15 years ago. [1] I hope that you and your students also,  do
some experiments on the successors to PI and RED and DRR - and also
follow the data where-ever it leads you.

I was fiercely proud of sfqred - until fq_codel blew it away on every
benchmark I could devise. I have long longed to find another
independent expert in the field to create new experiments and/or
recreate/reproduce/disprove our results.

[1] "For a successful technology, reality must take precedence over
public relations, for Nature cannot be fooled. " - Richard P. Feyman,
Challenger Disaster report:
https://www.youtube.com/watch?v=6Rwcbsn19c0

---

From: Vishal Misra <[email-masked]>
Date: Fri, 6 Mar 2015 14:46:14 -0500

Hi Dave,

> On Mar 5, 2015, at 8:58 AM, Dave Taht <[email-masked]> wrote:
> 

In 2003 we had published a paper on STPI (Self-Tuning PI). The self-tuning design accounted for variations in link capacity, presence of cross traffic (i.e. unregulated UDP flows) and variations in the number of flows being controlled. We also proved the (local, exponential) stability of our self-tuning mechanism.

The paper is available at http://dna-pubs.cs.columbia.edu/citation/paperfile/79/GLOBECOM_2003_STAQM.pdf

This was an evolution over our first PI design where we introduced the concept of linear controllers for AQM.

BTW STPI is not PIE, the differences as I see them are

(1) STPI explicitly accounts for cross traffic.
(2) STPI tunes the parameters continuously, over the entire range of loss (marking) rates unlike PIE which seems to be doing it for 3 specific values chosen ahead of time.
(3) The stability of the adaptive mechanism of STPI was rigorously proven in a linearized setting. 
(4) The tradeoff between stability and responsiveness for the time constant of adaptation was made explicit.
(5) STPI does not, as the author of PIE stated recently "control the offset to the reference level and second moment of the latency independently”. STPI simply controls the latency, I don’t know of any way to control the second moment of any reference signal by a linear controller like PI(E), but then I do not know the details of PIE. It was a very deliberate design choice by us to introduce a linear controller like PI for AQM because of ease of implementation. We could’ve gone the route of optimal and/or non-linear controllers but we didn’t.

As a side note, we also designed a self-tuning version of RED that we called STRED (different from ARED) but RED suffers from some fundamental limitations so exploring that won’t be of interest.

So I am getting STPI and PI implemented as part of cerowrt and will release the code for anyone to play with/evaluate.

More than anything, it is the increased deployment of ECN that has revived an interest in AQM for me.

-Vishal