Token bucket

Token bucket

A token bucket is a common algorithm used to control the amount of data that is injected into a network, allowing for bursts of data to be sent. Although it has several uses, it is best understood in the context of network traffic shaping or rate limiting.

Traffic shaping algorithms (leaky bucket versus token bucket)

Two predominant methods for shaping traffic exist: a leaky bucket implementation and a token bucket implementation. Sometimes they are mistakenly lumped together under the same name. Both these schemes have distinct properties and are used for distinct purposes [#REF| [1] . They differ principally in that the leaky bucket imposes a hard limit on the data transmission rate, whereas the token bucket allows a certain amount of burstiness while imposing a limit on the average data transmission rate.

High level view

The token bucket is a control mechanism that dictates when traffic can be transmitted, based on the presence of tokens in the bucket--an abstract container that holds aggregate network traffic to be transmitted. The bucket contains tokens, each of which can represent a unit of bytes or a single packet of predetermined size. Tokens in the bucket are effectively "cashed in" (removed) for the ability to send a packet. The network administrator specifies how many tokens are needed to transmit how many bytes. When tokens are present, a flow is allowed to transmit traffic. If there are no tokens in the bucket, a flow cannot transmit its packets. Therefore, a flow can transmit traffic up to its peak burst rate if there are adequate tokens in the bucket and if the burst threshold is configured appropriately.

The token bucket algorithm

The algorithm can be conceptually understood as follows:
*A token is added to the bucket every 1/r 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 PDU) 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".

The algorithm allows bursts of up to "b" bytes, but over the long run the output of conformant packets is limited to the constant rate, r. 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.

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.

Hierarchical Token Bucket

This is a faster replacement for the Class Based Queueing qdisc (queuing discipline) in Linux.

Description

HTBs help in controlling the use of the outbound bandwidth 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.

References

* "Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice" by John Evans, Clarence Filsfils (Morgan Kaufmann, 2007, ISBN 0-12-370549-5)

* Ferguson P., Huston G., Quality of Service: Delivering QoS on the Internet and in Corporate Networks, John Wiley & Sons, Inc., 1998. ISBN 0-471-24358-2.

* Andrew S. Tanenbaum, "Computer Networks", 3rd Edition, Prentice-Hall, 1996.

* Linux HTB Home Page http://luxik.cdi.cz/~devik/qos/htb/ ...

ee also

*Leaky bucket
*Traffic shaping
*Rate limiting
*Congestion Avoidance in Broadband Networks


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Token-Bucket-Algorithmus — Der Token Bucket Algorithmus ist ein Konzept der Informatik aus dem Bereich des Traffic Shapings. Es wird damit die Menge der übertragenen Daten geregelt. Dabei wird die durchschnittliche Datenrate begrenzt. Ein ähnlicher Algorithmus ist der… …   Deutsch Wikipedia

  • Bucket (computing) — In computing, the term bucket can have several meanings. It is used both as a live metaphor, and as a generally accepted technical term in some specialised areas. A bucket is most commonly a type of data buffer or a type of document or in which… …   Wikipedia

  • Bucket-Algorithmus (Begriffsklärung) — Als Bucket Algorithmus (Eimer Algorithmus) bezeichnet man verschiedene Rechenverfahren: Den Leaky Bucket Algorithmus zum Traffic Shaping in ATM Netzwerken Den Token Bucket Algorithmus ein weiterer Algorithmus zum Traffic Shaping Den Bucket… …   Deutsch Wikipedia

  • Leaky bucket — Although the leaky bucket algorithm has several uses, it is best understood in the context of network traffic shaping or rate limiting. Typically, the algorithm is used to control the rate at which data is injected into a network, smoothing out… …   Wikipedia

  • Leaky Bucket — Der Leaky Bucket Algorithmus ist ein einfaches Verfahren zum Traffic Shaping. Es wird damit die Menge der übertragenen Daten geregelt. Dabei wird die maximale Datenrate begrenzt. Ein ähnlicher Algorithmus ist der Token Bucket Algorithmus. Alle… …   Deutsch Wikipedia

  • Leaky-Bucket-Algorithmus — Der Leaky Bucket Algorithmus ist ein einfaches Verfahren zum Traffic Shaping. Es wird damit die Menge der übertragenen Daten geregelt. Dabei wird die maximale Datenrate begrenzt. Ein ähnlicher Algorithmus ist der Token Bucket Algorithmus. Leaky… …   Deutsch Wikipedia

  • Conformado de tráfico — Conformado de tráfico(conocido también como Traffic shaping o Packet shaping) es un mecanismo de control del tráfico inyectado a la red. Su objetivo es evitar la sobrecarga de la red con altas ráfagas de tráfico inyectado. En redes IP con QoS, es …   Wikipedia Español

  • Integrated services — In computer networking, IntServ or integrated services is an architecture that specifies the elements to guarantee quality of service (QoS) on networks. IntServ can for example be used to allow video and sound to reach the receiver without… …   Wikipedia

  • HTB — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • Traffic shaping — (also known as packet shaping ) is the control of computer network traffic in order to optimize or guarantee performance, lower latency, and/or increase usable bandwidth by delaying packets that meet certain criteria. [… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”