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

["Toke Høiland-Jørgensen" <toke@toke.dk>]

[-- Attachment #1: Type: text/plain, Size: 40 bytes --]

Since I forgot to cross-post...

-Toke


[-- Attachment #2: Type: message/rfc822, Size: 177070 bytes --]

[-- Attachment #2.1.1: Type: text/plain, Size: 4271 bytes --]

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


[-- Attachment #2.1.2: codel-drop-rate.pdf --]
[-- Type: application/pdf, Size: 127234 bytes --]