GATE CSE 2016 Set 1 | Question: 54

Question

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}$.

Comments

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.

Therefore,

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

---

https://gateoverflow.in/137521/token-bucket?fbclid=IwAR3KMw-onfZEV1wAJ3nXlNqN7rk0-5HXHxhu6omdYW5wZ75DFcnfoZLcrRU

Also see same type

---

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

---

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$

Ref: https://gateoverflow.in/137521/token-bucket

---

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

---

See the most easy way I can tell you to solve this one is:

Assume whatever token are there in buckets that could be sent at speed of infinity (assume)

Now say our remainingdata is : data – token in buckets earlier

We have to send this remainingdata at given speed of tokens. so we send it in remainingdata/speedOftoken = t(say)

Now very important thing is to check that we have assumed intially some data was sent at infinity, which is not true but say given Max data speed is X. then X*t > total data then we are fine because this could be done, but if not then we would have to make sure additional data will be sent and add that time also..

Follow this numerical every thing will be clear:

Say

1.Bucket capacity intially = 4000B (full of tokens)

2. total data to be sent is say  = 7000B 
3. Token arrive rate say = 100B/s
4. Maximum speed of the transmission is = 150B/s

So we now assume 4000B byte are sent at infinte speed, ok so now we are left with 3000B to send

so to send it we will require say 3000/100 = 30 seconds 

But see we have actually max speed with which we can send so in 30 sec we can send maxdata of 

150*30 = 4500 . So after 30 seconds we are left with 3500B which should require 3500/150 =23.33 additional second.

But say if we had data less than or equal to 4500 then in the given time we would have sent it, so no additional time was required

---

Sir in this situation

10t + 1 = 12

And t = 1.1 sec

Confusion::- at t =1.1 sec the capacity of token bucket is 12mb

And question is asking about data transmission time  from bucket not the capacity. I think it is slightly greater than 1.1 sec

---

Fact is in this problem Ans is not depending on Output rate at all
Only depends on Token rate and size of Bucket

---

My Solution  (please check and correct me if  i am wrong)

https://gateoverflow.in/39720/gate-cse-2016-set-1-question-54?show=420464#a420464

Good Explanation by @Pranavpurkar

https://gateoverflow.in/39720/gate-cse-2016-set-1-question-54?show=374049#c374049

Answer 1

Initially token bucket is full.

 Rate at which it is emptying is $(20-10)$ MBps.

Time taken to empty token bucket of $1$ MB is $\frac{1}{10}$  i.e  $0.1$ sec.

Data send in this time is $0.1*20=2$ MB (rate at which bucket is emptying is different from rate at which data is send) .

Data left to send is $12-2=10$ MB .

Now bucket is empty and rate of token arriving is less than that of going out so effective data speed will be $10$MBps.

Time to send remaining $10$MB will be $1$ sec. So total time is $1+0.1$=$1.1 $sec

Comments

So, if the bucket is not initially empty-
time taken to empty the bucket = capacity/(output rate - input rate) = k
amount of time transmitted in k time = k*transmission rate(output rate) = l

For the remaining data = (total -l)/(output - input)rate

---

Can’t it be like this?

Capacity= 1MB , 

Max o/p rate = 20MBps ,

incoming rate = 10MBps

initially the bucket is full (i.e 1MB)

and it will get out at the Max o/p rate  so ,

20MB →  1s

1MB → (1/20)s   i.e  0.05 s

Now, the remaining data is  (12 – 1) MB = 11 MB

this data will be out at the incoming rate which is 10MBps  so,

10MB → 1s

1MB → (1/10)s  i.e  0.1 s 

Then  11MB → 11* (0.1)s  i.e  1.1 s

Thus the total time to transfer 12MB data is  =   (1.1 + 0.05) s   =   1.15 s

which is in the range from  1.10 to 1.19 

---

@Pranavpurkar @Abhrajyoti00
is my approach correct?
$capacity + rate$ $of$ $ token *t=12MB$
$capacity = 1MB$,$rate=10$
$1MB+10MB*t=12MB$ 
$t=1.1sec$

Answer 2

Short answer

The total time to transmit data in Token Bucket algorithm is the sum of two times -

1. T₁ = Time to transmit data with max. transmission rate as long as the bucket is not empty.
2. T₂ = Time to transmit the remaining data after the bucket is empty. During this time, data can only be sent at the rate at which the tokens are generated.

[If size of data is less than or equal to the bucket capacity then all data will be transmitted before the bucket becomes empty. Therefore, only the first component gives the answer in this case.]

Calculating T₁ -
This is simple, but can be a bit tricky for some people like me. Since, the bucket's capacity is 1 MB, and the effective rate of token removal is 20 - 10 = 10 MBps, therefore the bucket will be emptied in 1 MB /10 MBps = 0.1 s. But, this does not mean that 1 MB data is transmitted in 0.1 s. During this time, 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.

