Subscribe by Email

## Monday, September 2, 2013

### Application areas of leaky bucket algorithm and token bucket algorithm

In this article we discuss about the applications of the leaky bucket algorithm and the token bucket algorithm.

Applications of Leaky Bucket Algorithm
- The leaky bucket algorithm is implemented in different versions.
- For example, the generic cell rate algorithm is a version of this algorithm which is often implemented in the networks using ATM (asynchronous transfer mode).
- The algorithm is applied at the user interfaces in the usage/network parameter control in order to provide protection to the network from the problems of congestive collapse or excess traffic.
- An algorithm equivalent to the generic cell rate algorithm might be used in shaping the transmissions made by the network interface card to a network using ATM.
There are two major applications of the leaky bucket algorithm.
- The first is using it as a counter only for checking whether the events or the traffics confirm to the defined limits or not.
- Whenever a packet arrives at the check point, the counter is incremented.
This is same as adding water to the bucket in an intermittent way.
- In the same way, the counter is decremented as the water leaks out at a constant rate.
- Because of this, the conformance of the packet to the burstiness and bandwidth limits is indicated by the value of this counter whenever a packet arrives.
- Or if an event occurs, the counter checks whether it confirms to the peak and average rate limits.
- So, when the packets arrive or an event occurs, water is added to the bucket and then leaks out. We call this version of the leaky bucket algorithm as a meter.
- Another application of the leaky bucket algorithm involves its use as queue implemented for controlling the flow of traffic.
- This queue maintains a direct control over the flow.
- When the packets arrive, they are put in to the queue.
- This is same as adding water to the bucket.
- The packets are then removed in the order they arrived at a constant rate.
This is same as water leaking out.
- As a result of this, there is no jitter or burstiness in the traffic flow.

Applications of Token Bucket Algorithm
- The token bucket algorithm finds its application in the telecommunications and packet switched computer networks.
- This algorithm is implemented for checking whether the data transmissions confirm to the burstiness and bandwidth predefined limits.
- The token bucket algorithm used in traffic policing and traffic shaping.
- In the former, the packets that are non-conformant are discarded or assigned low priorities.
- This is done for the management of the downstream traffic.
- On the other hand, the packets are kept in delay unless they are conformed in traffic shaping.
- Both of these are used in protecting the network against the burstiness of the traffic.
- Bursty traffic gives rise to congestion problems.
- These algorithms help in managing the bandwidth as well congestion of the network.
- Network interfaces commonly use the traffic shaping process for preventing the discarding of the transmissions by the network’s traffic management functions.
- This algorithm is based up on the analogy of a bucket with fixed capacity.
Tokens are added to this bucket at a fixed rate and represent a single packet of a fixed size.
- When the packet has to be checked whether it confirms to the predefined limits or not, first the bucket is checked if it contains sufficient tokens.
- If sufficient tokens are there, tokens equal to the number of bytes in the packet are removed and the packet is transmitted.
- If sufficient tokens are not there, the packet is said to be non-conformant and the number of tokens in the bucket remain unchanged.