Token bucket algorithm is one of the most commonly used algorithms in network traffic shaping and rate limiting. Usually, token bucket algorithm is used to control the amount of data sent to the network and allow the sending of burst data.
A token bucket with a fixed size can continuously generate tokens at a constant rate. If tokens are not consumed, or the consumption rate is less than the production rate, tokens will continue to increase until the bucket is filled. Tokens generated later will overflow from the bucket. The maximum number of tokens that can be saved in the last bucket will never exceed the size of the bucket.
The packets sent to the token bucket need to consume tokens. The number of tokens consumed is different for packets of different sizes.
Token bucket is a control mechanism that indicates when traffic can be sent according to whether there is a token in the token bucket. Each token in the token bucket represents a byte. If there is a token in the token bucket, traffic is allowed to be sent; If there is no token in the token bucket, traffic is not allowed to be sent. Therefore, if the burst threshold is properly configured and there are enough tokens in the token bucket, traffic can be sent at the peak rate.
The basic process of token bucket algorithm is as follows:
If the average sending rate configured by the user is r, a token is added to the bucket every 1/r seconds;
Assume that a bucket can store and issue at most b tokens. If the token bucket is full when the token arrives, the token will be discarded;
When an n-byte data packet arrives, delete n tokens from the token bucket and send the data packet to the network;
If there are less than n tokens in the token bucket, the tokens will not be deleted, and the packet is regarded as exceeding the traffic limit;
The algorithm allows bursts of up to b bytes, but from the long-term running results, the packet rate is limited to a constant R. Packets exceeding the traffic limit can be handled in different ways:
They can be discarded;
When enough tokens are accumulated in the token bucket, they can be put in the queue for transmission;
They can continue to send, but they need to be specially marked, and these specially marked packets will be discarded when the network is overloaded.
Note: Token bucket algorithm should not be confused with another common algorithm "leaky bucket". The main difference between these two algorithms is that leaky bucket can restrict the data transmission rate, while token bucket algorithm can limit the average data transmission rate and allow some burst transmission. In the token bucket algorithm, as long as there are tokens in the token bucket, data can be transmitted suddenly until the user-configured threshold is reached, so it is suitable for traffic with sudden characteristics.