From mboxrd@z Thu Jan 1 00:00:00 1970 From: Ed Wildgoose Date: Fri, 18 Jun 2004 12:50:17 +0000 Subject: Re: [LARTC] HTB is nor fair when 'borrowing? *bug* in HTB or some Message-Id: <40D2E509.4000405@wildgooses.com> List-Id: References: <40D21439.7000702@interia.pl> In-Reply-To: <40D21439.7000702@interia.pl> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: lartc@vger.kernel.org Ed Wildgoose wrote: > pljosh wrote: > >> Ed Wildgoose wrote: >> >>> Hmm, interesting. Can you switch the order of your IP mappings >>> around on this test so that you can prove that it is some feature of >>> HTB that user1 always gets more bandwidth, and no something about >>> that machine (ie if you swap ip's for user1 and 3 that it still >>> remains (the new) user1 who gets all the b/w? >>> >>> Obviously this should not be so, just curious to eliminate other >>> possibilities >>> >>> Ed W >> >> >> >> I did it already. When I set filter to direct 192.168.3.4 packets to >> 1:60 and 192.168.3.6 to 1:40 then lines on my graph switch: now blue >> is over red... >> The same switch happens when i set higher prio of 1:60... >> So it means than when two classes at the same level have same "prio" >> then class with lower minor id has higher priority than classes with >> lower minor id... So there is no possibility to set them to be equal >> when borrowing occurs. >> >> Now I am in trouble as I am writing my thesis and I wanted to show in >> my paper that HTB is excellent to share BW between users... what am I >> to write about this case? >> >> BTW: maybe someone could repeat my experiment? Maybe it is something >> wrong with my hadrware or some unbelievable coincidence? > > > > Have a read through the dequeue code. Perhaps you can spot a problem > - there are plenty of debug flags you can switch on > > If I had to guess, then I would suspect the following: When there is > spare bandwidth available, then there is some kind of round robin > scheduler which gives the spare stuff away by visiting each lower node > in ascending priority order. However, I suspect that the order is > deterministic and hence the first node with prio 1 effectively gets > visited more often than the next node with prio1 and so on (makes > sense from a computing implementation point of view - it's fast and > efficient, etc) > > It would also imply that the spare bandwidth is only allocated on a > per time slice point of view, ie there are no long term timers > checking that node 1 is not getting a little more than node 2 and > hence biasing the allocation to node 2. All that kind of code would > add overhead and is presumably therefore justified in not being there...? OK, have a look at "dequeue" and "htb_dequeue_tree". The algorithm is simply this: i = 0; while (some_spare_bw_available()) { queue = find_a_queue_with_given_prio_and_some_packets (i); if (queue) { Dequeue_one_packet(queue); } else { i++; } } So it finds a queue for a given priority, dequeues a packet and repeats until we have done eveything for that prio. What I can't quite see, but suspect, is that the "find_a_queue" function is supposed to rotate through each of the queues at a given prioriy each time, hence it *shouldn't* be biased towards any one queue... (see the "htb_lookup_leaf" function for details) Hope that helps... _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/