Token bucket

It can be used to check that data transmissions, in the form of packets, 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 fixed capacity bucket into which tokens, normally representing a unit of bytes or a single packet of predetermined size, are added at a fixed rate.

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.

Non-conformant packets can be treated in various ways: A conforming flow can thus contain traffic with an average rate up to the rate at which tokens are added to the bucket, and have a burstiness determined by the depth of the bucket.

This burstiness may be expressed in terms of either a jitter tolerance, i.e. how much sooner a packet might conform (e.g. arrive or be transmitted) than would be expected from the limit on the average rate, or a burst tolerance or maximum burst size, i.e. how much more than the average level of traffic might conform in some finite period.

Over the long run the output of conformant packets is limited by the token rate,

The token bucket algorithm is also used in controlling database IO flow.

By defining tokens to be the normalized sum of IO request weight and its length, the algorithm makes sure that the time derivative of the aforementioned function stays below the needed threshold.

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.

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.

The hierarchical token bucket (HTB) is a faster replacement for the class-based queueing (CBQ) queuing discipline in Linux.

Conceptually, HTB is an arbitrary number of token buckets arranged in a hierarchy.

This single HTB class will be set with two parameters, a rate and a ceil.

These values should be the same for the top-level class, and will represent the total available bandwidth on the link.

When choosing the bandwidth for a top-level class, traffic shaping only helps at the bottleneck between the LAN and the Internet.

Typically, this is the case in home and office network environments, where an entire LAN is serviced by a DSL or T1 connection.