The Gateway to Computer Science Excellence
+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.

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.

in Computer Networks by | 2.9k views

1 Answer

+15 votes
Best answer

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

@debashish_deka ,

if initally capacity of token bucket is C  then C tokens will be immediately be present in the network.

C: is the capacity of token bucket
R: every sec we are getting R tokens 

Then the number of packets that can enter the network during a time interval 't' is $C+Rt$

How do you account to these statements ?

Got it :) Thanks :)
@debashish_deka what if bucket is initially empty. Then what will be the time for maximum burst?
According to  me Then input token rate will decide how much time required. No burst (high rate) service.

Please share any other existing method.
was thinking the same. in the formula c should be replaced with 1 then.

 initially empty $\Rightarrow$ C=0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,436 answers
95,257 users