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

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

as the bucket was already filled so bw will be always 10MB Explanation given in ACE key is Maximum burst rate, M = 20 MB Token arrival rate, P = 10 MB Constant rate(bucket o/p), P = 10 MB Bucket capacity, C = 1 MB Time for 1 MB, S =C\(M-P)=1/(20-10)=0.1 For the total message of 12 MB is 1.2 sec. what do you say is it right or wrong?????

---

Hi Vaibhav , Can u pls be more precise. You told in 0.1 sec of time data sent is 0.1*20=2mb. But during that time data ll also come into the tocket bucket @10mbps right?.

And 0.1sec time time it takes to empty the token bucket. How can the data sent out simultaneously.

Please correct me if I am wrong.

---

it is similar to tank and water problem one tap is emptying the tap while other is filling it.

---

That's wat... U have taken only out going in that 0.1 sec that is 0.1*20=2mb.. At the same time data comes into the token bucket right?.. What about that data.. U have mentioned " now that bucket is empty..... Effective data rate is 10 Mbps......"... Y so?.. Bucket ll be filled with tockens during that 0.2 sec rite?

---

yes you are right at during initial 0.1 sec data is coming and going out at the same time but rate at which data is coming is 10mbps and rate at which it is going out is 20 mbps so for bucket it is effectively emptying at rate of 10mbps. But during this time we have enough data so that we can send data at rate of 20mbps but once bucket is emptied then outgoing rate must be same as that of incoming rate.

---

@ Vaibhav .. My point here is at the effective rate (20-10) Mbps the token bucket gets emptied as the outgoing rate is higher... With the effective rate the bucket with 1mb will be emptied in 0.1 sec .. I.e actual work done is sending out 1mb data in 0.1 sec.. It is clear till now... Now again ur calculating 20*0.1 = 2mb outgoing... U have already calculated the effective rate na... Emptying 1mb is done during that 0.1 sec duration... How come outgoing data calculated during that time... Really confused wit ur statement... Pls clarify

---

since initially bucket is full and outing rate is more than that of incoming so bucket is emptying right. but the rate at which bucket is emptying and the rate at which data is sent are two different things.

---

Hi Vaibhav, Thanks for ur reply. I got your explanation but I have some basic doubts in this concept. Can u clarify:

Q1) When data packets arrives at a hop (say a router) they will be stored in a buffer if the data rate at the sender is more than the outgoing link capacity. Say the router is using tocken bucket concept. Does the same buffer is used for tockens and data packets or is it different?

Q2) in your answer you have mentioned that "rate at which bucket is emptying is different from rate at which data is send". As per my understanding burst rate or maximum output rate is the rate at which output link can send data. Then 20mbps rate is considered for tocken emptying and data sending. Does both work at a time I mean does the output link empty tokens and send data at a time?.

Q3) In ur answer "Now bucket is empty and rate of token arriving is less than that of going out so effective data speed will be 10Mbps". As per my understanding if there is a tocken available in the bucken then only u can send data. U have taken 10mbps which is token arrival rate to send data because tokens should be present in the bucket to send data. Please let me know whether my assumption is correct or not.

If possible please explain with a digram or let me know a good resource to understand the concept better.

Kindly help!!!

---

where to read token-bucket from ? Any book reference will be very helpful :)

---

https://www.youtube.com/watch?v=ZYIdYIt7W_g in nptel

---

Read from tanenbaum page 404. Well explained there.

---

pls  explain more clearly this question @ Habibkhan @ Anirudh if possible with diagram

---

@Vaibhav,

I undestood the whole thing but please please can u help me to digest why you multiplied 0.1s by 20MBps ?

In 0.1s 1MB of the bucket is removed at the rate 10MBps...so far so good.

While the bucket is emptying At the same time there is incoming data from the sender. Now sender is transmitting at the rate of 10MBps..so in 0.1sec, data transmitted by sender should be 0.1s * 1MBps..ri8?

Why u have taken 0.1s * 20MBps ? (20MBps is the output rate of bucket na ?)

Any Help will be much appreciated..

---

"if initally capacity of token bucket is C  then C tokens will be immediately be present in the network "
 How does this situation is considered in  the answer give here ?

---

