Leaky bucket

The leaky bucket is an algorithm built on the picture of a bucket with a constant leak. If water is poured in faster on average than it leaks out, or if more is poured in at once than the bucket can hold, the bucket overflows. Applied to network traffic, the same picture decides whether a sequence of packets or other discrete events stays within agreed limits on its average rate and its peak rate, so that it can be used in traffic policing, traffic shaping and the scheduling of data transmissions on packet-switched and telecommunications networks. Two versions appear in the literature. In the meter version the bucket is a counter that is raised as each packet arrives and lowered at a fixed rate, and it only checks conformance. In the queue version the bucket is a queue that holds packets and releases them at a fixed rate, which smooths the traffic. The meter version is the mirror image of the token bucket, and the generic cell rate algorithm used for Asynchronous Transfer Mode networks is a form of it. Jonathan S. Turner is credited with the original description.