Short answer
The total time to transmit data in Token Bucket algorithm is the sum of two times -
- T1 = Time to transmit data with max. transmission rate as long as the bucket is not empty.
- T2 = Time to transmit the remaining data after the bucket is empty. During this time, data can only be sent at the rate at which the tokens are generated.
[If size of data is less than or equal to the bucket capacity then all data will be transmitted before the bucket becomes empty. Therefore, only the first component gives the answer in this case.]
Calculating T1 -
This is simple, but can be a bit tricky for some people like me. Since, the bucket's capacity is 1 MB, and the effective rate of token removal is 20 - 10 = 10 MBps, therefore the bucket will be emptied in 1 MB /10 MBps = 0.1 s. But, this does not mean that 1 MB data is transmitted in 0.1 s. During this time, data is transmitted at the rate of 20 MBps, not at the effective rate of 10 MBps. So, data sent is 20 MBps x 0.1 s = 2 MB.
Here, because of the relative nature of the formula used to calculate the time to empty the bucket, some people get confused. To clear the confusion, consider this simple problem.
Q. Two cars A and B start moving at the same time in the same direction at the speeds of 20 kmph and 10 kmph respectively. If B has a head start of 1 km, then what is the distance traveled by A to overtake B.
Ans:- Since both cars start moving at the same time, A must travel the same amount of time as B. So, the answer is simply the product of this time and A's speed, i.e., 20 kmph.
Now, one way to calculate this time is to use the concept of relative speeds. If B is put to rest (i.e, B's speed is decreased by 10 kmph), then A's speed also decreases by the same amount, thus resulting in a relative speed of 20 - 10 = 10 kmph. Since, B is at rest, therefore to overtake B, A only needs to cover the head start distance of 1 km. Therefore, time taken by A to overtake B = 1 km / 10 kmph = 0.1 hr. Clearly, this does not mean that A travels only 1 km. Since, A's actual speed is 20 kmph, therefore distance covered by A = 20 kmph x 0.1 hr = 2 km.
Calculating T2 -
This is straightforward. Since, the remaining data is 12 - 2 = 10 MB, and the rate of transmission of this data is equal to the rate of token arrival, i.e., 10 MBps, therefore time taken to transmit 10 MB = 10 MB / 10 MBps = 1 s.
Therefore, total time = T1 + T2 = 0.1 s + 1 s = 1.1 s
Long Answer
The concept is simple -
- Tokens are produced by the system at a fixed rate, and stored in a bucket having fixed capacity.
- Whenever a packet is transmitted, some tokens are removed from the bucket. How many are removed ? It depends. If all packets are of same size, then one token per packet is OK. Otherwise, one token per byte is deleted. By default, it is one token per byte.
- Transmission can be performed ONLY IF tokens are available in the bucket. If bucket is empty, then packets are queued until sufficient tokens are available.
the rate at which tokens are removed from the bucket is ALWAYS equal to the rate at which the packets are transmitted by the system.
Now comes the central question. "Why are the tokens STORED in a bucket ?" To understand this, consider what would happen if we don't store them !! If tokens are not stored, then the system will always transmit the packets at the same rate at which the tokens are produced. And, this is nothing but the "Leaky Bucket" algorithm, where the packet transmission rate is always fixed.
The "Token Bucket" algorithm with a zero bucket capacity is nothing but the "Leaky Bucket" algorithm.
If the tokens are stored, however, then the system is not limited to the token generation/arrival rate, and can transmit the packets at the maximum transmission rate. The max. transmission rate is generally greater than the token arrival rate.
As long as the bucket contains tokens, they can be removed at the max. possible rate, and so, the system transmits the data at max. transmission rate. But, since the rate of token removal is greater than the rate of token arrival, the bucket eventually becomes empty. After that, the tokens can be removed only at the rate at which they are produced. Therefore, when the bucket becomes empty, the system transmits data at the rate of token arrival.
On pg. no. 409 of the book "Computer Networks" (5th edition) by Tanenbaum, it is clearly stated that -
The host can send full throttle at the maximum transmission rate for a short while until it has drained the bucket...
When it (no. of tokens in the bucket) reaches zero, new packets can be sent only at the rate at which the buffer is filling; there can be no more bursts until the bucket has recovered...