[RFC iproute2] sch_red: TC_RED_HARDDROP

[RFC iproute2] sch_red: TC_RED_HARDDROP

[Eric Dumazet]

Hi Thomas

In 2005, TC_RED_HARDDROP kernel support was added to RED and GRED
(commit bdc450a0bb1 [PKT_SCHED]: (G)RED: Introduce hard dropping), but
current iproute2 doesnt have user land support.

Is there some patch waiting somewhere, or should we :

- Remove kernel support, since nobody uses it.

- Add iproute2 support.

Thanks

Re: [RFC iproute2] sch_red: TC_RED_HARDDROP

[Stephen Hemminger]

On Wed, 30 Nov 2011 21:25:49 +0100
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> Hi Thomas
> 
> In 2005, TC_RED_HARDDROP kernel support was added to RED and GRED
> (commit bdc450a0bb1 [PKT_SCHED]: (G)RED: Introduce hard dropping), but
> current iproute2 doesnt have user land support.
> 
> Is there some patch waiting somewhere, or should we :
> 
> - Remove kernel support, since nobody uses it.
> 
> - Add iproute2 support.

(Almost) nobody uses RED because they can't figure it out.
According to Wikipedia, VJ says that: 
 "there are not one, but two bugs in classic RED."


But if flag is present, then Thomas should have sent a patch, might have
been lost, that was pre-patchwork days.

[PATCH] sch_red: fix red_change

[Eric Dumazet]

Le mercredi 30 novembre 2011 à 14:36 -0800, Stephen Hemminger a écrit :

> (Almost) nobody uses RED because they can't figure it out.
> According to Wikipedia, VJ says that: 
>  "there are not one, but two bugs in classic RED."

RED is useful for high throughput routers, I doubt many linux machines
act as such devices.

I was considering adding Adaptative RED (Sally Floyd, Ramakrishna
Gummadi, Scott Shender), August 2001 

In this version, maxp is dynamic (from 1% to 50%), and user only have to
setup min_th (target average queue size)
(max_th and wq (burst in linux RED) are automatically setup)


By the way it seems we have a small bug in red_change()

if (skb_queue_empty(&sch->q))
	red_end_of_idle_period(&q->parms);

First, if queue is empty, we should call
red_start_of_idle_period(&q->parms);

Second, since we dont use anymore sch->q, but q->qdisc, the test is
meaningless.

Oh well...

[PATCH] sch_red: fix red_change()

Now RED is classful, we must check q->qdisc->q.qlen, and if queue is empty,
we start an idle period, not end it.

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c
index 6649463..d617161 100644
--- a/net/sched/sch_red.c
+++ b/net/sched/sch_red.c
@@ -209,8 +209,8 @@ static int red_change(struct Qdisc *sch, struct nlattr *opt)
 				 ctl->Plog, ctl->Scell_log,
 				 nla_data(tb[TCA_RED_STAB]));
 
-	if (skb_queue_empty(&sch->q))
-		red_end_of_idle_period(&q->parms);
+	if (!q->qdisc->q.qlen)
+		red_start_of_idle_period(&q->parms);
 
 	sch_tree_unlock(sch);
 	return 0;

Re: [PATCH] sch_red: fix red_change

[Dave Taht]

On Thu, Dec 1, 2011 at 10:06 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le mercredi 30 novembre 2011 à 14:36 -0800, Stephen Hemminger a écrit :
>
>> (Almost) nobody uses RED because they can't figure it out.
>> According to Wikipedia, VJ says that:
>>  "there are not one, but two bugs in classic RED."

Heh. "There were not two, but four bugs in Linux red".

Now reduced to 2. :)

> RED is useful for high throughput routers, I doubt many linux machines
> act as such devices.

"High throughput" at the time red was designed was not much faster
than a T1 line.

RED appears to be used by default in both gargoyle's and openwrt's QoS systems,
underneath unholy combinations of HTB, HSFC, and SFQ
so it's more widely used than you might think. Not that works well.

RED doesn't work worth beans on variable bandwidth links (cable
modems/wireless).

Once you are simulating a fixed rate link (e.g with HTB), then it sort of
kinda maybe can apply.

RED was also designed at a time when long distance traffic was fixed rate
and bidirectional, so the 'average packet' parameter made sense.
Modern day traffic is far more asymmetric.

RED might still be fairly effective on a modern day fixed rate line,
such as DSL,
and on DSLAMS and the like.

