Although the token 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 amount of data that is injected into a network, allowing for "bursts" of data to be sent.

Traffic shaping algorithms

Two predominant methods for shaping traffic exist: a leaky bucket implementation and a token bucket implementation. Sometimes the leaky bucket and token bucket algorithms are mistakenly lumped together under the same name. Both these schemes have distinctly different properties and are used for distinctly different purposes [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.

What is the Token-bucket algorithm used for?

The token bucket is similar in some respects to the leaky bucket, but the primary difference is that the token bucket allows bursty traffic to continue transmitting while there are tokens in the bucket, up to a user-configurable threshold, thereby accommodating traffic flows with bursty characteristics [1] (see Inefficiency of the token-bucket implementation).

How does the Token-bucket implementation work?

The token bucket is a control mechanism that dictates when traffic can be transmitted, based on the presence of tokens in the bucket. The token bucket contains tokens, each of which can represent a unit of bytes. The network administrator specifies how many tokens are needed to transmit however many number of 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.

References

[1] 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.

See also

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

External links

• Traffic shaping and rate control
• Congestion control
• A token bucket programming exercise