Leaky Bucket Algorithm – A Brief Explanation
Consider a bucket with a hole at its bottom. Whatever may be the inflow rate of water into the bucket, the outflow rate through that hole is constant. To be clearer, if the bucket has any water, the outflow rate is constant. If there is no water, outflow rate is zero. When the bucket is full, incoming water simply spills out.
This principle of the leaky bucket algorithm can be used to control or prevent congestion in networks. An interface containing such a leaky bucket interface is placed between each host and the network. Host may be sending packets at its own rate. All these packets are stored in the interface and are released at a constant rate. For example one packet for each clock tick.
If the queue at the interface is full, incoming packets will be discarded. Thus the rate at which packets are released into network is predictable. So, it is very easy to prevent congestion. When packets are variable size, we can regulate the traffic to be released in to network at a constant rate of ‘bytes per clock tick. However, if packets are of fixed size, this constant rate is ‘packets per clock tick’ in Leaky Bucket Algorithm.