Here, because of the relative nature of the formula used to calculate the time to empty the bucket, some people get confused. To clear the confusion, consider this simple problem.
Q. Two cars A and B start moving at the same time in the same direction at the speeds of 20 kmph and 10 kmph respectively. If B has a head start of 1 km, then what is the distance traveled by A to overtake B.
Ans:- Since both cars start moving at the same time, A must travel the same amount of time as B. So, the answer is simply the product of this time and A's speed, i.e., 20 kmph.
Now, one way to calculate this time is to use the concept of relative speeds. If B is put to rest (i.e, B's speed is decreased by 10 kmph), then A's speed also decreases by the same amount, thus resulting in a relative speed of 20 - 10 = 10 kmph. Since, B is at rest, therefore to overtake B, A only needs to cover the head start distance of 1 km. Therefore, time taken by A to overtake B = 1 km / 10 kmph = 0.1 hr. Clearly, this does not mean that A travels only 1 km. Since, A's actual speed is 20 kmph, therefore distance covered by A = 20 kmph x 0.1 hr = 2 km.

Calculating T₂ -
This is straightforward. Since, the remaining data is 12 - 2 = 10 MB, and the rate of transmission of this data is equal to the rate of token arrival, i.e., 10 MBps, therefore time taken to transmit 10 MB = 10 MB / 10 MBps = 1 s.

Therefore, total time = T₁ + T₂ = 0.1 s + 1 s = 1.1 s

Long Answer

The concept is simple -

• Tokens are produced by the system at a fixed rate, and stored in a bucket having fixed capacity.
• Whenever a packet is transmitted, some tokens are removed from the bucket. How many are removed ? It depends. If all packets are of same size, then one token per packet is OK. Otherwise, one token per byte is deleted. By default, it is one token per byte.
• Transmission can be performed ONLY IF tokens are available in the bucket. If bucket is empty, then packets are queued until sufficient tokens are available.

the rate at which tokens are removed from the bucket is ALWAYS equal to the rate at which the packets are transmitted by the system.

Now comes the central question. "Why are the tokens STORED in a bucket ?" To understand this, consider what would happen if we don't store them !! If tokens are not stored, then the system will always transmit the packets at the same rate at which the tokens are produced. And, this is nothing but the "Leaky Bucket" algorithm, where the packet transmission rate is always fixed.

The "Token Bucket" algorithm with a zero bucket capacity is nothing but the "Leaky Bucket" algorithm.

If the tokens are stored, however, then the system is not limited to the token generation/arrival rate, and can transmit the packets at the maximum transmission rate. The max. transmission rate is generally greater than the token arrival rate.

As long as the bucket contains tokens, they can be removed at the max. possible rate, and so, the system transmits the data at max. transmission rate. But, since the rate of token removal is greater than the rate of token arrival, the bucket eventually becomes empty. After that, the tokens can be removed only at the rate at which they are produced. Therefore, when the bucket becomes empty, the system transmits data at the rate of token arrival.

On pg. no. 409 of the book "Computer Networks" (5th edition) by Tanenbaum, it is clearly stated that -

The host can send full throttle at the maximum transmission rate for a short while until it has drained the bucket...

When it (no. of tokens in the bucket) reaches zero, new packets can be sent only at the rate at which the buffer is filling; there can be no more bursts until the bucket has recovered...

Comments

Best answer

---

beautiful explanation!

---

just perfect👍

Answer 3

Reffer: Token-Bucket .

• Token bucket has a capacity of 1 mega byte (maximum capacity $C$ )

Here  one byte is considered as one token

$\Rightarrow C=1 \text{M tokens}$

• output rate is 20 mega bytes per second ($M=20\text{MBps}$)
• Tokens arrive at a rate to sustain output at a rate of 10 mega bytes per second

$20-R=10$

$\Rightarrow$ Input Rate  $R=10\text{MBps}$

Unlike Leaky Bucket , idle hosts can capture and save up $ c \leq C $ tokens in order to send larger bursts later.

When we begin transfer  the tokens present in token buckt is transmitted at once to the network

ie. if initally capacity of token bucket is 'c'  then c tokens will be instantly be present in the network.

Time to Empty the token bucket

$c$: is the inital capacity of token bucket
$R$: every sec we are getting R tokens
$M$ : evey seconds M tokens are produced

INPUT FLOW : Then the number of packets that are ready to  enter the network during a time interval 't' is $c+Rt$

OUTPUT FLOW : Then the number of packets that are ready to  enter the network during a time interval 't' is $Mt$

INPUT FLOW = OUTPUT FLOW

$\Rightarrow c+Rt = Mt$

$\begin{align*} t&= \frac{c}{M-R} \\ &=\frac{1}{20-10} \\ &=0.1\text{sec} \end{align*}$

• Given that Token bucket is full ($c=C$)

---

Now , We have got  two cases  

• To transfer 1M tokens , Will it be instantly  with t=0
• Or to transfer 1M tokens , we take 10/ 20-10 = 0.1sec ?

To transfer 1M  (inital token) tokens , Will it be instantly  with t=0

Consider the equation

INPUTFLOW = c+Rt

This means that 
" c tokens (initally contained in token bucket  ) are transmitted without any delays "

Unlike Leaky bucket ,  token buckets can keep on reserving token if the sender is idle .Once it is ready to send the packets . Packets will take the token and will be transmitted to the network. $\Rightarrow c $ And then we are adding the $R$ tokens produced in $'t'$ time to finnaly get the INPUTFLOW

$\Rightarrow 1 \text{MB}$ is transmitted instantly . Now we are left with 11 MB to transmit

To trnasfer remaining 11 MB

at $t=0$ we begin transmitting 11 MB data.

at $t=0.1$sec :  1MB  (1 MB transfered)

at $t=0.2$sec :  1MB  (2 MB transfered)

..
..

at $t=1.1$ sec : 1MB (11 MB transfered )

Therefore to transfer 12MB it takes 1.1sec + 0 sec = 1.1 sec

Transfer 1M (inital token) tokens , we take  = 0.1sec

( if it take 0.1 sec for 1MB i could argue that it will take 1.2ssec for 12MB )

then during 0.1sec .   01 *10MBps = 1M tokens are fulled up .

t=0s : begin to transfer  12 MB data.

t=0.1s : 1MB

t=0.2s : 1MB  (2 MB transfered)

t=0.3s : 1MB  (3 MB transfered)
..
..

t=1.2s : 1MB  (12 MB transfered)

Therefore to transfer 12MB it takes 1.2sec

---

Question does clearly mention about this part . Hence it is common practice to always follw the best case .
Therefore the answer would be 1.1 sec
 

---

Reference

• http://www.slideshare.net/vimal25792/leaky-bucket-tocken-buckettraffic-shaping
• http://web.mst.edu/~saifullaha/courses/lecture19.pdf
• https://onl.wustl.edu/Tutorial/Filters,_Queues_and_Bandwidth/NSP_Architecture/Link_Rate.html
• http://quiz.geeksforgeeks.org/gate-gate-cs-2016-set-1-question-64/
• http://www.slideshare.net/UmeshGupta3/leaky-bucket-algorithm

Comments

I am not getting if question says bucket is filled initially with 512 KB (half of 1MB) then what will be the minimum time required to transmit the data??

In other words if bucket is not full initially. Then how much time will it take as for 12 MB and initially full bucket we calculated for remaining 11 MB.

---

thats wrong explanation.

---

20 - R = 10

please explain this part.

 

20 here is Maximum output rate and R here is input rate. what is meant by maximum output rate - input rate ?

Answer 4

Tokens arrive at 10MB/sec, i.e 1 MB in 0.10 sec
Tokens output at 20MB/sec, i.e 1 MB in 0.05 sec

Initially we have 1 MB in token bucket. Lets see what happens using timeline.
Please pay attention. This may seem confusing, understand what happens in between 0 - 0.1 sec

T=0.00,  Bucket contains 1 MB, Output = 0 MB
T=0.05,  Bucket contains 0.5 MB, Output = 1 MB
Since initially bucket is full with 1MB, it will take 0.05 sec to empty it, but during that 0.05 sec we will also get an input of 0.5 MB
T=0.10,  Bucket contains 0.5 MB, Output = 2 MB
At 0.1 sec, the previous 0.5 MB present in bucket + new 0.5 MB data will output, making a total output of 2 MB.
Here onwards everything is streamlined, we will output only when we get data, i.e evey 0.1 sec
T=0.15,  Bucket = 0.5 MB, Output = 2.5 MB
​​​​​​​T=0.20,  Bucket = 0.5 MB, Output = 3 MB
T=0.25,  Bucket = 0.5 MB, Output = 3.5 MB
​​​​​​​T=0.30,  Bucket = 0.5 MB, Output = 4 MB
T=0.35,  Bucket = 0.5 MB, Output = 4.5 MB
​​​​​​​T=0.40,  Bucket = 0.5 MB, Output = 5 MB
T=0.45,  Bucket = 0.5 MB, Output = 5.5 MB
​​​​​​​T=0.50,  Bucket = 0.5 MB, Output = 6 MB
T=0.55,  Bucket = 0.5 MB, Output = 6.5 MB
​​​​​​​T=0.60,  Bucket = 0.5 MB, Output = 7 MB
T=0.65,  Bucket = 0.5 MB, Output = 7.5 MB
​​​​​​​T=0.70,  Bucket = 0.5 MB, Output = 8 MB
T=0.75,  Bucket = 0.5 MB, Output = 8.5 MB
​​​​​​​T=0.80,  Bucket = 0.5 MB, Output = 9 MB
T=0.85,  Bucket = 0.5 MB, Output = 9.5 MB
​​​​​​​T=0.90,  Bucket = 0.5 MB, Output = 10 MB
T=0.95,  Bucket = 0.5 MB, Output = 10.5 MB
​​​​​​​T=1.00,  Bucket = 0.5 MB, Output = 11 MB
T=1.05,  Bucket = 0.5 MB, Output = 11.5 MB
​​​​​​​T=1.10,  Bucket = 0.0 MB, Output = 12 MB

​​​​​​​Hence, It will take 1.1 sec to transmit 12 MB data.

Comments

At t=0.05 sec bucket has 0.5 mb data, so how at t= 0.1 output is 2 mb, bucket has only 0.5 mb of data, so how it can give 1mb data outside. Please explain.