Manual:HTB-Token Bucket Algorithm

Applies to RouterOS: v6.35+

Overview

This part of the wiki will concentrate on the "Token Bucket" part of Hierarchical Token Bucket(HTB) - an algorithm inside the single queue. "Hierarchical" part of Hierarchical Token Bucket(HTB) queuing method is covered here: http://wiki.mikrotik.com/wiki/Manual:HTB

Token Bucket algorithm (Red part of the diagram)

The Token Bucket algorithm is based on an analogy to a bucket where tokens, represented in bytes, are added at a specific rate. The bucket itself has a specified capacity.

If the bucket fills to capacity, newly arriving tokens are dropped

Bucket capacity = bucket-size * max-limit

• bucket size (0..10, Default:0.1) - queue option was added in RouterOS v6.35, before that it was hard-coded to a value of "0.1".

Before allowing any packet to pass through the queue, the queue bucket is inspected to see if it already contains sufficient tokens at that moment.

If yes, the appropriate number of tokens are removed ("cashed in") and packet is permitted to pass through the queue.

If no, the packets stays at the start of packet waiting queue until the appropriate amount of tokens are available.

In case of a multi-level queue structure, tokens used in a child queue are also 'charged' to their parent queues. In other words - child queues 'borrow' tokens from their parent queues.

Packet queue (Blue part of the diagram)

The size of this packet queue, the sequence, how packets are added to this queue, and when packets are discarded are determined by:

• queue-type - http://wiki.mikrotik.com/wiki/Manual:Queue#Kinds
• queue-size - http://wiki.mikrotik.com/wiki/Manual:Queue_Size

Token rate selection (Black part of the diagram)

Maximal token rate at any given time is equal to highest active of these values:

• limit-at (NUMBER/NUMBER) : guaranteed upload/download data rate to a target
• max-limit (NUMBER/NUMBER) : maximal upload/download data rate that is allowed for a target
• burst-limit (NUMBER/NUMBER) : maximal upload/download data rate that is allowed for a target while the 'burst' is active

burst-limit is active only when 'burst' is in allowed state - more info here: http://wiki.mikrotik.com/index.php?title=Manual:Queues_-_Burst

In case where limit-at is the highest value, extra tokens need to be issued to compensate for all missing tokens that were not borrowed from it's parent queue.

The Diagram

Bucket Size in action

Lets have a simple setup where all traffic from and to one IP address is marked with a packet-mark:

/ip firewall mangle
add chain=forward action=mark-connection connection-mark=no-mark src-address=192.168.88.101 new-connection-mark=pc1_conn
add chain=forward action=mark-connection connection-mark=no-mark dst-address=192.168.88.101 new-connection-mark=pc1_conn
add chain=forward action=mark-packet connection-mark=pc1_conn new-packet-mark=pc1_traffic

Default Queue Bucket

/queue tree
add name=download parent=Local packet-mark=PC1-traffic max-limit=10M
add name=upload parent=Public packet-mark=PC1-traffic max-limit=10M

In this case bucket-size=0.1, so bucket-capacity= 0.1 x 10M = 1M

If the bucket is full (that is, client was not using full capacity of the queue for some time), the next 1Mb of traffic can pass through the queue at an unrestricted speed.

Large Queue Bucket

Lets try to apply the same logic to a situation when bucket-size is at its maximal value:

/queue tree
add name=download parent=Local packet-mark=PC1-traffic max-limit=10M bucket-size=10
add name=upload parent=Public packet-mark=PC1-traffic max-limit=10M bucket-size=10

In this case bucket-size=10, so bucket-capacity= 10 x 10M = 100M

If the bucket is full (that is, client was not using full capacity of the queue for some time), the next 100Mb of traffic can pass through the queue at an unrestricted speed.

So you can have:

• 20Mbps transfer speed for 10s
• 60Mbps transfer burst for 2s
• 1Gbps transfer burst for approximately 100ms

You can therefore see that the bucket permits a type of 'burstiness' of the traffic that passes through the queue. The behavior is similar to the normal burst feature, but lacks the upper limit of the burst. This setback can be avoided if we utilize bucket size in the queue structure:

Large Child Queue Bucket, Small Parent Queue Bucket

/queue tree
add name=download_parent parent=Local max-limit=20M
add name=download parent=download_parent packet-mark=PC1-traffic max-limit=10M bucket-size=10
add name=upload_parent parent=Public max-limit=20M
add name=upload parent=upload_parent packet-mark=PC1-traffic max-limit=10M bucket-size=10

In this case:

• parent queue bucket-size=0.1, bucket-capacity= 0.1 x 20M = 2M
• child queue bucket-size=10, bucket-capacity= 10 x 10M = 100M

The parent will run out of tokens much faster than child queue and as its child queue always borrows tokens from parent queue the whole system is restricted to token-rate of the parent queue - in this case to max-limit=20M. This rate will be sustained until the child queue runs out of tokens and will be restricted to its token-rate of 10Mbps.

In this way we can have a burst at 20Mbps for up to 10 seconds.