Token Bucket Algorithm
The token bucket algorithm is an algorithm used in packet-switched computer networks to ensure that data transmission in the form of packets does not cross its bandwidth.
To understand the algorithm, we can assume a bucket that is getting filled with tokens. The bucket is of limited size, and the tokens represent packets of predetermined size.
Whenever a packet wants to enter the bucket, the bucket checks its size and compares it with the defined limit of the bucket, if it does not go above the limit, it is allowed or else it is dropped.
For better understanding it can be divided into the following steps:
- Every 1/r second a token is added to the bucket.
- The capacity of the bucket is to hold b tokens.
- When it has reached capacity and a token arrives, it is dropped or discarded.
- Assuming a packet of n bytes comes, and there are already n tokens in the bucket, those tokens are removed and the packet is sent to the network. Or if there is lesser than n tokens, then no tokens are removed and the packet is said to be non-conformant.
It is used in traffic policing or traffic shaping.
In the case of traffic policing, non-conforming packets may be discarded or the priority may be reduced.
In the case of traffic-shaping, the packets are delayed until they are conformed.
It is done to protect the network from an overflow of traffic or bursty traffic. Traffic shaping is mostly used in the network interfaces in hosts to prevent transmissions from being discarded for traffic management.
Reference