Why are we emptying the bucket,why cant we keep on producing data whenever we have space?I mean complete empty means 100% empty,but when it is 99% full,wven then why cant we utilizae the space?

Do we alwys need to empty bucket first?Please help

---

@pc  , @prajwal  @rajes pradhan  bro   plz tell me if in case they dont mention bucket is full  then answer will be 12*0.1 = 1.2s is it correct ??,  and in the same question if bucket  capacity is 5mega byte then answer will be =(12-5)*0.5=3.5 ?? plz verify once by which my above  reading explanation going to be worth

---

Here there is better explanation

http://www.geeksforgeeks.org/gate-gate-cs-2016-set-1-question-64/

---

@bikram sir

reference to this answer https://gateoverflow.in/71906/token-bucket?show=71906#q71906

in the initial 0.1 sec the transmit rate is 20Mb/s ??

---

@ hem chandra joshi 

yes, transmit rate in this qstn is 20 MBps ... reference to that question, outgoing rate was given 10 Mbps But in this question outgoing rate is given 20 Mbps .

Rate at which bucket is emptying is different from rate at which data is send ( means transmission rate ) ......in this question , bucket empty at the rate of 10 MBps .

---

@Bikram Sir, I am getting 1.3 sec as:

Capacity = 1MB

Output rate = 20MBps

Input rate = 10MBps

since Outpur rate > Input rate it means data is continuously going out of the bucket at the rate of :

20-10 = 10 MBps

which means

1 sec ---------------- 10MB

so 1 MB data will take 0.1 sec.

Now it is given in the question that :

The token bucket is currently full 

which means already 1MB of data is present in the bucket so, first we need to empty this data which takes 

0.1 sec.

Now it is also mentioned that machine wants to send 12 MB of data.

So, for transferring 12 MB of it need

0.1*12  = 1.2 sec.

So, in total i.e. first empty the already filled data took 0.1 sec and for transferring 12 MB it take 1.2sec

So, finally it is 1.2 + 0.1 = 1.3 sec.

please tell what is wrong in this explanation.

---

Excellent explanation . This link contains an animation on this topic http://webmuseum.mi.fh-offenburg.de/index.php%3Fview=exh&src=8.html

---

thanks bro :) @Pritam Dutta

---

short & sweet

---

Let C be the capacity of the buffer

Initially, the bucket is full

1. When Bucket is full, output speed = burst rate(M) and input speed = constant rate(ρ)

for a bucket to become empty after 's' sec (when initially it was full)

C-Ms+ρs = 0

s = C/M-ρ 

 On substituting values s=0.1s

This 0.1s is time taken for the bucket to become empty

In this process Data outs from the bucket at max speed

Data outlet from the bucket during this time = 0.1 * M = 2MB

So remaining data to be send = 12MB - 2MB = 10MB

As Bucket becomes empty accumulation of tokens takes place until bucket capacity was reached

Time spent in accumulation =  C/ρ =0.1sec

After accumulation gets completed and the buffer is full again The system outputs at burst rate(M)

i.e, as in the previous case 

for next 0.1 sec - 2MB data gets transfered

0.1	2MB
0.1	Accumulation
0.1	2MB
0.1	Accumulation
0.1	2MB
0.1	Accumulation
0.1	2MB
0.1	Accumulation
0.1	2MB
0.1	Accumulation
0.1	2MB

so total 12 MB transfer takes 1.1 sec 

Is my reasoning was wrong?

---

@shubhanshu

when you are emptying the bucket it means you are sending data at that time but in your explanation you did not calculate the data send at that time . and the data send in 0.1 second =0.1*maximum output rate=0.1*20=2MB

so first subtract 2MB from 12MB after that your explanation is right

---

I think the process of bytes remaining in the bucket will be like this:

20-10 = 10MBps

1 MB in 0.1 seconds.

Time (in seconds)	Data currently in the bucket (in Megabytes)	Data Sent (in Megabytes)
0.1	0	2
0.2	1	3
0.3	1	4
0.4	1	5
0.5	1	6
0.6	1	7
0.7	1	8
0.8	1	9
0.9	1	10
1.0	1	11
1.1	1	12

 

---

They are asking for the MINIMUM time. That is 1.1s. Otherwise, I can even send the data in 100s, if I want, but that is not how this works

---

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.