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

From: Preethi Natarajan <[email-masked]>
Date: Thu, 07 Nov 2013 18:46:39 -0700

Hello AQMers:

Just wanted to bring up the following item for discussion either as part of
the recommendations draft or the evaluation criteria during Friday's
session/mailing list.

In access, edge and core routers the draining rate of a queue is affected by
traffic on other queues and thus can vary a lot (depending on the deployment
and traffic conditions). A queue length based AQM scheme such as RED or
derivatives tries to maintain the average queue size around a predictable
value under these changing draining rates. However, this queue size
translates to high queuing delay under low draining rates and vice-versa.
The unpredictability in resulting queueing delay was one of the reasons why
we opted PIE to be a latency-based scheme.

A queue length based AQM scheme could be perfectly valid for certain
deployments. For deployments where predictable queuing delay is expected
under varying draining rates, a latency based AQM is critical. We believe
this should be brought about in discussions somewhere at AQM ‹ perhaps in
the recommendations draft or w.r.t evaluation criteria.

Thanks,
Preethi (on behalf of PIE team)

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 7 Nov 2013 21:50:24 -0800

I fully agree with the need to have AQMs that use "queuing delay" as metric
and not "queue length" and this is already a bonus for algorithms that use
this metric (e.g. PIE). However, I believe that one can possibly modify RED
or its derivatives (e.g. Adaptive RED) to set their thresholds based on
"queuing delay" as well (although such algorithms don't exists yet as of
now). Whether the outcome of these modifications to xRED algorithms would
make them better than PIE and/or CoDel is another subject and I'm not going
to speculate on that here.

One specific issue with PIE is that it tries to *estimate* the queuing
delay over a certain time interval (t_update) and still somehow uses the
"queue length" and departure rate (over the interval) to estimate the
queuing delay. So saying that PIE uses the queueing delay instead of queue
length may not be 100% accurate.

Moreover, in a varying bandwidth scenario, depending on how often the
bandwidth changes and at what granularity, the derived "estimated queuing
delay" by PIE might be an outdated information e.g. it shows how the
channel has been (in term of delay) in the last 30ms and now how it is now!
if I'm not mistaken that has been somehow resolved in DOCSIS 3.1 by
coupling PIE's departure rate to the actual link layer rate.

In overall, while there are of course significant improvements made in
PIE's (and (FQ)-CoDel's) design, there are probably still lessons to be
learned from xRED family (check http://urn.nb.no/URN:NBN:no-38868 to see
some examples). Throwing away all the knowledge and improvement gained from
RED-like AQMs, CHoKe, etc and coming up with brand-new AQMs without
(experimentally) comparing them to the gallery of existing ones wouldn't be
great!

Cheers,
Naeem

On Thu, Nov 7, 2013 at 5:46 PM, Preethi Natarajan <[email-masked]>wrote:

> Hello AQMers:
>
> Just wanted to bring up the following item for discussion either as part
> of the recommendations draft or the evaluation criteria during Friday's
> session/mailing list.
>
> In access, edge and core routers the draining rate of a queue is affected
> by traffic on other queues and thus can vary a lot (depending on the
> deployment and traffic conditions). A queue length based AQM scheme such as
> RED or derivatives tries to maintain the average queue size around a
> predictable value under these changing draining rates. However, this queue
> size translates to high queuing delay under low draining rates and
> vice-versa. The unpredictability in resulting queueing delay was one of the
> reasons why we opted PIE to be a latency-based scheme.
>
> this should be brought about in discussions somewhere at AQM — perhaps in
> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm
>
>

---

From: Preethi Natarajan <[email-masked]>
Date: Fri, 08 Nov 2013 12:00:09 -0700

Hi Naeem, all:

Please see detailed responses inline.

From:  Naeem Khademi <[email-masked]>
Date:  Thursday, November 7, 2013 10:50 PM
To:  Preethi Natarajan <[email-masked]>
Cc:  "[email-masked]" <[email-masked]>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

> this metric (e.g. PIE). However, I believe that one can possibly modify RED or
> its derivatives (e.g. Adaptive RED) to set their thresholds based on "queuing
> delay" as well (although such algorithms don't exists yet as of now). Whether
> the outcome of these modifications to xRED algorithms would make them better
> than PIE and/or CoDel is another subject and I'm not going to speculate on
> that here. 

Of course. Our initial discussions considered a latency based RED
derivative. We later decided to focus on a proportional integral based
control law instead of RED (see below for more).

> 
> One specific issue with PIE is that it tries to *estimate* the queuing delay
> over a certain time interval (t_update) and still somehow uses the "queue
> length" and departure rate (over the interval) to estimate the queuing delay.
> So saying that PIE uses the queueing delay instead of queue length may not be
> 100% accurate. 

Any latency based scheme requires the queueing delay to work with. The fact
of the matter is, the queueing delay is not directly available on platforms.
Some platforms can afford timestamping to figure the queuing delay but not
all platforms  can. In fact, over the past months we've come to realize that
a latency based scheme is actually two different items at work ‹ (i) the
control law and (ii) the mechanism which provides the queueing delay to this
control law. This would be true for any latency based scheme, be it, PIE,
CoDEL, FQ_CoDEL or xRED. Based on this observation, we plan to separate out
the two components in PIE, possibly in the next version of the draft. The
objective being that (ii) would vary with the platform and it could be
direct input (if platform maintains it), timestamp-based (like in CoDEL
derivatives), dequeue-based, or even others that we are exploring at the
moment. 

The current version of the PIE draft fully acknowledges the fact that what
PIE acquires with the dequee-based rate estimation is only an estimate of
the queuing delay and not the actual (Section 4.2 of v00). The larger point
for discussion here is a latency based AQM that uses queuing delay instead
of queue length. 

> delay" by PIE might be an outdated information e.g. it shows how the channel
> has been (in term of delay) in the last 30ms and now how it is now! if I'm not
> mistaken that has been somehow resolved in DOCSIS 3.1 by coupling PIE's
> departure rate to the actual link layer rate.

We've experimented with timestamp-based delay inputs to PIE. We have not
seen any noticeable difference between the dequeue-based scheme and the
timestamp-based for all the scenarios Rong has presented at IETF thus far.
Even in extreme bandwidth changing conditions dequeue-based scheme can adapt
within few tupdate cycles. Again, PIE is flexible in its delay input
mechanism and will go with whatever is the best possible option available on
the platform. I don't think any latency based scheme can get better than
that :). 

> 
> In overall, while there are of course significant improvements made in PIE's
> (and (FQ)-CoDel's) design, there are probably still lessons to be learned from
> xRED family (check http://urn.nb.no/URN:NBN:no-38868 to see some examples).
> Throwing away all the knowledge and improvement gained from RED-like AQMs,
> CHoKe, etc and coming up with brand-new AQMs without (experimentally)
> comparing them to the gallery of existing ones wouldn't be great!

Our initial discussions considered more than just the RED varieties. As
we've mentioned before, PIE is based on the concept of proportional integral
(PI). PI is not something we discovered. PI controller has been around for
long and you can refer to Hollot, Towsley et. al's paper from a decade ago
for more information on PI based AQM scheme. We believe PI's strong
theoretical stability is valuable for diverse deployment conditions and
incorporated PI into our PIE design. We did our own set of theoretical
analysis for PIE and we were proved right. You can find more details about
that in our HPSR paper (http://www.ieee-hpsr.org/2013/)

Thanks,
Preethi

---

From: Michael Welzl <[email-masked]>
Date: Fri, 8 Nov 2013 13:11:00 -0800

On 8. nov. 2013, at 11:00, Preethi Natarajan <[email-masked]> wrote:

>> I fully agree with the need to have AQMs that use "queuing delay" as metric and not "queue length" and this is already a bonus for algorithms that use this metric (e.g. PIE). However, I believe that one can possibly modify RED or its derivatives (e.g. Adaptive RED) to set their thresholds based on "queuing delay" as well (although such algorithms don't exists yet as of now). Whether the outcome of these modifications to xRED algorithms would make them better than PIE and/or CoDel is another subject and I'm not going to speculate on that here. 
> 
> 
> Of course. Our initial discussions considered a latency based RED derivative. We later decided to focus on a proportional integral based control law instead of RED (see below for more). 
> 
>> 
>> One specific issue with PIE is that it tries to *estimate* the queuing delay over a certain time interval (t_update) and still somehow uses the "queue length" and departure rate (over the interval) to estimate the queuing delay. So saying that PIE uses the queueing delay instead of queue length may not be 100% accurate. 
> 
> 
> Any latency based scheme requires the queueing delay to work with. The fact of the matter is, the queueing delay is not directly available on platforms. Some platforms can afford timestamping to figure the queuing delay but not all platforms  can. In fact, over the past months we've come to realize that a latency based scheme is actually two different items at work — (i) the control law and (ii) the mechanism which provides the queueing delay to this control law. This would be true for any latency based scheme, be it, PIE, CoDEL, FQ_CoDEL or xRED. Based on this observation, we plan to separate out the two components in PIE, possibly in the next version of the draft. The objective being that (ii) would vary with the platform and it could be direct input (if platform maintains it), timestamp-based (like in CoDEL derivatives), dequeue-based, or even others that we are exploring at the moment. 
> 
> The current version of the PIE draft fully acknowledges the fact that what PIE acquires with the dequee-based rate estimation is only an estimate of the queuing delay and not the actual (Section 4.2 of v00). The larger point for discussion here is a latency based AQM that uses queuing delay instead of queue length. 
> 
> 
>> 
>> Moreover, in a varying bandwidth scenario, depending on how often the bandwidth changes and at what granularity, the derived "estimated queuing delay" by PIE might be an outdated information e.g. it shows how the channel has been (in term of delay) in the last 30ms and now how it is now! if I'm not mistaken that has been somehow resolved in DOCSIS 3.1 by coupling PIE's departure rate to the actual link layer rate.  
> 
> 
> We've experimented with timestamp-based delay inputs to PIE. We have not seen any noticeable difference between the dequeue-based scheme and the timestamp-based for all the scenarios Rong has presented at IETF thus far. Even in extreme bandwidth changing conditions dequeue-based scheme can adapt within few tupdate cycles. Again, PIE is flexible in its delay input mechanism and will go with whatever is the best possible option available on the platform. I don't think any latency based scheme can get better than that :). 

An AQM scheme should also work when the bandwidth is *not* changing. The results that Naeem presented in ICCRG don't indicate that PIE is consistently better than CoDel (which is also delay-based). I'm not trying to say if this or that is better, just that statements like this one are rather handwavy.

>> In overall, while there are of course significant improvements made in PIE's (and (FQ)-CoDel's) design, there are probably still lessons to be learned from xRED family (check http://urn.nb.no/URN:NBN:no-38868 to see some examples). Throwing away all the knowledge and improvement gained from RED-like AQMs, CHoKe, etc and coming up with brand-new AQMs without (experimentally) comparing them to the gallery of existing ones wouldn't be great!
> 
> 
> Our initial discussions considered more than just the RED varieties. As we've mentioned before, PIE is based on the concept of proportional integral (PI). PI is not something we discovered. PI controller has been around for long and you can refer to Hollot, Towsley et. al's paper from a decade ago for more information on PI based AQM scheme. We believe PI's strong theoretical stability is valuable for diverse deployment conditions and incorporated PI into our PIE design. We did our own set of theoretical analysis for PIE and we were proved right. You can find more details about that in our HPSR paper (http://www.ieee-hpsr.org/2013/)

Another handwavy statement. Using a PI controller may be a good design idea, but that alone doesn't really tell us much about the overall behavior.

Cheers,
Michael

---

From: Preethi Natarajan <[email-masked]>
Date: Fri, 08 Nov 2013 13:34:53 -0700

Hello Michael, all:

Please see inline.

From:  Michael Welzl <[email-masked]>
Date:  Friday, November 8, 2013 2:11 PM
To:  Preethi Natarajan <[email-masked]>
Cc:  Naeem Khademi <[email-masked]>, "[email-masked]" <[email-masked]>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

>>> has been (in term of delay) in the last 30ms and now how it is now! if I'm
>>> not mistaken that has been somehow resolved in DOCSIS 3.1 by coupling PIE's
>> We've experimented with timestamp-based delay inputs to PIE. We have not seen
>> any noticeable difference between the dequeue-based scheme and the
>> the platform. I don't think any latency based scheme can get better than that
>> :). 
> 
> An AQM scheme should also work when the bandwidth is *not* changing. The
> results that Naeem presented in ICCRG don't indicate that PIE is consistently
> better than CoDel (which is also delay-based). I'm not trying to say if this
> or that is better, just that statements like this one are rather handwavy.

Just to clarify, my previous comment was w.r.t how queuing delay input to
PIE or any latency based AQM scheme can't get better than the fact that the
scheme should use the best possible queueing delay input available on the
platform ‹ timestamp-based, dequeue-based or other flavors. There is nothing
hand wavy in this statement.

Of course, an AQM scheme should also work when the bandwidth is *not*
changing. W.r.t the PIE results presented, there are few things we don't
understand. We plan to follow-up with you on that, maybe on a separate
thread.

>>> (and (FQ)-CoDel's) design, there are probably still lessons to be learned
>>> from xRED family (check http://urn.nb.no/URN:NBN:no-38868 to see some
>>> examples). Throwing away all the knowledge and improvement gained from
>> Our initial discussions considered more than just the RED varieties. As we've
>> mentioned before, PIE is based on the concept of proportional integral (PI).
>> PI is not something we discovered. PI controller has been around for long and
>> you can refer to Hollot, Towsley et. al's paper from a decade ago for more
>> information on PI based AQM scheme. We believe PI's strong theoretical
>> stability is valuable for diverse deployment conditions and incorporated PI
>> into our PIE design. We did our own set of theoretical analysis for PIE and
>> we were proved right. You can find more details about that in our HPSR paper
>> (http://www.ieee-hpsr.org/2013/)
> 
> Another handwavy statement. Using a PI controller may be a good design idea,
> but that alone doesn't really tell us much about the overall behavior.

Again, I don't understand what is handwavy here. My comment was PI
controller has theoretical backing on why its good for various deployment
conditions. Here is the link to Hollot's paper I mentioned on PI design that
also talks in detail about the overall behavior --
ftp://ftp.cs.umass.edu/pub/net/pub/MisraInfocom01-AQM-Controller.pdf

Many thanks,
Preethi

---

From: Michael Welzl <[email-masked]>
Date: Fri, 8 Nov 2013 17:30:49 -0800

On 8. nov. 2013, at 12:34, Preethi Natarajan <[email-masked]> wrote:

> Just to clarify, my previous comment was w.r.t how queuing delay input to PIE or any latency based AQM scheme can't get better than the fact that the scheme should use the best possible queueing delay input available on the platform — timestamp-based, dequeue-based or other flavors. There is nothing hand wavy in this statement. 

ok, sorry -

> Of course, an AQM scheme should also work when the bandwidth is *not* changing. W.r.t the PIE results presented, there are few things we don't understand. We plan to follow-up with you on that, maybe on a separate thread.

> Again, I don't understand what is handwavy here. My comment was PI controller has theoretical backing on why its good for various deployment conditions. Here is the link to Hollot's paper I mentioned on PI design that also talks in detail about the overall behavior -- ftp://ftp.cs.umass.edu/pub/net/pub/MisraInfocom01-AQM-Controller.pdf

Thanks for the link. My point was just (along with Naeem) that it would be useful to compare PIE (or CoDel) against something else except CoDel and RED. When I just look at the graphs in the HPSR paper (sorry, didn't get to read it yet), again I see only PIE, CoDel, RED.

We tried ARED and were surprised to see how good it works - which is not to say that it is the ideal - but it was surprisingly often better than these newer schemes, despite its age of 10+ years... as we all know, there are many schemes out there, quite often designed with the goal of removing RED's dependence on parameters.

Cheers,
Michael

---

From: Preethi Natarajan <[email-masked]>
Date: Tue, 12 Nov 2013 15:56:30 -0800

Date:  Friday, November 8, 2013 5:30 PM

> 
> Thanks for the link. My point was just (along with Naeem) that it would be
> useful to compare PIE (or CoDel) against something else except CoDel and RED.
> When I just look at the graphs in the HPSR paper (sorry, didn't get to read it
> yet), again I see only PIE, CoDel, RED.
> 
> We tried ARED and were surprised to see how good it works - which is not to
> say that it is the ideal - but it was surprisingly often better than these
> newer schemes, despite its age of 10+ years... as we all know, there are many
> schemes out there, quite often designed with the goal of removing RED's
> dependence on parameters.

Michael, Naeem:

This is just a follow-up to better understand the ARED results presented at
AQM WG (http://www.ietf.org/proceedings/88/slides/slides-88-iccrg-4.pdf).

Could you please clarify whether the ARED parameters for the tests were set
as specified in the 2001 paper? I.e., when average queueing delay target =
1ms, the min and max thresholds would translate to 0.5ms and 1.5ms, and for
5 ms target the min and max thresh will be 2.5ms and 7.5ms, respectively,
right? Can you confirm?

Assuming ARED logic is intact, ARED drops all packets when average queue
size goes above max_thresh  (max_thresh = 1.5ms or 7.5ms etc.); this would
be semantically similar to a drop tail queue with shallow buffer (can be
confirmed by looking at cumulative packet drops by ARED).

This is probably why the delay values are tight for ARED, and why ARED
translates to poor utilization, especially for the lower target delay
values, as seen in your slides (#8, #11, #13).

Also,  wondering if bursty traffic was considered for evaluations, since
semantics of drop tail with shallow buffering doesn't accommodate bursty
traffic. 

Thanks,
Preethi & Rong

---

From: Naeem Khademi <[email-masked]>
Date: Wed, 13 Nov 2013 14:01:24 +0100

On Wed, Nov 13, 2013 at 12:56 AM, Preethi Natarajan
<[email-masked]>wrote:

> useful to compare PIE (or CoDel) against something else except CoDel and
> RED. When I just look at the graphs in the HPSR paper (sorry, didn't get to
> read it yet), again I see only PIE, CoDel, RED.
>
> We tried ARED and were surprised to see how good it works - which is not
> to say that it is the ideal - but it was surprisingly often better than
> these newer schemes, despite its age of 10+ years... as we all know, there
> are many schemes out there, quite often designed with the goal of removing
> RED's dependence on parameters.
>
>
>
Hi Preethi and Rong

replies follow inline

> Michael, Naeem:
>
> This is just a follow-up to better understand the ARED results presented
> at AQM WG (http://www.ietf.org/proceedings/88/slides/slides-88-iccrg-4.pdf
> ).
>
> Could you please clarify whether the ARED parameters for the tests were
> set as specified in the 2001 paper? I.e., when average queueing delay
> target = 1ms, the min and max thresholds would translate to 0.5ms and
> 1.5ms, and for 5 ms target the min and max thresh will be 2.5ms and 7.5ms,
> respectively, right? Can you confirm?
>

Copy/pasting from Section 3.1.3 of http://urn.nb.no/URN:NBN:no-38868
<http://urn.nb.no/URN:NBN:no-38868>

*"In case of ARED, the parameters are calculated based on the
recommendations in [19]*
*except when target delay=1 ms where th_min and th_max are set to 1 MTU*
*and 2 MTUs accordingly."*

*[19] S. Floyd, R. Gummadi, and S. Shenker. Adaptive RED: An Algorithm for*
*Increasing the Robustness of RED’s Active Queue Management. Technical*
*report, 2001.*

This means "yes" for all values of target delay except for 1 ms cases where
the thresholds become smaller than a single MTU transmission time on the 10
Mbps bottleneck link used in this case.  The recommendations in Sally
Flyod' s ARED 2001  (th_max=3*th_min; target=(th_max+th_min)/2) are used in
all other cases.

> size goes above max_thresh  (max_thresh = 1.5ms or 7.5ms etc.); this
> would be semantically similar to a drop tail queue with shallow buffer (can
> be confirmed by looking at cumulative packet drops by ARED).
>

Similar but not identical as ARED (and any other *RED) does averaging
instead of using instantaneous queue size (e.g. that being employed in
DCTCP AQM)

> values, as seen in your slides (#8, #11, #13).

True!

> semantics of drop tail with shallow buffering doesn't accommodate bursty

No, we did not consider bursty traffic (e.g. multimedia, etc) for this work
as this was our first (initial) fundamental step to understand in a
systematic way how AQMs work in real-life with long-lived TCP traffic
(which is the most common type of traffic that fills up any buffer and
consistently contributes to excessively long latencies experienced on the
Internet (a.k.a bufferbloat)).

The fact that AQMs *should* absorb sub-RTT bursts (due to rate mistmatch,
etc) does not diminish the basic requirement for AQMs that they should
control the latency induced by bulk (long-lived) TCP traffic in a well
manner. Any other type of traffic on the access links will most likely to
coexist with bulk TCP traffic when latency is observed to grow high. In
other words, if an AQM can't control the latency of (not so bursty as
others-) TCP traffic, it probably won't be able to do so for bursty traffic
as well.

Cheers,
Naeem

---

From: Preethi Natarajan <[email-masked]>
Date: Wed, 13 Nov 2013 10:25:19 -0800

Please see inlineŠ

From:  Naeem Khademi <[email-masked]>
Date:  Wednesday, November 13, 2013 5:01 AM
To:  Preethi Natarajan <[email-masked]>
Cc:  Michael Welzl <[email-masked]>, "[email-masked]" <[email-masked]>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

>> 1ms, the min and max thresholds would translate to 0.5ms and 1.5ms, and for 5
>> ms target the min and max thresh will be 2.5ms and 7.5ms, respectively,
>> right? Can you confirm?
> 
> "In case of ARED, the parameters are calculated based on the recommendations
> in [19]
> except when target delay=1 ms where th_min and th_max are set to 1 MTU
> and 2 MTUs accordingly."
> 
> [19] S. Floyd, R. Gummadi, and S. Shenker. Adaptive RED: An Algorithm for
> Increasing the Robustness of RED¹s Active Queue Management. Technical
> report, 2001.
> 
> Mbps bottleneck link used in this case.  The recommendations in Sally Flyod' s
> ARED 2001  (th_max=3*th_min; target=(th_max+th_min)/2) are used in all other
> cases. 
>  
>> Assuming ARED logic is intact, ARED drops all packets when average queue size
>> goes above max_thresh  (max_thresh = 1.5ms or 7.5ms etc.); this would be
>> semantically similar to a drop tail queue with shallow buffer (can be
> Similar but not identical as ARED (and any other *RED) does averaging instead
> of using instantaneous queue size (e.g. that being employed in DCTCP AQM)
>  
>> translates to poor utilization, especially for the lower target delay values,
>> as seen in your slides (#8, #11, #13).
> 
> True! 
>  

Thanks for clarifying. That definitely clears the air about why ARED's delay
values were so tight; trying to maintain the average queue delay between
such a narrow band between min and max thresholds (0.5ms to 1.5ms or 2.5ms
to 7.5ms) would naturally result in tighter delay values at the cost of
utilization. Of course, ARED works on the average queue size, but when it
comes to such a narrow band between min and max thresholds, we suspect there
wouldn't be much difference between ARED and drop tail.

> No, we did not consider bursty traffic (e.g. multimedia, etc) for this work as
> this was our first (initial) fundamental step to understand in a systematic
> way how AQMs work in real-life with long-lived TCP traffic (which is the most
> common type of traffic that fills up any buffer and consistently contributes
> to excessively long latencies experienced on the Internet (a.k.a
> bufferbloat)). 
> 
> The fact that AQMs *should* absorb sub-RTT bursts (due to rate mistmatch, etc)
> does not diminish the basic requirement for AQMs that they should control the
> latency induced by bulk (long-lived) TCP traffic in a well manner. Any other
> type of traffic on the access links will most likely to coexist with bulk TCP
> traffic when latency is observed to grow high. In other words, if an AQM can't
> control the latency of (not so bursty as others-) TCP traffic, it probably
> won't be able to do so for bursty traffic as well.

I would not limit an AQM design to absorb just sub-RTT bursts. A robust AQM
scheme should be able to handle any kind of bursts irrespective of RTT,
traffic patterns etc., since these bursts are quite common in deployments
today.

Thanks,
Preethi

---

From: Naeem Khademi <[email-masked]>
Date: Wed, 13 Nov 2013 21:14:36 +0100

On Wed, Nov 13, 2013 at 7:25 PM, Preethi Natarajan <[email-masked]>wrote:

> Please see inline…
>> at AQM WG (
>> http://www.ietf.org/proceedings/88/slides/slides-88-iccrg-4.pdf).
>>
> Copy/pasting from Section 3.1.3 of http://urn.nb.no/URN:NBN:no-38868 <http://urn.nb.no/URN:NBN:no-38868>
>
> This means "yes" for all values of target delay except for 1 ms cases
> where the thresholds become smaller than a single MTU transmission time on
> the 10 Mbps bottleneck link used in this case.  The recommendations in
> Sally Flyod' s ARED 2001  (th_max=3*th_min; target=(th_max+th_min)/2) are
> used in all other cases.
>
>
> Thanks for clarifying. That definitely clears the air about why ARED's
> delay values were so tight; trying to maintain the average queue delay
> between such a narrow band between min and max thresholds (0.5ms to 1.5ms
> or 2.5ms to 7.5ms) would naturally result in tighter delay values at the
> cost of utilization. Of course, ARED works on the average queue size, but
> when it comes to such a narrow band between min and max thresholds, we
> suspect there wouldn't be much difference between ARED and drop tail.
>

Very true, though that's what ARED *is* with very low thresholds (e.g.
resonate between 1 or 2 packets on the average in the queue). Indeed there
can possibly be some future work on ARED's (or any other similar AQM) burst
allowance but I don't think e.g. letting a 100 ms burst of packets to pass
through can be a good way of fixing it as this can lead to massive variance
in overall RTT distribution.

> No, we did not consider bursty traffic (e.g. multimedia, etc) for this
> work as this was our first (initial) fundamental step to understand in a
> I would not limit an AQM design to absorb just sub-RTT bursts.
>

Neither do I. What I said was that we don't necessarily need to have a very
long distribution tail for long-lived TCP traffic (as observed with PIE and
slightly with CoDel in the results presented at ICCRG, IETF88) to be able
to absorb the bursts.

> A robust AQM scheme should be able to handle any kind of bursts
> irrespective of RTT, traffic patterns etc., since these bursts are quite
> common in deployments today.
>

Agreed only in general terms -- but what would be considered as "packet
burst" and how would it be defined? This will probably have a subjective
answer e.g. one can argue that a size of TCP sawtooth of data is a burst
and therefore we need a BDP of buffering for that (that's what had actually
happened implicitly over the past decade). On the other hand, the
definition of the "burst" may likely to correspond to the application
generating it (e.g. video frames, IW10, etc) and therefore its size (and
even pattern) is application/transport dependent somehow. There are sub-RTT
and larger than one RTT bursts that the network (AQM node) has no clue
about their size (at least for the existing AQMs studied). In case of CoDel
for instance, the whole idea of "100 ms interval time" plus "dropping mode"
with packet drops with sqrt function of "TCP throughput vs. loss model" is
designed to absorb the sub-RTT TCP packet bursts (see CoDel paper @ ACM
Queue) and it assumes that a 100 ms interval works almost fine for most
ranges of RTTs. There's nothing explicit that I can find about bursts
bigger than an one RTT in CoDel's design. I'm curious to know how an AQM
can identify a burst and let it through without the implicit knowledge of
RTT or the transport/application behind it and I'm not sure if it's ever
supposed to? (note: I'm not saying AQM should know at all, just curious how
would it be possible to fulfill the goal you're stating above otherwise?)

Hopefully you or some people on the list can possibly help me with that
:-).

Thanks,

Cheers,
Naeem

---

From: Anoop Ghanwani <[email-masked]>
Date: Wed, 13 Nov 2013 14:43:48 -0800

On Wed, Nov 13, 2013 at 12:14 PM, Naeem Khademi <[email-masked]>wrote:

> even pattern) is application/transport dependent somehow.
>

There's one more case...the incast problem.  The sources themselves may not
be "bursty" but in a high port count switch, you could have 10's (or more)
ports sending traffic to a single output port at around the same time.

Perhaps it is useful to add a description of what we mean when we say
bursty.

Anoop

Anoop

---

From: Anoop Ghanwani <[email-masked]>
Date: Wed, 13 Nov 2013 15:33:30 -0800

On Wed, Nov 13, 2013 at 3:23 PM, Curtis Villamizar <[email-masked]>wrote:

>
> Including unrealistic scenarios, like going from near zero traffic to 10
> interfaces feeding one at full speed until overflow occurs, is
> counterproductive.

It is actually a problem that keeps many people busy because a number of
data center switches have very high port count with very small buffers.
 Some people address these buy using switches with bigger buffers, but
that's not a luxury that everyone indulges in.

That is why I specifically asked the question at the AQM meeting about
applicability of AQM to all types of networks/switches.  I was told the
answer is "yes" and so I would like to see this scenario addressed as well.
 Perhaps AQM cannot help this, but hopefully it won't hurt.  Trying to do
fancy things with small buffers is challenging.

Anoop

---

From: Preethi Natarajan <[email-masked]>
Date: Wed, 13 Nov 2013 17:17:56 -0800

Date:  Wednesday, November 13, 2013 12:14 PM

> resonate between 1 or 2 packets on the average in the queue). Indeed there can
> possibly be some future work on ARED's (or any other similar AQM) burst
> through can be a good way of fixing it as this can lead to massive variance in
> overall RTT distribution.

If you are referring to the burst_allowance parameter in PIE, this parameter
allows burst to go through when a system goes from an idle state into some
congestion state. The one we are talking about is accommodating bursts when
the system is in equilibirum -- how does the AQM scheme accommodate bursts
when already operating around target delay or congestion? Delay-based ARED
behaves similar to tail drop at max threshold. This is unacceptable of an
AQM even for max thresholds around 50ms.
Clearly delay-based ARED needs significant and careful redesign. I suppose
one can argue this task is as laborious as designing a new AQM scheme as
opposed to previous notions that delay-based ARED would work right out of
the box. 
Preethi

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 14:32:56 +0100

Hi Preethi

Please see comments inline

On Thu, Nov 14, 2013 at 2:17 AM, Preethi Natarajan <[email-masked]>wrote:

> If you are referring to the burst_allowance parameter in PIE, this
> parameter allows burst to go through when a system goes from an idle state
> into some congestion state. The one we are talking about is accommodating
> bursts when the system is in equilibirum
>

I wasn't referring to a PIE's parameter named "burst allowance" but rather
in a generic term.

> -- how does the AQM scheme accommodate bursts when already operating
> around target delay or congestion?
>

AFAIK all three studied AQMs (CoDel, PIE, ARED) have a parameter named
"target delay" or "target queuing". Judging based on the (param) name, they
supposedly try to maintain the queue delay/length around/at a certain value
although "target delay/queuing" has different semantics in each AQM and the
response to crossing that threshold/value is also different from one AQM to
another. Moreover, It is favorable for an AQM that tries to fix bufferbloat
problem to have a predictable delay distribution, most favorably around
(e.g. mean, median, max) a certain value. PIE uses it, CoDel has it and
ARED in fixed BW setups has it too. So, I'm not quite sure, why it
shouldn't be possible to allow a certain size of burst in such
threshold-based mechanisms (AFAIK (A)RED's Linux implementation already has
a "burst" param that can be tuned, although its semantics may not be
identical to the way CoDel or PIE handle bursts).

> Delay-based ARED behaves similar to tail drop at max threshold. This is
> unacceptable of an AQM even for max thresholds around 50ms.
>

I'm not sure if I understand this part correctly or even if I agree with
the conclusion it makes, assuming that I understood it correctly :-). If
I'm not mistaken, you're saying that "(delay-based) ARED  acts similar to
DropTail when the average queue size/delay grows beyond the th_max". If
that's the case, then I disagree since ARED uses a (delay-based) AIMD
function to tune the maximum drop probability and therefore it uses the AI
factor to increase its P_MAX when queue size/delay grows beyond the th_max
and on top of that, it does averaging, so nothing really similar to
DropTail.

> Clearly delay-based ARED needs significant and careful redesign. I
> suppose one can argue this task is as laborious as designing a new AQM
> scheme as opposed to previous notions that delay-based ARED would work
> right out of the box.
>

it's probably not accurate to say "redesign" as delay-based ARED doesn't
exist as of know. AFAIK given our latest results with ARED, we raised
the possibility of modifying ARED to use delay-based thresholds instead of
size-based thresholds during the ICCRG talk and in the TR, and declared it
as future work. I'm not aware of any other implementation/proposal of
delay-based ARED to exist as of now. We never claimed or speculated on how
this future delay-based AQM might perform and left it to when the future
work is done and the outcome is properly investigated and therefore we
never said that "it would work right out of the box" :-).

Cheers,
Naeem

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 16:43:40 +0100

> Delay-based ARED behaves similar to tail drop at max threshold.
>>
>
I think I now understand what you mean by this sentence ;-) and therefore
please ignore the paragraph responding to this specific point in the
previous email (sorry about that, I got it mixed with max_target). Indeed
ARED drops every packet when the average queue length grows beyond th_max
as drop probability jumps to 1 (when it's not in gentle mode). For this to
happen, the "average queue length" has to grow beyond th_max and depending
on how the averaging is done, that can correspond to certain burst
allowance at AQM. Moreover, this is done over 500 ms interval which means
the average queue length has to stay above th_max for mostly few rounds of
RTTs (assuming the typical distribution of RTTs on the Internet to have a
mean/average somewhere below that value e.g. 100~200 ms). This allows burst
that don't take the average queue size to above th_max over 500 ms period
to pass and clear themselves up the queue.

 > This is unacceptable of an AQM even for max thresholds around 50ms.

 Whether this is a good thing or bad thing is a subjective matter in my
opinion, as most AQMs at some point will drop every packet whether it be
the maximum queue length or at some thresholds.

Cheers,
Naeem

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 17:05:04 +0100

> that's not a luxury that everyone indulges in.

Fair point about the incast problem and I personally think AQMs designed
for data centers should address that.

> answer is "yes" and so I would like to see this scenario addressed as well.

Below is my personal opinion, but hopefully Fred can clarify this better
based on the AQM recommendations draft:

"applicability of AQM to all types of networks/switches" => "yes"

"applicability of *any* AQM to all types of networks/switches" => "no"

> fancy things with small buffers is challenging.

AQM will most likely to help from data centers to the access links, and so
on. But we may possibly need different AQMs for different network
scenarios; The fact that an AQMs should be auto-tunable doesn't imply that
it can be applied everywhere and we may need different auto-tunable AQMs
specifically designed for different networks (ideally better if we could
use fewer of them and they could work everywhere). I hope I'm not wrong.

Naeem

---

From: Preethi Natarajan <[email-masked]>
Date: Thu, 14 Nov 2013 11:46:21 -0800

Date:  Thursday, November 14, 2013 5:32 AM

> 
> AFAIK all three studied AQMs (CoDel, PIE, ARED) have a parameter named "target
> delay" or "target queuing". Judging based on the (param) name, they supposedly
> try to maintain the queue delay/length around/at a certain value although
> "target delay/queuing" has different semantics in each AQM and the response to
> crossing that threshold/value is also different from one AQM to another.
> Moreover, It is favorable for an AQM that tries to fix bufferbloat problem to
> have a predictable delay distribution, most favorably around (e.g. mean,
> median, max) a certain value. PIE uses it, CoDel has it and ARED in fixed BW
> setups has it too. So, I'm not quite sure, why it shouldn't be possible to
> allow a certain size of burst in such threshold-based mechanisms (AFAIK
> (A)RED's Linux implementation already has a "burst" param that can be tuned,
> although its semantics may not be identical to the way CoDel or PIE handle
> bursts).    

Of course. The question is how effective is the mechanism. As you note,
whatever "burst" mechanism exists in Linux's ARED wasn't effective as
evident from the low throughput in the plots.
  
>> opposed to previous notions that delay-based ARED would work right out of the
>> box. 
> 
> it's probably not accurate to say "redesign" as delay-based ARED doesn't exist
> as of know. AFAIK given our latest results with ARED, we raised the
> possibility of modifying ARED to use delay-based thresholds instead of
> size-based thresholds during the ICCRG talk and in the TR, and declared it as
> future work. I'm not aware of any other implementation/proposal of delay-based
> ARED to exist as of now. We never claimed or speculated on how this future
> delay-based AQM might perform and left it to when the future work is done and
> the outcome is properly investigated and therefore we never said that "it
> would work right out of the box" :-).
>  

Great. Thanks for confirming this point that ARED as is does not work well
for the scenarios considered. What is required is new AQM design, not just
plugging delay into ARED.
Preethi

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Thu, 14 Nov 2013 19:59:31 +0000

Please see inline…

Thanks,

Rong

From: Naeem Khademi <[email-masked]<mailto:[email-masked]>>
Date: Thursday, November 14, 2013 8:43 AM
To: Preethi Natarajan <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, Michael Welzl <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] AQM schemes: Queue length vs. delay based

I think I now understand what you mean by this sentence ;-) and therefore please ignore the paragraph responding to this specific point in the previous email (sorry about that, I got it mixed with max_target). Indeed ARED drops every packet when the average queue length grows beyond th_max as drop probability jumps to 1 (when it's not in gentle mode). For this to happen, the "average queue length" has to grow beyond th_max and depending on how the averaging is done, that can correspond to certain burst allowance at AQM. Moreover, this is done over 500 ms interval which means the average queue length has to stay above th_max for mostly few rounds of RTTs (assuming the typical distribution of RTTs on the Internet to have a mean/average somewhere below that value e.g. 100~200 ms). This allows burst that don't take the average queue size to above th_max over 500 ms period to pass and clear themselves up the queue.

 > This is unacceptable of an AQM even for max thresholds around 50ms.

-----------------------------
>>>>>>>>>>>>>RP: Two issues here, first, averaging has a parameter. How to tune it to avoid tail drop behavior? What would be its relationship to max_th? Do we understand ?  Second, one single tcp's behavior is very bursty, if 500ms burst allowance is effective in ARED, how come is it not reflected in your throughput chart? The one single tcp throughput is very low for low latency numbers, which is a clear indication of not enough buffering.
------------------------------------

Whether this is a good thing or bad thing is a subjective matter in my opinion, as most AQMs at some point will drop every packet whether it be the maximum queue length or at some thresholds.

----------------------------
>>>>>>>>>>>>RP: I don’t think so. Neither PIE nor Codel has drop-all threshold as AQM part of it. Tail drop exists, but it is not part of AQM. Putting the latency-based  ARED aside, ARED in this current form has the issues that we mentioned in the previous emails. It needs significant and careful redesign.
---------------------------

There is also a comment about "Throwing away all the knowledge and improvement gained from RED-like AQMs, CHoKe, etc and coming up with brand-new AQMs …".

------------------------------------------
>>>>>>>>>>RP: After I worked on CHOKe (now in Linux Kernel)  in 2000 as part of my Ph.D. thesis at Stanford, I have worked on AFD (implemented in many Cisco flagship products), QCN (now IEEEE standard for data center ethernet, 802.1Qau), all of which are AQM schemes. I also helped writing guidelines in tuning WRED at Cisco. New thinkings were brought into PIE after I learned precious lessons (both good and bad) from all of them. Discarding them as "coming up with brand-new AQMs" is ignorant.

Regards,

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

Cheers,
Naeem

>>>>>>>>>>>>RP:

---

From: Preethi Natarajan <[email-masked]>
Date: Thu, 14 Nov 2013 12:00:05 -0800

From:  Naeem Khademi <[email-masked]>
Date:  Thursday, November 14, 2013 8:05 AM
To:  Anoop Ghanwani <[email-masked]>
Cc:  <[email-masked]>, Michael Welzl <[email-masked]>,
"[email-masked]" <[email-masked]>, Preethi Natarajan <[email-masked]>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

> 
> 
> Below is my personal opinion, but hopefully Fred can clarify this better based
> on the AQM recommendations draft:
> 
> AQM will most likely to help from data centers to the access links, and so on.
> But we may possibly need different AQMs for different network scenarios; The
> fact that an AQMs should be auto-tunable doesn't imply that it can be applied
> everywhere and we may need different auto-tunable AQMs specifically designed
> for different networks (ideally better if we could use fewer of them and they
> could work everywhere). I hope I'm not wrong.
>  

Again, please hold on. Even if its personal opinion, I would state facts
backed with evidence instead of "hopes", since the community's thought
process is at stake here.

>From the preliminary results we've seen, PIE has been able to address data
center issues quite well. There is no evidence thus far why PIE's control
law with auto-tuned parameters cannot adapt to data center or other network
environments. 

Given that, its too early to "hope" that different network scenarios need
different AQM schemes. Of course, different network environments may choose
to deploy different AQM schemes for various other reasons, which is not the
point of discussion here.

Preethi

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 21:19:59 +0100

> plugging delay into ARED.

Agreed with all your points though to complete it, developing new AQMs
without looking back at and learning from what we have had available leads
to inventing things that improve utilization instead of delay for instance
:-). Again to emphasis we never recommended that people should turn on RED
or ARED (or any future variant of ARED) on their edge devices, but rather
we experimentally demonstrated that it worked better than CoDel and PIE is
most of the scenarios we studied except in very few. We thought it was
important to have more basic understandable experimental results (with
long-lived TCP flows) available before we indulge in looking at more
complex traffic scenarios.

What I would probably choose to investigate e.g. why PIE performs with a
very long upper distribution tail of RTTs with common long-lived TCP
traffic more specifically for lower target delay values even though we know
TCP isn't a very bursty type of traffic? Could that be related to the way
it handles bursts?  or any other reason?  The technical report provides a
very first insight into such issues that need to be explored like this one
but then the story doesn't stop here and ARED was only a benchmark that was
close enough to IETF-documented RED and could work with a certain target
delay (in our scenarios).

Naeem

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 21:25:35 +0100

Very sorry for double-posting as for some reasons "what I was answering to"
was missed from the rest of my previous email. So here again:

---

From: "Ilpo Järvinen" <[email-masked]>
Date: Thu, 14 Nov 2013 22:32:51 +0200 (EET)

On Thu, 14 Nov 2013, Preethi Natarajan wrote:

> "target delay" or "target queuing". Judging based on the (param) name,
> they supposedly try to maintain the queue delay/length around/at a
> certain value although "target delay/queuing" has different semantics
> in each AQM and the response to crossing that threshold/value is also
> different from one AQM to another. Moreover, It is favorable for an
> AQM that tries to fix bufferbloat problem to have a predictable delay
> distribution, most favorably around (e.g. mean, median, max) a certain
> value. PIE uses it, CoDel has it and ARED in fixed BW setups has it
> too. So, I'm not quite sure, why it shouldn't be possible to allow a
> certain size of burst in such threshold-based mechanisms (AFAIK
> (A)RED's Linux implementation already has a "burst" param that can be
> tuned, although its semantics may not be identical to the way CoDel or
> PIE handle bursts). Of course. The question is how effective is the 
> mechanism. As you note, whatever "burst" mechanism exists in Linux's 
> ARED wasn't effective as evident from the low throughput in the plots. 

IIRC, the Linux burst parameter is taken into account in frontend tc-tool 
only to calculate parameters for the kernel. I think its meaning was quite 
close to what L is in formula 3 [1] but it's like ten years ago when I 
read that bit of code. As such, its value only applies to the case where 
the queue average is zero before the burst occurs.

However, the real problem with these "burst" parameters is that they 
do not specify a limit for the burst. Instead, they are only used to set a 
minimum burst they allow but by no means give a way to specify a hard 
deadline when the burst has to be stopped at latest. By no means 
drops/marks typically occur soon after the "burst" threshold is crossed 
because the drop probability will be extremely small.

I've shown this lack of control with a typical RED setup [2] (ARED is 
actually worse than RED because of auto-tuning makes it even slower than 
typical RED setup but I didn't go to prove that). It also talks about 
th_max cutter and tail-drop fallback, which both seemed to be already 
mentioned in this thread. Based on how timers work in CoDel and PIE it is 
pretty obvious that the lack of control problem is present in them too 
(I've a paper coming up very soon on these issues too).

-- 
 i.

[1] Random Early Detection gateways for Congestion Avoidance.
Floyd, S., and Jacobson, V.
IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413.

[2] Ilpo Järvinen, Aaron Yi Ding, Aki Nyrhinen, Markku Kojo, "Harsh RED: 
Improving RED for Limited Aggregate Traffic", In Proc. IEEE International 
Conference on Advanced Information Networking and Applications (IEEE AINA 
2012), Fukuoka, Japan, March 2012.
[http://www.cs.helsinki.fi/group/wibra/aina12.pdf]

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 21:58:44 +0100

Hi Rong

comments follow inline

Thanks
Naeem

On Thu, Nov 14, 2013 at 8:59 PM, Rong Pan (ropan) <[email-masked]> wrote:

> Cc: "[email-masked]" <[email-masked]>, Michael Welzl <[email-masked]>
>
>  I think I now understand what you mean by this sentence ;-) and
> therefore please ignore the paragraph responding to this specific point in
> the previous email (sorry about that, I got it mixed with max_target).
> Indeed ARED drops every packet when the average queue length grows beyond
> th_max as drop probability jumps to 1 (when it's not in gentle mode). For
> this to happen, the "average queue length" has to grow beyond th_max and
> depending on how the averaging is done, that can correspond to certain
> burst allowance at AQM. Moreover, this is done over 500 ms interval which
> means the average queue length has to stay above th_max for mostly few
> rounds of RTTs (assuming the typical distribution of RTTs on the Internet
> to have a mean/average somewhere below that value e.g. 100~200 ms). This
> allows burst that don't take the average queue size to above th_max over
> 500 ms period to pass and clear themselves up the queue.
>
>  >>>>>>>>>>>>>RP: Two issues here, first, averaging has a parameter. How
> to tune it to avoid tail drop behavior? What would be its relationship to
> max_th? Do we understand ?  Second, one single tcp's behavior is very
> bursty, if 500ms burst allowance is effective in ARED, how come is it not
> reflected in your throughput chart? The one single tcp throughput is very
> low for low latency numbers, which is a clear indication of not enough
> buffering.

NAEEMK: As stated before, we're not advocating using ARED whatsoever.
Therefore trying to fix/address ARED's inherent issues that have been
stated on this thread repeatedly would not be an option nor it enhances the
argument to support PIE or CoDel for deployment. So, I'm not going to
speculate on how one can possibly fix ARED thresholds and its burst
allowance. On the other hand, based on the presented experimental results,
we would alternatively like to see why CoDel and PIE performed worse that
ARED (designed in 2001) while they were expected to achieve latencies far
better than *RED.

>
>
>     Whether this is a good thing or bad thing is a subjective matter in
> my opinion, as most AQMs at some point will drop every packet whether it be
>  >>>>>>>>>>>>RP: I don’t think so. Neither PIE nor Codel has drop-all
> threshold as AQM part of it. Tail drop exists, but it is not part of AQM.
> Putting the latency-based  ARED aside, ARED in this current form has the
> issues that we mentioned in the previous emails. It needs significant and
> careful redesign.
>

NAEEMK: The same response as above.

>  There is also a comment about "Throwing away all the knowledge and
> improvement gained from RED-like AQMs, CHoKe, etc and coming up with
> brand-new AQMs …".
>
> >>>>>>>>>>RP: After I worked on CHOKe (now in Linux Kernel)  in 2000 as
> part of my Ph.D. thesis at Stanford, I have worked on AFD (implemented in
> many Cisco flagship products), QCN (now IEEEE standard for data center
> ethernet, 802.1Qau), all of which are AQM schemes. I also helped writing
> guidelines in tuning WRED at Cisco. New thinkings were brought into PIE
> after I learned precious lessons (both good and bad) from all of them.
> Discarding them as "coming up with brand-new AQMs" is ignorant.
>

NAEEMK: agreed! and we are on same side :-) though it will be nice to see
the connection points between above AQMs and PIE and lessons learned being
somehow documented.

---

From: Naeem Khademi <[email-masked]>
Date: Thu, 14 Nov 2013 22:06:50 +0100

This should have probably been brought in different thread...

comments follow inline

On Thu, Nov 14, 2013 at 9:00 PM, Preethi Natarajan <[email-masked]>wrote:

> Cc: <[email-masked]>, Michael Welzl <[email-masked]>, "
> [email-masked]" <[email-masked]>, Preethi Natarajan <[email-masked]>
>

Taking what is mentioned in above sentence granted, there is no evidence if
it cannot or if it can and this point is also orthogonal to my response to
Anoop which was about his question at IETF about AQM deployment in general.

>
> Given that, its too early to "hope" that different network scenarios needdifferent AQM schemes. Of course, different network environments may choose

It should have been on another thread. Sorry :-)

Naeem

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Thu, 14 Nov 2013 22:32:10 +0000

From: Naeem Khademi <[email-masked]<mailto:[email-masked]>>
Date: Thursday, November 14, 2013 1:58 PM
To: Cisco Employee <[email-masked]<mailto:[email-masked]>>
Cc: Preethi Natarajan <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, Michael Welzl <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] AQM schemes: Queue length vs. delay based

Hi Rong

comments follow inline

Thanks
Naeem

On Thu, Nov 14, 2013 at 8:59 PM, Rong Pan (ropan) <[email-masked]<mailto:[email-masked]>> wrote:
Please see inline…

Thanks,

Rong

NAEEMK: As stated before, we're not advocating using ARED whatsoever. Therefore trying to fix/address ARED's inherent issues that have been stated on this thread repeatedly would not be an option nor it enhances the argument to support PIE or CoDel for deployment. So, I'm not going to speculate on how one can possibly fix ARED thresholds and its burst allowance. On the other hand, based on the presented experimental results, we would alternatively like to see why CoDel and PIE performed worse that ARED (designed in 2001) while they were expected to achieve latencies far better than *RED.

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

>>>>>>>>>>RP: After I worked on CHOKe (now in Linux Kernel)  in 2000 as part of my Ph.D. thesis at Stanford, I have worked on AFD (implemented in many Cisco flagship products), QCN (now IEEEE standar…

NAEEMK: agreed! and we are on same side :-) though it will be nice to see the connection points between above AQMs and PIE and lessons learned being somehow documented.

>>>>>>RP: starting reading some of the papers about those designs, especially PIE on HPSR2013, would be a good start….

Regards,

Rong

Regards,

Rong

Cheers,
Naeem

---

From: Preethi Natarajan <[email-masked]>
Date: Thu, 14 Nov 2013 17:33:35 -0800

From:  Naeem Khademi <[email-masked]>
Date:  Thursday, November 14, 2013 1:06 PM
To:  Preethi Natarajan <[email-masked]>
Cc:  curtis <[email-masked]>, Michael Welzl <[email-masked]>,
"[email-masked]" <[email-masked]>, Anoop Ghanwani <[email-masked]>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

>>> on. But we may possibly need different AQMs for different network scenarios;
>>> The fact that an AQMs should be auto-tunable doesn't imply that it can be
>>> applied everywhere and we may need different auto-tunable AQMs specifically
>>> designed for different networks (ideally better if we could use fewer of
>>> them and they could work everywhere). I hope I'm not wrong.
>>>  
>> 
>> center issues quite well. There is no evidence thus far why PIE's control law
>> with auto-tuned parameters cannot adapt to data center or other network
>> environments. 
> 
> Taking what is mentioned in above sentence granted, there is no evidence if it
> cannot or if it can and this point is also orthogonal to my response to Anoop
> which was about his question at IETF about AQM deployment in general.

Just pointing out the evidence here --
http://www.ietf.org/proceedings/86/slides/slides-86-iccrg-5.pdf

The slides contain preliminary results from DC scenarios, showing PIE's
parameters and adaptability to DC scenarios. Thank god for the IETF archives
:)

Thanks,
Preethi

---

From: Michael Welzl <[email-masked]>
Date: Fri, 15 Nov 2013 11:06:32 +0100

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)

- 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: 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.

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.

Cheers,
Michael

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 15 Nov 2013 16:03:51 +0000

On Nov 13, 2013, at 2:43 PM, Anoop Ghanwani <[email-masked]> wrote:

> On Wed, Nov 13, 2013 at 12:14 PM, Naeem Khademi <[email-masked]> wrote:
> 
> Agreed only in general terms -- but what would be considered as "packet burst" and how would it be defined? This will probably have a subjective answer e.g. one can argue that a size of TCP sawtooth of data is a burst and therefore we need a BDP of buffering for that (that's what had actually happened implicitly over the past decade). On the other hand, the definition of the "burst" may likely to correspond to the application generating it (e.g. video frames, IW10, etc) and therefore its size (and even pattern) is application/transport dependent somehow. 
> 
> There's one more case...the incast problem.  The sources themselves may not be "bursty" but in a high port count switch, you could have 10's (or more) ports sending traffic to a single output port at around the same time.
> 
> Perhaps it is useful to add a description of what we mean when we say bursty.

Possibly, but what you just highlighted is that there are at least two definitions. At the Transport layer, it's not unusual for TCP to send a number of segments back to back - our specifications say 2-4, but Google seems to favor as many as ten, and I'm told that measurements suggest that some on the net are sending as many as 44. That would be in a single session. What you're discussing is what I call "lemmings"; a single thread in a map/reduce or multi-cache application might simultaneously open short sessions (either opening new TCP sessions or using standing TCP sessions) with hundreds or thousands of neighbors, each of which now sends a transport-layer burst with effects as you describe. That is an application-layer burst.

Bob's DCTCP suggestion could be useful in that.

I wonder if we need a separate term for the application layer behavior, however. Maybe "flash crowd"?

> Anoop 

------------------------------------------------------
8 issues in virtual infrastructure
http://dcrocker.net/#fallacies

---

From: Andrew Mcgregor <[email-masked]>
Date: Fri, 15 Nov 2013 10:05:03 -0800

TCP as deployed can be pretty bursty; TSO often results in 44 packet bursts
(later in connections, once the window has opened wide enough), which is
one reason IW10 caused very little harm.  I wouldn't say Google favours
that; as Yuchung's presentation in TCPM showed, the TCP team here is
working hard to reduce that burstiness.  However, that is deployed reality,
and will be for some years on the net at large, no matter how undesirable
it is in terms of excessive packet loss and buffer pressure.

I very much think we should be thinking about DCTCP-style ECN; that seems
more deployable and a significant benefit, unlike the ambiguous benefit of
classic ECN.

On 15 November 2013 08:03, Fred Baker (fred) <[email-masked]> wrote:

> There's one more case...the incast problem.  The sources themselves may
> not be "bursty" but in a high port count switch, you could have 10's (or
> more) ports sending traffic to a single output port at around the same time.
>
> Possibly, but what you just highlighted is that there are at least two
> definitions. At the Transport layer, it's not unusual for TCP to send a
> number of segments back to back - our specifications say 2-4, but Google
> seems to favor as many as ten, and I'm told that measurements suggest that
> some on the net are sending as many as 44. That would be in a single
> session. What you're discussing is what I call "lemmings"; a single thread
> in a map/reduce or multi-cache application might simultaneously open short
> sessions (either opening new TCP sessions or using standing TCP sessions)
> with hundreds or thousands of neighbors, each of which now sends a
> transport-layer burst with effects as you describe. That is an
> application-layer burst.
>

