Manual:HTB-Token Bucket Algorithm

Applies to RouterOS: v6.35+

Overview

This part of the wiki will concentrate on "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 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 added in RouterOS v6.35, before that it was hard-coded to "0.1".

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

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

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

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

Packet queue (Blue part of the diagram)

Size of this packet queue, sequence, how packets are added to this queue, and when packets are discarded, is 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 limit-at was the highest, extra tokens need to be issued to compensate for all missing tokens that were not borrowed from 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

So if bucket is full (client was not using full capacity of the queue for some time), next 1Mb of traffic can cross the queue at unrestricted speed.

Large Queue Bucket

Lets try to apply same logic to 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

So if bucket is full (client was not using full capacity of the queue for some time), next 100Mb of traffic can cross the queue at unrestricted speed.

So you can have:

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

So as you can see bucket permits certain burstiness of the traffic that passes the queue. So behavior is similar to our burst feature, but lacks the upper limit of the burst. But this setback can be avoided when we utilize bucket size in 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 10M = 1M
• child queue bucket-size=10, bucket-capacity= 10 x 10M = 100M

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

So this way we can have up to 10 second burst at 20Mbps