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@xxxxxxxxx "Using Linux as bandwidth manager" http://www.docum.org/ #lartc @ irc.oftc.net
