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

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

Answer 2

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

Answer 3

The Answer is 1.1 sec.

Answer 4

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.