Manual:HTB

From MikroTik Wiki
Revision as of 13:33, 2 October 2008 by Megis (talk | contribs)
Jump to navigation Jump to search

Theory

Structure

Hierarchical Token Bucket (HTB) allows to create hierarchical queue structure and determine relations between parent and child queues and relation between child queues. As soon as queue have at least one child it become a parent queue. All child queues (don't matter how many levels of parents they have) are treated as they were on the same (bottom) level of HTB. Child queues make actual traffic consumption, parent queues are responsible only for traffic distribution. Child queues are not able to get more traffic than parent has.

In RouterOS it is necessary to specify parent option to assign queue as a child to other queue

Dual Limitation

Each queue in HTB have two rate limits:

  • CIR (Committed Information Rate) – (limit-at in RouterOS) worst case scenario, flow will get this amount of traffic no matter what (assuming we can actually send so much data)
  • MIR (Maximal Information Rate) – (max-limit in RouterOS) best case scenario, rate that flow can get up to, if there is spare bandwidth


In another words, at first HTB will try to satisfy every child queue's limit-at (CIR) only then it will try to reach max-limit (MIR)

To ensure optimal (as designed) usage of dual limitation feature we suggest to stick to these rules:

  • Sum of committed rates of all children must be less or equal to amount of traffic that is available to parent.
CIR(parent)* ≥ CIR(child1) +...+ CIR(childN)
*in case if parent is main parent CIR(parent)=MIR(parent)
  • Maximal rate of any child must be less or equal to maximal rate of the parent
MIR (parent) ≥ MIR(child1) & MIR (parent) ≥ MIR(child2) & MIR (parent) ≥ MIR(childN)

Priority

Priority is used for creation of the strict order - who will get traffic first. Queue with higher priority will reach its limit-at before the queue with lower priority and after all limit-ats are satisfied queue with higher priority will reach its MIR before the queue with lower priority. 8 is the lowest priority, 1 is the highest.

Make a note that priority only works:

  • for child queues - as soon as you assign at least one child to the queue, priority option will have no meaning in this queue
  • if limit-at and/or max-limit is specified (not 0)


Example

In this section we will analyze HTB in action. To do so we will take one specific example of HTB in one specific moment in time, when HTB have to recycle specific amount of incoming traffic.

Structure

Our HTB structure will consist of 14 queues:

  • Queue01 has two childs - Queue02 and Queue08
  • Queue02 has two childs - Queue03 and Queue07
  • Queue03 has three childs - Queue04, Queue05 and Queue06
  • Queue04 child
  • Queue05 child
  • Queue06 child
  • Queue07 child
  • Queue08 has two childs - Queue09 and Queue12
  • Queue09 has two childs - Queue10 and Queue11
  • Queue10 child
  • Queue11 child
  • Queue12 has two childs - Queue13 and Queue14
  • Queue13 child
  • Queue14 child


Priorities, limits and amounts of incoming traffic

We will use 50Mbps as basic rate for this particular HTB tree. Limitations and priorities are set according the rules mentioned earlier in this page. Amounts of incoming traffic are assigned to ensure meaningfulness of the example.

All data can be seen in the table below:

File:Stage1 1.jpg


Stage 1 - Satisfying the Limit-at

As we know that in this particular setup sum of children limit-ats are less or equal to traffic that is available to parent, we can assume, that this HTB will have no problems to give limit-at amount of traffic to each and every child queue if required

  1. Queue07 has the highest priority - it will get its 10Mbps (limit-at) first.
    By doing so it will decrees available traffic of parents (Queue02,Queue01,Queue01) by 10Mbps
    Queue07 still has 28Mbps to send out
  2. Queue10 has the second highest priority - it will get its 5Mbps (limit-at)
    By doing so it will decrees available traffic of parents (Queue09,Queue08,Queue01) by 5Mbps
    Queue10 still has 5Mbps to send out
  3. Queue11 has the next highest priority - it will get its 5Mbps (limit-at)
    By doing so it will decrees available traffic of parents (Queue09,Queue08,Queue01) by 5Mbps
    Queue11 still has 17Mbps to send out
  4. Queue13 and Queue05 has the next highest priority - as till now there is still 30Mbps available both can get traffic withou any problems
    Queue13 can get its 10Mbps (limit-at), but it needs only 5Mbps
    By doing so it will decrees available traffic of parents (Queue12,Queue08,Queue01) by 5Mbps
    Queue13 is satisfied - all traffic sent out
    Queue05 can get its 3Mbps (limit-at), but it needs only 2Mbps
    By doing so it will decrees available traffic of parents (Queue03,Queue02,Queue01) by 2Mbps
    Queue05 is satisfied - all traffic sent out
  5. Queue14 has the next highest priority - it can get its 10Mbps (limit-at)
    By doing so it will decrees available traffic of parents (Queue12,Queue08,Queue01) by 10Mbps
    Queue14 still has 8Mbps to send out
  6. Queue04 has the next highest priority - it can get its 3Mbps (limit-at)
    By doing so it will decrees available traffic of parents (Queue03,Queue02,Queue01) by 3Mbps
    Queue04 still has 3Mbps to send out
  7. Queue06 has the next highest priority - it can get its 3Mbps (limit-at), but no traffic is required


So by satisfying limit-at of all queues we spend 40Mbps out of 50Mbps. We still have lots of unsatisfied traffic.

Results after this step can be seen here:

File:Stage1 2.jpg

Stage 2 - Getting closer to Max-limit

  1. Queue07 has the highest priority and it still requires 28Mbps - so it might be able to get the pending 10Mbps, BUT there is a problem - its parent Queue02 has only 5Mbps available (limit-at)
    Queue02 can ask its parent Queue01 to get additional 5Mbps, but Queue01 must first satisfy limit-ats of all children (Queue02,Queue08) before it can give out traffic above limit-at. So in this step Queue07 can get only 5Mbps
    By doing so it will decrees available traffic of parents (Queue02,Queue01) by 5Mbps
    Queue07 still has 21Mbps to send out
  2. Queue10 has the second highest priority and it still requires 5Mbps , BUT its parent Queue09 has no available traffic (limit-at)
    Queue09 can ask his parent Queue08 to get additional 5Mbps, but Queue08 must first satisfy limit-ats of all children (Queue09,Queue12) before it can give out traffic above limit-at. So in this step Queue10 will not get any traffic
  3. Queue11 has the next highest priority and it still requires 17Mbps, BUT it has the same same situation as *Queue10. So in this step Queue10 will not get any traffic
  4. Queue05 and Queue13 has the next highest priority but have no traffic.
  5. Queue14 has the next highest priority and it still requires 8Mbps, and its parent is able to provide 5Mbps. So in this step Queue14 can get 5Mbps.
    By doing so it will decrees available traffic of parents (Queue12,Queue08,Queue01) by 5Mbps
    Queue14 still has 3Mbps to send out
  6. No more traffic available - rest of pending traffic will be scheduled or dropped.


Final results can be seen here:

Stage1 3.jpg