-- 
Andrew McGregor | SRE | [email-masked] | +61 4 8143 7128

---

From: Anoop Ghanwani <[email-masked]>
Date: Sun, 17 Nov 2013 10:53:57 -0800

On Thu, Nov 14, 2013 at 5:33 PM, Preethi Natarajan <[email-masked]>wrote:
> parameters and adaptability to DC scenarios. Thank god for the IETF
> archives :)
>
> Hi Preethi,

In these simulations what was the buffer size used?  From my read, it looks
like the setup had ~400 KB per port before any marking/discarding would
take place.  This is significantly more than what is available in
top-of-the-rack switches used in many data centers.

This should give you an idea of the kind of buffering that is actually
available.  As port-counts go up, the amount of buffering per port goes
down.
http://people.ucsc.edu/~warner/buffer.html

For the simulations to be relevant for such switches, they would have to be
done with significantly smaller buffer sizes.  The sizing gets even worse
when we consider there may be multiple priorities and some of those may be
lossless (requiring dedicated buffers be set aside for them).

Anoop

---

From: Mikael Abrahamsson <[email-masked]>
Date: Mon, 18 Nov 2013 06:55:49 +0100 (CET)

On Sun, 17 Nov 2013, Anoop Ghanwani wrote:

> down. http://people.ucsc.edu/~warner/buffer.html

