[Codel] experimental codel patch

[Codel] experimental codel patch

[Dave Täht]

While this patch does improve matters over what currently exists,
(at least in the cases I've tested)

Van & Kathie want to have the real solution which is a control law 
that can adapt to being in a sort of steady state.

So please consider this highly experimental and think upon ways
to improve the behavior further.

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

[Dave Täht]

From: Dave Taht <dave.taht@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

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

[Eric Dumazet]

On Sun, 2012-08-26 at 12:02 -0700, Dave Täht wrote:
> From: Dave Taht <dave.taht@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

> +		codel_Newton_step(vars);
> +		codel_Newton_step(vars);

This makes no sense for several reasons :

1) If we do the 	vars->count = 1;
        vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;

Then there is no need of _any_ Newton steps.
The rec_inv_sqrt value is the good one.

2) If we change vars->count to vars->count - 2
  Then a single step is enough.


I can understand that with the current way :

   vars->count =  vars->count - vars->lastcount

then we can have a slight error, but this gave no difference in codel
experimental behavior.

I would say that codel response to bad queue is pretty easy (doing count
++ at each drop), but changes in count to adapt to oscillations between
good and bad queues is yet to be investigated.

Do we have to do 
0) current way (count - lastcount)
1) count = count - 1 
2) count = count - 2 
3) count = count * 88%
4) count = count * 75%
5) count  = count * 50%
6) count = count * 25%
7) count = some clever function using history of previous changes
...

In my prior tests, 1) and 2) were pretty bad, I am sure it is not the
right way.

(the count = 1 is only done when queue was idle for a long time)

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

[Dave Taht]

On Mon, Aug 27, 2012 at 5:17 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Sun, 2012-08-26 at 12:02 -0700, Dave Täht wrote:
>> From: Dave Taht <dave.taht@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
>
>> +             codel_Newton_step(vars);
>> +             codel_Newton_step(vars);
>
> This makes no sense for several reasons :
>
> 1) If we do the         vars->count = 1;
>         vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
>
> Then there is no need of _any_ Newton steps.
> The rec_inv_sqrt value is the good one.
>
> 2) If we change vars->count to vars->count - 2
>   Then a single step is enough.
>

The double newton step now is an artifact of when count could jump
from one large number to a smaller one. It didn't hurt, I didn't feel
like thinking about it, and I wanted to match the behavior of a real sqrt
and the model more exactly.

I thought really hard about ripping it out and going back to the invsqrt
code, too. I also fiddled with the clock...

>
> I can understand that with the current way :
>
>    vars->count =  vars->count - vars->lastcount
>
> then we can have a slight error, but this gave no difference in codel
> experimental behavior.

Actually the error could be quite large. (as in off by a factor of 2)

> I would say that codel response to bad queue is pretty easy (doing count
> ++ at each drop), but changes in count to adapt to oscillations between
> good and bad queues is yet to be investigated.
>
> Do we have to do
> 0) current way (count - lastcount)
> 1) count = count - 1
> 2) count = count - 2
> 3) count = count * 88%
> 4) count = count * 75%
> 5) count  = count * 50%
> 6) count = count * 25%
> 7) count = some clever function using history of previous changes
> ...
>
> In my prior tests, 1) and 2) were pretty bad, I am sure it is not the
> right way.

I was *utterly sure* it was not the right way, either, then

(after fiddling with various variants of the above for a month),

only then I implemented kathie's change to do the control_law inside
of ok_to_drop...

... and count-2 worked much better than I expected.

Please note that kathie and van aren't satisfied with this variant either,
but do try it...

> (the count = 1 is only done when queue was idle for a long time)

See the additional placement of the control law.

>
>
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel



-- 
Dave Täht
http://www.bufferbloat.net/projects/cerowrt/wiki - "3.3.8-17 is out
with fq_codel!"