[Codel] [RFC PATCH] codel: tighten responsiveness and more reliably deal with loads

[Dave Taht]

On Mon, Aug 27, 2012 at 5:17 AM, Eric Dumazet <eric.dumazet at gmail.com> wrote:
> On Sun, 2012-08-26 at 12:02 -0700, Dave Täht wrote:
>> From: Dave Taht <dave.taht at bufferbloat.net>
>>
>> This updates the codel algorithm to more closely match the current
>> experimental ns2 code. Not presently recomended for mainline.
>>
>> 1) It shortens the search for the minimum by reducing the window over
>>    the intervals and re-running the control law to better schedule
>>    the estimate.
>> 2) Holds onto the drop schedule harder when re-entering drop state.
>> 3) Corrects for newton method running in reverse.
>>
>> ---
>>  include/net/codel.h |   39 +++++++++++++++++++++++----------------
>>  1 file changed, 23 insertions(+), 16 deletions(-)
>>
>> diff --git a/include/net/codel.h b/include/net/codel.h
>> index 389cf62..57031ad 100644
>> --- a/include/net/codel.h
>> +++ b/include/net/codel.h
>
>> +             codel_Newton_step(vars);
>> +             codel_Newton_step(vars);
>
> This makes no sense for several reasons :
>
> 1) If we do the         vars->count = 1;
>         vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
>
> Then there is no need of _any_ Newton steps.
> The rec_inv_sqrt value is the good one.
>
> 2) If we change vars->count to vars->count - 2
>   Then a single step is enough.
>

The double newton step now is an artifact of when count could jump
from one large number to a smaller one. It didn't hurt, I didn't feel
like thinking about it, and I wanted to match the behavior of a real sqrt
and the model more exactly.

I thought really hard about ripping it out and going back to the invsqrt
code, too. I also fiddled with the clock...

>
> I can understand that with the current way :
>
>    vars->count =  vars->count - vars->lastcount
>
> then we can have a slight error, but this gave no difference in codel
> experimental behavior.

Actually the error could be quite large. (as in off by a factor of 2)

> I would say that codel response to bad queue is pretty easy (doing count
> ++ at each drop), but changes in count to adapt to oscillations between
> good and bad queues is yet to be investigated.
>
> Do we have to do
> 0) current way (count - lastcount)
> 1) count = count - 1
> 2) count = count - 2
> 3) count = count * 88%
> 4) count = count * 75%
> 5) count  = count * 50%
> 6) count = count * 25%
> 7) count = some clever function using history of previous changes
> ...
>
> In my prior tests, 1) and 2) were pretty bad, I am sure it is not the
> right way.

I was *utterly sure* it was not the right way, either, then

(after fiddling with various variants of the above for a month),

only then I implemented kathie's change to do the control_law inside
of ok_to_drop...

... and count-2 worked much better than I expected.

Please note that kathie and van aren't satisfied with this variant either,
but do try it...

> (the count = 1 is only done when queue was idle for a long time)

See the additional placement of the control law.

>
>
> _______________________________________________
> Codel mailing list
> Codel at lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel



-- 
Dave Täht
http://www.bufferbloat.net/projects/cerowrt/wiki - "3.3.8-17 is out
with fq_codel!"