Token bucket

The token bucket is a traffic-shaping and rate-limiting algorithm used in packet-switched and telecommunications networks. It checks that data transmissions, sent as packets, conform to defined limits on average bandwidth and on burstiness, which is the unevenness of the traffic flow. The method is built on the picture of a bucket of fixed capacity into which tokens, each standing for a unit such as a byte or a packet, are added at a steady rate. When a packet arrives, the bucket is inspected: if it holds enough tokens the matching number is removed and the packet passes, and if not the packet is non-conformant and the bucket is left unchanged. Non-conformant packets may be dropped, queued until enough tokens have built up, or sent but marked so they can be discarded later if the network is overloaded. The rate of token arrival sets the long-term average rate and the depth of the bucket sets how large a burst is tolerated. The same mechanism can also act as a scheduling algorithm that decides when transmissions will comply with the limits, and it is closely related to the leaky bucket meter.