The Gateway to Computer Science Excellence
+63 votes
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of $1$ $\text{megabyte}$ and the maximum output rate is $20$ $\text{megabytes}$ per $\text{second}$. Tokens arrive at a rate to sustain output at a rate of $10$ $\text{megabytes}$ per $\text{second}$. The token bucket is currently full and the machine needs to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.
in Computer Networks by Loyal (7.2k points)
edited by | 13k views
Wasn't it out of course?
According to official key answer for the above question should be 1.1 sec. Can someone explain the correct procedure.
obviously not.
dear downvoters, it was in syllabus. So i dnt know the reason behind downvoting. And token bucket question came in 2008 also when IISC made the paper.
It is in congestion control .

This diagram might help. For a packet to get transmitted into the network it needs to remove a token. If the token bucket is empty packet has to wait.

Because token generation rate is 'r', the maximum no of packets that can enter the network at any interval of time 't' is given by 

r.t + b

So, here I have considered packets to be of size 1MB.

b = 1MB (given)

r = 10MBps

Data to transfer = 12MB.


10.t + 1 = 12

=> 10.t = 11

=> t = 1.1sec (ans)


here tokens arrive at a rate to sustain an output rate of 10mbps doesnt mean the net rate

at time t tends to infinity the (C+r*t)/t   becomes r which is the input rate hence the rate to sustain at 10 we should maintain an inflow of 10 inflow will become outflow as time tends to infinity and maximum output rate is determined by the network we can only send that much though we can send more we can send only at that rate

so the notion of 20-R=10 is wrong according to this

however this doesnt affect the answer or R value of 10 remains the same

please correct me if  i am wrong but the procedure is same
token ring is out of syllabus not token bucket
Here in this question it is mentioned that


"Tokens arrive at a rate to sustain output at a rate of 10megabytes per second"


Does not this means that output of token bucket is 10 mb/sec ? And tokens have to arrive in such a rate that this output rate of 10mbps is sustained?
In your given solution, it is not dependent of the outflow rate, How it is? Pls explain.
Token Bucket is already filled with 1 MB of tokens and machine needs to send 12 MB of data. Since we already have 1 MB of tokens in the bucket we can immediately transfer 1 MB of the data.

Now we are remaining with 11 MB of data to be transferred for which we need to generate tokens. To generate 11 MB of tokens time taken = $\dfrac{11 MB}{10 MBps} = 1.1s$

This entire thing is possible bcz output rate is higher than token generation rate and so we are only bothered about token generation rate

'The token bucket is currently full' and the machine needs to send 12 megabytes of data.

$\\ Max\ rate=\dfrac{c+rt}{t}\\ \\ 20Mbps=\dfrac{11Mb+10Mbps\times t}{t}\\ \\ 20Mbps\times t-10Mbps\times t=11Mb\\ \\ 10Mbps\times t=11Mb\\ \\ t=1.1sec$

$Ans: 1.1\ sec$ $(Wrong:X)$


$\\ Max\ rate=\dfrac{c+rt}{t}\\ \\ 20Mbps=\dfrac{1Mb+10Mbps\times t}{t}\\ \\ 20Mbps\times t-10Mbps\times t=1Mb\\ \\ 10Mbps\times t=1Mb\\ \\ t=0.1sec$

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.

Remaining data=10 MB

It will be transmitted at token arrival rate & not the maximum output rate.Hence 1sec more is required to transmit the remaining data of 10 MB

$\therefore0.1sec+1sec=1.1sec$ $\checkmark$



@Kushagra गुप्ता Max Bucket capacity (c) is 1Mb. How did you get 11Mb ?


@Syedarshadali Yes you might be right, I must have taken that value wrongly. Let me verify and then change the comment. Thanks.

Initially if the bucket is completely full then it has 1 MB of data. (if nothing is given about token take 1 Byte = 1 token).

