Re: [LARTC] HTB rate, borrowing, and dequeuing

[Stef Coene <stef.coene@docum.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*22 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/