LARTC - Jun 2004 - HTB is nor fair when ''borrowing? Can someone correct me or maybe Devik''s HTB has a bug?

Hello there!
Yesterday I started my experiments with HTB.
I configured it this way:
1: root HTB qdisc
      |
1:1 HTB class  rate 1000kbit
      |
  /-------+------\
1:40   1:50   1:60
user1  user2  user3

rate 333 & ceil 1000 for everyone.

User2 is disconnected and user1 and user3 are downloading.
For all the time (t1-t5) there are ONLY these two users downloading!

HTB should give fifty-fifty to U1 and U3... but it is not...
What is happening is that HTB gives about 350-380kbit for user3 and 
everything else(more than 600kbit) for user1... this period is marked as 
"t1" on my graph...

Tahe a look at this:
http://www.icpnet.pl/~eniu/mgr/10170_600.png
(Y-axis shows bytes/s)

During my research I found that the more classes i create (each with 
rate=1000/no_of_users and ceil=1000) the more precise HTB is... When you 
look at my graph - in "t1" there were 3 classes (1:40, 1:50, 1:60).
Then
I was relaunching my script with higher amount of classes - in "t2" 
there were 4 classes:rate=250/ceil=1000 in "t3" I prepared 5 classes
and
finally in "t4" there were 6 or 7 classes.

But even in "t4" htb is not 100% fair (but it is acceptable).
In "t5" i created only two classes 1:40 and 1:60 - and then HTB is 
perfect! It is so precise you can see only one line - blue as the red 
one is behind it...

For me it looks like HTB is very good when it doesnt have to borrow from 
other classes for more than one class. When two classes are fighting for 
BW abowe "rate" then HTB is not fair...

BUT MAYBE I configured something not the way it should be and this is 
why I have what you can see...??

-josh

p.s.
I''ve uploaded the contents of my script''s output for each of
the periods
so you can see how it was configured at each time.
The script itself is also available.
I am running debian sarge with 2.4.26.
User1 has 192.168.3.4
User2 has 192.168.3.6

http://www.icpnet.pl/~eniu/mgr/t1
http://www.icpnet.pl/~eniu/mgr/t2
http://www.icpnet.pl/~eniu/mgr/t3
http://www.icpnet.pl/~eniu/mgr/t4
http://www.icpnet.pl/~eniu/mgr/t5

http://www.icpnet.pl/~eniu/mgr/rc.shape

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

>
> HTB should give fifty-fifty to U1 and U3... but it is not...
> What is happening is that HTB gives about 350-380kbit for user3 and 
> everything else(more than 600kbit) for user1... this period is marked 
> as "t1" on my graph...

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
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

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?

-josh


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

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

This would be my hunch, but there is plenty of info on the HTB site on 
the theory, and I should think it worth checking the dequeue code with 
some debug statements to prove this (or not).  Fixing it looks a little 
harder though...

Ed W
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.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/

Użytkownik Ed Wildgoose napisał:
> (see the "htb_lookup_leaf" function for details)
> Hope that helps...
Hmm... My greatest C program was the most simple snmp client you can 
ever imagine - and I was writing it for 2 weeks to finish my classes... 
So I think it is not good idea for me to patch (or even to take a look 
at) HTB code :)
-josh

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

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?
I just tested with my script and also see a 5-8% advantage for the lower 
  handle class.

I wouldn''t call it a bug though - HTB is written for high traffic
setups
   and trade off needs to be made between perfect behaviour and CPU 
usage and you say it gets better with more classes.

Andy.


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

> I just tested with my script and also see a 5-8% advantage for the lower 
>  handle class.
> 
> I wouldn''t call it a bug though - HTB is written for high traffic
setups
>   and trade off needs to be made between perfect behaviour and CPU usage 
> and you say it gets better with more classes.
> 
> Andy.
Well - you had 5-8% while I noticed 50-80% difference! (user1 ~76kB/s 
and user3 ~45kB/s).
Of course - as you can see on the graph I created: with more classes 
difference beteween u1&u3 is smaller...

Can you send me the script you used for your test which gave you only 
5-8%? Maybe there is something wrong with the one of mine?

