[LARTC] CBQ and WRR

[LARTC] CBQ and WRR

[Rick Goh]

Is WRR built into CBQ?

I read in Advance Routing HOW TO and saw under the queuing disciplines that
WRR has to be patched before it could function. But then I read that the
"weight" in CBQ class is actually an implementation of WRR...

So??

The most probable thing is that the default WRR in kernel 2.2.17 which is
what i'm using already has an earlier version of WRR??

I'm confused. Can anyone clear my doubts? THanks.


Regards.



_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[Christian Worm Mortensen]

Hi,

> Is WRR built into CBQ?

You confuse qdiscs as described in the howto with strategies the qdiscs implement.

The WRR qdisc described in the howto implements Weighted Round Robin scheduling.

The CBQ qdisc implements CBQ scheduling. CBQ scheduling uses as one of its basic elements (at least in the Linux implementation) principles from Weighted Round Robin scheduling.

In this sence the CBQ qdisc is more advanced than the WRR qdisc. I have tried some time ago to use CBQ just to perform weighted round robin scheduling but I did not succedd. Maybe I just did it wrong because there was not really any documentation for the CBQ qdisc.

> The most probable thing is that the default WRR in kernel 2.2.17 which is
> what i'm using already has an earlier version of WRR??

The WRR qdisc mentioned in the howto has never been a part of the standard kernel.


Christian


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[jamal]

On Tue, 27 Mar 2001, Christian Worm Mortensen wrote:

> The WRR qdisc mentioned in the howto has never been a part of the standard kernel.

Linux CBQ actually _does_ implement a WRR variant known as DRR (Deficit
Round Robin). DRR is better than classical WRR. Read the Varghese paper
to see the difference.

In any case to the original poster: You can look at qdiscs as building
blocks with a well known interface and that are defined to provide a
certain specific 'service' to packets travessing them.
They could be schedulers like Prio or markers like dsmark or active queue
management schemes like GRED. Normally there is an associate queue with
a queing discipline although sometimes not directly owned by the qdisc
rather by other embedded qdiscs (eg prio with attached FIFO qdiscs).

cheers,
jamal


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[Christian Worm Mortensen]

Hi,

> > The WRR qdisc mentioned in the howto has never been a part of the standard kernel.
> 
> Linux CBQ actually _does_ implement a WRR variant known as DRR (Deficit
> Round Robin). DRR is better than classical WRR. Read the Varghese paper
> to see the difference.

Yes, but in the howto also a qdisc named WRR is mentioned.

A quick search on Google BTW said that DRR is only better in terms of speed of the implementation but is worse in terms distribution bandwidth.


Christian


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[jamal]

On Tue, 27 Mar 2001, Christian Worm Mortensen wrote:

>
> Yes, but in the howto also a qdisc named WRR is mentioned.

What HOWTO? Is this one of those schedulers that Martin wrote? Never
paid much attention; Maybe because i never thought that WRR was important
once we had DRR.

>
> A quick search on Google BTW said that DRR is only better in terms
> of speed of the implementation but is worse in terms distribution bandwidth.

WRR works well when you apriori know the packet/cell sizes (eg in ATM).
If you cant do this, then WRR is unfair once you start having a lot of
flows going or you mistweak your weights etc. DRR fixes this. The
improvements on computation comes in as a bonus _not_ as the advantage of
DRR over WRR.
Why dont you read the classical paper at:
http://www.acm.org/sigcomm/sigcomm95/papers/shreedhar.html

cheers,
jamal


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[Christian Worm Mortensen]

Hi,

> > Yes, but in the howto also a qdisc named WRR is mentioned.
> 
> What HOWTO?

This thread is on two mailing lists. One of the lists is for the howto located on http://ds9a.nl/2.4Routing/. This howto mentions the WRR qdisc (see http://wipl-wrr.dkik.dk/wrr/) which is a qdisc that is _not_ included in the standard kernel and has nothing to do with CBQ.

> WRR works well when you apriori know the packet/cell sizes (eg in ATM).
> If you cant do this, then WRR is unfair once you start having a lot of
> flows going or you mistweak your weights etc. DRR fixes this.

Hmm... Maybe you talk about how WRR/DRR is implemented in CBQ? A pure WRR scheduler works perfect no matter what size the packets have. If, of course, the scheduler takes packet sizes into account. What exactly is the problem with a WRR scheduler? 

Another thing: Unless you have a need to give special traffic very low delay I don't see any reason why you would want to use CBQ instead of pure WRR? I.e.: If you use CBQ with all prio parameters set to the same, why not use pure WRR instead?

> Why dont you read the classical paper at:
> http://www.acm.org/sigcomm/sigcomm95/papers/shreedhar.html

What I really need is a paper describing CBQ in Linux - the original article desribing CBQ is very generel. And when I experimented with CBQ the last time I did not see the behaviour I would exepect from the article assuming that the generel scehudler was a WRR scheduler.


Christian


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[jamal]

On Wed, 28 Mar 2001, Christian Worm Mortensen wrote:

> Hi,
>
> > > Yes, but in the howto also a qdisc named WRR is mentioned.
> >
> > What HOWTO?
>
> This thread is on two mailing lists. One of the lists is for the howto
> located on http://ds9a.nl/2.4Routing/. This howto mentions the WRR qdisc
> (see http://wipl-wrr.dkik.dk/wrr/) which is a qdisc that is _not_
> included in the standard kernel and has nothing to do with CBQ.
>

Ah, this is something Bert Hubert was trying to put together a few months
back. It seems to be going well (although it didnt seem like he changed
the ingress qdisc stuff like i suggested ;->)

> > WRR works well when you apriori know the packet/cell sizes (eg in ATM).
> > If you cant do this, then WRR is unfair once you start having a lot of
> > flows going or you mistweak your weights etc. DRR fixes this.
>
> Hmm... Maybe you talk about how WRR/DRR is implemented in CBQ?
> A pure WRR scheduler works perfect no matter what size the packets have.
> If, of course, the scheduler takes packet sizes into account.
> What exactly is the problem with a WRR scheduler?

There are other minor details (hence my suggestion to read the paper
because i cant remember details), but fixing the deficit such that you
take into consideration 'byte credit' a queue has when you preempt it
makes a WRR implementation closer to DRR. If you are already doing this
just read the paper and fill up the other minor details.
You might also wanna hook up with Martin aka 'devik' -- if i am not
mistaken he also wrote a DRR scheduler

>
> Another thing: Unless you have a need to give special traffic very low delay I don't see any reason why you would want to use CBQ instead of pure WRR? I.e.: If you use CBQ with all prio parameters set to the same, why not use pure WRR instead?
>
> > Why dont you read the classical paper at:
> > http://www.acm.org/sigcomm/sigcomm95/papers/shreedhar.html
>
> What I really need is a paper describing CBQ in Linux - the original
> article desribing CBQ is very generel. And when I experimented with CBQ
> the last time I did not see the behaviour I would exepect from the
> article assuming that the generel scehudler was a WRR scheduler.

The original CBQ implementation is the classical WRR; linux is DRR.
So the behavior might not be exactly the same; if the results
make intuitional sense then that should suffice. You might have been a
victim of bugs or mistuning of parameters.
Note there have been attempts to document Linux CBQ; search the mailing
list.

cheers,
jamal


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[Christian Worm Mortensen]

Hi,

> > Hmm... Maybe you talk about how WRR/DRR is implemented in CBQ?
> > A pure WRR scheduler works perfect no matter what size the packets have.
> > If, of course, the scheduler takes packet sizes into account.
> > What exactly is the problem with a WRR scheduler?
> 
> There are other minor details (hence my suggestion to read the paper
> because i cant remember details),

Maybe I will read it some day ;-)

> but fixing the deficit such that you
> take into consideration 'byte credit' a queue has when you preempt it
> makes a WRR implementation closer to DRR.

Well, the WRR qdisc essentially works this way:

* For each band (=class) there is a byte counter
* When a band transfers a packet the byte counter is increased by the packet size divided with the weight (which is a number between 0 and 1)
* The next band that can transfer a packet is always the one with the lowest byte counter.

It also does some additional things to make sure that when a new band has something to send it can send it immedialty. I don't see any way this scheme can be improved.

> > What I really need is a paper describing CBQ in Linux - the original
> > article desribing CBQ is very generel. And when I experimented with CBQ
> > the last time I did not see the behaviour I would exepect from the
> > article assuming that the generel scehudler was a WRR scheduler.
> 
> The original CBQ implementation is the classical WRR;

But it did not take the packet size into account?

> Note there have been attempts to document Linux CBQ; search the mailing
> list.

Hmm, interesseting, maybe I should subscribe to the linux-diffserv mailing list. 


Christian


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[jamal]

On Wed, 28 Mar 2001, Christian Worm Mortensen wrote:

> Maybe I will read it some day ;-)

I think you _Must_ (especially if you are implementing WRR). There are
some good ideas there

>
> > but fixing the deficit such that you
> > take into consideration 'byte credit' a queue has when you preempt it
> > makes a WRR implementation closer to DRR.
>
> Well, the WRR qdisc essentially works this way:
>
> * For each band (=class) there is a byte counter
> * When a band transfers a packet the byte counter is
>    increased by the packet size divided with the weight (which is a
>    number between 0 and 1)
> * The next band that can transfer a packet is always the one with the
>   lowest byte counter.
>
> It also does some additional things to make sure that when a new band
> has something to send it can send it immedialty. I don't see any way
> this scheme can be improved.
>

So is this decision on packet by packet?
I.e when do you decide that a 'band' should stop sending?
Are there opportunities that a 'band' could be starved?
Dont make me go read the Varghese paper again. You should ;->

> > The original CBQ implementation is the classical WRR;
>
> But it did not take the packet size into account?

It didnt.

cheers,
jamal


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/

Re: [LARTC] CBQ and WRR

[Christian Worm Mortensen]

Hi,

> > Maybe I will read it some day ;-)
> 
> I think you _Must_ (especially if you are implementing WRR). There are
> some good ideas there

Yes... I will.. 

> > Well, the WRR qdisc essentially works this way:
> >
> > * For each band (=class) there is a byte counter
> > * When a band transfers a packet the byte counter is
> >    increased by the packet size divided with the weight (which is a
> >    number between 0 and 1)
> > * The next band that can transfer a packet is always the one with the
> >   lowest byte counter.
> >
> > It also does some additional things to make sure that when a new band
> > has something to send it can send it immedialty. I don't see any way
> > this scheme can be improved.
> >
> 
> So is this decision on packet by packet?

Yes. The above is done for each packet.

> Are there opportunities that a 'band' could be starved?

No.

> Dont make me go read the Varghese paper again. You should ;->

Without having read the article what is stressed is that it is an O(1) implementaion while WRR as described above is O(lg n) in a simple implementation where n is the number of bands having something to send. It can be improved to O(lg lg w) where w is the word size or maybe to even to O(lg lg n). But I don't think it is worth it and it is not even sure that it would be faster in practice - depending on the size of n, of course.

> > > The original CBQ implementation is the classical WRR;
> >
> > But it did not take the packet size into account?
> 
> It didnt.

Ok... That might explain why I did not see what I expected.


Christian


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/2.4Routing/