Token bucket

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The token bucket is an algorithm used in packet-switched and telecommunications networks. 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). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see network scheduler.

The token bucket is an algorithm used in packet-switched and telecommunications networks. 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). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see network scheduler.

Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every 1/r 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 = (r*S)/1000 . Then T_\text{max} = \begin{cases} b/(M -r) & \text{ if } r is the maximum burst time, that is the time for which the rate M is fully utilized. The maximum burst size is thus B_\text{max} = T_\text{max}*M

Hierarchical token bucket

The hierarchical token bucket (HTB) is a faster replacement for the class-based queueing (CBQ) queuing discipline in Linux. It is useful for limiting each client's download/upload rate so that the limited client cannot saturate the total bandwidth. Conceptually, HTB is an arbitrary number of token buckets arranged in a hierarchy. The primary egress queuing discipline (qdisc) on any device is known as the root qdisc. The root qdisc will contain one class. 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. In HTB, rate means the guaranteed bandwidth available for a given class and ceil (short for ceiling) indicates the maximum bandwidth that class is allowed to consume. When a class requests a bandwidth more than guaranteed, it may borrow bandwidth from its parent as long as both ceils are not reached.

Hierarchical Token Bucket implements a classful queuing mechanism for the Linux traffic control system, and provides rate and ceil to allow the user to control the absolute bandwidth to particular classes of traffic as well as indicate the ratio of distribution of bandwidth when extra bandwidth becomes available (up to ceil). 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374879767 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.