Subject: Re: [aqm] AQM schemes: Queue length vs. delay based

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 15 Nov 2013 18:19:47 +0000

Please see inline…

Thanks,

Rong

From: Michael Welzl <[email-masked]<mailto:[email-masked]>>
Date: Friday, November 15, 2013 3:06 AM
To: Cisco Employee <[email-masked]<mailto:[email-masked]>>
Cc: Naeem Khademi <[email-masked]<mailto:[email-masked]>>, Preethi Natarajan <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] AQM schemes: Queue length vs. delay based

Hi,

Interesting discussion!

I would like to say that in my opinion the real value of what Naeem has presented is not so much in pushing ARED, but in:

- reminding people that there was AQM stuff done between RED and CoDel, and some of this is worth looking at. Rong, we're aware of at least some of your previous work, and I'm personally a fan of CHOKe. However I do understand that CHOKe is probably not appropriate for the problem we're trying to solve here ... but you know, there were lots and lots of others made (e.g. AVQ, just to toss another name of an AQM that seemed to be well done to me when I read about it all these years ago)

------------------------------------------
>>>>>>>RP: Thank you! The comment about throwing away all experiences sounded ignorant.  I am aware of AVQ, and I am a fan of virtual queue concept (brought out by Frank Kelly ) in general. PCN that Bob is pushing is along these lines of work. I wish the industry as a whole can embrace the concept.
------------------------------------------

- hopefully helping set the bar a bit higher regarding evaluations. I'm not saying we did enough (e.g. we didn't get to look at anything else than bulk TCP transfers yet), but I think we've done more than I have seen documented elsewhere so far (apologies if we missed a study; we tried to cover them in the table in our tech. rep.).

I just personally found it a bit pathetic to first see CoDel and PIE presented with comparisons against only themselves and RED, and then see that the more-than-a-decade-old-ARED very often performs better than both of them. It makes me wonder how many other 5-10 year old AQMs are at least as good as CoDel and PIE.

------------------------------------------
>>>>>>>>RP:  RED is the only one out there that got wide adoptions. Compared with the state of the art in products (not in papers) is the idea. But that does not mean we don't know/learn from other AQM schemes. As matter of fact, PI controller and AVQ came out about the same time. PIE also adopts the PI controller design. From my years of experience, I think PI controller is a better controller in this space as queue and rate lend themselves to be the proportional and integral pair.

>>>>>>>>RP: I disagree with the notion that ARED often performs better. If tight delay control comes from narrow-band bang-bang control, the tail drop with shallow buffer would behave similarly. For example, if target_delay = 1ms, min_th = 0.5ms and max_th = 1.5ms, the queue really allows one packet in the queue. I don't see how this will be different from tail drop.  Your throughput plot showed 25% throughput loss. This is a case considered good?
-----------------------------------------

About this:

RP: If low latencies are achieved at the cost of losing quite a bit of throughput, it is a no-starter for AQM design.

That's rather obvious  :-)    but it's about the relationship between the two. e.g., the evaluations in the original CoDel paper essentially showed that CoDel gave higher throughput than RED at the expense of more latency. That's not exactly convincing either, given that latency reduction is the main goal we're pursuing now. And for ARED, we're only talking about a subset of scenarios (and perhaps not even the most relevant ones -  e.g. do we really care that much about the throughput of one single TCP connection?). Let's not forget that in many scenarios that we looked at (in fact, I'd say this was the majority of cases) it had better throughput AND lower delay than CoDel and PIE. I would also venture to guess that the problem with low multiplexing cases could be addressed relatively easily.

------------------------------------------
>>>>>>>>RP:  Again, the tight delay control comes from narrow-band bang-bang control with hard drops. The scenarios that throughputs are good are in higher congestion scenarios where there are enough packets showing up to fill the pipe. That is not the effectiveness of AQM. Tail drop with shallow buffer will have high throughput in those cases too. Try a scenario when link is congested and a burst comes, see how many packets of that burst can go through.
------------------------------------------

Naeem and Preethi have agreed that some significant design changes would be necessary to make use of ARED as a new delay-based AQM. I agree, but mainly I'd expect these significant changes to deal with ECN (where we made the point that ALL AQMs should be changed in fact (*), but that's another story) and with WLAN scenarios, where ARED performed quite badly. We'll see - mainly we conclude that it's probably worth playing around with it.

