[Codel] [PATCH] codel: Refine re-entering drop state to react sooner

[Dave Täht]

From: Dave Taht <dave.taht at bufferbloat.net>

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 state
   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 = count - (3 * 4), or an ewma based on ldelay.

4) Note that in heavy dropping states, count now increases slower, as well,
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 wrap
-						* since there is no more divide
-						*/
 				codel_Newton_step(vars);
 				if (params->ecn && INET_ECN_set_ce(skb)) {
 					stats->ecn_mark++;
@@ -305,7 +305,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++;
@@ -317,28 +317,32 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 			drop = codel_should_drop(skb, sch, vars, params,
 						 stats, now);
 		}
-		vars->dropping = true;
+		vars->dropping = drop;
 		/* if min went above target close to when we last went below it
 		 * 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.
+		if (drop) { /* we can exit dropping state above */
+			delta = vars->count - 3;
+			if(codel_time_before(now - vars->drop_next,
+				      8 * params->interval)) {
+				vars->count = 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 = 1;
-			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
+				codel_Newton_step(vars);
+				codel_Newton_step(vars);
+			} else {
+				vars->count = 1;
+				vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
+				codel_Newton_step(vars);
+			}
+			vars->lastcount = vars->count;
+			vars->drop_next = codel_control_law(vars->drop_next,
+							    params->interval,
+							    vars->rec_inv_sqrt);
 		}
-		vars->lastcount = vars->count;
-		vars->drop_next = codel_control_law(now, params->interval,
-						    vars->rec_inv_sqrt);
 	}
 end:
 	return skb;
-- 
1.7.9.5