[Codel] count and rec_inv_sqrt initialization

[Codel] count and rec_inv_sqrt initialization

[Anton Mich]

I'm looking into the Codel implementation in Linux and the ns-2 and ns-3 simulation and found some inconsistency regarding the behavior of the count variable.

Specifically, in the ACM paper the count is decreased by 2 in the pseudocode (and ns-3 code) when re-entering a dropping state, in Linux the count is reduced to the difference of the current count minus the last count, and in ns-2 the count is reduced by 1. I assume that the most up to date version is that in linux but for me it's not very obvious why we set the value of the count like that, departing from the ACM paper intuition.

Also, when testing the Linux codel scheme I discovered the following behavior:
Because rec_inv_sqrt is initialized to 0, it remains 0 under some specific traffic patterns and that forces the interval/rec_inv_sqrt to a very small number, no matter what the actual count is. For this not to happen we have to enter the else statement that sets: 
		
		 else {
			vars->count = 1;
			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
			}

I found that this behavior is fixed when initializing rec_inv_sqrt like (reason being that when the newton step is first evaluated, the count is equal to 1, so we need a good guess of the rec_inv_sqrt):

@@ -166,6 +166,7 @@
 static void codel_vars_init(struct codel_vars *vars)
 {
 	memset(vars, 0, sizeof(*vars));
+	vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
 }

Has anybody encountered this behavior? Is this the correct fix?

 
Best,
Antonios

[Codel] Fwd: count and rec_inv_sqrt initialization

[Anton Mich]

I'm looking into the Codel implementation in Linux and the ns-2 and ns-3 simulation and found some inconsistency regarding the behavior of the count variable.

Specifically, in the ACM paper the count is decreased by 2 in the pseudocode (and ns-3 code) when re-entering a dropping state, in Linux the count is reduced to the difference of the current count minus the last count, and in ns-2 the count is reduced by 1. I assume that the most up to date version is that in linux but for me it's not very obvious why we set the value of the count like that, departing from the ACM paper intuition.

Also, when testing the Linux codel scheme I discovered the following behavior:
Because rec_inv_sqrt is initialized to 0, it remains 0 under some specific traffic patterns and that forces the interval/rec_inv_sqrt to a very small number, no matter what the actual count is. For this not to happen we have to enter the else statement that sets: 
		
		 else {
			vars->count = 1;
			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
			}

I found that this behavior is fixed when initializing rec_inv_sqrt like (reason being that when the newton step is first evaluated, the count is equal to 1, so we need a good guess of the rec_inv_sqrt):

@@ -166,6 +166,7 @@
static void codel_vars_init(struct codel_vars *vars)
{
	memset(vars, 0, sizeof(*vars));
+	vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
}

Has anybody encountered this behavior? Is this the correct fix?


Best,
Antonios

Re: [Codel] Fwd: count and rec_inv_sqrt initialization

[Eric Dumazet]

On Fri, 2012-07-06 at 11:20 -0700, Anton Mich wrote:
> I'm looking into the Codel implementation in Linux and the ns-2 and
> ns-3 simulation and found some inconsistency regarding the behavior of
> the count variable.
> 
> Specifically, in the ACM paper the count is decreased by 2 in the
> pseudocode (and ns-3 code) when re-entering a dropping state, in Linux
> the count is reduced to the difference of the current count minus the
> last count, and in ns-2 the count is reduced by 1. I assume that the
> most up to date version is that in linux but for me it's not very
> obvious why we set the value of the count like that, departing from
> the ACM paper intuition.
> 
> Also, when testing the Linux codel scheme I discovered the following
> behavior:
> Because rec_inv_sqrt is initialized to 0, it remains 0 under some
> specific traffic patterns and that forces the interval/rec_inv_sqrt to
> a very small number, no matter what the actual count is. For this not
> to happen we have to enter the else statement that sets: 
> 		
> 		 else {
> 			vars->count = 1;
> 			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> 			}
> 
> I found that this behavior is fixed when initializing rec_inv_sqrt
> like (reason being that when the newton step is first evaluated, the
> count is equal to 1, so we need a good guess of the rec_inv_sqrt):
> 
> @@ -166,6 +166,7 @@
> static void codel_vars_init(struct codel_vars *vars)
> {
> 	memset(vars, 0, sizeof(*vars));
> +	vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> }
> 
> Has anybody encountered this behavior? Is this the correct fix?