---------------------------------------------
>>>>>>>>RP:  Sure. The significant design changes to ARED won't be just for ECN, but to address the core issue of how effective ARED is as an AQM scheme. Don't get us wrong -- we would be happy to see these improvements on ARED.  Just a side note and you seemed to know what happened in the early 2000 time frame.  Sally's ARED paper did not eventually publish because there was a consensus in the community that control analysis is essential in AQM (other papers like AVQ and PI do have control analysis). It would be great if your group can add in this space too, especially auto-tuning needs deeper understanding of the knobs involved.

Best Regards,

Rong
-------------------------------------------

Cheers,
Michael

---

From: Michael Welzl <[email-masked]>
Date: Fri, 15 Nov 2013 20:35:49 +0100

Hi,

In line, but snipping some things away:

> [About evaluating against other-than-RED AQMs]

Ok, fair point about RED, and I agree that a PI controller can do well. The "SoA in products" bit makes me wonder - I never really knew, but since it's in principle easy to deploy an AQM scheme (you design it, you like it, you put it in your product?), I always assumed that RED wouldn't be the only one out there.

Now from this and other recent discussions I get the impression that RED *is* the only one that was ever turned on, and maybe the only one shipped? Do you know, is that the case? Just curious...  I guess that some products would sell with a strange secret AQM scheme that works very well, or not? That was just my imagination.

> >>>>>>>>RP: I disagree with the notion that ARED often performs better. If tight delay control comes from narrow-band bang-bang control, the tail drop with shallow buffer would behave similarly. Fo…

By "often" I mean pretty much all cases except the very lightly loaded or extremely low target delay cases that you keep referring to.

Maybe we disagree about the goals... why would you want to allow a burst on an already congested link?

> Naeem and Preethi have agreed that some significant design changes would be necessary to make use of ARED as a new delay-based AQM. I agree, but mainly I'd expect these significant changes to deal…

Well, sounds like your opinion about that consensus; no doubt that analysis makes a paper stronger, but also no point in speculating about the reasons why she never got it published.

Getting back to the matter at hand, call me naive, but it seems to me that ARED was doing just the right thing in mildly loaded to overloaded scenarios, i.e. "bang bang" control may be just the right thing to do then? On that basis, isn't it a matter of just detecting the lightly loaded scenarios and becoming less aggressive under these circumstances? I suppose that the control could be tuned to do that. But this is just speculative...

Cheers,
Michael

---

From: Dave Taht <[email-masked]>
Date: Fri, 15 Nov 2013 11:59:37 -0800

I have been doing my best to ignore this thread.

Gripe #1:

What I saw of the ARED presentation seemed to show that if you
sacrificed quite a bit of throughput you'd get vastly better latency,
on a very simple set of benchmarks. I can go through each slide to see
where there were results that were in obvious.

The goal in this exercise is to aim for 100% utilization at 0 latency.

#2)

I also find box plots while often informative to be misleading when
thinking about network dynamics, where you care more about the
patterns of the outliers. At some point I suspect I'll go back to
using them on appropriate benchmarks but I generally prefer raw graphs
of the data and cdf plots of the summary data.

#3) The bufferbloat effort has been in full swing for 3+ years now.
Unlike previous efforts we didn't stop for publication, patents, etc,
but published results as fast as we could on the bloat list, and
cycled code into ns2 and the linux kernel as fast as possible. In
nearly cases there were negative results, which are hard to publish
anyway. I apologize for having not left a academic paper trail that
could be followed, but as there was no funding for the effort
whatsoever and very little benefit to me as to academic publishing, we
skipped it. Secondly, as fast as I found what seemed to be a problem,
or an interesting result worth writing about, Eric Dumazet and other
members of the netdev group of linux viewed it as a bug, and fixed it
- to the point where the linux stack looks nothing like it did when it
started. I would like it very much if others merely reported their
interesting results and treated them as bugs to be fixed rather than
papers to be written.

I hope to document some of this stuff in an upcoming fq_codel rfc. And
I'd certainly love to make CCR, ACM queue (again) and lwn, but we're
at the point where code is being seriously deployed and I'm mostly
engaged in fixing wifi right now.

Some history for the new:

I started with wonder shaper, and wondering why it didn't scale up,
and how to address it's flaws.

A big focus was how to fix variable bandwidth systems like cable,
wireless and wifi, where fixed rates were inadequate. Secondary was
finding a fixed rate system that would work against things like DSL.
We figured if we fixed the first, the second would be easy.

