Saturday, August 31, 2013
- Telecommunications networks and the packet switched computer networks make use of the leaky bucket algorithm for checking the data transmissions.
- This check is carried out in the form of packets.
About Leaky Bucket Algorithm
- This algorithm is used for determining whether the data transmissions confirm to the limits that have been defined for the burstiness and bandwidth.
- Leaky bucket counters also use the leaky bucket algorithm for detecting the peak or the average rate of the stochastic or random events and processes and if they are exceeding the predefined limits.
We shall take analogy of a bucket for explaining this algorithm.
- Consider a bucket having a hole in its bottom through which the water it has will leak away.
- The rate of leakage is constant if it is not empty.
- We can intermittently add water to it that is in short bursts.
- But if a large amount of water is added to it in one go, the water will exceed the bucket’s capacity and overflow will occur.
- Hence, it is determined using this leaky bucket algorithm that whether or not adding water to it will make up the average rate or will exceed it.
- Leak rate sets the average rate of adding the water and depth of the bucket decides the amount of water to be added.
- Asynchronous transfer mode networks use the generic cell rate algorithm which is one of the versions of the leaky bucket algorithms.
- At the user network interfaces, these algorithms are used in the usage/ network parameter control.
- The algorithm is also used in network-network interfaces and inter-network interfaces for protecting networks from the overwhelming traffic levels through the connections in the network.
- A network interface card can be used on a network using ATM for shaping the transmissions.
- This network interface card might use an equivalent of the generic cell rate algorithm or this algorithm itself.
- The leaky bucket algorithm can be implemented in two different ways both of which are mentioned in the literature.
- It appears as if there are two distinct algorithms that are together known as the leaky bucket algorithm.
About Token Bucket Algorithm
- At an interval of every 1/r seconds the token bucket algorithm adds a token to a bucket.
- The maximum number of tokens that can be handled by a bucket are b.
- Any token above this limit is rejected by the bucket.
- When the bucket receives a packet from the network layer consisting of n bytes, the n numbers of tokens are taken out from the bucket and then the packet is transmitted in to the network.
- If number of tokens available is less than n, the packet is treated as being non-conformant.
- A bucket with a fixed capacity is associated with some virtual user and the rate at which it leaks is fixed.
- No leakage occurs if there is nothing in the bucket.
- Some water has to be added to the bucket in order to make the packet conform-ant.
- No water is added to the bucket if adding this amount of water will cause the bucket to exceed its capacity.
- Therefore, we can see that one algorithm adds something constantly to the bucket and removes also for conforming packets.
- The other algorithm removes something constantly and adds something for confirming packets.
- Both the algorithms are same in effectiveness and this is why the two see each the same packet as non-confirming or confirming.
- The leaky bucket algorithm is often used as meter.