7,379 views
3 votes
3 votes

For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 mega byte and the maximum output rate is 20 mega bytes per second. Tokens arrive at a rate to sustain output at a rate of 10 mega bytes per second. The token bucket is currently full and the machine needs to send 12 mega bytes of data. The minimum time required to transmit the data is _____________ seconds.

https://gateoverflow.in/39720/gate-2016-1-54

How do the answer differ If the bucket is initially filled to capacity with C ( take some suitable value )Megabits ?

Tokens are discarded when the bucket is full

Im not getting how to consider above statement from token bucket algorithm.

1 Answer

Best answer
16 votes
16 votes

From forouzan tcp/ip protocol suite:

The token bucket algorithm allows idle hosts to accumulate credit for the future in the form of tokens. For each tick of the clock, the system sends $n$ tokens to the bucket. The system removes one token for every cell (or byte) of data sent. For example, if $n$ is 100 and the host is idle for 100 ticks, the bucket collects $10,000$ tokens. Now the host can consume all these tokens in one tick with $10,000$ cells, or the host takes $1,000$ ticks with $10$ cells per tick. In other words, the host can send bursty data as long as the bucket is not empty. Figure shows the idea.

 

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


  • The bucket has a capacity. If a host is idle for a long time, then the system will completely fill up the bucket with its maximum capacity of tokens. Token is discarded when bucket is full means token_counter value in token bucket implementation can not go beyond some capacity value C (predefined)

 


$\begin{align*} &\text{If bucket is full initially with capacity = C} \\ &\text{Then,} \\ &\text{Time to empty the bucket } \\ &T= \frac{C}{R_2-R_1} \\ \\&T = \text{Time for which system can support max data delivery at rate } R_2 \end{align*}$

selected by

Related questions

2 votes
2 votes
1 answer
2
abheet asked Jul 31, 2022
1,216 views
Imagine a flow specification that has the maximum packet size 800 bytes, token bucket rate of $5 \times 10^{6}$ bytes/sec. Token bucket size is 1 million byte and the max...
0 votes
0 votes
2 answers
3