I'd tried RED back in the early 00s and wondershaper blew it away...
Moved from there to SFB, which was fixed and pushed into the linux
kernel first of all the ideas we had. It didn't work worth a damn.
Kathie and Van of course had RED at their disposal, and thinking about
various replacements like RED light and what became codel. In trying
to match up a multiplicity of RED related results, I noticed that RED
as implemented in linux behaved nothing like RED in the papers, and
eric dumazet found and fixed the two bugs in it that had existed for
several years (I think the broken period was from 2.6.36 through 3.4).

I went through I think nearly every paper published in the 90s and 00s
that was available online. There was a big survey of every RED variant
in there that as I recall had FRED in it and a few others that I
discarded as not useful.

Stephen hemminger did a couple qdiscs, like choke, which also didn't
work as well as advertised. I remember that kathie looked into AVQ
among others.

I spent a lot of time combining qdiscs, notably DRR or QFQ + a drop
system of some kind, like RED, choke, etc. This is partially
documented in the debloat script. Around august of the first year I'd
concluded the biggest win would be that combination but failed to
pursuade many.

Eric spent an enormous amount of time improving SFQ based on ideas
that Paul Mckenney had discarded as "too hard" back in the days of the
68020. The big version of that paper was pretty crucial to
understanding what we could achieve on modern hardware. Paul has been
a great help...

Along the way he got hot on ARED, for about two weeks, and implemented
that, from which I got generally lousy results in isolation. SFQRED
worked pretty good in a range of bandwidths between 4Mbit and 65Mbit
but proved hard to tune. Naheem rightly points out that SFQARED
variant was rather inadaquately tested (as about that time codel was
beginning to emerge) - but as I pointed out months ago, the code is
readily available in the linux kernel and GO FOR IT.

We had an idea ("hoq" or head of queue) in SFQRED that was very
SQF-like (as it turned out) but didn't work correctly, so we ended up
dropping it from linux 3.4

Andrew Mcgregor and I spent many a late night discussing among other
things the mixed-rtt problem and testing out all these algorithms
live, over video conferencing, and other systems. JG as well. There
were hundreds of people on the bloat list and dozens of cerowrt users
helping as well, I'm sorry for not listing names here and I'm sure
I've forgotten someone.

Kathie briefed us on codel one day in may, I got very excited, I wrote
the first  version for linux, eric dumazet then fixed it, sped it up
by 100x, an excited team assembled (see the early days of the codel
list) found a bug in the paper before it was even published, and fixed
that, one week later it was in the kernel and then one saturday
afternoon after we'd caught up on sleep, eric combined DRR and codel
to create fq_codel, and also got that slammed into the linux kernel in
under a week.

... I tried it on a wide range of benchmarks and said, at about 4AM
that day, that "wow. We just fixed the internet."

PIE took the fundamental insights of codel and created something
simpler from a straight aqm standpoint, and it is easier to implement
in *some* hardware... but doesn't interact with a packet scheduler
anywhere near as well as fq_codel.

I have been working ever since to help improve pie so that those forms
of hardware can have some form of AQM, and so that the linux
implementation is accurate and can be directly compared to all the
other packet schedulers and aqm systems also in there.

And there we stand today. If you want more papers published I have
hundreds of thousands of rrul and related plots, other harder to
express experiments, and will gladly co-author something or
participate in more experiments that seem sane in order to achieve
publication.

The ONLY paper I managed to get published was this one

http://www.enst.fr/ drossi/paper/rossi13tma-b.pdf

and all we were doing was pointing out that - if we won as big as we
expected with some form of aqm or packet scheduling - we'd at a single
stroke obsolete the field of low priority congestion control, with
some ideas towards making it work again...

Dario Rossi has since continued to analyze RED vs ledbat...

anyway...

I would not mind at all if others started with wondershaper and worked
up. I am VERY big on repeatable results, and repeatable experiments.
I'd love to see the presentation given at ietf against sfq, for
example. I'd like sources for the new DCTCP ECN results, too....

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 15 Nov 2013 22:02:46 +0000

>>>>Well, sounds like your opinion about that consensus; no doubt that analysis makes a paper stronger, but also no point in speculating about the reasons why she never got it published.