Hi Anton

Sorry for the delay !

I did some testings and yes, it seems we have an init problem.

But as codel_vars_init() is more often used, I prefer the following
fix :

diff --git a/include/net/codel.h b/include/net/codel.h
index 550debf..c6d92fd 100644
--- a/include/net/codel.h
+++ b/include/net/codel.h
@@ -305,6 +305,8 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 			}
 		}
 	} else if (drop) {
+		u32 delta;
+
 		if (params->ecn && INET_ECN_set_ce(skb)) {
 			stats->ecn_mark++;
 		} else {
@@ -320,9 +322,10 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 		 * assume that the drop rate that controlled the queue on the
 		 * last cycle is a good starting point to control it now.
 		 */
-		if (codel_time_before(now - vars->drop_next,
-				      16 * params->interval)) {
-			vars->count = (vars->count - vars->lastcount) | 1;
+		delta = vars->count - vars->lastcount;
+		if (delta && 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.

Re: [Codel] Fwd: count and rec_inv_sqrt initialization

[Anton Mich]

Hi Eric,

Thanks for looking into this! 
May I also ask what is the intuition behind using this delta (which is, in my understanding, equal to the number of drops between the lastcount and the current count) as the new count value? I tried to track down in the codel list when this changed from what's in the paper, pseudocode and NS-2 to what is now in Linux but I didn't find anything.

Best,
Anton


On Jul 25, 2012, at 3:26 AM, Eric Dumazet wrote:

> On Fri, 2012-07-06 at 11:20 -0700, Anton Mich wrote:
>> I'm looking into the Codel implementation in Linux and the ns-2 and
>> ns-3 simulation and found some inconsistency regarding the behavior of
>> the count variable.
>> 
>> Specifically, in the ACM paper the count is decreased by 2 in the
>> pseudocode (and ns-3 code) when re-entering a dropping state, in Linux
>> the count is reduced to the difference of the current count minus the
>> last count, and in ns-2 the count is reduced by 1. I assume that the
>> most up to date version is that in linux but for me it's not very
>> obvious why we set the value of the count like that, departing from
>> the ACM paper intuition.
>> 
>> Also, when testing the Linux codel scheme I discovered the following
>> behavior:
>> Because rec_inv_sqrt is initialized to 0, it remains 0 under some
>> specific traffic patterns and that forces the interval/rec_inv_sqrt to
>> a very small number, no matter what the actual count is. For this not
>> to happen we have to enter the else statement that sets: 
>> 		
>> 		 else {
>> 			vars->count = 1;
>> 			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
>> 			}
>> 
>> I found that this behavior is fixed when initializing rec_inv_sqrt
>> like (reason being that when the newton step is first evaluated, the
>> count is equal to 1, so we need a good guess of the rec_inv_sqrt):
>> 
>> @@ -166,6 +166,7 @@
>> static void codel_vars_init(struct codel_vars *vars)
>> {
>> 	memset(vars, 0, sizeof(*vars));
>> +	vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
>> }
>> 
>> Has anybody encountered this behavior? Is this the correct fix?
> 
> 
> Hi Anton
> 
> Sorry for the delay !
> 
> I did some testings and yes, it seems we have an init problem.
> 
> But as codel_vars_init() is more often used, I prefer the following
> fix :
> 
> diff --git a/include/net/codel.h b/include/net/codel.h
> index 550debf..c6d92fd 100644
> --- a/include/net/codel.h
> +++ b/include/net/codel.h
> @@ -305,6 +305,8 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
> 			}
> 		}
> 	} else if (drop) {
> +		u32 delta;
> +
> 		if (params->ecn && INET_ECN_set_ce(skb)) {
> 			stats->ecn_mark++;
> 		} else {
> @@ -320,9 +322,10 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
> 		 * assume that the drop rate that controlled the queue on the
> 		 * last cycle is a good starting point to control it now.
> 		 */
> -		if (codel_time_before(now - vars->drop_next,
> -				      16 * params->interval)) {
> -			vars->count = (vars->count - vars->lastcount) | 1;
> +		delta = vars->count - vars->lastcount;
> +		if (delta && 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.
> 
> 

Re: [Codel] Fwd: count and rec_inv_sqrt initialization

[Eric Dumazet]

On Thu, 2012-07-26 at 16:47 -0700, Anton Mich wrote:
> Hi Eric,
> 
> Thanks for looking into this! 
> May I also ask what is the intuition behind using this delta (which
> is, in my understanding, equal to the number of drops between the
> lastcount and the current count) as the new count value? I tried to
> track down in the codel list when this changed from what's in the
> paper, pseudocode and NS-2 to what is now in Linux but I didn't find
> anything.
> 

Kathleen & Van are still discussing of what should be exactly done here.

The delta idea came from them, at a moment no public discussion was
happening (before publication, we were privately implementing codel)

Before the delta, we had following codes :

Version v1 -> v6 : (05/03/2012 -> 05/05/2012)

+                       if (now.tv64 - q->drop_next.tv64 < 
+                               16 * q->interval.tv64) {
+                               int c = q->count - 1;
+                               q->count = c < 1 ? 1 : c;
+                       } else {
+                               q->count = 1;
+                       }

But count was growing and was not going back to lower values

I suggested to use instead :

if (now - drop_next<  16.*interval) {
        unsigned int c = q->count >> 1;

        count = c < 1 ? 1 : c;
else {
        count = 1;
}

Then we also tried 

c = min(q->count - 1, q->count - (q->count>>4));

(Dave even had a  module param :)

static u32 count_rescale(struct codel_sched_data *q, codel_time_t now) {
        s32 c = 1;

        if (codel_time_after(now - q->drop_next, 16 * q->interval)) {
                switch(decrease_method) {
                        case 3:
                                break;
                        case 2: /* Dumazet 2 */
                                c = q->count >> 1;
                                break;
                        case 1: /* Dumazet 1 */
                                c = min(q->count - 1,
                                        q->count - (q->count >> 4));
                                break;
                        case 0: /* Codel Paper Default */
                        default:
                                c = q->count - 1;
                }
                c = max(1U, c);
        }
        return (u32) c;
}

in v13 ( 05/10/2012) we had the current form

But codel is not finalized ;)

Re: [Codel] Fwd: count and rec_inv_sqrt initialization

[Kathleen Nichols]

Probably best to say the control law is where we are still working.

On Jul 26, 2012, at 10:12 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:

> On Thu, 2012-07-26 at 16:47 -0700, Anton Mich wrote:
>> Hi Eric,
>> 
>> Thanks for looking into this! 
>> May I also ask what is the intuition behind using this delta (which
>> is, in my understanding, equal to the number of drops between the
>> lastcount and the current count) as the new count value? I tried to
>> track down in the codel list when this changed from what's in the
>> paper, pseudocode and NS-2 to what is now in Linux but I didn't find
>> anything.
>> 
> 
> Kathleen & Van are still discussing of what should be exactly done here.
> 
> The delta idea came from them, at a moment no public discussion was
> happening (before publication, we were privately implementing codel)
> 
> Before the delta, we had following codes :
> 
> Version v1 -> v6 : (05/03/2012 -> 05/05/2012)
> 
> +                       if (now.tv64 - q->drop_next.tv64 < 
> +                               16 * q->interval.tv64) {
> +                               int c = q->count - 1;
> +                               q->count = c < 1 ? 1 : c;
> +                       } else {
> +                               q->count = 1;
> +                       }
> 
> But count was growing and was not going back to lower values
> 
> I suggested to use instead :
> 
> if (now - drop_next<  16.*interval) {
>        unsigned int c = q->count >> 1;
> 
>        count = c < 1 ? 1 : c;
> else {
>        count = 1;
> }
> 
> Then we also tried 
> 
> c = min(q->count - 1, q->count - (q->count>>4));
> 
> (Dave even had a  module param :)
> 
> static u32 count_rescale(struct codel_sched_data *q, codel_time_t now) {
>        s32 c = 1;
> 
>        if (codel_time_after(now - q->drop_next, 16 * q->interval)) {
>                switch(decrease_method) {
>                        case 3:
>                                break;
>                        case 2: /* Dumazet 2 */
>                                c = q->count >> 1;
>                                break;
>                        case 1: /* Dumazet 1 */
>                                c = min(q->count - 1,
>                                        q->count - (q->count >> 4));
>                                break;
>                        case 0: /* Codel Paper Default */
>                        default:
>                                c = q->count - 1;
>                }
>                c = max(1U, c);
>        }
>        return (u32) c;
> }
> 
> in v13 ( 05/10/2012) we had the current form
> 
> But codel is not finalized ;)
> 
> 
> 
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel