Leaky bucket

Although the leaky 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 rate at which data is injected into a network, smoothing out "burstiness" in the data rate.

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 distinct properties and are used for distinct purposes [#REF| [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.

Uses

The leaky-bucket implementation is used to control the rate at which traffic is sent to the network (see Figure 1). A leaky bucket provides a mechanism by which bursty traffic can be shaped to present a steady stream of traffic to the network, as opposed to traffic with erratic bursts of low-volume and high-volume flows.

The leaky-bucket algorithm

The algorithm can be conceptually understood as follows:
*Consider a bucket with a hole in the bottom.
*If packets arrive, they are placed into the bucket. If the bucket is full, packets are discarded.
*Packets in the bucket are sent at a constant rate, equivalent to the size of the hole in the bucket.

The Generic Cell Rate Algorithm used in traffic shaping of ATM networks is equivalent to the leaky bucket algorithm.

In one of the earliest publications mentioning the leaky bucket algorithm, J.S. Turner describes it like this [Cite journal
issn = 0163-6804
volume = 24
issue = 10
pages = 8-15
last = Turner
first = J.
title = New directions in communications (or which way to the information age?)
journal = Communications Magazine, IEEE
date = 1986] :

"A counter associated with each user transmitting on a connection is incremented whenever the user sends a packet and is decremented periodically. If the counter exceeds a threshold upon being incremented, the network discards the packet. The user specifies the rate at which the counter is decremented (this determines the average bandwidth) and the value of the threshold (a measure of burstiness)."

Automobile traffic analogy

An appropriate analogy for the leaky bucket is a scenario in which four lanes of automobile traffic converge into a single lane. A regulated admission interval into the single lane of traffic flow helps the traffic move. The benefit of this approach is that traffic flow into the major arteries (the network) is predictable and controlled. The major liability is that when the volume of traffic is vastly greater than the bucket size, in conjunction with the drainage-time interval, inward traffic for the bucket and beyond bucket capacity, is discarded [#REF| [1]

Inefficiency of the leaky-bucket implementation

The leaky-bucket implementation does not efficiently use available network resources. Because its leak rate is a fixed parameter, there will be many instances when the traffic volume is very low and large portions of network resources (bandwidth in particular) are not being used. Therefore no mechanism exists in the leaky-bucket implementation to allow individual flows to burst up to port speed, effectively consuming network resources at times when there would not be resource contention in the network. The token bucket implementation does however accommodate traffic flows with bursty characteristics [#REF| [1] . The leaky-bucket and token bucket implementations can be combined to provide maximum efficiency and control of the traffic flows into a network.

ee also

*Token bucket
*Traffic shaping
*Rate limiting
*Congestion Avoidance in Broadband Networks
*The Generic Cell Rate Algorithm

References

* "Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice" by John Evans, Clarence Filsfils (Morgan Kaufmann, 2007, ISBN 0-12-370549-5)

* Ferguson P., Huston G., Quality of Service: Delivering QoS on the Internet and in Corporate Networks, John Wiley & Sons, Inc., 1998.