The leaky bucket algorithm is an algorithm that works on the premise that even a bucket with a hole will overflow if the amount of water poured into it is greater than that leaked out. It is used to determine how to control a sequence of events to match the container’s limit without overflowing. In simple terms, it regulates the traffic that goes to a system for processing.
That seems complicated. Think of it this way instead. You have a plant that should be watered at a specific rate; otherwise, it will die. You drill a hole in a bucket to control the amount of water it gets. You then put the bucket with a hole over it and fill it with water. So long as the bucket with a hole doesn’t spill water onto your plant when it overflows, the plant will never get more water than it needs and end up dying.
Read More about the “Leaky Bucket Algorithm”
No matter how much input the leaky bucket gets in the leaky bucket algorithm, its output remains the same. Watch this video for a more detailed explanation:
Here’s a diagram to explain the concept as well.
Leaky Bucket Algorithm Concepts
To use the leaky bucket algorithm successfully for traffic policing or shaping, you need to keep these concepts in mind:
- The bucket has a fixed capacity that leaks content at a fixed rate.
- An empty bucket will stop leaking.
- To make the leak uniform, you need to add a specific amount of content to the bucket. That amount can be the same for all packets (traffic, files, etc.) or proportional to how much you want the packets (leak drops) to be.
Leaky Bucket Algorithm Uses
The leaky bucket algorithm is used in various industries, such as:
The leaky bucket algorithm is a means to temporarily store a varying number of requests to organize them to fit a predetermined packet size. The water from the faucet (input) translates to incoming requests in a network that uses the algorithm. The bucket is the server, which has a fixed size or, in computing terms, processing capability. The water that comes out of the bucket is the output or, in computing’s case, the processed data, which comes out at a constant rate, depending on the server’s processing speed. Excess requests are not processed because they will overflow from the container.
In the telecommunications sector, the algorithm is used to avoid network congestion. Subscribers sign a contract with a provider when they avail of a service. That contract tells both parties how much bandwidth the subscriber can use within a specified period. If the subscriber exceeds that allocation, the packets sent in excess spill out of the bucket. Only a bucketful, in that case, is allowed to flow through the service provider’s network.
Think of it this way. You subscribe to a 25GB data plan each month. When you’ve exhausted the allocated bandwidth, you won’t be able to surf the Web using the device anymore.
The leaky bucket algorithm remains in use today to control application rate limits. One such app is Shopify. Telecommunications companies the world over also use the algorithm to this day to control and limit data traffic. And so do network administrators.