From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by huchra.bufferbloat.net (Postfix, from userid 1000) id 92B87200AA1; Sun, 26 Aug 2012 12:06:10 -0700 (PDT) From: =?UTF-8?q?Dave=20T=C3=A4ht?= To: codel@lists.bufferbloat.net Date: Sun, 26 Aug 2012 12:02:53 -0700 Message-Id: <1346007773-26679-2-git-send-email-dave.taht@bufferbloat.net> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1346007773-26679-1-git-send-email-dave.taht@bufferbloat.net> References: <1346007773-26679-1-git-send-email-dave.taht@bufferbloat.net> Cc: Dave Taht Subject: [Codel] [RFC PATCH] codel: tighten responsiveness and more reliably deal with loads 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: Sun, 26 Aug 2012 19:06:10 -0000 From: Dave Taht This updates the codel algorithm to more closely match the current experimental ns2 code. Not presently recomended for mainline. 1) It shortens the search for the minimum by reducing the window over the intervals and re-running the control law to better schedule the estimate. 2) Holds onto the drop schedule harder when re-entering drop state. 3) Corrects for newton method running in reverse. --- include/net/codel.h | 39 +++++++++++++++++++++++---------------- 1 file changed, 23 insertions(+), 16 deletions(-) diff --git a/include/net/codel.h b/include/net/codel.h index 389cf62..57031ad 100644 --- a/include/net/codel.h +++ b/include/net/codel.h @@ -233,9 +233,15 @@ static bool codel_should_drop(const struct sk_buff *skb, ok_to_drop = false; if (vars->first_above_time == 0) { /* just went above from below. If we stay above - * for at least interval we'll say it's ok to drop + * for at least current control law we'll say it's ok to drop */ - vars->first_above_time = now + params->interval; + if(vars->count > 1 && codel_time_before(now - vars->drop_next, + 8 * params->interval)) { + vars->first_above_time = codel_control_law( + now, params->interval, vars->rec_inv_sqrt); + } else { + vars->first_above_time = now + params->interval; + } } else if (codel_time_after(now, vars->first_above_time)) { ok_to_drop = true; } @@ -276,7 +282,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch, */ while (vars->dropping && codel_time_after_eq(now, vars->drop_next)) { - vars->count++; /* dont care of possible wrap + vars->count++; /* don't care about wrap * since there is no more divide */ codel_Newton_step(vars); @@ -305,7 +311,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch, } } } else if (drop) { - u32 delta; + s32 delta; if (params->ecn && INET_ECN_set_ce(skb)) { stats->ecn_mark++; @@ -322,22 +328,23 @@ 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. */ - delta = vars->count - vars->lastcount; - if (delta > 1 && - 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. - */ - codel_Newton_step(vars); + if(codel_time_before(now - vars->drop_next, + 8 * params->interval)) { + delta = vars->count - 2; + vars->count = delta > 0 ? (u32) delta : 1; } else { vars->count = 1; vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT; - } + } + /* 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); + codel_Newton_step(vars); vars->lastcount = vars->count; - vars->drop_next = codel_control_law(now, params->interval, + vars->drop_next = codel_control_law(now, + params->interval, vars->rec_inv_sqrt); } end: -- 1.7.9.5