Manual:HTB-Token Bucket Algorithm: Difference between revisions

From MikroTik Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{Versions|v6.33+ }}
{{Versions|v6.35+ }}


==Overview==
==Overview==


This part of the wiki will concentrate on "Token Bucket" part of '''Hierarchical Token Bucket'''(HTB) - an algorithm inside the single queue.   
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:
"Hierarchical" part of '''Hierarchical Token Bucket'''(HTB) queuing method is covered here:
http://wiki.mikrotik.com/wiki/Manual:HTB
http://wiki.mikrotik.com/wiki/Manual:HTB
Line 9: Line 9:
==Token Bucket algorithm (Red part of the diagram)==
==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 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.  
The bucket itself has a specified capacity.  
Queue gets tokens from parent queue, at a rate determined by parent queue.


If the bucket fills to capacity, newly arriving tokens are dropped  
If the bucket fills to capacity, newly arriving tokens are dropped  
Line 18: Line 16:
'''Bucket capacity = bucket-size * max-limit '''  
'''Bucket capacity = bucket-size * max-limit '''  


*'''bucket size''' (0..10, Default:0.1) - queue option added in RouterOS v6.35, before that it had value was hard-coded to "0.1".
*'''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 letting any packet pass through queue, the bucket is inspected to see if it contains sufficient tokens at that moment.
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 can pass the queue.
If yes, the appropriate number of tokens are removed ("cashed in") and packet is permitted to pass through the queue.


If, no, packets stays in the beginning of packet waiting queue until the appropriate amount of tokens are available.
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)==
==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:
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-type''' - http://wiki.mikrotik.com/wiki/Manual:Queue#Kinds
*'''queue-size''' - http://wiki.mikrotik.com/wiki/Manual:Queue_Size
*'''queue-size''' - http://wiki.mikrotik.com/wiki/Manual:Queue_Size
Line 39: Line 40:
* '''limit-at''' (''NUMBER/NUMBER'') : guaranteed upload/download data rate to a target  
* '''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
* '''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''' (''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
'''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 issued by parent queue.
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==
==The Diagram==


[[File:bucket_size.png|800px]]
[[File:bucket_size.png|800px]]
==Bucket Size in action==
Lets have a simple setup where all traffic from and to one IP address is marked with a packet-mark:
<pre>
/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
</pre>
===Default Queue Bucket===
<pre>
/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
</pre>
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:
<pre>
/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
</pre>
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 ===
<pre>
/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
</pre>
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.

Latest revision as of 04:58, 22 April 2019

Version.png

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:


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.png

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.