-josh


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

pljosh wrote:
>> I just tested with my script and also see a 5-8% advantage for the 
>> lower  handle class.
>>
>> I wouldn''t call it a bug though - HTB is written for high
traffic
>> setups   and trade off needs to be made between perfect behaviour and 
>> CPU usage and you say it gets better with more classes.
>>
>> Andy.
> 
> 
> Well - you had 5-8% while I noticed 50-80% difference! (user1 ~76kB/s 
> and user3 ~45kB/s).
I did notice on the graph I looked at, that it was a bit higher - I only 
tested with wget. I was going to repeat properly and if you were still 
higher suggest that you set quantums to mtu, low bursts and set

HTB_HYSTERESIS 0 in net/sched/sch_htb.c.

I also have esfq attached to classes

> Of course - as you can see on the graph I created: with more classes 
> difference beteween u1&u3 is smaller...
Hmm I only have 2+default shared by IP - but two more "above".
> 
> Can you send me the script you used for your test which gave you only 
> 5-8%? Maybe there is something wrong with the one of mine?
OK but it won''t work for you - I guess. It needs connbytes a hacked IMQ
and esfq. It''s just a test evolved from digriz script really.

I also have half your bandwidth - and it was set at 400kbit for the test.

Andy.

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

Andy Furniss wrote:
> I also have half your bandwidth - and it was set at 400kbit for the test.
I meant to say aswell, that if you are doing the tests on downloads you 
need to throttle to about 80% of your rate, so you can build up queues 
and have a bit of spare for latency.

Andy.


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

> 
> HTB_HYSTERESIS 0 in net/sched/sch_htb.c.
> 
I did it, recompiled, launched... and i looks like it is even a little 
bit worser: user1 has almost twice as much BW as user3...
I DO NOT GET IT
IT LOOKS LIKE HTB WORKS FOR EVERYONE EXCEPT ME :(

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

> I meant to say aswell, that if you are doing the tests on downloads you 
> need to throttle to about 80% of your rate, so you can build up queues 
> and have a bit of spare for latency.
This 80% rule doesnt affect me as I am doing this on my local 100mbit 
network. I mean all the traffic is local - inside one phisical network.
[.1.1/24]--100mbit---[/eth0/-.1.70-.3.1-/eth1/]--100mbit--[.3.4]&[.3.6]

HTB is shaping at eth1 at 999kbps on a 100mbit network link.
.3.4 and .3.6 are downloading from .1.1 through linux router (eth0@.1.70 
and eth1@.3.1).


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

pljosh wrote:
> 
>>
>> HTB_HYSTERESIS 0 in net/sched/sch_htb.c.
>>
> 
> I did it, recompiled, launched... and i looks like it is even a little 
> bit worser: user1 has almost twice as much BW as user3...
> I DO NOT GET IT
> IT LOOKS LIKE HTB WORKS FOR EVERYONE EXCEPT ME :(
> 
> 
I tried with your rc.shape script on my LAN using scp. I couldn''t get 
the bash to work - it looks to me like it will only set one user. But I 
hardcoded my settings in it and checked with tc -s class ls dev eth0 
that my 2 classes existed.

I SCPd a file from gateway to 2 PCs and thay were shaped OK and came in 
second perfect. It was the same for 500,1000 and 5000 ceils. The 500 
test took 15 mins.

So I don''t really know whats going on for you.


Andy.




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

Użytkownik Andy Furniss napisał:
> I tried with your rc.shape script on my LAN using scp. I couldn''t
get
> the bash to work - it looks to me like it will only set one user. But I 
Did you launch it passing argument in "" or ''''?
./rc.shape "4 5 6"
is quite far different than
./rc.shape 4 5 6
> hardcoded my settings in it and checked with tc -s class ls dev eth0 
> that my 2 classes existed.
I dont get it: you prepared two classes for two PCs which is equivalent 
to "t5" on my graph which shows that HTB acts PERFECT in such
conditions.
> I SCPd a file from gateway to 2 PCs and thay were shaped OK and came in 
> second perfect. It was the same for 500,1000 and 5000 ceils. The 500 
> test took 15 mins.
> So I don''t really know whats going on for you.
> Andy.
Try the same using 3 classes and stress it with 2 PCs only (each class 
has rate=1/3 of max bw and ceil=max bw. You will se that first class 
will get from HTB almost TWICE as much as secound one one!

-josh

p.s.
I made same test on other network with other PCs and different kernel 
version and it was the same...

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

pljosh wrote:
> Użytkownik Andy Furniss napisał:
> 
>> I tried with your rc.shape script on my LAN using scp. I
couldn''t get
>> the bash to work - it looks to me like it will only set one user. But I
> 
> 
> Did you launch it passing argument in "" or ''''?
> ./rc.shape "4 5 6"
> is quite far different than
> ./rc.shape 4 5 6
> 
>> hardcoded my settings in it and checked with tc -s class ls dev eth0 
>> that my 2 classes existed.
> 
> 
> I dont get it: you prepared two classes for two PCs which is equivalent 
> to "t5" on my graph which shows that HTB acts PERFECT in such
conditions.
Oops I was thinking less classes were worse - I should have reread the 
post. I''ll try later with more.

Andy.

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

> p.s.
> I made same test on other network with other PCs and different kernel 
> version and it was the same...

Have you got something recent?  Try a 2.6.5 or newer kernel perhaps - 
this has 1000Hz scheduling (I think) and presumably the latest HTB 
patches.  I guess make sure your tc is up to date as well....

Of the wall, but you never know

Ed W

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

Andy Furniss wrote:
> pljosh wrote:
> 
>> Użytkownik Andy Furniss napisał:
>>
>>> I tried with your rc.shape script on my LAN using scp. I
couldn''t get
>>> the bash to work - it looks to me like it will only set one user.
But I
>>
>>
>>
>> Did you launch it passing argument in "" or
''''?
>> ./rc.shape "4 5 6"
>> is quite far different than
>> ./rc.shape 4 5 6
>>
>>> hardcoded my settings in it and checked with tc -s class ls dev
eth0
>>> that my 2 classes existed.
>>
>>
>>
>> I dont get it: you prepared two classes for two PCs which is 
>> equivalent to "t5" on my graph which shows that HTB acts
PERFECT in
>> such conditions.
> 
> 
> Oops I was thinking less classes were worse - I should have reread the 
> post. I''ll try later with more.
> 
I just tried with 2 d/l and 3 classes - I see the same as you now.

Andy.


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

Użytkownik Andy Furniss napisał:
> 
> I just tried with 2 d/l and 3 classes - I see the same as you now.
> 
> Andy.
I am happy that there is finally confirmation of what I''ve seen :)
But what now? I am just starting with traffic shaping and my question 
is: how is that - that so many people are using HTB for so long time and 
nobody noticed it is not fair?
I suppose with more complex configurtions which are propably more common 
  the fact that some part of HTB is not fair (borrowing I suppose) is 
blured and hard to notice some incorrect behavior.

Does Devik work on HTB yet. Maybe he could look at this problem closer? 
Should I notice him about that? What do you think?

-josh



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

pljosh wrote:
> Użytkownik Andy Furniss napisał:
> 
>>
>> I just tried with 2 d/l and 3 classes - I see the same as you now.
>>
>> Andy.
> 
> 
> I am happy that there is finally confirmation of what I''ve seen :)
> But what now? I am just starting with traffic shaping and my question 
> is: how is that - that so many people are using HTB for so long time and 
> nobody noticed it is not fair?
> I suppose with more complex configurtions which are propably more common 
>  the fact that some part of HTB is not fair (borrowing I suppose) is 
> blured and hard to notice some incorrect behavior.
> 
> Does Devik work on HTB yet. Maybe he could look at this problem closer? 
> Should I notice him about that? What do you think?
I assume you saw the patch - and it''s OK now?

Andy.


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

> I assume you saw the patch - and it''s OK now?
> 
> Andy.
Yes, I was the one who tested it before Devik made it public :)
(and he wrote my name together with info about this patch)

I wrote to him about that after you confirmed you can see the same 
behavior of htb.
Now it works PERFECT!
(three times ''hip-hip-hurray'' for HTB :)

-josh

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