Have you been to a restaurant or any food services? Let’s be more friendly. Have you been to a street food stall? Imagine the two situations, the presence of a crowd and a few people. Will the delivery rate be the same? Will he supply the orders in the same way in both scenarios? Of course, No! He will try as fast as to deliver. He will first empty (deliver) the earlier orders and take the next, considering customer priority. Let us now apply this to our topic.
Prerequisite zone:
Leaky bucket: It is one of the traffic shaping algorithms that provide the network with a constant network rate independent of the incoming traffic to the bucket or buffer. What exactly is a bucket and how this algorithm works? Take a quick look and come back! I’ll wait for a couple of minutes.
Bucket: A place where data is stored temporarily before putting the data (or packets) to the transmission link.
Burst: A high transmission rate in a short interval of time.
Committed Information Rate (CIR): The amount of data that can be sent to a network per unit interval of time is CIR. This is often referred to as the mean rate flow.
Committed Burst Size (CBS): It specifies that the maximum number of bytes that can be sent to a network in a very short interval of time. In other words, when the time interval approaches near zero, CBS represents the number of packets that can be instantaneously sent to the network, which is practically not possible.
The terms could be more technical or formal, but we will try to make them simpler while we go further.
If you have gone through the Leaky bucket algorithm, there are a few disadvantages to it. If the bucket is completely filled, then the packets are lost. This is where our street food concept (just an analogy) or Token bucket algorithm comes into the picture.
A token bucket algorithm is a mechanism that allows the desired level of burstiness within a flow by limiting its average rate and maximum burst size. It has both the bucket and queue or data buffer.
The token bucket permits bursty traffic but bounds it. It guarantees that the burstiness is bounded so that the incoming flow will not exceed the capacity of the bucket (CIR).
Let’s understand this by an example.
Example:
Let’s say we have the following values. CIR=2.4 Mbps; CBS=3000 bytes and a burst of duration 10 millisec. We can understand from the question that, there are 3000 incoming tokens in a burst of 10 millisec such that the information rate should not exceed 2.4 Mbps. Now the CBS is our bucket size and CIR is the incoming flow to our bucket.
Now, at 10 millisec our burst size is 3000 tokens. Refer to the below figure.
As there can’t be a better example to explain the concept, the example has been directly imported from ScienceDirect.com
Assume that the token bucket contains 3000 tokens when time t=0. At time t=1 millisec, packet A of size 1000 bytes arrives. Since the bucket contains enough tokens, the packet is immediately transmitted and 1000 tokens are removed from the bucket leaving only 2000 tokens in the bucket. Now, packet B of size 1500 bytes arrives at t=5 millisec and that is also transmitted immediately since 1500 tokens are available in the bucket. After packet B is transmitted, the bucket is left with 500 tokens. At t=8 millisec, packet C of size 700 bytes arrives. Since there are not enough tokens in the bucket, packet C is queued.
A fresh set of 3000 tokens is credited to the bucket at t=10 millisec (burst time). However, there are already 500 tokens, and thus, only 2500 of the new 3000 tokens are added so that the total does not exceed the burst size of 3000 tokens. The rest of the tokens are discarded (tokens are discarded, not the packets). Now the packet C can be transmitted as the bucket has enough tokens.
Thus, it departs at t=10 millisec and the bucket is left with 2300 tokens after deducting 700 tokens for packet C. Packet D of size 2000 bytes that arrive at t=12 millisec is immediately transmitted leaving only 300 tokens in the bucket. Now packet E of size 1700 bytes and F of size 1600 bytes, which arrive at t=1 millisec and t=18 millisec, respectively, are queued since not enough tokens are available.
At t=20 millisec another fresh set of 3000 tokens is credited to the bucket. Out of these, 300 tokens are discarded since 300 tokens from the previous interval were present in the bucket. Now packet E is transmitted, as sufficient tokens are available after a delay of 6 millisec. The remaining 1300 tokens are not enough for packet F.
Thus, it has to wait until the next token interval when a new set of tokens arrives at t=30 millisec. Finally, packet F is transmitted at t=30 millisec after a delay of 12 millisec.
If the things are unclear, just give it a second read.
We can see that a total of 8500 bytes was transmitted in an interval of 30 millisec, and thus, the rate of transfer is 2.26 Mbps (= 8500×8/(30×10-3)), which is less than the mean rate of 2.4 Mbps. The above calculation is in (bits per sec); 1 byte=8 bits so 8500*8 bits and 1 milli sec= 10-3 so 30*10-3 sec. and further conversion is to Mbps.
Got why the imaginary situation has taken? Independent of the size of the incoming packets, they are filled to the bucket by removing (delivering) the existing tokens to the network.
What’s happening in the above example? When the new packets are arriving, the existing tokens are removed (and the packets are sent) and assigned again to the incoming packets. In this way, if the larger packets arrive at the bucket, they are either queued or transmitted to the network. But, if we observe, the output flow is irregular. The output is almost directly proportional to the incoming size.
How the flow can be regulated? If you remember, the flow in the Leaky bucket is constant independent of the incoming flow. What if we add a leaky bucket after the token bucket? Yes, we have overcome the flaw.
The disadvantage in the Leaky bucket is the overflow of packets and is solved using the Token bucket. The disadvantage in the Token bucket is its irregular flow and is resolved using the Leaky bucket. So, using the algorithms in conjunction leaves the network in a steady and efficient state.
Leaky bucket Vs Token bucket
| Leaky Bucket | Token Bucket |
| The output flow is constant. | The output flow is irregular. |
| If there are no packets in the bucket, there will be no transmission. | If there are no tokens in the bucket, there will be no transmission. |
| Bursty traffic can be regulated by the Token bucket. | Irregular flow can be regulated by the Leaky bucket. |
| The packets are discarded when the bucket overflows. | The packets are queued when the bucket overflows. |
Techprodezza 
This really helped a lot ! Thank you 🙂
LikeLiked by 1 person
We are glad that it helped Aayush.
LikeLike