[Codel] [PATCH] codel: Refine re-entering drop state to react sooner

[Dave Taht]

re-re-reviewing this in the light of dawn...

On Thu, Aug 23, 2012 at 1:37 AM, Dave Täht <dave.taht at bufferbloat.net> wrote:
> From: Dave Taht <dave.taht at bufferbloat.net>
>
> This patch attempts to smooth out codel behavior in several ways.
>
> These first two are arguably bugs.
>
> 1) Newton's method doesn't run well in reverse, run it twice on a decline
> 2) Account for the idea of dropping out of drop state after a drop
> upon entering drop state.
>
> 3) the old "count - lastcount" method gyrates between a heavy dropping state
>    and nearly nothing when it should find an optimum. For example, if
>    the optimum count was 66, which was found by going up 6 from lastcount
>    of 60, the old result would be 6. In this version of the code, it
>    would be 63. Arguably this could be curved by the width of the
>    8*interval between entering drop states, so > interval * 4 could be
>    something like count = count - (3 * 4), or an ewma based on ldelay.
>
> 4) Note that in heavy dropping states, count now increases slower, as well,
> as it is moved outside of the while loop.
>
> Some of this is borrowed from ideas in the ns2 code.
> ---
>  include/net/codel.h |   44 ++++++++++++++++++++++++--------------------
>  1 file changed, 24 insertions(+), 20 deletions(-)
>
> diff --git a/include/net/codel.h b/include/net/codel.h
> index 389cf62..dbfccb7 100644
> --- a/include/net/codel.h
> +++ b/include/net/codel.h
> @@ -274,11 +274,11 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
>                          * that the next drop should happen now,
>                          * hence the while loop.
>                          */
> +                       vars->count++; /* don't care about possible wrap
> +                                       * since there is no more divide
> +                                       */
>                         while (vars->dropping &&
>                                codel_time_after_eq(now, vars->drop_next)) {
> -                               vars->count++; /* dont care of possible wrap
> -                                               * since there is no more divide
> -                                               */
>                                 codel_Newton_step(vars);

This is here because in an unfinished patch I'm incrementing count by more
if we are near queue size limits... and this approximation varies slightly...

>                                 if (params->ecn && INET_ECN_set_ce(skb)) {
>                                         stats->ecn_mark++;
> @@ -305,7 +305,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
>                         }
>                 }
>         } else if (drop) {
> -               u32 delta;
> +               s32 delta;
>
>                 if (params->ecn && INET_ECN_set_ce(skb)) {
>                         stats->ecn_mark++;
> @@ -317,28 +317,32 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
>                         drop = codel_should_drop(skb, sch, vars, params,
>                                                  stats, now);
>                 }
> -               vars->dropping = true;
> +               vars->dropping = drop;

bugfix was here

>                 /* if min went above target close to when we last went below it
>                  * assume that the drop rate that controlled the queue on the
>                  * last cycle is a good starting point to control it now.
>                  */
> -               delta = vars->count - vars->lastcount;
> -               if (delta > 1 &&
> -                   codel_time_before(now - vars->drop_next,
> -                                     16 * params->interval)) {
> -                       vars->count = delta;
> -                       /* we dont care if rec_inv_sqrt approximation
> -                        * is not very precise :
> -                        * Next Newton steps will correct it quadratically.
> +               if (drop) { /* we can exit dropping state above */

part 2 of that bugfix

> +                       delta = vars->count - 3;
> +                       if(codel_time_before(now - vars->drop_next,
> +                                     8 * params->interval)) {
> +                               vars->count = delta > 0 ? (u32) delta : 1;
> +                       /* we don't care if rec_inv_sqrt approximation
> +                        * in reverse is not very precise :
> +                        * 2 Newton steps will correct it quadratically.
>                          */
> -                       codel_Newton_step(vars);
> -               } else {
> -                       vars->count = 1;
> -                       vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> +                               codel_Newton_step(vars);
> +                               codel_Newton_step(vars);
> +                       } else {
> +                               vars->count = 1;
> +                               vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> +                               codel_Newton_step(vars);
> +                       }
> +                       vars->lastcount = vars->count;
> +                       vars->drop_next = codel_control_law(vars->drop_next,
> +                                                           params->interval,
> +                                                           vars->rec_inv_sqrt);

Actually this doesn't do what I want, I think. What I wanted was to
restart dropping at slightly less than the same rate over roughly the
same interval
since the last drop...

but we are if (8 * interval) here, I guess it makes more
sense to go with now... [me scratches head]

>                 }
> -               vars->lastcount = vars->count;
> -               vars->drop_next = codel_control_law(now, params->interval,
> -                                                   vars->rec_inv_sqrt);
>         }
>  end:
>         return skb;
> --
> 1.7.9.5
>
> _______________________________________________
> 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!"