Leaky Bucket Algorithm
Leaky bucket algorithm is one of the two traffic shaping algorithms.
Traffic shaping is a mechanism to control the traffic in a network. Before the Network layer can guarantee Quality of Service, it needs to ensure there is traffic. Traffic shaping reduces congestion and regulates the rate of data transmission.
To understand the leaky bucket algorithm, we can take the example of a bucket into which there is an active but random flow of water. To get water at a fixed rate, we make a hole at the bottom of the bucket. This ensures the water comes at a fixed rate of flow and if the bucket is full, we stop the flow of water into the bucket.
In this way, the input rate varies, but the output rate remains the same.
In networking, the leaky bucket algorithm is used to smooth out bursty traffic. The bursty chunks of traffic are stored in the bucket and sent out at an average and constant rate.
It prevents congestion, and also without this algorithm, the burst at the beginning can hurt the network by using more bandwidth than set aside for this particular host.
It can be implemented by using a FIFO queue, it holds the packets. If the traffic consists of packets of fixed size then the process can remove a fixed number of packets from the queue.
And for variable-sized packets, the algorithm uses the following approach:
- It initializes a counter to n.
- If n is greater than the size of the packet, it sends the packet and decrements the counter by the packet size.
- It keeps sending packets and decrementing the counter value till n is smaller than the packet size.
- Then it resets the counter and repeats from step 1.
Reference