From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pb0-f43.google.com (mail-pb0-f43.google.com [209.85.160.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 3B7DF2021A8 for ; Thu, 26 Jul 2012 16:47:55 -0700 (PDT) Received: by pbcwz7 with SMTP id wz7so6034367pbc.16 for ; Thu, 26 Jul 2012 16:47:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:mime-version:content-type:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to:x-mailer; bh=g9QZSlQ9UHbLsfqAuU+Z4qIuflqaaMy1Aq4i67ovyRA=; b=uyjE3K1DFqxZYj5fxhP+BSbvqt8tjPUw+WCAv6dIE9Ik+6Ls1lBMwlyh9TuzRPfKWS sMk0B/R3XCxQJD7h9c9VpHmZR6WxgbVm7q81/WXELU8SmZVRu1UGXVlBIk4m2oTV1KvM iuVCrahtUn9jjYCWTtFxcl2wJx3mkYCKTLR6sTgP5NNCoDQGDTu6snBxVvKlzIGfAGbY qG381PBUjqec7MfjN+wUjCWIQAk5tCEgSAcSUwvbG+DVlPIXYnj5pWOeFS+MOjIm22xP K0tVU9CFOjizE86Ofug5IcGMhHnjBrZJi4IJEILIeyvB0Ut0DxAW6KrOCmNjg999xk+1 cz1g== Received: by 10.68.236.67 with SMTP id us3mr8895498pbc.80.1343346474388; Thu, 26 Jul 2012 16:47:54 -0700 (PDT) Received: from ?IPv6:2001:420:301:1005:226:8ff:feea:2cc1? ([2001:420:301:1005:226:8ff:feea:2cc1]) by mx.google.com with ESMTPS id rx7sm624076pbc.64.2012.07.26.16.47.52 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 26 Jul 2012 16:47:53 -0700 (PDT) Mime-Version: 1.0 (Apple Message framework v1084) Content-Type: text/plain; charset=us-ascii From: Anton Mich In-Reply-To: <1343211979.2626.11148.camel@edumazet-glaptop> Date: Thu, 26 Jul 2012 16:47:51 -0700 Content-Transfer-Encoding: quoted-printable Message-Id: <5D281805-E7EE-4852-B10F-DDF7A1E3677A@gmail.com> References: <1343211979.2626.11148.camel@edumazet-glaptop> To: Eric Dumazet X-Mailer: Apple Mail (2.1084) 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: Thu, 26 Jul 2012 23:47:55 -0000 Hi Eric, Thanks for looking into this!=20 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. >>=20 >> 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. >>=20 >> 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:=20 >> =09 >> else { >> vars->count =3D 1; >> vars->rec_inv_sqrt =3D ~0U >> = REC_INV_SQRT_SHIFT; >> } >>=20 >> 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): >>=20 >> @@ -166,6 +166,7 @@ >> static void codel_vars_init(struct codel_vars *vars) >> { >> memset(vars, 0, sizeof(*vars)); >> + vars->rec_inv_sqrt =3D ~0U >> REC_INV_SQRT_SHIFT; >> } >>=20 >> Has anybody encountered this behavior? Is this the correct fix? >=20 >=20 > Hi Anton >=20 > Sorry for the delay ! >=20 > I did some testings and yes, it seems we have an init problem. >=20 > But as codel_vars_init() is more often used, I prefer the following > fix : >=20 > 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 =3D (vars->count - vars->lastcount) = | 1; > + delta =3D vars->count - vars->lastcount; > + if (delta && codel_time_before(now - vars->drop_next, > + 16 * params->interval)) { > + vars->count =3D delta; > /* we dont care if rec_inv_sqrt approximation > * is not very precise : > * Next Newton steps will correct it = quadratically. >=20 >=20