Leaky bucket algorithm

 Imagine you have a bucket and you're pouring water into it at random intervals. However, you need to get the water out of the bucket at a fixed rate. To accomplish this, you decide to make a small hole at the bottom of the bucket. By doing this, the water will flow out at a constant rate, even if the input rate varies. Additionally, if the bucket becomes too full, you'll stop pouring water into it to prevent overflowing.

This concept is similar to a technique used in networking called the "leaky bucket" algorithm. It helps to smooth out bursts of traffic by storing the incoming data in a buffer and sending it out at an average rate. This ensures that the output rate remains constant, regardless of fluctuations in the input rate.

Leaky bucket is a traffic shaping technique that can smooth out bursty traffic and ensure that the traffic conforms to a specific committed bandwidth. It works by storing bursty chunks of traffic in a bucket and then sending them out at an average rate.

In the example above, we assume that a network has committed a bandwidth of 3 Mbps for a host. The leaky bucket ensures that the input traffic conforms to this committed bandwidth. For instance, if the host sends a burst of data at a rate of 12 Mbps for 2 seconds, the leaky bucket will smooth out the traffic by sending data out at a rate of 3 Mbps during the same 2 seconds. This prevents the bursty traffic from consuming more bandwidth than is set aside for the host.

A simple leaky bucket algorithm can be implemented using a FIFO (First In First Out) queue. The queue holds the packets, and if the traffic consists of fixed-size packets (e.g., cells in ATM networks), a fixed number of packets are removed from the queue at each tick of the clock. If the traffic consists of variable-length packets, the fixed output rate must be based on the number of bytes or bits.

The algorithm for variable-length packets involves initializing a counter to n at the tick of the clock. The algorithm repeats until n is smaller than the packet size of the packet at the head of the queue. Then, a packet is popped out of the head of the queue, sent into the network, and the counter is decremented by the size of the packet. This process continues until the counter is reset, and the algorithm returns to the beginning.

in below examples

The head of the queue is the rightmost position, and the tail of the queue is the leftmost position

Example: Let n=1000 

Packet=

Since n > size of the packet at the head of the Queue, i.e. n > 200 
Therefore, n = 1000-200 = 800 
Packet size of 200 is sent into the network. 

Now, again n > size of the packet at the head of the Queue, i.e. n > 400 
Therefore, n = 800-400 = 400 
Packet size of 400 is sent into the network.

Since, n < size of the packet at the head of the Queue, i.e.  n < 450
Therefore, the procedure is stopped.

Initialise n = 1000 on another tick of the clock. 
This procedure is repeated until all the packets are sent into the network.

.