# GATE2016-1-54

16.3k 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
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.
4
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 .
33

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
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
2

'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)$

Edited:

$\\ 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$

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.

1
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.

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 .

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
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

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

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

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 Well a brilliant explanation has already been given, but I'm just sharing my interpretation that may make it a bit easier.

In token bucket algorithm, suppose if I want to send 1MB data, I need to have 1MB of tokens.

Here, we need to transmit 12MB of data, so we need to generate 12 MB of tokens.

The bucket capacity is 1MB and it has been stated that the bucket is full. So we already have 1 MB tokens available, now remaining only 11 MB of data. So, we require only 11 MB of tokens to be generated.

Now, token generation rate is 10 MBps:

10 MB ---> 1 sec

so 11 MB ---> ?

which is equal to 11/10 sec i.e. 1.1 sec

PS: Correct me if I'm wrong.

## Related questions

1
6.6k views
An IP datagram of size $1000$ $\text{bytes }$arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is $100$ $\text{bytes }$. Assume that the size of the IP header is $20$ $\text{bytes }.$ The number of fragments that the IP datagram will be divided into for transmission is________.
A sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames are of size $1000$ bytes and the transmission rate at the sender is $80$ Kbps (1 Kbps = 1000 bits/second). Size of an acknowledgment is $100$ bytes and the transmission ... $100$ milliseconds. Assuming no frame is lost, the sender throughput is ________ bytes/ second.
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &5 \\ 2&0 &5 &8 \\ 8&5 &0 &x \\ 5& 8 &x &0 \end{bmatrix}$ The largest possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________