Leaky Bucket

The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). The leaky bucket algorithm is also used in leaky bucket counters, e.g. to detect when the average or peak rate of random or stochastic events or stochastic processes exceed defined limits.

The Leaky Bucket Algorithm is based on an analogy of a bucket (figure 1) that has a hole in the bottom through which any water it contains will leak away at a constant rate, until or unless it is empty. Water can be added intermittently, i.e. in bursts, but if too much is added at once, or it is added at too high an average rate, the water will exceed the capacity of the bucket, which will overflow. Hence, this leaky bucket determines whether adding some amount of water would exceed or conform to a limit on the rate at which water can be added, set by the leak rate, and a limit on how much water can be added in a burst, set by the depth of the bucket.

There are actually two different methods of applying this analogy described in the literature. These give what appear to be two different algorithms, both of which are referred to as the leaky bucket algorithm and generally without reference to the other method. This has resulted in confusion about what the leaky bucket algorithm is and what its properties are.

In one version of applying the analogy, the analogue of the bucket is a counter or variable, separate from the flow of traffic or scheduling of events. This counter is used only to check that the traffic or events conform to the limits: The counter is incremented as each packet arrives at the point where the check is being made or an event occurs, which is equivalent to the way water is added intermittently to the bucket. The counter is also decremented at a fixed rate, equivalent to the way the water leaks out of the bucket. As a result, the value in the counter when a packet arrives indicates its conformance to the bandwidth and burstiness limits or when an event occurs, its conformance to the average and peak rate limits. So in this version, the analogue of the water is carried by the packets or the events, added to the bucket on their arriving or occurring, and then leaks away. This version is referred to here as the leaky bucket as a meter.

In the second version, the analogue of the bucket is a queue in the flow of traffic. This queue is used to directly control that flow: Packets are entered into the queue as they arrive, equivalent to the water being added to the bucket. These packet are then removed from the queue (first come, first served), usually at a fixed rate, e.g. for onward transmission, equivalent to water leaking from the bucket. As a result, the rate at which the queue is serviced directly controls the onward transmission rate of the traffic. Thus it imposes conformance rather than checking it, and where the queue is serviced at a fixed rate (and where the packets are all the same length), the resulting traffic stream is necessarily devoid of burstiness or jitter. So in this version, the traffic itself is the analogue of the water passing through the bucket. It is not clear how this version of applying the analogy might be used to the check the rates of discrete events. This version is referred to here as the leaky bucket as a queue.

The leaky bucket as a meter is equivalent to (a mirror image of) the token bucket algorithm, and given the same parameters will see the same traffic as conforming or nonconforming. The leaky bucket as a queue can be seen as a special case of the leaky bucket as a meter.

A version of the leaky bucket as a meter, the Generic Cell Rate Algorithm, is recommended for Asynchronous Transfer Mode networks in Usage/Network Parameter Control at User–Network Interfaces or Inter-Network Interfaces or Network-Network Interfaces. The Generic Cell Rate Algorithm, or an equivalent, may also be used to control transmissions by a Network Interface Card onto an ATM network (i.e. on the user side of the User-Network Interface).

Read more about Leaky Bucket:  The Leaky Bucket Algorithm As A Meter, The Leaky Bucket Algorithm As A Queue, Comparison Between The Two Versions of The Leaky Bucket Algorithm

Famous quotes containing the words leaky and/or bucket:

    A leaky faucet, a barking dog—those are things you tolerate.
    Candace Gingrich (b. c. 1967)

    She was a charming middle-aged lady with a face like a bucket of mud. I gave her a drink. She was a gal who’d take a drink if she had to knock me down to get the bottle.
    John Paxton (1911–1985)