netdev - Re: [PATCH] sch_red: fix red

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAA93jw7wAL75pVrB-q+xGAcpQtiZz4iVW0Z2W9E8VGSyUFOo-w@mail.gmail.com>
Date:	Thu, 1 Dec 2011 22:35:31 +0100
From:	Dave Taht <dave.taht@...il.com>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	Stephen Hemminger <shemminger@...tta.com>,
	Thomas Graf <tgraf@...radead.org>,
	netdev <netdev@...r.kernel.org>, Jim Gettys <jg@...edesktop.org>
Subject: Re: [PATCH] sch_red: fix red_change

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. :)

> 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@...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

-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
FR Tel: 0638645374
http://www.bufferbloat.net
--
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