From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Christian Worm Mortensen" Date: Wed, 28 Mar 2001 14:22:26 +0000 Subject: Re: [LARTC] CBQ and WRR Message-Id: List-Id: References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: lartc@vger.kernel.org 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/