Token bucket
Encyclopedia
The token bucket is an algorithm
used in packet switched computer network
s and telecommunications networks
to check that data transmission
s conform to defined limits on bandwidth
and burstiness
(a measure of the unevenness or variations in the traffic
flow).
The token bucket algorithm is based on an analogy
of a bucket
that contains tokens
, each of which can represent a unit of bytes or a single packet of predetermined size. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e.g. equivalent to the length of the packet in bytes, are removed ("cashed in"), and the packet is passed, e.g., for transmission. If there are insufficient tokens in the bucket the packet does not conform and the contents of the bucket are not changed. Non-conformant packets can be treated in various ways:
A conforming flow can thus contain traffic up to its peak burst rate if there are adequate tokens in the bucket and if the depth of the bucket is set appropriately.
seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds = 
.
.
Then
is the maximum burst time, that is the time for which the rate M is fully utilized.
The maximum burst size is thus
or traffic policing
. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see bandwidth management
and congestion avoidance. Traffic shaping is commonly used in the network interfaces in hosts
to prevent transmissions being discarded by traffic management functions in the network.
algorithm described in the literature. This comparable version of the leaky bucket is described on the relevant Wikipedia page as the leaky bucket algorithm as a meter. This is a mirror image of the token bucket, in that conforming packets add fluid, equivalent to the tokens, to a finite capacity bucket, from which this fluid then drains away at a constant rate, equivalent to the process in the token bucket algorithm in which tokens are added at a fixed rate.
There is, however, another version of the leaky bucket algorithm, described on the relevant Wikipedia page as the leaky bucket algorithm as a queue. This is a special case of the leaky bucket as a meter, which can be described by the conforming packets passing through the bucket. The leaky bucket as a queue is therefore applicable only to traffic shaping, and does not, in general, allow the output packet stream to be bursty, i.e. it is jitter free. It is therefore significantly different from the token bucket algorithm.
These two versions of the leaky bucket
algorithm have both been described in the literature under the same name. This has led to considerable confusion over the properties of that algorithm and its comparison with the token bucket algorithm. However, fundamentally, the two algorithms are the same, and will, if implemented correctly and given the same parameters, see exactly the same packets as conforming and nonconforming.
.
on a given link
.
HTB allows using one single physical link
to simulate multiple slower links and to send different kinds of traffic
on different simulated links. In both cases, one has to specify how to divide the physical link into simulated links and how to decide which simulated link a given packet is to be sent across.
In other words, HTB is very useful to limit a client's download/upload rate. Thus, the limited client cannot saturate the total bandwidth.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used in packet switched computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
s and telecommunications networks
Telecommunication
Telecommunication is the transmission of information over significant distances to communicate. In earlier times, telecommunications involved the use of visual signals, such as beacons, smoke signals, semaphore telegraphs, signal flags, and optical heliographs, or audio messages via coded...
to check that data transmission
Data transmission
Data transmission, digital transmission, or digital communications is the physical transfer of data over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibres, wireless communication channels, and storage media...
s conform to defined limits on bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
and burstiness
Burst transmission
In telecommunication, the term burst transmission or data burst has the following meanings:# Any relatively high-bandwidth transmission over a short period of time...
(a measure of the unevenness or variations in the traffic
Network traffic
Network traffic is data in a network. In computer networks, the data is encapsulated in packets.*Network traffic control*Network traffic measurement*Network traffic simulation...
flow).
The token bucket algorithm is based on an analogy
Analogy
Analogy is a cognitive process of transferring information or meaning from a particular subject to another particular subject , and a linguistic expression corresponding to such a process...
of a bucket
Bucket
A bucket, also called a pail, is typically a watertight, vertical cylinder or truncated cone, with an open top and a flat bottom, usually attached to a semicircular carrying handle called the bail. A pail can have an open top or can have a lid....
that contains tokens
Type–token distinction
In disciplines such as philosophy and knowledge representation, the type-token distinction is a distinction that separates an abstract concept from the objects which are particular instances of the concept...
, each of which can represent a unit of bytes or a single packet of predetermined size. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e.g. equivalent to the length of the packet in bytes, are removed ("cashed in"), and the packet is passed, e.g., for transmission. If there are insufficient tokens in the bucket the packet does not conform and the contents of the bucket are not changed. Non-conformant packets can be treated in various ways:
- They may be dropped.
- They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket.
- They may be transmitted, but marked as being non-conformant, possibly to be dropped subsequently if the network is overloaded.
A conforming flow can thus contain traffic up to its peak burst rate if there are adequate tokens in the bucket and if the depth of the bucket is set appropriately.
The token bucket algorithm
The algorithm can be conceptually understood as follows:- A token is added to the bucket every
seconds. - The bucket can hold at the most b tokens. If a token arrives when the bucket is full, it is discarded.
- When a packet (network layer PDUProtocol data unitIn telecommunications, the term protocol data unit has the following meanings:#Information that is delivered as a unit among peer entities of a network and that may contain control information, address information, or data....
) of n bytes arrives, n tokens are removed from the bucket, and the packet is sent to the network. - If fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.
Variations
Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds = .Average rate
Over the long run the output of conformant packets is limited by the token rate,.Burst size
Let M be the maximum possible transmission rate in bytes/second.Then
is the maximum burst time, that is the time for which the rate M is fully utilized.The maximum burst size is thus
Uses
The token bucket can be used in either traffic shapingTraffic shaping
Traffic shaping is the control of computer network traffic in order to optimize or guarantee performance, improve latency, and/or increase usable bandwidth for some kinds of packets by delaying other kinds of packets that meet certain criteria...
or traffic policing
Traffic policing
Traffic policing is the process of monitoring network traffic for compliance with a traffic contract and taking steps to enforce that contract. Traffic sources which are aware of a traffic contract may apply traffic shaping to ensure their output stays within the contract and is thus not discarded...
. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see bandwidth management
Bandwidth management
Bandwidth management is the process of measuring and controlling the communications on a network link, to avoid filling the link to capacity or overfilling the link, which would result in network congestion and poor performance of the network.- Management :Bandwidth management mechanisms may be...
and congestion avoidance. Traffic shaping is commonly used in the network interfaces in hosts
Host (network)
A network host is a computer connected to a computer network. A network host may offer information resources, services, and applications to users or other nodes on the network. A network host is a network node that is assigned a network layer host address....
to prevent transmissions being discarded by traffic management functions in the network.
Comparison to leaky bucket
The token bucket algorithm is directly comparable to one of the two versions of the leaky bucketLeaky bucket
The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness . The leaky bucket algorithm is also used in leaky bucket counters, e.g...
algorithm described in the literature. This comparable version of the leaky bucket is described on the relevant Wikipedia page as the leaky bucket algorithm as a meter. This is a mirror image of the token bucket, in that conforming packets add fluid, equivalent to the tokens, to a finite capacity bucket, from which this fluid then drains away at a constant rate, equivalent to the process in the token bucket algorithm in which tokens are added at a fixed rate.
There is, however, another version of the leaky bucket algorithm, described on the relevant Wikipedia page as the leaky bucket algorithm as a queue. This is a special case of the leaky bucket as a meter, which can be described by the conforming packets passing through the bucket. The leaky bucket as a queue is therefore applicable only to traffic shaping, and does not, in general, allow the output packet stream to be bursty, i.e. it is jitter free. It is therefore significantly different from the token bucket algorithm.
These two versions of the leaky bucket
Leaky bucket
The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness . The leaky bucket algorithm is also used in leaky bucket counters, e.g...
algorithm have both been described in the literature under the same name. This has led to considerable confusion over the properties of that algorithm and its comparison with the token bucket algorithm. However, fundamentally, the two algorithms are the same, and will, if implemented correctly and given the same parameters, see exactly the same packets as conforming and nonconforming.
Hierarchical token bucket
The Hierarchical Token Bucket (HTB) is a faster replacement for the class-based queueing qdisc (queuing discipline) in LinuxLinux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
.
Description
HTBs help in controlling the use of the outbound bandwidthBandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
on a given link
Data link
In telecommunication a data link is the means of connecting one location to another for the purpose of transmitting and receiving information. It can also refer to a set of electronics assemblies, consisting of a transmitter and a receiver and the interconnecting data telecommunication circuit...
.
HTB allows using one single physical link
Data link
In telecommunication a data link is the means of connecting one location to another for the purpose of transmitting and receiving information. It can also refer to a set of electronics assemblies, consisting of a transmitter and a receiver and the interconnecting data telecommunication circuit...
to simulate multiple slower links and to send different kinds of traffic
Internet traffic
-Historical Internet Traffic Growth:Because of the distributed nature of the Internet, there is no single point of measurement for total Internet traffic...
on different simulated links. In both cases, one has to specify how to divide the physical link into simulated links and how to decide which simulated link a given packet is to be sent across.
In other words, HTB is very useful to limit a client's download/upload rate. Thus, the limited client cannot saturate the total bandwidth.
See also
- Leaky bucketLeaky bucketThe leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness . The leaky bucket algorithm is also used in leaky bucket counters, e.g...
- Traffic shapingTraffic shapingTraffic shaping is the control of computer network traffic in order to optimize or guarantee performance, improve latency, and/or increase usable bandwidth for some kinds of packets by delaying other kinds of packets that meet certain criteria...
- Rate limitingRate limitingIn computer networks, rate limiting is used to control the rate of traffic sent or received on a network interface. Traffic that is less than or equal to the specified rate is sent, whereas traffic that exceeds the rate is dropped or delayed...
- Congestion Avoidance in Broadband NetworksBroadband NetworksThe ideal telecommunication network has the following characteristics: broadband, multi-media, multi-point, multi-rate and economical implementation for a diversity of services [1][2]. The Broadband Integrated Services Digital Network provides these characteristics in today's networks...