[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.
> 
>