11,167 views

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

1. $1.6$ seconds
2. $2$ seconds
3. $5$ seconds
4. $8$ seconds

Is token bucket in gate syllabus 2018 since token ring is not in syllabus ?
Its not related to token ring . It is a congestion control algorithm in network layer (falls under traffic shaping).
edited

Confusion in the analysis of the problem.

 at $t = 0$ Bucket occupancy $= 16 \ Mb$ between $t = 0 \text{ and } t = 1$ $10 \ Mb$ worth of token (and packet data) is drained out. $2 \ Mb$ worth of token is added to the bucket. at the end of $t = 1$ Bucket occupancy $= (16 - 10 + 2) \ Mb = 8 \ Mb$ between $t = 1 \text{ and } t = 2$ What will happen here?

My understanding: $2$ possibilities

1. $2 \ Mb$ worth of token is first added to the bucket. And then, $10 \ Mb$ worth of token is removed. This leaves bucket occupancy $= 0 \ Mb$. This gives a full rate transmission time of $2$ seconds.
2. $8 \ Mb$ worth of token is first drained out of the bucket, and then, $2 \ Mb$ worth of token is added. This leaves bucket occupancy $= 2 \ Mb$. This gives a full rate transmission time of $1$ second.

As per the discussions here, it is evident that the former approach is preferred over the latter. But, intuitively, I do not see any reason for doing this.

• Why would the transmitter wait for the bucket to fill again with $2 \ Mb$ worth of token (possibility $1$) when it already has $8 \ Mb$ worth of token in the bucket and can use it to transmit $8 \ Mb$ data?

I would appreciate an intuitive explanation, rather than using the formula $T_{trans} = \frac{16 \ Mb}{(10 - 2) \ Mbps}$

Is this there in the syllabus?
yes

congestion control is there is syllabus
Ok, Thanks.

$\\ Max\ rate=\dfrac{c+rt}{t}\\ \\ 10Mbps=\dfrac{16Mb+2Mbps\times t}{t}\\ \\ 10Mbps\times t-2Mbps\times t=16Mb\\ \\ 8Mbps\times t=16Mb\\ \\ t=2sec$

Ans: 2sec

New tokens are added at the rate of $r$ bits/sec which is $2\;\text{Mbps}$ in the given question.

Capacity of the token bucket $(b) = 16\;\text{Mbits}$
Maximum possible transmission rate $(M) = 10\;\text{Mbps}$
So, the maximum burst time $= b/(M-r) = 16/(10-2) = 2 \;\text{seconds}$
Here is the animation for token bucket hope this will help us to understand the concept.

Correct Answer: $B$

Can you please explain how the formula is derived?
say till t sec it operate at 10mbps,

t*2+16=10*t

8t=16

so  t=2

I tried this easiest method! Is my approach correct, yes or no? plz let me know!

That animation link is not working. Those who are interested to see that: http://webmuseum.mi.fh-offenburg.de/index.php%3Fview=exh&src=8.html
@partner it is also not working

Yes, it is not working now, unfortunately!

TIME TOKEN IN BUCKET TOKEN SEND LEFT IN BUCKET
First sec 16Mb+ 2Mb =18Mb 10Mb 8Mb
next sec 8Mb+2Mb 10Mb 0Mb

Hence for 2 seconds we can send the tokens at 10 Mbps.

by

### 1 comment

Capacity of the bucket is mention is 16Mb, so how it can hold 18Mb token in 1st second?

It's 'kind of' aptitude question:

packets leaving bucket at 10Mbps   &&   packets entering bucket at 2Mbps.

So "actual rate" of bucket being empty is 10-2=8Mbps.

so (capacity/transmission rate) = 16/8 =2seconds.

### 1 comment

Why did you subtract 8 from 10 and please do interpret the question?
• I/P rate of tokens=2 Mega bps. 2 Megabits tokens come 1 sec
• O/P rate of tokens=10 Mega bps. 10 Megabits tokens comes out in 1 sec
• Capacity of the bucket=16 megabits
• At t=0, bucket=16 Megabits
• At t=1, 10 Megabits tokens comes out(as it is filled so first tokens have to pulled out then it will be filled), 2 Megabits tokens come in, (16-10+2)=8 Megabits tokens. At t=1 bucket has 8 Megabits tokens
• At t=2, bucket has 8 Megabits tokens(it is not full no first tokens will come in then pulled out), 2 Megabits tokens comes in, bucket=8+2=10 Megabits. 10 Megabits tokens will come out. Now bucket has 0 Megabits tokens
• At t=3, bucket has 0 tokens, 2 Megabits tokens comes in and 2 Megabits tokens goes out. So here tokens are send at the rate of 2 Mega bps and this will continue
• In t=1 sec 10 Megabits tokens comes out
• At t=2, 10 Megabits tokens come out
• So till 2 sec we're able to send tokens at 10 Mega bps
by

Just correct the last second line. You missed to write 10 there .

I think rate of adding tokens to bucket and rate of consuming tokens from bucket happens according to the capacity of Bucket (for example, it takes 1 sec to consume a token and 2 sec to add a token, then for every 2 sec - 2 tokens are used and 1 token is added).

Correct me, if i am wrong.

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.

### 1 comment

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

### 1 comment

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

Direct formula based question

This formula always works.

by

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.

by