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
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm
--
________________________________________________________________
Bob Briscoe http://bobbriscoe.net/
_______________________________________________
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm
