[Codel] [RFC PATCH] codel: tighten responsiveness and more reliably deal with loads

[Dave Täht]

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

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