[Codel] count and rec_inv_sqrt initialization

Anton Mich lp2s1h at gmail.com
Fri Jul 6 14:10:38 EDT 2012

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?


More information about the Codel mailing list