From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f181.google.com (mail-wi0-f181.google.com [209.85.212.181]) (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 3E441202295 for ; Thu, 23 Aug 2012 07:22:37 -0700 (PDT) Received: by wibhm2 with SMTP id hm2so702735wib.10 for ; Thu, 23 Aug 2012 07:22:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=nLOhrNsCtaIi/YP9iN1E8LW9t/JNu6Lw4me0SwvuLCw=; b=EgtAmVRljVSkCtnet13nvQfLp+6Encd0z3tB3lWSfSeyH/wp5xs3nO/uDCelA4EDSQ 5K62HiNFuxUPIZRtdld14JH6A7SqiXb1SIL2EV9ovfRb15Pu/TCCrvsmvlrElhuamTQ0 2f7m30e/vz51NNqWhpcLIV7qxv5f3fXOSv3hvj0qfrkSSTqpU2jTJwm3HAER9xcuW2XD qrmw0/bshfzP00fa8ljm419ZKlw5xg6dscUJ08UPCcj5rlIqEYZHKB4ceX1f7QIvw0F8 1NQ3w3K/xL1mdG5ZBOZPbs6cifkR5XhRXQKvothi8tfILy5V4IF9iZvKiK1PitHStDK8 AynA== MIME-Version: 1.0 Received: by 10.180.78.170 with SMTP id c10mr15430075wix.3.1345731754649; Thu, 23 Aug 2012 07:22:34 -0700 (PDT) Received: by 10.223.143.69 with HTTP; Thu, 23 Aug 2012 07:22:34 -0700 (PDT) In-Reply-To: <1345711043-4796-1-git-send-email-dave.taht@bufferbloat.net> References: <1345711043-4796-1-git-send-email-dave.taht@bufferbloat.net> Date: Thu, 23 Aug 2012 07:22:34 -0700 Message-ID: From: Dave Taht To: =?ISO-8859-1?Q?Dave_T=E4ht?= Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: codel@lists.bufferbloat.net Subject: Re: [Codel] [PATCH] codel: Refine re-entering drop state to react sooner 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, 23 Aug 2012 14:22:39 -0000 re-re-reviewing this in the light of dawn... On Thu, Aug 23, 2012 at 1:37 AM, Dave T=E4ht wr= ote: > From: Dave Taht > > This patch attempts to smooth out codel behavior in several ways. > > These first two are arguably bugs. > > 1) Newton's method doesn't run well in reverse, run it twice on a decline > 2) Account for the idea of dropping out of drop state after a drop > upon entering drop state. > > 3) the old "count - lastcount" method gyrates between a heavy dropping st= ate > and nearly nothing when it should find an optimum. For example, if > the optimum count was 66, which was found by going up 6 from lastcount > of 60, the old result would be 6. In this version of the code, it > would be 63. Arguably this could be curved by the width of the > 8*interval between entering drop states, so > interval * 4 could be > something like count =3D count - (3 * 4), or an ewma based on ldelay. > > 4) Note that in heavy dropping states, count now increases slower, as wel= l, > as it is moved outside of the while loop. > > Some of this is borrowed from ideas in the ns2 code. > --- > include/net/codel.h | 44 ++++++++++++++++++++++++-------------------- > 1 file changed, 24 insertions(+), 20 deletions(-) > > diff --git a/include/net/codel.h b/include/net/codel.h > index 389cf62..dbfccb7 100644 > --- a/include/net/codel.h > +++ b/include/net/codel.h > @@ -274,11 +274,11 @@ static struct sk_buff *codel_dequeue(struct Qdisc *= sch, > * that the next drop should happen now, > * hence the while loop. > */ > + vars->count++; /* don't care about possible wrap > + * since there is no more divide > + */ > while (vars->dropping && > codel_time_after_eq(now, vars->drop_next))= { > - vars->count++; /* dont care of possible w= rap > - * since there is no more = divide > - */ > codel_Newton_step(vars); This is here because in an unfinished patch I'm incrementing count by more if we are near queue size limits... and this approximation varies slightly.= .. > if (params->ecn && INET_ECN_set_ce(skb)) = { > stats->ecn_mark++; > @@ -305,7 +305,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sc= h, > } > } > } else if (drop) { > - u32 delta; > + s32 delta; > > if (params->ecn && INET_ECN_set_ce(skb)) { > stats->ecn_mark++; > @@ -317,28 +317,32 @@ static struct sk_buff *codel_dequeue(struct Qdisc *= sch, > drop =3D codel_should_drop(skb, sch, vars, params= , > stats, now); > } > - vars->dropping =3D true; > + vars->dropping =3D drop; bugfix was here > /* if min went above target close to when we last went be= low it > * assume that the drop rate that controlled the queue on= the > * last cycle is a good starting point to control it now. > */ > - delta =3D vars->count - vars->lastcount; > - if (delta > 1 && > - 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 quadraticall= y. > + if (drop) { /* we can exit dropping state above */ part 2 of that bugfix > + delta =3D vars->count - 3; > + if(codel_time_before(now - vars->drop_next, > + 8 * params->interval)) { > + vars->count =3D delta > 0 ? (u32) delta := 1; > + /* we don't care if rec_inv_sqrt approximation > + * in reverse is not very precise : > + * 2 Newton steps will correct it quadratically. > */ > - codel_Newton_step(vars); > - } else { > - vars->count =3D 1; > - vars->rec_inv_sqrt =3D ~0U >> REC_INV_SQRT_SHIFT; > + codel_Newton_step(vars); > + codel_Newton_step(vars); > + } else { > + vars->count =3D 1; > + vars->rec_inv_sqrt =3D ~0U >> REC_INV_SQR= T_SHIFT; > + codel_Newton_step(vars); > + } > + vars->lastcount =3D vars->count; > + vars->drop_next =3D codel_control_law(vars->drop_= next, > + params->inter= val, > + vars->rec_inv= _sqrt); Actually this doesn't do what I want, I think. What I wanted was to restart dropping at slightly less than the same rate over roughly the same interval since the last drop... but we are if (8 * interval) here, I guess it makes more sense to go with now... [me scratches head] > } > - vars->lastcount =3D vars->count; > - vars->drop_next =3D codel_control_law(now, params->interv= al, > - vars->rec_inv_sqrt); > } > end: > return skb; > -- > 1.7.9.5 > > _______________________________________________ > Codel mailing list > Codel@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/codel --=20 Dave T=E4ht http://www.bufferbloat.net/projects/cerowrt/wiki - "3.3.8-17 is out with fq_codel!"