Now whenever we take the maximum output rate (M) then it's equal to initial window size (C) completely full means 1 MB in this case + output rate * time .....Now here the output rate is rate at which the data goes out from the sender, these is the real output rate. But if we want to calculate Maximum output rate,

$M = \frac{C+RT}{T}$

where C = Window Size
           R = actual output Rate
           M = maximum output rate

difference between maximum and actual output rate is in maximum rate is we take the window size full initially + data sent in time T ..means R*T (as rate is R bytes per sec. then in time T how much will be sent? it's nothing but R*T)
now as we are talking about rate which is nothing but per unit time therefore we have divided by T in the formula...

So this formula says in time T we can send C (window size which is full) + data sent in time T which is R*T
Now, from these we can calculate time ,
$T = \frac{C}{M-R}$

now if put values given in question we get,
$T=\frac{1}{20-10}$ = .1 Sec.
means in .1 sec we have sent 1 MB (initial window is full) and .1*10 = 1 MB
so total 2 MB sent in 0.1 sec.
now to sent remaining 10 MB , Here is where actual output rate will be used which is 10 MB/s so ,
in 1 sec we can send 10 MB means only 1 sec reqd. for remaining 10 MB

so total time to sent 12 MB = .1 sec (for 2 MB) + 1 Sec (for remaining 10 MB)
                                            = 1.1 sec ans.

15 Answers

0 votes


1 (First second)

1MB(capacity)+10MB(generated in 1 second)=11MB

11MB< generate more.

NOT send because 12 MB have to be send at once. 11MB

2(next second)

t second



So time is less than a second for the generation of 12 MB.


t=0.1 sec


now we have 12MB Tokens in bucket 


      0 MB in bucket.

Hence in total time of 1+0.1 sec=1.1 we are able to send 12 MB .

by Active (3.5k points)
0 votes
we know formulae

( Capacity of token bucket + input Token Rate * Burst Time) / Burst Time = Burst speed

(1 + 10 * T ) /T = 20 => T= 0.1 sec

hence for 0.1 sec  burst speed was 20MBps , In this much time we can send 0.1 * 20 MBps = 2MB

After this bust time speed become 10 MBps and we want to send remaining 10 MB

It will take 10MB / 10 MBps =  1 sec

Total 1.1 sec
by Loyal (5.3k points)
0 votes
I will simplify the question.......Firstly since the output rate is more than incoming rate, we will calculate the time when the bucket will be empty, that is


capacity +(input rate x S)  =(output rate x S)

1+ (10 x S) =(20 x S)

S=0.1 sec this time bucket will be empty, till this time we have transferred data at max rate of 20 MB/sec, thus we have transferred 0.1  x 20 =2 MB , now we have to transfer 10 MB more, since the bucket is empty, now the output rate will be equal to input rate, thus

to transfer 10 MB at speed 10 MB/sec, it will require 1 sec.



Thus ans= 1 + .1 =1.1 sec
by Active (1.2k points)
0 votes

Let, C= Capacity of token bucket=1MB,

M= Maximum number of packets that can enter in network during a time interval 't'= C+rt



12 = 1 +10t


by (73 points)
0 votes

We know number of packets that can be sent at t sec is --> c+rt

Therefore we can write -->


=> (12-1)/10 second =t

=> t= 1.1 second

by Active (3.6k points)
0 votes
Capacity (c) = 1 MB

Max Output Rate (m) = 20 MB/sec
Rate of arrival of token (r) =  10 MB/sec

Time taken to send 1 MB of data =  c / m-r = 1 / 20 -10 = 0.1

 Since, the bucket is initially full, it already has 1 Mb to transmit so it will be transmitted instantly.
So, we are left with only (12 – 1) Mb, i.e. 11 Mb of data to be transmitted.
Therefore, time required to send the 11 MB will be 11 * 0.1 = 1.1 sec
by (495 points)
0 votes

The Answer is 1.1 sec.

ago by Active (4.3k points)

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
50,737 questions
57,284 answers
104,863 users