Manual:HTB-Token Bucket Algorithm: Difference between revisions
No edit summary |
|||
| (6 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Versions|v6. | {{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. | ||
| 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 | *'''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 | 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 | If yes, the appropriate number of tokens are removed ("cashed in") and packet is permitted to pass through the queue. | ||
If | 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 | 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)== | ||
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''' | 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 | ||
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 | |||
===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 | ||
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 | |||
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 | * 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 === | ===Large Child Queue Bucket, Small Parent Queue Bucket === | ||
| Line 109: | Line 107: | ||
In this case: | In this case: | ||
*parent queue bucket-size=0.1, bucket-capacity= 0.1 x | *parent queue bucket-size=0.1, bucket-capacity= 0.1 x 20M = 2M | ||
*child queue bucket-size=10, bucket-capacity= 10 x 10M = 100M | *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 06:58, 22 April 2019
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.