Linux's red has an additional problem in that it seems byte oriented
rather than packet
oriented, and most folk even trying to do simulations with red seem to be
choosing packet oriented - which ties into the asymmetric problem noted above
mildly better.

All that said, it's time came, and is rapidly ending.

I do look forward to a replacement for the algorithm one day soon.

> I was considering adding Adaptative RED (Sally Floyd, Ramakrishna
> Gummadi, Scott Shender), August 2001
>
> In this version, maxp is dynamic (from 1% to 50%), and user only have to
> setup min_th (target average queue size)
> (max_th and wq (burst in linux RED) are automatically setup)

I currently have no opinion. There are hundreds of papers on red
and red-like algorithms. cc'ing jim for an opinion. Will read paper.

I'd like to find something that dealt with superpackets sanely.

>
> By the way it seems we have a small bug in red_change()
>
> if (skb_queue_empty(&sch->q))
>        red_end_of_idle_period(&q->parms);
>
> First, if queue is empty, we should call
> red_start_of_idle_period(&q->parms);
>
> Second, since we dont use anymore sch->q, but q->qdisc, the test is
> meaningless.
>
> Oh well...
>
> [PATCH] sch_red: fix red_change()
>
> Now RED is classful, we must check q->qdisc->q.qlen, and if queue is empty,
> we start an idle period, not end it.
>
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
> ---
> diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c
> index 6649463..d617161 100644
> --- a/net/sched/sch_red.c
> +++ b/net/sched/sch_red.c
> @@ -209,8 +209,8 @@ static int red_change(struct Qdisc *sch, struct nlattr *opt)
>                                 ctl->Plog, ctl->Scell_log,
>                                 nla_data(tb[TCA_RED_STAB]));
>
> -       if (skb_queue_empty(&sch->q))
> -               red_end_of_idle_period(&q->parms);
> +       if (!q->qdisc->q.qlen)
> +               red_start_of_idle_period(&q->parms);
>
>        sch_tree_unlock(sch);
>        return 0;
>
>
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
FR Tel: 0638645374
http://www.bufferbloat.net

Re: [PATCH] sch_red: fix red_change

[Jim Gettys]

On 12/01/2011 04:35 PM, Dave Taht wrote:
> On Thu, Dec 1, 2011 at 10:06 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>> Le mercredi 30 novembre 2011 à 14:36 -0800, Stephen Hemminger a écrit :
>>
>>> (Almost) nobody uses RED because they can't figure it out.
>>> According to Wikipedia, VJ says that:
>>>  "there are not one, but two bugs in classic RED."
> Heh. "There were not two, but four bugs in Linux red".
>
> Now reduced to 2. :)

That's good.  There may be enough use to be worth fixing...  RED itself
is buggy in a couple ways, including it's fundamental idea of keying off
the queue length.

>
>> RED is useful for high throughput routers, I doubt many linux machines
>> act as such devices.
> "High throughput" at the time red was designed was not much faster
> than a T1 line.
>
> RED appears to be used by default in both gargoyle's and openwrt's QoS systems,
> underneath unholy combinations of HTB, HSFC, and SFQ
> so it's more widely used than you might think. Not that works well.
>
> RED doesn't work worth beans on variable bandwidth links (cable
> modems/wireless).
>
> Once you are simulating a fixed rate link (e.g with HTB), then it sort of
> kinda maybe can apply.
>
> RED was also designed at a time when long distance traffic was fixed rate
> and bidirectional, so the 'average packet' parameter made sense.
> Modern day traffic is far more asymmetric.

Not to mention is that RED is fundamentally flawed: there is almost no
information in the instantaneous length of the queue.   You can see how
variable bandwidth screws this idea to the wall, can't you?

So the closer to the edge you get (where BDP variation in flows will
dominate), the worse classic RED can possibly work.  In the home, you
are at the extreme, along with variable bandwidth now with Powerboost
and wireless.


>
> RED might still be fairly effective on a modern day fixed rate line,
> such as DSL,
> and on DSLAMS and the like.

Might is the operative word; the resurrection of using N TCP connections
in the web, and the ICW change to 10 makes me highly skeptical.

>
> Linux's red has an additional problem in that it seems byte oriented
> rather than packet
> oriented, and most folk even trying to do simulations with red seem to be
> choosing packet oriented - which ties into the asymmetric problem noted above
> mildly better.
>
> All that said, it's time came, and is rapidly ending.
>
> I do look forward to a replacement for the algorithm one day soon.

