* [Codel] [PATCH] codel: Refine re-entering drop state to react sooner
@ 2012-08-23 8:37 Dave Täht
2012-08-23 8:37 ` [Codel] [PATCH 2/2] codel: reduce count after exiting dropping state after one maxpacket Dave Täht
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: Dave Täht @ 2012-08-23 8:37 UTC (permalink / raw)
To: codel; +Cc: Dave Taht
From: Dave Taht <dave.taht@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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Codel] [PATCH 2/2] codel: reduce count after exiting dropping state after one maxpacket
2012-08-23 8:37 [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Täht
@ 2012-08-23 8:37 ` Dave Täht
2012-08-23 14:22 ` [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Taht
2012-08-26 18:08 ` Dave Taht
2 siblings, 0 replies; 4+ messages in thread
From: Dave Täht @ 2012-08-23 8:37 UTC (permalink / raw)
To: codel; +Cc: Dave Taht
From: Dave Taht <dave.taht@bufferbloat.net>
At a knife's edge, where we are rapidly entering and existing
a dropping state, seek lower to find the optimimum.
---
include/net/codel.h | 3 +++
1 file changed, 3 insertions(+)
diff --git a/include/net/codel.h b/include/net/codel.h
index dbfccb7..5e85632 100644
--- a/include/net/codel.h
+++ b/include/net/codel.h
@@ -342,6 +342,9 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
vars->drop_next = codel_control_law(vars->drop_next,
params->interval,
vars->rec_inv_sqrt);
+ } else { /* we dropped out of the dropping state in 1 pkt */
+ vars->count = vars->count > 1 ? vars->count - 1 : 1;
+ codel_Newton_step(vars);
}
}
end:
--
1.7.9.5
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Codel] [PATCH] codel: Refine re-entering drop state to react sooner
2012-08-23 8:37 [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Täht
2012-08-23 8:37 ` [Codel] [PATCH 2/2] codel: reduce count after exiting dropping state after one maxpacket Dave Täht
@ 2012-08-23 14:22 ` Dave Taht
2012-08-26 18:08 ` Dave Taht
2 siblings, 0 replies; 4+ messages in thread
From: Dave Taht @ 2012-08-23 14:22 UTC (permalink / raw)
To: Dave Täht; +Cc: codel
re-re-reviewing this in the light of dawn...
On Thu, Aug 23, 2012 at 1:37 AM, Dave Täht <dave.taht@bufferbloat.net> wrote:
> From: Dave Taht <dave.taht@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);
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 *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;
bugfix was here
> /* 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 */
part 2 of that bugfix
> + 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);
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 = vars->count;
> - vars->drop_next = codel_control_law(now, params->interval,
> - vars->rec_inv_sqrt);
> }
> end:
> return skb;
> --
> 1.7.9.5
>
> _______________________________________________
> 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!"
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Codel] [PATCH] codel: Refine re-entering drop state to react sooner
2012-08-23 8:37 [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Täht
2012-08-23 8:37 ` [Codel] [PATCH 2/2] codel: reduce count after exiting dropping state after one maxpacket Dave Täht
2012-08-23 14:22 ` [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Taht
@ 2012-08-26 18:08 ` Dave Taht
2 siblings, 0 replies; 4+ messages in thread
From: Dave Taht @ 2012-08-26 18:08 UTC (permalink / raw)
To: Dave Täht; +Cc: codel, cerowrt-devel
I had an entertaining couple days wrapping my head around
the behavior of the ns2 model, running tons of experiments and putting
together multiple variants of codel and fq_codel. This patch was not
optimal in several ways and should be ignored.
(I should have marked it as an rfc anyway),
I have a new patch coming up that adheres closely to the ns2 model
that won... some notes follow:
On Thu, Aug 23, 2012 at 1:37 AM, Dave Täht <dave.taht@bufferbloat.net> wrote:
> From: Dave Taht <dave.taht@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
Seems to help.
> 2) Account for the idea of dropping out of drop state after a drop
> upon entering drop state.
Didn't work as well as I thought it would. It's an interesting piece
of information but...
>
> 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.
The ns2 notion of a steady count - 2 works well, with the ns2 change in the
ok_to_drop routine that re-runs the control law. I'd done the first in this
version of the patch, but not the latter. With both in the upcoming
patch, life got better. This latter change was key to seeing the bump
up in codel's utilization.
> 4) Note that in heavy dropping states, count now increases slower, as well,
> as it is moved outside of the while loop.
Moving it inside the while loop worked much better...
I did most of my testing at 100Mbit (line rate) and 1Mbit (htb), with
8 bidirectional streams to two devices (from a 3rd), and a competing
ping.
(same (short) RTTs)
Testing at higher rates and with tons more streams and a variety of
RTTs would be useful.
> Some of this is borrowed from ideas in the ns2 code.
The code I have is now identical to the current ns2 code, with
the exception of this bit in s3
// kmn decay tests
if(count_ > 126) count_ = 0.9844 * (count_ + 2);
In fq_codel's case, it's really rare count gets this large, except
under a udp flood (where the basic assumption of codel vs tcp doesn't
hold anyway)
Codel can get up there...
In the process of testing I gradually switched the test server box to
running 3.6-rc{1,2,3}, and now kind of need to re-run everything.
But in the upcoming patch:
Bidirectional utilization is nearly perfect. ~182.X consistently for
anything with fq in it. Even pfifo_fast (when coupled with fq on the
other side) in the same ballpark most of the time.
std deviation for 8 streams for fq_codel wins over everything else
Codel'd ECN and non-ecn streams now perform ~identically. Codel
improved from 153/163 Mbit in one test type to ~172/172 - to what
extent this is the CE fix, TSQ, other changes in 3.6-rc3, or what I
just did, don't know, working on it.
TCP small queues is pretty amazing. I need to backport it to 3.3.8
(only one (puzzling) line of the patch doesn't apply), as I can no
longer "trust" the test server box to misbehave on TCP with any qdisc
and now have to toss more boxes inline on the wire to get interesting
results, and I figure it will do helpful things for netserver on the
routers... D**n it, eric...
--
Dave Täht
http://www.bufferbloat.net/projects/cerowrt/wiki - "3.3.8-17 is out
with fq_codel!"
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2012-08-26 18:08 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-08-23 8:37 [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Täht
2012-08-23 8:37 ` [Codel] [PATCH 2/2] codel: reduce count after exiting dropping state after one maxpacket Dave Täht
2012-08-23 14:22 ` [Codel] [PATCH] codel: Refine re-entering drop state to react sooner Dave Taht
2012-08-26 18:08 ` Dave Taht
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox