GATE CSE 2008 | Question: 58

Question

A computer on a $10\text{Mbps}$ network is regulated by a token bucket. The token bucket is filled at a rate of $2\text{Mbps}$. It is initially filled to capacity with $16\text{Megabits}$. What is the maximum duration for which the computer can transmit at the full $10\text{Mbps}$?

• A. $1.6$ seconds
• B. $2$ seconds
• C. $5$ seconds
• D. $8$ seconds

Comments

I had the same confusion but here is the explanation:

Intuitively speaking, at t = 1 sec , you have 8 Mb of tokens in the bucket, so either you can fill 2 Mb into the bucket and then transmit 10 Mb of full capacity or else transmit 8 Mb which is not the full capacity.

But the first choice is made, the reason being that the the bucket is not full currently, you want to transmit at full capacity and currently you have 2 Mb less than the full capacity and hence you will prefer to first fill the bucket completely and then transmit. Hence 2 Mb is first put in which takes 1 second and then at t = 2 sec, you transmit the complete 10 Mb.

---

THE ACTUAL CONCEPT used

https://gateoverflow.in/481/gate-cse-2008-question-58?show=409187#a409187

---

$\frac{c+rt}{t}=10\;Mbps$
$\frac{16\;Mb+2\;Mbps\times t}{t}=10\;Mbps$
$16\;Mb+2\;Mbps\times t=10\;Mbps\times t$
$8\;Mbps\times t=16\;Mb$
$t=2\;sec$

Answer 1

Simple way :

Token rate into bucket = 2 Mbps

Output rate of bucket = 10 Mbps

Effective rate = 10-2 = 8 Mbps

Bucket capacity is full, 16 Mb

So, at effective rate bucket will drain in 16/8 = 2s

In these 2s, output capacity of bucket will be 10Mbps, after bucket gets empty, it's capacity will reduce to effective rate of 8Mbps.

Comments

Its capacity will reduce to effective rate of 2 Mbps, not 8 Mbps.

Answer 2

Direct formula based question

This formula always works.

Answer 3

Answer is 2 sec...

Comments

How do you know that the bucket empties at 8mbps. I'm unable to get the logic. Please clarify?

Answer 4

Written in Hindi:

Aare mere bhai wha dekh pehle se hi mentioned h ki Bucket m initially 16Mbits tokens rakha hua tha, yaani ki jab transmission suru hoga toh pehle ka 10 Mbits toh 1 second m  nikal jayega ab bucket m para rhega 6 Mbits tokens ,pr isi 1 sec time m 2 Mbits token v toh generate hoga na mere bhai Yaani abhi bucket m 6 Mbits + 2 Mbits = 8 Mbits tokens rakha hua h.Toh mujhe is pehla 1 sec m 10 Mbps ka max transfer rate achieve hua .
Ab dekh jb 1 aur sec bitega toh 2 Mbits tokens firse generate hoga 
Yaani ab bucket m 8 Mbits+2 Mbits = 10 Mbits tokens honge.
Toh jaasehi ye dursa sec bitega hume firse 10Mbps ka max speed mila
Yaani total hume 2 sec k lie Max transfer speed of 10 Mbps achieve hua.