You might speak with your opinion. I spoke with my scarred experience. Our original proposal of BCN/QCN got rejected in IEEE 802.1 because of lacking a control theoretic analysis. It was only after we presented control analysis in the fall of 2005 before PAR could be established. If you are interested in this, you can check out the history log here.

http://www.ieee802.org/1/files/public/minutes/2005-09-minutes.pdf

http://www.ieee802.org/1/pages/802.1au.html

Regards,

Rong

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 18 Nov 2013 12:44:41 +0000

[chair hat off]

Hi Michael,

>>>>>>>>RP:  Again, the tight delay control comes from narrow-band bang-bang control with hard drops. The scenarios >that throughputs are good are in higher congestion scenarios where there are enough packets showing up to fill the >pipe. That is not the effectiveness of AQM. Tail drop with shallow buffer will have high throughput in those cases >too. Try a scenario when link is congested and a burst comes, see how many packets of that burst can go through.

How do you define congested link?

You will want to be burst-tolerant on a link running at full capacity - but is such a link already congested?

In any case, defining a scenario that would lead to excessive buffering delay in the drop-tail case, and comparing this for various AQMs should be documented.

Richard Scheffenegger

From: [email-masked] [mailto:[email-masked]] On Behalf Of Michael Welzl
Sent: Freitag, 15. November 2013 20:36
To: Rong Pan (ropan)
Cc: Naeem Khademi; Preethi Natarajan; [email-masked]
Subject: Re: [aqm] AQM schemes: Queue length vs. delay based

Hi,

Cheers,
Michael

---

From: Michael Welzl <[email-masked]>
Date: Mon, 18 Nov 2013 14:01:18 +0100

> You will want to be burst-tolerant on a link running at full capacity - but is such a link already congested?

I'd say no, this is just perfectly saturated. I was thinking of a link running at full capacity + a non-empty queue.

BTW, there was talk about how to define congestion and how to define congestion control at the AQM meeting, during Fred's presentation. If we need text for this, it's worth looking at the ICCRG archives, I remember a long and boring discussion about these definitions early in the life of ICCRG.

> In any case, defining a scenario that would lead to excessive buffering delay in the drop-tail case, and comparing this for various AQMs should be documented.

Sure

Cheers,
Michael

---

From: Preethi Natarajan <[email-masked]>
Date: Mon, 18 Nov 2013 11:38:54 -0800

On 11/18/13 4:44 AM, "Scheffenegger, Richard" <[email-masked]> wrote:

>>>>>>>>>RP:  Again, the tight delay control comes from narrow-band
>>>>>>>>>bang-bang control with hard drops. The scenarios >that
>>>>>>>>>throughputs are good are in higher congestion scenarios where
>>>>>>>>>there are enough packets showing up to fill the >pipe. That is
>>>>>>>>>not the effectiveness of AQM. Tail drop with shallow buffer will
>>>>>>>>>have high throughput in those cases >too. Try a scenario when
>>>>>>>>>link is congested and a burst comes, see how many packets of that
>>>>>>>>>burst can go through.

Great questions Richard. Defining congestion is probably the main point of
contention here. Michael, thanks for mentioning about ICCRG discussions on
this topic, I think it'd be worthwhile to go through that as well. If you
can send everyone a pointer that'd be useful as well.

Here is my humble opinion -- congestion should be defined based on its
impact (to the applications). In that sense, there will be varying levels
of congestion -- mild to severe. Symptoms of mild congestion could be
slowly increasing (by some delta) buffering and queueing delay. Symptoms
of severe congestion could be packet drops at the tail, blocking other
flows etc. 

A full capacity + non-empty queue doesn't impact applications in any way,
so this doesn't signify congestion.

A latency-based AQM scheme should operate the queue at a specified
queueing delay, which means the outgoing link is under some level of
congestion already. Under these conditions, an AQM scheme should be able
to handle bursts in an effective way. A mechanism's effectiveness in
handling these bursts could be evaluated/determined by factors such as (i)
how long does it take to bring burst under control, (ii) packet drops
during this period, (iii) link utilization during this period, and may be
others that I am missing.

>
>In any case, defining a scenario that would lead to excessive buffering
>delay in the drop-tail case, and comparing this for various AQMs should
>be documented.

I agree. Thinking more, maybe we should evaluate an AQM for the varying
levels of congestion. Document scenarios that'd create the different
levels of congestion from mild to severe and compare AQMs for all these
levels, not just empirically but also highlight their behavioral
differences. 

Thanks,
Preethi