Kathie and Van have been simulating their new algorithm;  hopeful
results, but still too soon to tell as not enough situations have been
simulated.  And they need to talk to Eben Moglen yet about ensuring
proper publication so that no one can patent it out from under them. 
They want no barriers to widespread adoption in free software (and
anywhere else).

I get the sense that maybe there might be something to try in a couple
months; probably first best to do it on ethernet rather than wireless.
                        - Jim


>
>> I was considering adding Adaptative RED (Sally Floyd, Ramakrishna
>> Gummadi, Scott Shender), August 2001
>>
>> In this version, maxp is dynamic (from 1% to 50%), and user only have to
>> setup min_th (target average queue size)
>> (max_th and wq (burst in linux RED) are automatically setup)
> I currently have no opinion. There are hundreds of papers on red
> and red-like algorithms. cc'ing jim for an opinion. Will read paper.
>
> I'd like to find something that dealt with superpackets sanely.
>
>> By the way it seems we have a small bug in red_change()
>>
>> if (skb_queue_empty(&sch->q))
>>        red_end_of_idle_period(&q->parms);
>>
>> First, if queue is empty, we should call
>> red_start_of_idle_period(&q->parms);
>>
>> Second, since we dont use anymore sch->q, but q->qdisc, the test is
>> meaningless.
>>
>> Oh well...
>>
>> [PATCH] sch_red: fix red_change()
>>
>> Now RED is classful, we must check q->qdisc->q.qlen, and if queue is empty,
>> we start an idle period, not end it.
>>
>> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
>> ---
>> diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c
>> index 6649463..d617161 100644
>> --- a/net/sched/sch_red.c
>> +++ b/net/sched/sch_red.c
>> @@ -209,8 +209,8 @@ static int red_change(struct Qdisc *sch, struct nlattr *opt)
>>                                 ctl->Plog, ctl->Scell_log,
>>                                 nla_data(tb[TCA_RED_STAB]));
>>
>> -       if (skb_queue_empty(&sch->q))
>> -               red_end_of_idle_period(&q->parms);
>> +       if (!q->qdisc->q.qlen)
>> +               red_start_of_idle_period(&q->parms);
>>
>>        sch_tree_unlock(sch);
>>        return 0;
>>
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe netdev" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>

Re: [PATCH] sch_red: fix red_change

[Eric Dumazet]

Le jeudi 01 décembre 2011 à 22:35 +0100, Dave Taht a écrit :
> On Thu, Dec 1, 2011 at 10:06 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > Le mercredi 30 novembre 2011 à 14:36 -0800, Stephen Hemminger a écrit :
> >
> >> (Almost) nobody uses RED because they can't figure it out.
> >> According to Wikipedia, VJ says that:
> >>  "there are not one, but two bugs in classic RED."
> 
> Heh. "There were not two, but four bugs in Linux red".
> 
> Now reduced to 2. :)
> 

This story about VJ and bugs in classic RED is urban legend if you ask
me :)



> RED is useful for high throughput routers, I doubt many linux machines
> > act as such devices.
> 
> "High throughput" at the time red was designed was not much faster
> than a T1 line.
> 
> RED appears to be used by default in both gargoyle's and openwrt's QoS systems,
> underneath unholy combinations of HTB, HSFC, and SFQ
> so it's more widely used than you might think. Not that works well.
> 
> RED doesn't work worth beans on variable bandwidth links (cable
> modems/wireless).
> 

Adaptative RED is the answer

> Once you are simulating a fixed rate link (e.g with HTB), then it sort of
> kinda maybe can apply.
> 
> RED was also designed at a time when long distance traffic was fixed rate
> and bidirectional, so the 'average packet' parameter made sense.
> Modern day traffic is far more asymmetric.
> 

The truth is : For RED be effective (with say 20 to 100 flows), you need
a reasonable amount of packets in queue, and low wq (high burst value in
linux), depending on the RTT. And on consumer links (ADSL, cable
modem ...), RTT is quite big.

RED performance is best when the average queue size is estimated over a
small _multiple_ of round-trip times, not over a fraction of a single
round-trip time.

In this respect, your RED setups are pathological (minimum burst value,
meaning wq = 0.5 or so), so in a small fraction of RTT, avgqsz value is
completely changed, so flows have no chance to be able to react
smoothly.

