Congestion Control Algorithm

We already know congestion and congestion control in detail. Now needs to understand the congestion control algorithm that is used to reduce traffic in a network.

We will discuss two congestion control algorithms here. Both are having their pros and cons, which we will discuss later.

Leaky Bucket Algorithm
Token Bucket Algorithm

Let's discuss each in detail,

1. Leaky Bucket Algorithm

The leaky bucket algorithm ensures data flow (in packets) with a fixed rate throughout the network to avoid traffic. It will have an interface that takes data packets at an unregulated rate and send them at a fixed rate. Now, we will look at an example to understand it in a better way.

In the first half of the above diagram, the water in the bucket is dipping through the source(consider it a tap). No matter at which rate the water is dipping in the bucket, the water will flow out at a constant rate only if there is a hole in the bucket. As the water is dipping at an unregulated rate, to some extent, the bucket will get full and will not take any more water. Water will start flowing out of the bucket, so the source will stop pouring water until vacant space to avoid loss.

Now, we will understand the 2nd half (implementation part) of the diagram stepwise along with its comparison with the above description.

Here Host computer will act as a tap(source of water), and when he wants to send data, he will throw data packets in the interface containing buffer(similar to the leaky bucket).
An interface containing a leaky bucket will send packets in the network at a constant rate.
Once the interface containing packets gets full; the source will stop sending data packets anymore. If not, they will get lost.

The leaky bucket algorithm is effective, but due to having the fixed rate at which data packets can transmit over the network, it may be slow when there is lots of packet in the queue to transmit.

2. Token Bucket Algorithm

The token bucket algorithm provides flexibility while dealing with busty traffic. It will speed up its output speed, which was misses out there in the leaky bucket. In the leaky bucket, the packet transmission was done at a constant rate. In contrast, the token bucket algorithm is based on the token generated after a specific time limit and resides in the bucket.

Let's understand this algorithm with the example considering the above figure:

There is a host computer trying to throw five packets in the bucket.But at any instant, only three tokens are generated in the bucket so that it will accept only three packets out of five. The rest will be stuck out there in the queue and will wait for the next tokens to be generated.The three tokens thrown in the bucket will be sent over the network.For the rest two packet, new tokens will be generated to introduce them over the network.

Differences between Leaky bucket and the Token bucket algorithm

Index	Leaky Bucket	Token Bucket
1	Packet will transmit over the network at an average speed.	Packets will transmit only if the token is available.
2	The output rate is fully independent of burst size.	The output rate is dependent on the burst size.
3	It is token independent	It is token dependent
4	When the bucket gets full, pockets get discarded.	When the bucket gets full, the token will get discarded, not packets.