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

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

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

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

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

U=BFytkownik Ed Wildgoose napisa=B3:
> (see the "htb_lookup_leaf" function for details)
> Hope that helps...

Hmm... My greatest C program was the most simple snmp client you can=20
ever imagine - and I was writing it for 2 weeks to finish my classes...=20
So I think it is not good idea for me to patch (or even to take a look=20
at) HTB code :)
-josh

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.

> 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

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.

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.

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

>
> 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 :(

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.

U=BFytkownik Andy Furniss napisa=B3:
> I tried with your rc.shape script on my LAN using scp. I couldn't get=20
> the bash to work - it looks to me like it will only set one user. But I=
=20

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=20
> that my 2 classes existed.

I dont get it: you prepared two classes for two PCs which is equivalent=20
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=
=20
> second perfect. It was the same for 500,1000 and 5000 ceils. The 500=20
> 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=20
has rate=3D1/3 of max bw and ceil=3Dmax bw. You will se that first class=20
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=20
version and it was the same...

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.

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.

U=BFytkownik Andy Furniss napisa=B3:
>=20
> I just tried with 2 d/l and 3 classes - I see the same as you now.
>=20
> 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=20
is: how is that - that so many people are using HTB for so long time and=20
nobody noticed it is not fair?
I suppose with more complex configurtions which are propably more common=20
  the fact that some part of HTB is not fair (borrowing I suppose) is=20
blured and hard to notice some incorrect behavior.

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

-josh

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.

> 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

> 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