Difference between revisions of "Manual:HTB-Token Bucket Algorithm"

From MikroTik Wiki
Jump to: navigation, search
(Token Bucket algorithm (Red part of the diagram))
Line 3: Line 3:
 
==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.  
  
Line 16: 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 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 queue 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 permuitted 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 queue structure tokens used in a child queue are charged to parent queues also.
+
In case of a multi-level queue structure, tokens used in a child queue are also 'charged' to their parent queues.
in other words - children queues borrow tokens from 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 40: 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 borrowed from 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==
Line 71: Line 71:
 
In this case bucket-size=0.1, so bucket-capacity= 0.1 x 10M = 1M
 
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),
+
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.
next 1Mb of traffic can cross the queue at unrestricted speed.
 
  
 
===Large Queue Bucket===
 
===Large Queue Bucket===
  
Lets try to apply same logic to situation when bucket-size is at its maximal value:
+
Lets try to apply the same logic to a situation when bucket-size is at its maximal value:
  
 
<pre>
 
<pre>
Line 86: Line 85:
 
In this case bucket-size=10, so bucket-capacity= 10 x 10M = 100M
 
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),
+
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.
next 100Mb of traffic can cross the queue at unrestricted speed.
 
  
 
So you can have:
 
So you can have:
 
* 20Mbps transfer speed for 10s
 
* 20Mbps transfer speed for 10s
 
* 60Mbps transfer burst for 2s
 
* 60Mbps transfer burst for 2s
* 1Gbps transfer burst for ~100ms
+
* 1Gbps transfer burst for approximately 100ms
  
So as you can see bucket permits certain burstiness of the traffic that passes the queue.
+
You can therefore see that the bucket permits a type of 'burstiness' of the traffic that passes through the queue.
So behavior is similar to our burst feature, but lacks the upper limit of the burst.
+
The behavior is similar to the normal burst feature, but lacks the upper limit of the burst.
But this setback can be avoided when we utilize bucket size in queue structure:
+
This setback can be avoided if we utilize bucket size in the queue structure:
  
 
===Large Child Queue Bucket, Small Parent Queue Bucket ===
 
===Large Child Queue Bucket, Small Parent Queue Bucket ===
Line 112: Line 110:
 
*child queue bucket-size=10, bucket-capacity= 10 x 10M = 100M
 
*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.
+
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.
  
So this way we can have up to 10 second burst at 20Mbps
+
In this way we can have a burst at 20Mbps for up to 10 seconds.

Revision as of 11:06, 13 May 2016

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 permuitted 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 10M = 1M
  • 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.