Re: [LARTC] CBQ and WRR

["Christian Worm Mortensen" <worm@dkik.dk>]

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/