Date:	Thu, 01 Dec 2011 16:48:11 -0500
From:	Jim Gettys <jg@...edesktop.org>
To:	Dave Taht <dave.taht@...il.com>
CC:	Eric Dumazet <eric.dumazet@...il.com>,
	Stephen Hemminger <shemminger@...tta.com>,
	Thomas Graf <tgraf@...radead.org>,
	netdev <netdev@...r.kernel.org>
Subject: Re: [PATCH] sch_red: fix red_change

On 12/01/2011 04:35 PM, Dave Taht wrote:
> On Thu, Dec 1, 2011 at 10:06 PM, Eric Dumazet <eric.dumazet@...il.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@...il.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@...r.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists