Subject: Re: [aqm] CoDel's control law that determines drop frequency

From: Bob Briscoe <[email-masked]>
Date: Thu, 24 Sep 2015 21:27:20 +0100

Toke,

Having originally whinged that no-one ever responded to my original 2013 
posting, now it's my turn to be embarrassed for having missed your 
interesting response for over 3 months.

Cool that the analysis proves correct in practice - always nice.

The question is still open whether this was the intention, and if so why 
this particular control law was intended.
I would rather we started from a statement of what the control law ought 
to do, then derive it.

Andrew McGregor said he would have a go at this question some time 
ago... Andrew?

Bob

On 07/06/15 20:27, Toke Høiland-Jørgensen wrote:
> Hi Bob
>
> Apologies for reviving this ancient thread; been meaning to get around
> to it sooner, but well... better late than never I suppose.
>
> (Web link to your original mail, in case Message-ID referencing breaks:
> https://www.ietf.org/mail-archive/web/aqm/current/msg00376.html ).
>
> Having recently had a need to understand CoDel's behaviour in more
> detail, your analysis popped out of wherever it's been hiding in the
> back of my mind and presented itself as maybe a good place to start. :)
>
> So anyhow, I'm going to skip the initial assertions in your email and
> focus on the analysis:
>
>> Here's my working (pls check it - I may have made mistakes)
>> _________________
>> For brevity, I'll define some briefer variable names:
>>          interval =      I [s]
>>          next_drop =     D [s]
>>          packet-rate =   R [pkt/s]
>>          count =         n [pkt]
>>
>>  From the CoDel control law code:
>>          D(n) = I / sqrt(n)
>> And the instantaneous drop probability is:
>>          p(n) = 1/( R * D(n) )
>>
>> Then the slope of the rise in drop probability with time is:
>>          Delta p / Delta t       = [p(n+1) - p(n)] / D(n)
>>                                  = [1/D(n+1) - 1/D(n)] / [ R * D(n) ]
>>                                  = sqrt(n) * [sqrt(n+1) - sqrt(n)] / [R*I*I]
>>                                  = [ sqrt(n(n+1)) - n ] / R*I^2
> I couldn't find anything wrong with the derivation. I'm not entirely
> sure that I think it makes sense to speak about an "instantaneous drop
> probability" for an algorithm that is not probabilistic in nature.
> However, interpreting p(n) as "the fraction of packets dropped over the
> interval from D(n) to D(n+1)" makes sense, I guess, and for this
> analysis that works.
>
>> At count = 1, the numerator starts at sqrt(2)-1 = 0.414.
>> Amd as n increases, it rapidly tends to 1/2.
>>
>> So CoDel's rate of increase of drop probability with time is nearly constant (it
>> is always between 0.414 and 0.5) and it rapidly approaches 0.5 after a few
>> drops, tending towards:
>>          dp/dt = 1/(2*R*I^2)
>>
>> This constant increase clearly has very little to do with the square-root law of
>> TCP Reno.
>>
>> In the above formula, drop probability increases inversely proportional to the
>> packet rate. For instance, with I = 100ms and 1500B packets
>> at 10Mb/s =>    R = 833 pkt/s =>        dp/dt = 6.0% /s
>> at 100Mb/s =>   R = 8333 pkt/s =>       dp/dt = 0.6% /s
> I also tried to test this. I configured CoDel (on a Linux 4.0 box) on
> 1Mbps, 2Mbps and 10Mbps links with interval settings of 1 second and
> 500ms, and a total packet limit of 100k packets. This was to make it
> deliberately slower to react (so the change in drop probability is more
> visible), and to make sure no packets are dropped from queue overflow.
>
> I then sent an unresponsive UDP stream over the link at 110% of the link
> capacity (as passed to Iperf, so approximately), and collected the
> output of `tc -s qdisc` every 0.2 seconds.
>
> The attached plot is of 'pkts dropped / (pkts sent + pkts dropped)' in a
> 2-second sliding window over the duration of the test (the plot is also
> available here:
> https://kau.toke.dk/ietf/codel-drop-rate/codel-drop-rate.svg ).
>
> I've included linear trend lines from the initial time to the point of
> maximum drop probability, and as is apparent from the plot, got quite a
> good fit (r>0.99 for all six data sets). The legend includes the slopes
> of the linear fits for each of the data sets, which are not too far from
> what your analysis predicts (and I'm guessing the difference can be
> attributed to the difference in exact packet rates, but I haven't
> checked).
>
> The Flent data files with the qdisc stats over time (readable by the
> newest git version of Flent), as well as the Python script I used to
> create the graph are available here: https://kau.toke.dk/ietf/codel-drop-rate/
>
> So, in short: It seems that CoDel's "drop rate" does increase linearly
> in the presence of a persistent queue, and that the rate of increase
> depends on both the interval and the link rate.
>
> Now, I'll refrain from commenting on whether or not this is "bad", or
> indeed if it is contrary to design. It was surprising to me at least, so
> I thought I'd share my findings, in the hope that someone would either
> find them useful or tell me how they're wrong (or both!). :)
>
> -Toke
>
>
> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Andrew Mcgregor <[email-masked]>
Date: Wed, 30 Sep 2015 10:42:04 +1000

Hmm, that's really interesting.

Most interesting is that my understanding is that the control law was
intended to deal with aggregates of mostly TCP-like traffic, and that an
overload of unresponsive traffic wasn't much of a goal; this seems like
vaguely reasonable behaviour, I suppose, given that pathological situation.

But I don't have a way to derive the control law from first principles at
this time (I haven't been working on that for a long time now).

On 25 September 2015 at 06:27, Bob Briscoe <[email-masked]> wrote:

> Andrew McGregor said he would have a go at this question some time ago...
> Andrew?
>
>
> Bob
>
>
>
> (Web link to your original mail, in case Message-ID referencing breaks:https://www.ietf.org/mail-archive/web/aqm/current/msg00376.html ).
>
> available here:https://kau.toke.dk/ietf/codel-drop-rate/codel-drop-rate.svg ).
>
> aqm mailing [email-masked]://www.ietf.org/mailman/listinfo/aqm
>
>
> --

-- 
Andrew McGregor | SRE | [email-masked] | +61 4 1071 2221

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 30 Sep 2015 09:50:41 +0100

Andrew,

I am also not so interested in an AQM dealing directly with unresponsive 
traffic - I prefer to keep policing and AQM as separately deployable 
functions, because AQM should be policy-neutral, whereas policing 
inherently involves policy.

My concern was merely that CoDel's linear increase in drop probability 
can take a long time to reach where it intends to get to. I would have 
thought some form of exponential increase, or at least super-linear, 
would have been more responsive to changing traffic conditions. I.e., 
rather than have to answer the question "how quickly should drop 
probability increase?", make it increase increasingly quickly.

Early on, Rong Pan showed that it takes CoDel ages to bring high load 
under control. I think this linear increase is the reason.

Bob

On 30/09/15 01:42, Andrew Mcgregor wrote:
> intended to deal with aggregates of mostly TCP-like traffic, and that 
> an overload of unresponsive traffic wasn't much of a goal; this seems 
> like vaguely reasonable behaviour, I suppose, given that pathological 
> situation.
>
> But I don't have a way to derive the control law from first principles 
> at this time (I haven't been working on that for a long time now).
>
> On 25 September 2015 at 06:27, Bob Briscoe <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Toke,
>
>     Having originally whinged that no-one ever responded to my
>     original 2013 posting, now it's my turn to be embarrassed for
>     having missed your interesting response for over 3 months.
>
>     The question is still open whether this was the intention, and if
>     so why this particular control law was intended.
>     I would rather we started from a statement of what the control law
>     ought to do, then derive it.
>
>>     create the graph are available here:https://kau.toke.dk/ietf/codel-drop-rate/
>>
>>     [email-masked] <mailto:[email-masked]>
>     Bob Briscoehttp://bobbriscoe.net/
>
>
>     [email-masked] <mailto:[email-masked]>
> Andrew McGregor | SRE [email-masked] 
> <mailto:[email-masked]> | +61 4 1071 2221

---

From: Dave Taht <[email-masked]>
Date: Wed, 30 Sep 2015 02:00:02 -0700

On Wed, Sep 30, 2015 at 1:50 AM, Bob Briscoe <[email-masked]> wrote:
> functions, because AQM should be policy-neutral, whereas policing inherently
> involves policy.
>
> My concern was merely that CoDel's linear increase in drop probability can
> take a long time to reach where it intends to get to. I would have thought
> some form of exponential increase, or at least super-linear, would have been
> more responsive to changing traffic conditions. I.e., rather than have to
> answer the question "how quickly should drop probability increase?", make it
> increase increasingly quickly.
>
> Early on, Rong Pan showed that it takes CoDel ages to bring high load under
> control. I think this linear increase is the reason.

cake uses a better curve for codel, but we still need to do more
testing in the lab.

http://www.bufferbloat.net/projects/codel/wiki/CakeTechnical

>> create the graph are available here:
>> https://kau.toke.dk/ietf/codel-drop-rate/
>>

-- 
Dave Täht
Do you want faster, better, wifi? https://www.patreon.com/dtaht

---

From: Jonathan Morton <[email-masked]>
Date: Wed, 30 Sep 2015 12:04:50 +0300

The combination of flow isolation and "tallest sunflower" dropping on
overflow is a practical safety valve for coping with unresponsive traffic
until Codel catches up with it.  Without that, it would be too easy for one
bad flow to starve out all other traffic.

- Jonathan Morton

---

From: Polina Goltsman <[email-masked]>
Date: Wed, 30 Sep 2015 11:13:29 +0200

Dear Bob,

> under control. I think this linear increase is the reason.

Is there a link to this ?

Polina

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 30 Sep 2015 13:52:28 +0200

> Is there a link to this ?

I have an analysis of transient behaviour in my recent paper (section 6.2):
http://www.sciencedirect.com/science/article/pii/S1389128615002479

PIE struggles with this too, BTW...

-Toke

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Wed, 30 Sep 2015 14:20:28 +0200

Hi,

> PIE struggles with this too, BTW...

Thanks for the pointer, but I guess that's a different issue.
If I understood Bob correctly, he was referring to a steady state
situation with many flows (=high load?) in congestion avoidance phase.
But maybe Bob can clarify this...

Regards,
 Roland

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 30 Sep 2015 14:25:12 +0200

> But maybe Bob can clarify this...

Well, steady state has (by definition) nothing to do with how long it
takes to get there? Once CoDel has found the right scaling point it
stays there, so surely the problem is with transients?

-Toke

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 30 Sep 2015 13:59:45 +0100

Polina,

I think this was it:
<https://www.ietf.org/proceedings/85/slides/slides-85-iccrg-2.pdf>

I have a set of charts from Rong with many more tests showing CoDel's 
sluggish responsiveness, but I believe the above was the published summary.

Bob

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 30 Sep 2015 14:02:06 +0100

Roland, Toke,

Yes, Toke's right - I was talking about how fast the control law moves, 
not the steady state.

Bob

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Wed, 30 Sep 2015 15:08:08 +0200

Hi,

> Yes, Toke's right - I was talking about how fast the control law moves,

Ok, talking past each other...I meant steady state of TCP flows and not
steady state of CoDel, i.e. CA phase not slow start. Sorry for the
confusion.

Regards,
 Roland

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 30 Sep 2015 14:08:32 +0100

Dave,

It says the point at which cake enters drop state depends on how quickly 
the queue is growing.
But I don't see anything on the page you referenced about a better 
curve. I looked under AQM and under other possibly relevant headings.

I meant to say in my mail to Andrew that the rate at which the control 
law increases the dropping frequency ought to depend on how far the 
queue is from target, or even how quickly it is diverging from target. 
I've always said that this control law should not be just a hard-coded 
thing that has no dependency on how the queue is moving.

Also below I've restated a couple of points I made back in 2013 when I 
first posted this.

On 12/11/13 22:30, Bob Briscoe wrote:
> 5/ My analysis also shows that the rate of increase in drop probablity 
> is inversely proportional to the link rate. I don't believe this is 
> desirable, as it will require tuning for the expected number of flows 
> on the link. However it is probably OK for variable rate links.
>
> 6/ The rate of increase of drop probability is also inversely 
> proportional to the square of 'interval'. I suggest a new constant is 
> defined for the control law, rather than relating the control law to 
> interval in this way. Otherwise, when anyone tunes interval, they will 
> get undesirable changes to the control law (e.g. reducing interval 10x 
> [to 10ms] would make the control law 100x more sluggish).

This last point is particularly important. If the control law is still 
to be hard-coded, it should relate to another variable RTT_ave, not 
interval. TO decide when to enter dropping state, interval should be set 
to the likely worst-case RTT (in the low hundreds of ms). But, If 
hard-coded, the dynamics of the control law will be correct most often 
if it depends on the /most likely/ RTT, which these days with CDNs is 
perhaps 10-25ms (depending on population density in a country).

There's another reason for having two separate variables, not just 
'interval' for both. I've said the following before somewhere as well: 
For ECN marking, 'interval' can be set much lower (or even zero) because 
being on a hair-trigger with ECN marks doesn't matter, whereas it does 
for drops.{Note 1} Then CoDel will signal ECN without the sluggish delay 
it has to have before it starts dropping. However, once it has entered 
dropping state, the ECN control law still needs to be based on the same 
RTT_ave as for drop, because the control law is trying to mimic the 
dynamics of the congestion control, which RFC3168 says should be the 
same for ECN as for drop.{Note 2}

Bob

{Note 1}: The faster dynamics won't affect the long-term stable rate 
between an ECN and a non-ECN flow, because by definition long-term 
stable means the dynamics have settled.
{Note 2}: As suggested in draft-briscoe-aqm-dualq-coupled-00, if the 
congestion control were radically different, the packets would probably 
need another identifier to distinguish them from 'classic' ECN.

---

From: Kuhn Nicolas <[email-masked]>
Date: Wed, 30 Sep 2015 15:16:57 +0000

All, 

CoDel's issues with high load have also been measured in [1]. 

Cheers, 

Nicolas 

[1] Jarvinen, I.; Kojo, M., "Evaluating CoDel, PIE, and HRED AQM techniques with load transients," in Local Computer Networks (LCN), 2014 IEEE 39th Conference on , vol., no., pp.159-167, 8-11 Sept. 2014. doi: 10.1109/LCN.2014.6925768
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6925768&isnumber=6925725

-----Message d'origine-----
De : aqm [mailto:[email-masked]] De la part de Bob Briscoe
Envoyé : mercredi 30 septembre 2015 15:00
À : Polina Goltsman
Cc : AQM IETF list
Objet : Re: [aqm] CoDel's control law that determines drop frequency

Polina,

I think this was it:

I have a set of charts from Rong with many more tests showing CoDel's sluggish responsiveness, but I believe the above was the published summary.

Bob

---

From: Polina Goltsman <[email-masked]>
Date: Wed, 30 Sep 2015 17:43:56 +0200

Bob,

May I ask how curvy red is supposed to perform in those situations?

If I understand Codel's law correctly, Codel "starts fresh" every time 
it enters dropping state, so when the load increases it will take more 
time for the control law to reach the correct "count" value for the 
queue to drop. Thus with higher load latency is increased.

Now, if I understood your curvey red report correctly, you argued that 
AQM should increase latency when load increases since otherwise it will 
cause too much loss. Which makes Codel's behavior at least justified ...

BTW, I haven't seen any place in the original specification that 
suggested that fixed target delay is the intended design goal.

Does this make any sense?

Regards,
Polina

On 09/30/2015 02:59 PM, Bob Briscoe wrote:
>>> Early on, Rong Pan showed that it takes CoDel ages to bring high 
>>> load under control. I think this linear increase is the reason.
>>

---

From: Jeff Weeks <[email-masked]>
Date: Wed, 30 Sep 2015 15:57:24 +0000

I don't believe codel does start fresh; there are various back-off mechanisms that have been employed in the management of 'count' such that if the drop state is entered soon after it previously left the drop state, it'll re-enter at close to the same interval.

I believe these mechanisms were put in place to combat the sluggishness, but that doesn't help the initial drop state.

In practice, I've found that incrementing 'count' more rapidly can help to a point... but incrementing it too much appears to result in the sqrt approximation diverging from the ideal value, and then things start to fall apart.

--Jeff

________________________________________
From: aqm [[email-masked]] on behalf of Polina Goltsman [[email-masked]]
Sent: Wednesday, September 30, 2015 11:43 AM
To: Bob Briscoe
Cc: AQM IETF list
Subject: Re: [aqm] CoDel's control law that determines drop frequency

Bob,

Regards,
Polina

---

From: Polina Goltsman <[email-masked]>
Date: Wed, 30 Sep 2015 18:37:14 +0200

It seems that  the presentation used Linux version for Codel. I can't 
quite get what exactly it does but it does not decrease count by two (as 
in the draft):

on reentering dropping state within 16 intervals:
delta = vars->count - vars->lastcount;
vars->count = delta;
vars->lastcount = vars->count;

See  the bottom image on slide 18 
https://www.ietf.org/proceedings/85/slides/slides-85-iccrg-2.pdf: count 
does not get reset to zero, but it drops by at least two times * .

It also seems that the delay variations on slide 15 with two UDP flows 
were caused by this reentering behavior...

* cake version did not exist at the time, did it?