Subject: Re: [aqm] Question re draft-baker-aqm-recommendations recomendation #2

From: Bob Briscoe <[email-masked]>
Date: Fri, 12 Jul 2013 01:15:47 +0100

Dave,

At 17:40 30/04/2013, Dave Taht wrote:
>On Tue, Apr 30, 2013 at 9:29 AM, Wesley Eddy <[email-masked]> wrote:
> > On 4/29/2013 10:00 AM, Fred Baker (fred) wrote:
> >> Do we generally agree with the recommendation of 
> http://tools.ietf.org/html/draft-baker-aqm-recommendation-01#section-4.2? 
> This is the question of signaling to an endpoint using both dropping and ECN.
> > The second part (imposing an upper bound) might be worth expanding a
> > bit.  I don't know what a reasonable upper bound is, for failing into
> > a tail-drop mode,
>
>No reason to specify "tail" drop here.

I agree with you here that it doesn't have to be tail-drop. But I 
would add that we need to record the lessons learned in the past, not 
just say "drop" and hope people understand.

1/ The RED algo was defined such that at a configured length of the 
smoothed queue it rose to 100% drop probability. When that was 
initially implemented in alt_q, it allowed an unresponsive flow to 
turn RED into a DOS amplifier, because 100% drop = 0% throughput. Of 
course, once the algo drops 100% of incoming traffic, the smoothed 
queue will reduce and the drop prob will reduce, but this led to 
unstable behaviour.

In the alt_q RED code you can still see this 100% drop stuff that 
Kenjiro Cho commented out, and replaced with fall-back to tail drop.