Re: [PATCH] sch_red: fix red_change

[Jim Gettys]

On 12/01/2011 04:57 PM, Eric Dumazet wrote:
> Le jeudi 01 décembre 2011 à 22:35 +0100, Dave Taht a écrit :
>> On Thu, Dec 1, 2011 at 10:06 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>>> Le mercredi 30 novembre 2011 à 14:36 -0800, Stephen Hemminger a écrit :
>>>
>>>> (Almost) nobody uses RED because they can't figure it out.
>>>> According to Wikipedia, VJ says that:
>>>>  "there are not one, but two bugs in classic RED."
>> Heh. "There were not two, but four bugs in Linux red".
>>
>> Now reduced to 2. :)
>>
> This story about VJ and bugs in classic RED is urban legend if you ask
> me :)
>

Well, I've heard this directly from Van, first hand.  So you are now
second hand.

 And you can see much of what's wrong by tracking down "RED in a
different light", which he tried to get published to get people aware of it.
                - Jim

>
>> RED is useful for high throughput routers, I doubt many linux machines
>>> act as such devices.
>> "High throughput" at the time red was designed was not much faster
>> than a T1 line.
>>
>> RED appears to be used by default in both gargoyle's and openwrt's QoS systems,
>> underneath unholy combinations of HTB, HSFC, and SFQ
>> so it's more widely used than you might think. Not that works well.
>>
>> RED doesn't work worth beans on variable bandwidth links (cable
>> modems/wireless).
>>
> Adaptative RED is the answer
>
>> Once you are simulating a fixed rate link (e.g with HTB), then it sort of
>> kinda maybe can apply.
>>
>> RED was also designed at a time when long distance traffic was fixed rate
>> and bidirectional, so the 'average packet' parameter made sense.
>> Modern day traffic is far more asymmetric.
>>
> The truth is : For RED be effective (with say 20 to 100 flows), you need
> a reasonable amount of packets in queue, and low wq (high burst value in
> linux), depending on the RTT. And on consumer links (ADSL, cable
> modem ...), RTT is quite big.
>
> RED performance is best when the average queue size is estimated over a
> small _multiple_ of round-trip times, not over a fraction of a single
> round-trip time.
>
> In this respect, your RED setups are pathological (minimum burst value,
> meaning wq = 0.5 or so), so in a small fraction of RTT, avgqsz value is
> completely changed, so flows have no chance to be able to react
> smoothly.
>
>
>

Re: [PATCH] sch_red: fix red_change

[Ilpo Järvinen]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 4237 bytes --]

On Thu, 1 Dec 2011, Eric Dumazet wrote:
> Le jeudi 01 décembre 2011 à 22:35 +0100, Dave Taht a écrit :
> > On Thu, Dec 1, 2011 at 10:06 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > > Le mercredi 30 novembre 2011 à 14:36 -0800, Stephen Hemminger a écrit :
> > >
> > >> (Almost) nobody uses RED because they can't figure it out.
> > >> According to Wikipedia, VJ says that:
> > >>  "there are not one, but two bugs in classic RED."
> > 
> > Heh. "There were not two, but four bugs in Linux red".
> > 
> > Now reduced to 2. :)
> 
> This story about VJ and bugs in classic RED is urban legend if you ask
> me :)

I think at least one bug he claims to find in "the" manuscript is not a 
bug at all :-). Essentially he assumes that once instantaneous queue is 
zero, the load is zero, which is not true (e.g., during any typical slow 
start while the link is still not saturated).

> > RED is useful for high throughput routers, I doubt many linux machines
> > > act as such devices.
> > 
> > "High throughput" at the time red was designed was not much faster
> > than a T1 line.
> > 
> > RED appears to be used by default in both gargoyle's and openwrt's QoS systems,
> > underneath unholy combinations of HTB, HSFC, and SFQ
> > so it's more widely used than you might think. Not that works well.
> > 
> > RED doesn't work worth beans on variable bandwidth links (cable
> > modems/wireless).
> 
> Adaptative RED is the answer

I disagree. Slowly responding adaptation is not going to do much good if 
put together with variable something.

And besides, Adaptive RED is as hard if not even harder to configure than 
the standard RED. That is, it has one key parameter and absolutely no info 
is given how that should be configured?!? :-)

