Token Bucket Algorithm	Leaky Bucket Algorithm
It depends on tokens.	It does not depend on tokens.
If bucket is full, token is discarded but not the packet.	If bucket is full, then packets are discarded.
Packets can only transmit when there are enough tokens.	Packets are transmitted continuously.
Allows large bursts to be sent at faster rate. Bucket has maximum capacity.	Sends the packet at a constant rate.
The bucket holds tokens generated at regular intervals of time.	When the host has to send a packet , packet is thrown in bucket.
If there is a ready packet , a token is removed from Bucket and packet is send.	Bursty traffic is converted into uniform traffic by leaky bucket.
If there is no token in the bucket, then the packet cannot be sent.	In practice bucket is a finite queue outputs at finite rate.

Leaky bucket algorithm shapes bursty traffic into fixed-rate traffic by averaging the data rate. It may drop the packets if the bucket is full. But this technique is very restrictive. It does not credit an idle host. For example, if a host is not sending for a while, its bucket becomes empty. If the host has bursty data, the leaky bucket allows only an average rate. The time when the host is idle is not take into account. On the other hand, token bucket algorithm allows idle hosts to accumulate credit for the future in the form of tokens. And that is how it overcomes the shortcoming of leaky bucket algorithm.

Working of Token Bucket Algorithm

It allows bursty traffic at a regulated maximum rate. It allows idle hosts to accumulate credit for the future in the form of tokens. The system removes one token for every cell of data sent. For each tick of the clock the system send n tokens to the bucket. If n is 100 and host is idle for 100 ticks, bucket collects 10000 tokens. Host can now consume all these tokens with 10 cells per tick.

Token bucket can be easily implemented with a counter. The token is initiated to zero. Each time a token is added, counter is incremented to 1. Each time a unit of data is sent, counter is decremented by 1. When the counter is zero, host cannot send data.

Steps Involved in Token Bucket Algorithm

Step 1: Creation of Bucket: An imaginative bucket is assigned a fixed capacity, known as “rate limit”. It can hold up to a certain number of tokens.

Step 2: Refill the Bucket: The bucket is dynamic; it gets periodically filled with tokens. Tokens are added to the bucket at a fixed rate.

Step 3: Incoming Requests: Upon receiving a request, we verify the presence of tokens in the bucket.

Step 4: Consume Tokens: If there are tokens in the bucket, we pick one token from it. This means the request is allowed to proceed. The time of token consumption is also recorded.

Step 5: Empty Bucket: If the bucket is depleted, meaning there are no tokens remaining, the request is denied. This precautionary measure prevents server or system overload, ensuring operation stays within predefined limits.

Advantage of Token Bucket over Leaky Bucket

• If a bucket is full in tokens, then tokens are discarded and not the packets. While in leaky bucket algorithm, packets are discarded.
• Token bucket can send large bursts at a faster rate while leaky bucket always sends packets at constant rate.
• Token bucket ensures predictable traffic shaping as it allows for setting token arrival rate and maximum token count. In leaky bucket, such control may not be present.
• Premium Quality of Service(QoS) is provided by prioritizing different traffic types through distinct token arrival rates. Such flexibility in prioritization is not provided by leaky bucket.
• Token bucket is suitable for high-speed data transfer or streaming video content as it allows transmission of large bursts of data. As leaky bucket operates at a constant rate, it can lead to less efficient bandwidth utilization.
• Token Bucket provides more granular control as administrators can adjust token arrival rate and maximum token count based on network requirements. Leaky Bucket has limited granularity in controlling traffic compared to Token Bucket.

Disadvantages of Token Bucket Algorithm

• Token Bucket has the tendency to generate tokens at a fixed rate, even when the network traffic is not present. This is leads of accumulation of unused tokens during times when there is no traffic, hence leading to wastage.
• Due to token accumulation, delays can introduced in the packet delivery. If the token bucket happens to be empty, packets will have to wait for new tokens, leading to increased latency and potential packet loss.
• Token Bucket happens to be less flexible than leaky bucket when it comes to network traffic shaping. The fixed token generation rate cannot be easily altered to meet changing network requirements, unlike the adaptable nature of leaky bucket.
• The implementation involved in token bucket can be more complex, especially due to the fact that different token generation rates are used for different traffic types. Configuration and management might be more difficult due to this.
• Usage of large bursts of data may lead to inefficient use of bandwidth, and may cause congestion. Leaky bucket algorithm, on the other hand helps prevent congestion by limiting the amount of data sent at any given time, promoting more efficient bandwidth utilization.

Frequently Asked Questions on Token Bucket Algorithm

What is leaky bucket algorithm?

Leaky bucket algorithm converts bursty traffic into a fixed rate traffic by maintaining a constant data output rate. Similar to water leaking from a bucket at a consistent rate, bursty data is stored in the bucket and sent out at an average rate. However, a drawback is that the leaky bucket imposes a constant data flow, disregarding the idle periods of the host and limiting adaptability to bursty data patterns.

Where is token bucket algorithm used?

Token bucket algorithm is generally used in packet-switched and telecommunication networks. It can be used to filter the requests depending on the levels of traffic currently present. It can find usage in functionalities like Spike Arrest and Rate Limiting operations.

What are the disadvantages of token bucket?

The main drawback of the token bucket algorithm is that it can be exploited by malicious or greedy clients. Since the client can make requests as fast as it wants, it can consume all the tokens in the bucket and starve other clients from accessing the API.