Skip to contentSkip to conversation

HTB theory?

LARTC Dmitry Golubev 4 participants 6 messages Jun 12, 2004 – Jun 16, 2004

lore
Share & tools
lore
#0 lore raw

Hello,

I have been searching for HTB theory documentation and found two interesting sources - Devik's page and docum.org FAQ. In some places they are contradictory which make me think that Devik's theoretic document (marked "actual") is just too old and does not reflect the latest changes. After reading http://www.docum.org/docum.org/faq/cache/30.html and others, I feel that I do not understand anything ...

Where can I find the current and actual documentation on how HTB3 is working (I am interested in in-depth theoretical material)?

Please, help...
Dmitry
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#1 lore raw
Quoted 9 lines · Dmitry Golubev

Hello,

I have been searching for HTB theory documentation and found two interesting sources - Devik's page and docum.org FAQ. In some places they are
contradictory which make me think that Devik's theoretic document (marked "actual") is just too old and does not reflect the latest changes. After reading http://www.docum.org/docum.org/faq/cache/30.html and others, I feel that I do not understand anything ...

I know some information in the faq pages on docum.org is outdated. Some information is for htb2, other information changed in htb3 (like the max and min for quantum).
I had a problem with my faq pages (memory problem with faqomatic), but they are working again. I'm checking and updating all pages (I also converted them all to php) and soon I will check the faq pages for errors.

Quoted 2 lines

Where can I find the current and actual documentation on how HTB3 is working (I am interested in in-depth theoretical material)?

Htb pages and htb sources.

Stef

Signature · 6 lines
[email protected]
 "Using Linux as bandwidth manager"
     http://www.docum.org/
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
#2 lore raw
In reply to Dmitry Golubev

OK then, could you tell if I understand correctly and correct me if not?

1. In order of priority, we satisfy all leaf classes' rates (while the class is “green”)
2. When the leaf classes' rate is reached (all the leaf classes are “yellow”), borrow the unused speed from parent classes if they have something to give (if they are not “red”). In this case, each leaf class is equal to others until their ceil is met or until they will have no parent to borrow from... Or maybe their level matters?

I also think that:
1. Until all leaf classes' rate is met we even do not check anything else (including ceil of parent classes)
2. the root queue is unlimited feed for the classes which are attached to it directly

One think I do not understand neither for SFQ nor for HTB (please explain for both) - how can we maintain fairness in case of differently-sizes packets. As I understand, one packet is atomic unit, and interface is requesting not more and not less than one packet. Now given a quantum for each leaf class in HTB or the same for SQF (are they different in this process?) of 1500 bytes - do they wait for more packets from one subclass (asking it once again in the next turn, of course, if they have nothing to send, we switch to the next...)? And if one subclass is providing 1500 packets in each turn, and another subclass is providing 800-byte packets - will they be equal on the amount of traffic they are allowed to send in case the real channel is smaller than the sum of their effective ceil values?

(I am preparing for a seminar in which I will tell people how it works, so I need to know this perfectly :))) )

Thanks,
Dmitry

Quoted 18 lines · Stef Coene
Quoted 9 lines · Dmitry Golubev

Hello,

I have been searching for HTB theory documentation and found two interesting sources - Devik's page and docum.org FAQ. In some places they are
contradictory which make me think that Devik's theoretic document (marked "actual") is just too old and does not reflect the latest changes. After reading http://www.docum.org/docum.org/faq/cache/30.html and others, I feel that I do not understand anything ...

I know some information in the faq pages on docum.org is outdated. Some information is for htb2, other information changed in htb3 (like the max and min for quantum).
I had a problem with my faq pages (memory problem with faqomatic), but they are working again. I'm checking and updating all pages (I also converted them all to php) and soon I will check the faq pages for errors.

Quoted 6 lines
Quoted 2 lines

Where can I find the current and actual documentation on how HTB3 is working (I am interested in in-depth theoretical material)?

Htb pages and htb sources.

Stef

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#3 lore raw
In reply to Dmitry Golubev

Dmitry Golubev wrote:

<snip>

Quoted 4 lines

One think I do not understand neither for SFQ nor for HTB (please explain for both) - how can we maintain fairness in case of differently-sizes packets. As I understand, one packet is atomic unit, and interface is requesting not more and not less than one packet.

I don't know about HTB, but SFQ uses quantum (= MTU by default). When a packet is dequeued its length is taken away from a counter for the flow. If it's <=0 then the next flow is set up for the next dequeue and credited with quantum bytes. If its >0 then it will be called again next dequeue. SFQ returns the skb for the dequeued packet - so HTB can look up its len, I don't know the HTB code - but that's the next level of documentation for you.

Andy.

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#4 lore raw
In reply to Dmitry Golubev
Quoted 7 lines

1. In order of priority, we satisfy all leaf classes' rates (while the class is “green”)
2. When the leaf classes' rate is reached (all the leaf classes are “yellow”), borrow the unused speed from parent classes if they have something to give (if they are not “red”). In this case, each leaf class is equal to others until their ceil is met or until they will have no parent to borrow from... Or maybe their level matters?

In both cases DRR is used to cycle classes to dequeue - this gives us fairness (weighted by "quantums").

Quoted 3 lines

I also think that:
1. Until all leaf classes' rate is met we even do not check anything else (including ceil of parent classes)

correct

Quoted 2 lines

2. the root queue is unlimited feed for the classes which are attached to it directly

yes

Quoted 11 lines

One think I do not understand neither for SFQ nor for HTB (please explain for both) - how can we maintain fairness in case of differently-sizes packets. As I understand, one packet is atomic unit, and interface is requesting not more and not less than one packet. Now given a quantum for each leaf class in HTB or the same for SQF (are they different in this process?) of 1500 bytes - do they wait for more packets from one subclass (asking it once again in the next turn, of course, if they have nothing to send, we switch to the next...)? And if one subclass is providing 1500 packets in each turn, and another subclass is providing 800-byte packets - will they be equal on the amount of traffic they are allowed to send in case the real channel is smaller than the sum of their effective ceil values?

both SFQ and HTB (and CBQ) uses DRR which uses BYTES as count not packets. Look into literature for "leaky bucket" description. To answer your last mail, cannonical HTB theory (v.3 = latest one) is:
http://luxik.cdi.cz/~devik/qos/htb/manual/theory.htm. It is up to date - mainly because algorithm is the same since 2002.

Quoted 2 lines

(I am preparing for a seminar in which I will tell people how it works, so I need to know this perfectly :))) )

Hmm I have talk at SUCON (http://www.suug.ch/sucon/04/speakers.html#7) so that
I'll need to refresh it too :)

devik

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#5 lore raw
In reply to Dmitry Golubev

Thanks very much, Devik and Andy, I had seminar today and I think it has some success, and (for now?) I do not feel like having unanswered questions.

Dmitry

Quoted 48 lines · Martin Devera
Quoted 7 lines

1. In order of priority, we satisfy all leaf classes' rates (while the class is “green”)
2. When the leaf classes' rate is reached (all the leaf classes are “yellow”), borrow the unused speed from parent classes if they have something to give (if they are not “red”). In this case, each leaf class is equal to others until their ceil is met or until they will have no parent to borrow from... Or maybe their level matters?

In both cases DRR is used to cycle classes to dequeue - this gives us fairness (weighted by "quantums").

Quoted 3 lines

I also think that:
1. Until all leaf classes' rate is met we even do not check anything else (including ceil of parent classes)

correct

Quoted 2 lines

2. the root queue is unlimited feed for the classes which are attached to it directly

yes

Quoted 4 lines

One think I do not understand neither for SFQ nor for HTB (please explain for both) - how can we maintain fairness in case of differently-sizes packets. As I understand, one packet is atomic unit, and interface is requesting not more and not less than one packet. Now given a quantum for

Quoted 8 lines

each leaf class in HTB or the same for SQF (are they different in this process?) of 1500 bytes - do they wait for more packets from one subclass (asking it once again in the next turn, of course, if they have nothing to send, we switch to the next...)? And if one subclass is providing 1500 packets in each turn, and another subclass is providing 800-byte packets
- will they be equal on the amount of traffic they are allowed to send in case the real channel is smaller than the sum of their effective ceil values?

both SFQ and HTB (and CBQ) uses DRR which uses BYTES as count not packets. Look into literature for "leaky bucket" description. To answer your last mail, cannonical HTB theory (v.3 = latest one) is:
http://luxik.cdi.cz/~devik/qos/htb/manual/theory.htm. It is up to date - mainly because algorithm is the same since 2002.

Quoted 2 lines

(I am preparing for a seminar in which I will tell people how it works, so I need to know this perfectly :))) )

Hmm I have talk at SUCON (http://www.suug.ch/sucon/04/speakers.html#7) so that
I'll need to refresh it too :)

Quoted 5 lines

devik

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/