When I last looked at the CoDel code (which wasn't recently), if 
unresponsive traffic was keeping the queue above threshold, it used 
the drop_next_ variable to continually decrease the time between 
drops until it would eventually drop 100%. I figured it was likely 
the same instability would ensue. You may have fixed this since, 
given CoDel performed badly with unresponsive traffic in the early tests.

My point is that we need to record this advice, because everyone 
seems to start out making the same mistake - the boundary conditions 
of the algos get overlooked, and they are important for Internet stability.

So we should give examples of good and bad approaches for the 
boundary conditions. An example of a good simple strategy would be 
something very much like tail drop, but where the 'tail' is a fixed 
tight delay cap, not the tail of the buffer.

BTW #1, once in dropping mode, the CoDel code that I looked at 
initially took the square-root of the count of drops to decrease the 
time between drops. Ironically this leads to a /linear/ increase in 
drop frequency over /time/. So I'm sure there should be a much 
simpler way to code it without the square root, by driving drops from 
elapsed time not drop count.

BTW #2, in that same CoDel code, the dropping pattern once in the 
dropping mode did not depend on how large the queuing delay was 
getting - it was all pre-ordained how it would behave. Again, this 
may have since been fixed, but to me it seemed very wrong not to drop 
more frequently if the queuing delay was getting longer and longer.

When I looked at the original CoDel code, I just thought the word 
auto-tuning was being used as empty marketing BS. It's use of service 
time certainly auto-tuned the queue threshold to the link rate. 
However, in both its modes it didn't change how quickly it responded 
dependent on how bad the problem had become.

As an output of this proposed AQM WG, I would like to see advice that 
says what auto-tuning means, not just the empty word "auto-tuning", 
ie. not just using time as the unit of queuing, but also an AQM 
should not take a hard-coded time to respond irrespective of how much 
the queuing delay has grown.

[Sorry for responding nearly 2 months late (I'm just catching up on 
stuff that arrived while I was tuned out from the AQM list, due to other work)]

Bob

________________________________________________________________
Bob Briscoe,                                                  BT

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 12 Jul 2013 01:06:23 +0000

On Jul 11, 2013, at 5:15 PM, Bob Briscoe <[email-masked]>
 wrote:

> As an output of this proposed AQM WG, I would like to see advice that says what auto-tuning means, not just the empty word "auto-tuning", ie. not just using time as the unit of queuing, but also an AQM should not take a hard-coded time to respond irrespective of how much the queuing delay has grown.

I'm all for that. Maybe we can get the WG, if there is one, to add a document describing that, or add text to the AQM recommendation. Suggest text/approach?

I'd suggest perhaps discussing this in Berlin.

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 12 Jul 2013 19:27:00 +0100

Dave & Fred, (two birds in one posting)

At 02:06 12/07/2013, Fred Baker (fred) wrote:

> > As an output of this proposed AQM WG, I would like to see advice 
> that says what auto-tuning means, not just the empty word 
> "auto-tuning", ie. not just using time as the unit of queuing, but 
> also an AQM should not take a hard-coded time to respond 
> irrespective of how much the queuing delay has grown.
>
>I'm all for that. Maybe we can get the WG, if there is one, to add a 
>document describing that, or add text to the AQM recommendation. 
>Suggest text/approach?
>

Fred, Altho I said it originally, I'm not sure how much we can or 
should write down about the basic art of controlling stuff. A 
standards body is good for people who want to check that product X 
has features a,b,&c. It's not necessarily the right place to write 
documents for Mr Brown in procurement to check that the subtleties of 
algorithm Y comply with articles d,e&f of control theory.

>At 02:49 12/07/2013, Dave Taht wrote
>[Bob Brisoe has copied this response across from another thread, 
>'cos it was written in response to this point about auto-tuning]:
>
>The sqrt->linear drop approach is tcp friendly and currently works
>well on a wide range of RTTs. It certainly seems like a worthwhile
>research effort to measure and act on the slope of the curve, both up
>and down, in a codel variant, in order to get better results faster.

Dave, Setting aside TCP-friendly for a minute, depending on the slope 
would be research yes. But let's get the basics first. The only thing 
that depends on queue delay (in the CoDel drop code I looked at) was 
when drop started and when it stopped. In between, the pattern of 
gaps between the drops was pre-ordained and hard coded. If the queue 
was growing ridiculously long (e.g. due to a flash crowd), CoDel 
still laboriously decreased the gap between each drop in its 
preordained pattern.

I hope that's been improved in more recent CoDel code. This is the 
basic structure of an algo - I'd hardly even call it auto-tuning, 
it's about ensuring the intensity of the dropping within the 
algorithm depends on the effect it is trying to control.

Similarly, the delay before dropping starts is completely independent 
of whether the queue  has been slightly above 'target' for 'interval' 
or queue delay has headed off into the stratosphere during 
'interval'. IOW, I would challenge that the very use of the min() 
function in CoDel is counter to auto-tuning (auto-controlling) principles.

________
Finally, I can't resist having a snipe at that TCP-friendly sentence. 
If you can justify it I would be most impressed. It looked like BS 
when I saw it in VJ/Nichols paper, and it still looks like BS. That 
sqrt is relative to the count of drops, which is nothing to do with 
the sqrt in the TCP formula. It's as likely to be related to 
mass-energy equivalence, because that's got a square term in it too.

[Anyway, only Reno congestion window is proportional to 1/p^0.5. The 
cwnd of Cubic & Compound are proportional to 1/p^0.75 and 1/p^0.8 
respectively.]

Bob

---

From: Dave Taht <[email-masked]>
Date: Mon, 15 Jul 2013 15:51:02 -0400

On Fri, Jul 12, 2013 at 2:27 PM, Bob Briscoe <[email-masked]> wrote:
>> > says what auto-tuning means, not just the empty word "auto-tuning", ie. not
>> > just using time as the unit of queuing, but also an AQM should not take a
>> > hard-coded time to respond irrespective of how much the queuing delay has
>> > grown.
>>
>> document describing that, or add text to the AQM recommendation. Suggest
>> text/approach?
>>
> Fred, Altho I said it originally, I'm not sure how much we can or should
> write down about the basic art of controlling stuff. A standards body is
> good for people who want to check that product X has features a,b,&c. It's
> not necessarily the right place to write documents for Mr Brown in
> procurement to check that the subtleties of algorithm Y comply with articles
> d,e&f of control theory.
>
>> [Bob Brisoe has copied this response across from another thread, 'cos it
>> was written in response to this point about auto-tuning]:
>>
> Dave, Setting aside TCP-friendly for a minute, depending on the slope would
> be research yes. But let's get the basics first. The only thing that depends
> on queue delay (in the CoDel drop code I looked at) was when drop started
> and when it stopped. In between, the pattern of gaps between the drops was
> pre-ordained and hard coded.

It's subtle, but you'll notice the gap between restarting at a given drop rate
is dynamic. This is the bit that searches for an ideal drop rate.

This was heavily discussed towards the tail end of my stanford talk.

> If the queue was growing ridiculously long
> (e.g. due to a flash crowd), CoDel still laboriously decreased the gap
> between each drop in its preordained pattern.

"The queue". When you are using fair queuing "the queues", the
"problematic queue" grows longer and is delayed more as it is
interleaved with the other queues, thus the apparent drop rate on that
flow increases not as a proportion of packets in the flow but as a
proportion of the overall delays it is experiencing.

> I hope that's been improved in more recent CoDel code.

Codel doesn't stand alone. See last paragraph here:
https://gettys.wordpress.com/2013/07/10/low-latency-requires-smart-queuing-traditional-aqm-is-not-enough/
We've not said anything different...

There are patches for various things floating around. In particular I
have a version that is "tighter" but I fear it will perform badly at
1sec+ rtts. I'd like to consider ewma for managing the slope rather
than the current strategy but am not there yet. I've been building up
my lab to be able to look closely at longer RTT and videoconferencing
issues in what we have so far.

patches have been posted to the codel list. We are discussing now the
nature of a more ideal replacement for the existing default queue
discipline in linux, which has three fq_codel tiers in it (priority,
best effort, and background) over there at the moment.

Yep, further research is needed.

> This is the basic
> structure of an algo - I'd hardly even call it auto-tuning, it's about
> ensuring the intensity of the dropping within the algorithm depends on the
> effect it is trying to control.

The goal of a queue is to absorb bursts. If it's possible within the
target to drain that burst entirely, then dropping at a high rate is a
bad idea. Codel will gently and eventually get there. So I agree with
the statement it's about ensuring that the intensity of the dropping
within the algorithm depending on the effect you are trying to control
- in this case, signalling the other side of the flow to slow down
with a drop or mark.

... but I'm pretty sure that's not what you meant.

> Similarly, the delay before dropping starts is completely independent of
> whether the queue  has been slightly above 'target' for 'interval' or queue
> delay has headed off into the stratosphere during 'interval'. IOW,

As I described, yes, for certain values of stratosphere, a more robust dropping
strategy should be tried. That said, the goal is to wait long enough for the
signal to reach the other side...

> I would
> challenge that the very use of the min() function in CoDel is counter to
> auto-tuning (auto-controlling) principles.
>
> ________
> Finally, I can't resist having a snipe at that TCP-friendly sentence. If you
> can justify it I would be most impressed. It looked like BS when I saw it in
> VJ/Nichols paper, and it still looks like BS. That sqrt is relative to the
> count of drops, which is nothing to do with the sqrt in the TCP formula.
> It's as likely to be related to mass-energy equivalence, because that's got
> a square term in it too.

Heh. I'll leave it to kathie and van to defend their usage. I think
"RTT-friendly"
would have been more accurate, but that's not a defined term. Perhaps it
should be?

>
> [Anyway, only Reno congestion window is proportional to 1/p^0.5. The cwnd of
> Cubic & Compound are proportional to 1/p^0.75 and 1/p^0.8 respectively.]
>
>
>
>
> Bob
>
>

-- 
Dave Täht

Fixing bufferbloat with cerowrt: http://www.teklibre.com/cerowrt/subscribe.html