> > Once you are simulating a fixed rate link (e.g with HTB), then it sort of
> > kinda maybe can apply.
> > 
> > RED was also designed at a time when long distance traffic was fixed rate
> > and bidirectional, so the 'average packet' parameter made sense.
> > Modern day traffic is far more asymmetric.
> > 
> 
> The truth is : For RED be effective (with say 20 to 100 flows), you need
> a reasonable amount of packets in queue, and low wq (high burst value in
> linux), depending on the RTT. And on consumer links (ADSL, cable
> modem ...), RTT is quite big.

To be more exact, it's BDP (BW-delay product) which matters, not the RTT 
alone.

> RED performance is best when the average queue size is estimated over a
> small _multiple_ of round-trip times, not over a fraction of a single
> round-trip time.

I disagree. If there's any slow starting flow that alone can fill the 
bottleneck, anything significantly larger than RTT just harms. RED is 
just "too slow" if you follow the recommended parametrization..

In a core router you can probably get away with multiple RTTs, but near 
edge that is a grave mistake due to how slow-start behaves. With average 
based on many RTTs, RED still estimates that the link has low load while 
congestion has escalated to higher dimensions due to slow start. As a 
result, RED graciously falls back to tail-drop once the physical queue 
runs out and the flows respond allowing the load to decrease. However, 
finally RED reaches a state where it starts to "pro-actively" react to an 
"incipient congestion"?!? :-/ => Problem is made worse by those extra 
drops/marks happening too late.

...And the obvious looking solution by making physical buffer size 
larger brings in even worse problems. There's simply no other way around 
this than making wq larger instead of smaller in order to arrest the slow 
start in time. (We have a paper to appear about these in AINA 2012.)

I know this is pretty much against the mantra repeated about RED. And I'm 
not too surprised why so many have found out that RED does not help.

> In this respect, your RED setups are pathological (minimum burst value,
> meaning wq = 0.5 or so), so in a small fraction of RTT, avgqsz value is
> completely changed, so flows have no chance to be able to react
> smoothly.

Here I agree, 0.5 is probably too much though... only if BDP is very small 
this is useful but then RED is probably having other problems due to 
granularities affecting its measurement accuracy.


-- 
 i.

Re: [PATCH] sch_red: fix red_change

[Hagen Paul Pfeifer]

* Ilpo Järvinen | 2011-12-05 13:42:44 [+0200]:

>I disagree. If there's any slow starting flow that alone can fill the 
>bottleneck, anything significantly larger than RTT just harms. RED is 
>just "too slow" if you follow the recommended parametrization..
>
>In a core router you can probably get away with multiple RTTs, but near 
>edge that is a grave mistake due to how slow-start behaves. With average 
>based on many RTTs, RED still estimates that the link has low load while 
>congestion has escalated to higher dimensions due to slow start. As a 
>result, RED graciously falls back to tail-drop once the physical queue 
>runs out and the flows respond allowing the load to decrease. However, 
>finally RED reaches a state where it starts to "pro-actively" react to an 
>"incipient congestion"?!? :-/ => Problem is made worse by those extra 
>drops/marks happening too late.

But then one question Ilpo: drive IW10 or IW14 the behavior even worse?
Especially if n connections start almost simultanously? You did some analysis
on this topic.


HGN

Re: [PATCH] sch_red: fix red_change

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Thu, 01 Dec 2011 22:06:34 +0100

> [PATCH] sch_red: fix red_change()
> 
> Now RED is classful, we must check q->qdisc->q.qlen, and if queue is empty,
> we start an idle period, not end it.
> 
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>

Applied and queued up for -stable, thanks Eric.

Re: [RFC iproute2] sch_red: TC_RED_HARDDROP

[Thomas Graf]

On Wed, Nov 30, 2011 at 09:25:49PM +0100, Eric Dumazet wrote:
> In 2005, TC_RED_HARDDROP kernel support was added to RED and GRED
> (commit bdc450a0bb1 [PKT_SCHED]: (G)RED: Introduce hard dropping), but
> current iproute2 doesnt have user land support.
> 
> Is there some patch waiting somewhere, or should we :
> 
> - Remove kernel support, since nobody uses it.
> 
> - Add iproute2 support.

I used it in a project which configured the GRED qdisc directly from
the application.

I thought I added iproute2 support back then but obviously must have
missed it or the patch got lost. I'll send a patch to Stephen.