Leaky Bucket Algorithm

The leaky bucket algorithm is a method of temporarily storing a variable, number of requests and organizing them into a set-rate output of packets in an asynchronous transfer mode network. The leaky bucket is used to implement traffic policing and traffic shaping in Ethernet and cellular data network.

Suppose we have a bucket in which we are pouring water in a random order but we have to get water in a fixed rate, for this we will make a hole at the bottom of the bucket. It will ensure that water coming out is in a some fixed rate, and also if bucket will fill we will stop pouring in it.

The input rate can vary but the output rate remains constant. Similarly, in networking, a technique called leaky bucket can smooth out bursty traffic. Bursty chunks are stored in the bucket and sent out at an average rate.

Assume that the network has committed a bandwidth of 3 Mbps for a host. The use of the leaky bucket shapes the input traffic to make it conform to this commitments. The host sends a burst of data at a rate of 12 Mbps for 2 sec, for a total of 24 Mbits of data. The host is silent for 3 sec for a total of 6 Mbits of data. In all, the host has sent 30 Mbits of data in 10 sec. The leaky bucket smooths the traffic by sending out data at a rate of 3 Mbps during the 10 sec. Without the leaky bucket, the beginning burst may have hurt the network by consuming more bandwidth that is set aside for this host. We can also see that the leaky bucket may prevent congestion.

A simple leaky bucket algorithm can be implemented using FIFO queue, A FIFO queue holds the packets. If the traffic consists of fixed size packets, the process remove a fixed number of packets 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 following is  an algorithm for variable length packets:

1. Initialize a counter to n at the tick of the clock.

2. If n is greater than the size of the packet, send the packet and decrement the counter    by the packet size. Repeat this step until n is smaller than the packet size.

3. Reset the counter and go to step 1.