Tokenbucket

Token bucket is a rate limiting and traffic shaping algorithm used in computer networks and software to control the amount of data that can be transmitted over time. It models a bucket that holds tokens. Tokens accumulate in the bucket at a fixed rate up to a maximum capacity. Each unit of data that wishes to be sent requires a number of tokens; often one token per byte or per packet, depending on the implementation. If the bucket has enough tokens, the data is transmitted immediately and the corresponding tokens are removed. If not, transmission is delayed until sufficient tokens accumulate or the data is dropped according to policy.

The key parameters are the refill rate and the bucket capacity. The average output rate is limited to the refill rate, while the bucket capacity allows short bursts up to the number of tokens it can hold. This enables occasional bursts without exceeding the long‑term average. In some implementations, tokens are added continuously; in others, the process is discretized into fixed time steps.

Applications include traffic shaping and rate limiting in routers, switches, firewalls, and load balancers; API rate limiting in software services; and message or event processing systems. It is commonly used to enforce per‑client quotas and to smooth traffic, preventing network congestion or service overload.

Relation to leaky bucket: the token bucket permits bursts up to the bucket capacity, whereas a leaky bucket enforces a fixed outgoing rate. Choosing appropriate values for the refill rate and bucket capacity depends on desired average throughput and burst tolerance, as well as QoS requirements.