Not only that, but some switches actually have shared buffer space for 
some or all ports, so if one port is congested, you can get immediate 
drops on other ports because of lack of buffer space.

> For the simulations to be relevant for such switches, they would have to 
> be done with significantly smaller buffer sizes.  The sizing gets even 
> worse when we consider there may be multiple priorities and some of 
> those may be lossless (requiring dedicated buffers be set aside for 
> them).

For instance, I have a switch at home with 24 gig ports that have 128 
kilobytes of memory total, shared for the entire switch for all ports. 
It's a really cheap one, but still meant for enterprise deployment.

How would we model something like that?

Guess it won't add much to bufferbloat so perhaps moot discussion :)

-- 
Mikael Abrahamsson    email: [email-masked]

---

From: Preethi Natarajan <[email-masked]>
Date: Mon, 18 Nov 2013 12:03:06 -0800

From:  Anoop Ghanwani <[email-masked]>
Date:  Sunday, November 17, 2013 10:53 AM
To:  Preethi Natarajan <[email-masked]>
Cc:  Naeem Khademi <[email-masked]>, curtis
<[email-masked]>, Michael Welzl <[email-masked]>, "[email-masked]"
<[email-masked]>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

> like the setup had ~400 KB per port before any marking/discarding would take
> place.  This is significantly more than what is available in top-of-the-rack
> switches used in many data centers.
> 
> available.  As port-counts go up, the amount of buffering per port goes down.
> done with significantly smaller buffer sizes.  The sizing gets even worse when
> we consider there may be multiple priorities and some of those may be lossless
> (requiring dedicated buffers be set aside for them).
> 

Hi Anoop,

Thanks for the pointer regarding small buffers.

We haven't run simulations with small buffers in DC environments. However,
from our experience, PIE's control law usually adapts well to small buffers
for a given network condition. Maybe you can help us refine the DC
simulation parameters and we can give this a try.

We'll follow-up offline if that makes sense.

Thanks,
Preethi