From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-bk0-f43.google.com (mail-bk0-f43.google.com [209.85.214.43]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id A64DF21F0E5 for ; Wed, 25 Jul 2012 03:26:34 -0700 (PDT) Received: by bkty15 with SMTP id y15so517055bkt.16 for ; Wed, 25 Jul 2012 03:26:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:from:to:cc:in-reply-to:references:content-type:date :message-id:mime-version:x-mailer:content-transfer-encoding; bh=nUgDQgTs/qVc5WqyXLW784atye57tR3RkJB2tUQ7AA4=; b=Q8mjP1lUglFYSHOvCKp9Tactpz2PhXjgPxlalxqXzII3qQYsOyUOw842sDwM3Axj5e vwTr/+7ax8J/VQkG5TBgevg9jCEeSVixe5hWq4v9Fsn4aZVh/8eTUFQqeXhJQnQIzVKy r8/dNXpCd5X9ucN0p6C/sH6RpS7XrdWd1wzaSciA9bEe2Z8G/J5pShsqk1dnQYpzMg2+ 8qw/2/2AmV+bQHJJw0MvncliB2CGNZuCjRELkEWBzgfSaorV/yRcLHmhaEL1iYQlYIyg yvv8iFnVKWNcNioWCdo2fMutJiBBJN4C7rSkhfxMNOSCuLJbRdrQpfxq82wBV7ZA3t0j MusA== Received: by 10.204.152.220 with SMTP id h28mr11664504bkw.30.1343211991743; Wed, 25 Jul 2012 03:26:31 -0700 (PDT) Received: from [172.28.90.119] ([74.125.122.49]) by mx.google.com with ESMTPS id hs2sm12436683bkc.1.2012.07.25.03.26.20 (version=SSLv3 cipher=OTHER); Wed, 25 Jul 2012 03:26:21 -0700 (PDT) From: Eric Dumazet To: Anton Mich In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 25 Jul 2012 12:26:19 +0200 Message-ID: <1343211979.2626.11148.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit Cc: codel@lists.bufferbloat.net Subject: Re: [Codel] Fwd: count and rec_inv_sqrt initialization X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 25 Jul 2012 10:26:35 -0000 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.