12.2k views
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}$.

edited | 12.2k views
+7
Wasn't it out of course?
+1
According to official key answer for the above question should be 1.1 sec. Can someone explain the correct procedure.
+1
obviously not.
+3
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.
0
It is in congestion control .
+26

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.

Therefore,

10.t + 1 = 12

=> 10.t = 11

=> t = 1.1sec (ans)

0
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
0
token ring is out of syllabus not token bucket
+2
+1
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?
0
In your given solution, it is not dependent of the outflow rate, How it is? Pls explain.
0
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
0

'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

0

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

0

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

TIME

TOTAL TOKENS IN BUCKET

TOKENS SEND TOKENS LEFT IN BUCKET
1 (First second)

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

11MB<12MB..so generate more.

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

2(next second)

t second

11MB+10MB=21MB

21MB>20MB

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

11MB+t*10MB=12MB

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)
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 Active (4.9k points)
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  .............at 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)

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

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

M=C+rt

12MB=1MB+10MB/sec*tsec

12 = 1 +10t

t=1.1sec

by (73 points)

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

Therefore we can write -->

12=c+rt

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

=> t= 1.1 second

by Active (3.5k points)
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 (405 points)