Manual:HTB

Theory

Structure

Hierarchical Token Bucket (HTB) allows to create a hierarchical queue structure and determine relations between queues, like "parent-child" or "child-child".

As soon as queue has at least one child it becomes a inner queue, all queues without children - leaf queues. Leaf queues make actual traffic consumption, Inner queues are responsible only for traffic distribution. All leaf queues are treated on equal basis.

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

Dual Limitation

Each queue in HTB has 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 queue's parent has spare bandwidth

In another words, at first limit-at (CIR) of the all queues will be satisfied, only then child queues will try to borrow the necessary data rate from their parents in order to reach their max-limit (MIR).

Note: CIR will be assigned to the corresponding queue no matter what. (even if max-limit of the parent is exceeded)

That is why, 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)

Queue colors in Winbox:

• 0% - 50% available traffic used - green
• 51% - 75% available traffic used - yellow
• 76% - 100% available traffic used - red

Priority

We already know that limit-at (CIR) to all queues will be given out no matter what.

Priority is responsible for distribution of remaining parent queues traffic to child queues so that they are able to reach max-limit

Queue with higher priority will reach its max-limit before the queue with lower priority. 8 is the lowest priority, 1 is the highest.

Make a note that priority only works:

• for leaf queues - priority in inner queue have no meaning.
• if max-limit is specified (not 0)

Examples

In this section we will analyze HTB in action. To do sow we will take one HTB structure and will try to cover all the possible situations and features, by changing the amount of incoming traffic that HTB have to recycle. and changing some options.

Structure

File:HTB structure.png

Structure

Our HTB structure will consist of 5 queues:

• Queue01 inner queue with two children - Queue02 and Queue03
• Queue02 inner queue with two children - Queue04 and Queue05
• Queue03 leaf queue
• Queue04 leaf queue
• Queue05 leaf queue

Queue03, Queue04 and Queue05 are clients who require 10Mbps all the time Outgoing interface is able to handle 10Mbps of traffic.

Example 1 : Usual case

• Queue01 limit-at=0Mbps max-limit=10Mbps
• Queue02 limit-at=4Mbps max-limit=10Mbps
• Queue03 limit-at=6Mbps max-limit=10Mbps priority=1
• Queue04 limit-at=2Mbps max-limit=10Mbps priority=3
• Queue05 limit-at=2Mbps max-limit=10Mbps priority=5

Result of Example 1

• Queue03 will receive 6Mbps
• Queue04 will receive 2Mbps
• Queue05 will receive 2Mbps
• Clarification: HTB was build so, that, by satisfying all limit-ats, main queue no longer have throughput to distribute

Example 2 : Usual case with max-limit

• Queue01 limit-at=0Mbps max-limit=10Mbps
• Queue02 limit-at=4Mbps max-limit=10Mbps
• Queue03 limit-at=2Mbps max-limit=10Mbps priority=3
• Queue04 limit-at=2Mbps max-limit=10Mbps priority=1
• Queue05 limit-at=2Mbps max-limit=10Mbps priority=5

Result of Example 2

• Queue03 will receive 2Mbps
• Queue04 will receive 6Mbps
• Queue05 will receive 2Mbps
• Clarification: After satisfying all limit-ats HTB will give throughput to queue with highest priority.

Example 3 : Inner queue limit-at

• Queue01 limit-at=0Mbps max-limit=10Mbps
• Queue02 limit-at=8Mbps max-limit=10Mbps
• Queue03 limit-at=2Mbps max-limit=10Mbps priority=1
• Queue04 limit-at=2Mbps max-limit=10Mbps priority=3
• Queue05 limit-at=2Mbps max-limit=10Mbps priority=5

Result of Example 3

• Queue03 will receive 2Mbps
• Queue04 will receive 6Mbps
• Queue05 will receive 2Mbps
• Clarification: After satisfying all limit-ats HTB will give throughput to queue with highest priority. But in this case inner queue Queue02 had limit-at specified, by doing so, it reserved 8Mbps of throughput for queues Queue04 and Queue05. From these two Queue04 have highest priority, that is why it gets additional throughput.

Example 4 : Leaf queue limit-at

• Queue01 limit-at=0Mbps max-limit=10Mbps
• Queue02 limit-at=4Mbps max-limit=10Mbps
• Queue03 limit-at=6Mbps max-limit=10Mbps priority=1
• Queue04 limit-at=2Mbps max-limit=10Mbps priority=3
• Queue05 limit-at=12Mbps max-limit=15Mbps priority=5

Result of Example 4

• Queue03 will receive ~3Mbps
• Queue04 will receive ~1Mbps
• Queue05 will receive ~6Mbps
• Clarification: Only by satisfying all limit-ats HTB was forced to allocate 20Mbps - 6Mbps to Queue03, 2Mbps to Queue04, 12Mbps to Queue05, but our output interface is able to handle 10Mbps. As output interface queue is usually FIFO throughput allocation will keep ratio 6:2:12 or 3:1:6

Temp

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

File:HTB structure.png

Structure

Our HTB structure will consist of 14 queues:

• Queue01 inner queue with two children - Queue02 and Queue08
• Queue02 inner queue with two children - Queue03 and Queue07
• Queue03 inner queue with three children - Queue04, Queue05 and Queue06
• Queue04 leaf queue
• Queue05 leaf queue
• Queue06 leaf queue
• Queue07 leaf queue
• Queue08 inner queue with two children - Queue09 and Queue12
• Queue09 inner queue with two children - Queue10 and Queue11
• Queue10 leaf queue
• Queue11 leaf queue
• Queue12 inner queue with two children - Queue13 and Queue14
• Queue13 leaf queue
• Queue14 leaf queue

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 without 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 if they still require traffic (as we can see Queue08 does require) and only then 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 23Mbps 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 if they still require traffic (as we can see Queue12 does require) and only then 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: