Kathie, Van,
In <http://tools.ietf.org/html/draft-nichols-tsvwg-codel-01> (and in
the ACM queue paper), you say CoDel's control law was designed around
TCP Reno's formula relating packet drop probability to throughput. Quoting:
" The next
drop time is decreased in inverse proportion to the square root of
the number of drops since the dropping state was entered, using the
well-known relationship of drop rate to throughput to get a linear
change in throughput. [REDL1998, MACTCP1997]
"
1/ It's questionable whether it's desirable to design an AQM around
any particular transport algorithm. However, let's leave this point
aside for now...
2/ It's questionable whether it's reasonable to design an AQM around
NewReno's square-root law that is known not to scale, which means
NewReno is being superceded by algorithms like Cubic that move away
from the square root. Specifically if the window W is proportional to
1/p^b, then for:
NewReno, b = 0.5
Cubic, b = 0.75
Compound, b = 0.8
HSTCP, b = 0.835
DCTCP, b = 1
Relentless, b = 1
Scalable TCP, b = 1
However, let's leave this point aside too for now...
3/ Back in Apr'13, for myself, I plotted how the CoDel algorithm
increases drop probability with time, and it looked pretty linear to
me, not a square root law. I've just got round to doing the analysis,
and indeed it tends very quickly to a linear law with time. So,
Codel's control law will actually cause Reno's throughput to fall
with the square root of time, not linearly.
4/ It seems to be a waste of cycles to implement CoDel's control law
using a square-root. Given it results in a linear increase in drop
frequency with time, it should be possible to design a much simpler algorithm.
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).
7/ We'll need to debate how the control law should behave in the
presence of unresponsive flows, so this analysis should at least
support that discussion.
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
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
If CoDel was designed for scalable transports like DCTCP, and it was
designed for the same number of flows on any size link, this scaling
with link rate would make sense. But there are two reasons for an AQM
to have to scale with link rate:
a) Variable rate link
You would probably want to design for about the same number of flows
no matter how the link rate varies, so the control law could work for
variable rate links (assuming scalable transports, which we are
gradually tending towards).
b) Deploying CoDel on links in different parts of a network
At any one time, we tend to design a network assuming there will be
more flows on faster links. So, in order to remain as responsive on
faster links, CoDel's control law will need to be tuned for the
expected number of flows before it is deployed on different size links.
Cheers
Bob
________________________________________________________________
Bob Briscoe, BT
_______________________________________________
aqm mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/aqm
