Hello all, I seem to recall having read answers to some of these questions before, but I cannot find the answers now, and there are other answers I don''t think I have ever known! - How is rate calculated in HTB? - Over what number of seconds is rate averaged? - Is it calculated using exponential weighted moving average (EWMA)? - Do children borrow tokens or ctokens from parent classes? - What does it mean when a class lends (tokens?, ctokens?) to itself? [1] This seems illogical to me. Is this a LARTC FAQ typo, Stef? Why would a class borrow from itself? - According to the LARTC HOWTO (9.5.2.2) [1], the kernel asks the root qdisc on an interface to dequeue a packet, and the qdisc hands this opportunity to dequeue to each subclass. Is this also accurate for HTB? (If so, this explains for me why only leaf classes can perform shaping, and why children classes can exceed lower parent class rates.) Thanks in advance for any replies, -Martin [1] http://www.docum.org/stef.coene/qos/faq/cache/33.html [2] http://lartc.org/howto/lartc.qdisc.classful.html#AEN866 [3] http://mailman.ds9a.nl/pipermail/lartc/2003q1/006636.html [4] http://mailman.ds9a.nl/pipermail/lartc/2002q3/004713.html During my research in preparing these questions, I found an answer to one of them in the LARTC mail archive, and I figured I''d post this answer along with my other related HTB questions. - According to this LARTC thread [3], child classes borrow from their parent up to ceil in quantum increments. I thought bandwidth was divided between child classes by rate. Can anybody disambiguate or elucidate on this discrepancy? The answer, Martin, is as follows (see [4] for a restatement). All borrowing from the parent is done as each class has the opportunity to ask the parent for tokens. This means that during each turn, a class has the opportunity to borrow a maximum of quantum tokens, before another class gets serviced. The confusion is understandable, since HTB calculates a reasonable quantum (when it is not specified) from rate and r2q at the creation of the HTB class. So, practically speaking, unless the user is supplying r2q and quantum, bandwidth will be borrowed from the parent in a ratio derived from rate. As always, quantum must be greater than or equal to MTU for HTB calculations to be accurate. -- Martin A. Brown --- SecurePipe, Inc. --- mabrown@securepipe.com _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
On Sunday 06 April 2003 00:33, Martin A. Brown wrote:> Hello all, > > I seem to recall having read answers to some of these questions before, > but I cannot find the answers now, and there are other answers I don''t > think I have ever known!I will try to answer them. Some of these answers are maybe wrong because that''s the way how I see it.> - How is rate calculated in HTB?HTB is based on TBF. Actually, htb uses 2 tbf queues, one for the rate and one for the ceil to control a class. So you can ask you the quesion, how is rate calculated in tbf. I think rate is not really calculated and checked. It''s based on a bucket with tokens to control the rate. You have a rate of tokens and you need a token to send a packet. So if you control the amount of tokens, you control the rate. But I wonder if the size of the packet is used in the calculations.> - Over what number of seconds is rate averaged?The internal kernel clock is used for this. After each tic, the rate of the active class is checked again. You can change this clock : http://www.docum.org/stef.coene/qos/faq/cache/40.html That''s also why you need a minimal burst. This burst depends on the clock you have. If you have a more precize clock, you can specify a smaller burst. The burst is the amount of data you can send between 2 timer tics. A smaller burst is useless, because you can not check it From http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm#burst: Limitation: when you operate with high rates on computer with low resolution timer you need some minimal burst and cburst to be set for all classes. Timer resolution on i386 systems is 10ms and 1ms on Alphas. The minimal burst can be computed as max_rate*timer_resolution. So that for 10Mbit on plain i386 you needs burst 12kb.> - Is it calculated using exponential weighted moving average (EWMA)?Again, I don''t think you can speak about controlling a rate, but you have to think about a bucket with tokens and a supply of tokens.> - Do children borrow tokens or ctokens from parent classes?Yes. If a class sends a packet, a token and a ctoken is used. So the bucket of tokens and ctokens is decremented for each packet that''s send. The same token is decremented from the parent ctoken en token bucket. But there is also a supply of tokens and ctokens equal to the rate and ceil. So if child classes are sending packets equal to the rate, the used tokens are also decrement from the token/ctokens if the parent. I have some tests to prove this : http://www.docum.org/stef.coene/qos/tests/htb/burst/ Take a look at the first test. Class 11 and 10 are sending packets. So tokens are used both from the classes and the parent. But class 10 has a burst and so it has some extra tokens and it can send more data then it''s rate. But the parent has no burst so it''s tokens are dragged negative. Mhh. I just asked my self why the parent tokens and the child tokens are different even if you specify the same burst. Somehow the rate is used when tokens are calculated and when tokens are used. But when the tokens are used, there is also a correlation with the rate. Mhh.> - What does it mean when a class lends (tokens?, ctokens?) to itself? [1] > This seems illogical to me. Is this a LARTC FAQ typo, Stef? Why would > a class borrow from itself?Ask Devik :) I found that on his htb page, but I can''t find it anymore. Maybe Devik corrected it and then I shoud correct my faq page too.> - According to the LARTC HOWTO (9.5.2.2) [1], the kernel asks the root > qdisc on an interface to dequeue a packet, and the qdisc hands this > opportunity to dequeue to each subclass. Is this also accurate for > HTB? (If so, this explains for me why only leaf classes can perform > shaping, and why children classes can exceed lower parent class rates.)The fact that children classes can exceed parent class rate is because the htb algorithme allowes this. Checking also the parent rate/ceil is difficult and Devik did not implement it because he couldn''t figured out to do so.> Thanks in advance for any replies, > > -Martin > > [1] http://www.docum.org/stef.coene/qos/faq/cache/33.html > [2] http://lartc.org/howto/lartc.qdisc.classful.html#AEN866 > [3] http://mailman.ds9a.nl/pipermail/lartc/2003q1/006636.html > [4] http://mailman.ds9a.nl/pipermail/lartc/2002q3/004713.html > > > During my research in preparing these questions, I found an answer to one > of them in the LARTC mail archive, and I figured I''d post this answer > along with my other related HTB questions. > > - According to this LARTC thread [3], child classes borrow from their > parent up to ceil in quantum increments. I thought bandwidth was > divided between child classes by rate. Can anybody disambiguate or > elucidate on this discrepancy? > > The answer, Martin, is as follows (see [4] for a restatement). All > borrowing from the parent is done as each class has the opportunity to ask > the parent for tokens. This means that during each turn, a class has the > opportunity to borrow a maximum of quantum tokens, before another class > gets serviced.Indeed. Quantum is only used when a class wants to send more then it''s rate and less then it''s ceil.> The confusion is understandable, since HTB calculates a reasonable quantum > (when it is not specified) from rate and r2q at the creation of the HTB > class. So, practically speaking, unless the user is supplying r2q and > quantum, bandwidth will be borrowed from the parent in a ratio derived > from rate.Indeed.> As always, quantum must be greater than or equal to MTU for HTB > calculations to be accurate.Otherwise a class with quamtum = 500 may send 500 byte. But if it sends 1000byte, it can, but it will count as 500byte. Pfff. Long post. Stef -- stef.coene@docum.org "Using Linux as bandwidth manager" http://www.docum.org/ #lartc @ irc.oftc.net _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hi Stef and list,
Get ready for another long mail!
: > - How is rate calculated in HTB?
Sorry, Stef, I was unclear with my question. I understand how HTB
determines when to dequeue a packet and when not to dequeue a packet based
on presence of tokens or ctokens. What I fail to understand is how HTB
reports to the user the rate in a given class. [ See more below. ]
: HTB is based on TBF. Actually, htb uses 2 tbf queues, one for the rate
: and one for the ceil to control a class. So you can ask you the
: quesion, how is rate calculated in tbf.
:
: I think rate is not really calculated and checked.
OK--the rate is not calculated in preparation for transmission of packets.
The mechanism controlling dequeuing of packets is essentially a classful
token bucket filter.
It has to be calculated somewhere, though, even if only for display,
because.....when I run "tc -s class show dev $DEV", the output shows a
rate for each class. I hope to learn how this rate is calculated for
reporting.
: It''s based on a bucket with tokens to control the rate. You have a
: rate of tokens and you need a token to send a packet. So if you control
: the amount of tokens, you control the rate. But I wonder if the size
: of the packet is used in the calculations.
Right. So, I understand the concept of tokens/ctokens, and that the rate
of dequeued packets is dependent on the rate of tokens entering the
"rate"
bucket of size "burst". It seems to me that a token is used for every
byte transmitted, so the size of the packet is explicitly used in the
calculations.
So, if I transmit a 500 byte ethernet frame, 500 tokens are used. Is this
incorrect?
: > - Over what number of seconds is rate averaged?
: The internal kernel clock is used for this. After each tic, the rate
: of the active class is checked again. You can change this clock :
: http://www.docum.org/stef.coene/qos/faq/cache/40.html That''s also
why
: you need a minimal burst. This burst depends on the clock you have.
: If you have a more precize clock, you can specify a smaller burst.
: The burst is the amount of data you can send between 2 timer tics. A
: smaller burst is useless, because you can not check it
If I understand your description correctly, a [leaf] class will dequeue as
much data as possible up to burst in one timer tick, and {c,}tokens are
not added to their buckets until the next timer tick. Is this accurate?
I''ll need to think about this some more--I''ll have more
questions about
this. Something doesn''t make sense, but I''m not sure how to
articulate my
question or confusion.
<snipped burst/timer text from Devik''s site>
: > - Is it calculated using exponential weighted moving average (EWMA)?
: Again, I don''t think you can speak about controlling a rate, but you
: have to think about a bucket with tokens and a supply of tokens.
I retract this question. This was my feeble rephrasing of my generally
worded question on how HTB calculates the rate for display to the user.
Let me take another stab:
How are the rate and pps figures in "tc -s class show dev $DEVICE"
calculated?
: > - Do children borrow tokens or ctokens from parent classes?
:
: Yes. If a class sends a packet, a token and a ctoken is used. So the
: bucket of tokens and ctokens is decremented for each packet that''s
: send. The same token is decremented from the parent ctoken en token
: bucket. But there is also a supply of tokens and ctokens equal to the
: rate and ceil. So if child classes are sending packets equal to the
: rate, the used tokens are also decrement from the token/ctokens if the
: parent.
:
: I have some tests to prove this :
: http://www.docum.org/stef.coene/qos/tests/htb/burst/ Take a look at the
: first test. Class 11 and 10 are sending packets. So tokens are used
: both from the classes and the parent. But class 10 has a burst and so
: it has some extra tokens and it can send more data then it''s rate.
: But the parent has no burst so it''s tokens are dragged negative.
Interesting. This makes HTB''s rate and ceiling limiting mechanism a
double leaky bucket, right? This is not obvious to me when I generate
traffic and watch the fluctuating class statistics. Nonetheless, your
explanation convinces me. Thank you.
: Mhh. I just asked my self why the parent tokens and the child tokens
: are different even if you specify the same burst. Somehow the rate is
: used when tokens are calculated and when tokens are used. But when the
: tokens are used, there is also a correlation with the rate. Mhh.
Stef! This sounds like a cat chasing its tail! :)
: > - What does it mean when a class lends (tokens?, ctokens?) to itself?
[1]
: > This seems illogical to me. Is this a LARTC FAQ typo, Stef? Why
would
: > a class borrow from itself?
: Ask Devik :) I found that on his htb page, but I can''t find it
anymore.
: Maybe Devik corrected it and then I shoud correct my faq page too.
OK. I''ll ask Devik....I''ll start a separate thread on this
matter.
: > - According to the LARTC HOWTO (9.5.2.2) [1], the kernel asks the root
: > qdisc on an interface to dequeue a packet, and the qdisc hands this
: > opportunity to dequeue to each subclass. Is this also accurate for
: > HTB? (If so, this explains for me why only leaf classes can perform
: > shaping, and why children classes can exceed lower parent class
rates.)
:
: The fact that children classes can exceed parent class rate is because
: the htb algorithme allowes this. Checking also the parent rate/ceil is
: difficult and Devik did not implement it because he couldn''t figured
: out to do so.
Right! Thanks. I recall having read that it would be a very expensive
operation for him to determine whether parent class rates would be
exceeded, hence this amusing question and answer:
"What if sum of child rates is greater than parent rate?
Then interesting things can happen. Total rate delivered by
children can be higher that parent''s rate (thus its rate is
not respected)."
--Devik, http://luxik.cdi.cz/~devik/qos/htb/htbfaq.htm
I think it''s terrible that children don''t respect their
parents today.
On the other hand, if we have more efficient children, delivering at a
rate higher than their parents.....
Finally, could you (or somebody) confirm that the dequeue request from the
kernel is passed to the root qdisc, and then the root qdisc hands the
opportunity to dequeue to a subclass?
Thanks again for suffering my long questions!
-Martin
--
Martin A. Brown --- SecurePipe, Inc. --- mabrown@securepipe.com
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Some warnings about this thread and my answers in it : I have no idea how this really works. It''s just the way I think how it works.> : HTB is based on TBF. Actually, htb uses 2 tbf queues, one for the rate > : and one for the ceil to control a class. So you can ask you the > : quesion, how is rate calculated in tbf. > : > : I think rate is not really calculated and checked. > > OK--the rate is not calculated in preparation for transmission of packets. > The mechanism controlling dequeuing of packets is essentially a classful > token bucket filter. > > It has to be calculated somewhere, though, even if only for display, > because.....when I run "tc -s class show dev $DEV", the output shows a > rate for each class. I hope to learn how this rate is calculated for > reporting.I thought it was an average of the last 10 seconds, but I''m not sure> : It''s based on a bucket with tokens to control the rate. You have a > : rate of tokens and you need a token to send a packet. So if you control > : the amount of tokens, you control the rate. But I wonder if the size > : of the packet is used in the calculations. > > Right. So, I understand the concept of tokens/ctokens, and that the rate > of dequeued packets is dependent on the rate of tokens entering the "rate" > bucket of size "burst". It seems to me that a token is used for every > byte transmitted, so the size of the packet is explicitly used in the > calculations. > > So, if I transmit a 500 byte ethernet frame, 500 tokens are used. Is this > incorrect?To be honest, untill 5 days ago, I thought tokens = packets. But then I did some tests and I tried to calculate the tokens/ctokens manually and I couldn''t find the equation. I have 2 classes (parent-child) with different rate, the same burst. And I have different tokens. So the rate is used somewhere in the calculations.> : > - Over what number of seconds is rate averaged? > : > : The internal kernel clock is used for this. After each tic, the rate > : of the active class is checked again. You can change this clock : > : http://www.docum.org/stef.coene/qos/faq/cache/40.html That''s also why > : you need a minimal burst. This burst depends on the clock you have. > : If you have a more precize clock, you can specify a smaller burst. > : The burst is the amount of data you can send between 2 timer tics. A > : smaller burst is useless, because you can not check it > > If I understand your description correctly, a [leaf] class will dequeue as > much data as possible up to burst in one timer tick, and {c,}tokens are > not added to their buckets until the next timer tick. Is this accurate?I think so.> I''ll need to think about this some more--I''ll have more questions about > this. Something doesn''t make sense, but I''m not sure how to articulate my > question or confusion. > > <snipped burst/timer text from Devik''s site> > > : > - Is it calculated using exponential weighted moving average (EWMA)? > : > : Again, I don''t think you can speak about controlling a rate, but you > : have to think about a bucket with tokens and a supply of tokens. > > I retract this question. This was my feeble rephrasing of my generally > worded question on how HTB calculates the rate for display to the user. > Let me take another stab: > > How are the rate and pps figures in "tc -s class show dev $DEVICE" > calculated?Founded in the htb source : #define HTB_HSIZE 16 /* classid hash size */ #define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */ and cl->stats.bps = cl->rate_bytes/(HTB_EWMAC*HTB_HSIZE); cl->stats.pps = cl->rate_packets/(HTB_EWMAC*HTB_HSIZE); So 16*2=32 seconds average ???> : > - Do children borrow tokens or ctokens from parent classes? > : > : Yes. If a class sends a packet, a token and a ctoken is used. So the > : bucket of tokens and ctokens is decremented for each packet that''s > : send. The same token is decremented from the parent ctoken en token > : bucket. But there is also a supply of tokens and ctokens equal to the > : rate and ceil. So if child classes are sending packets equal to the > : rate, the used tokens are also decrement from the token/ctokens if the > : parent. > : > : I have some tests to prove this : > : http://www.docum.org/stef.coene/qos/tests/htb/burst/ Take a look at the > : first test. Class 11 and 10 are sending packets. So tokens are used > : both from the classes and the parent. But class 10 has a burst and so > : it has some extra tokens and it can send more data then it''s rate. > : But the parent has no burst so it''s tokens are dragged negative. > > Interesting. This makes HTB''s rate and ceiling limiting mechanism a > double leaky bucket, right? This is not obvious to me when I generate > traffic and watch the fluctuating class statistics. Nonetheless, your > explanation convinces me. Thank you.> : Mhh. I just asked my self why the parent tokens and the child tokens > : are different even if you specify the same burst. Somehow the rate is > : used when tokens are calculated and when tokens are used. But when the > : tokens are used, there is also a correlation with the rate. Mhh. > > Stef! This sounds like a cat chasing its tail! :)That''s why I said "Mhh".> : > - According to the LARTC HOWTO (9.5.2.2) [1], the kernel asks the > : > root qdisc on an interface to dequeue a packet, and the qdisc hands > : > this opportunity to dequeue to each subclass. Is this also accurate > : > for HTB? (If so, this explains for me why only leaf classes can > : > perform shaping, and why children classes can exceed lower parent > : > class rates.) > : > : The fact that children classes can exceed parent class rate is because > : the htb algorithme allowes this. Checking also the parent rate/ceil is > : difficult and Devik did not implement it because he couldn''t figured > : out to do so. > > Right! Thanks. I recall having read that it would be a very expensive > operation for him to determine whether parent class rates would be > exceeded, hence this amusing question and answer: > > "What if sum of child rates is greater than parent rate? > Then interesting things can happen. Total rate delivered by > children can be higher that parent''s rate (thus its rate is > not respected)." > --Devik, http://luxik.cdi.cz/~devik/qos/htb/htbfaq.htm > > I think it''s terrible that children don''t respect their parents today. > On the other hand, if we have more efficient children, delivering at a > rate higher than their parents.....:)> Finally, could you (or somebody) confirm that the dequeue request from the > kernel is passed to the root qdisc, and then the root qdisc hands the > opportunity to dequeue to a subclass?I think you need somebody, not me. Stef -- stef.coene@docum.org "Using Linux as bandwidth manager" http://www.docum.org/ #lartc @ irc.oftc.net _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/