in Computer Networks edited by
11,167 views
27 votes

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
in Computer Networks edited by
11.2k views

7 Comments

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

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

1
Is this there in the syllabus?
0
yes

congestion control is there is syllabus
3
Ok, Thanks.
0

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

10

8 Answers

45 votes
 
Best answer

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$

edited by

8 Comments

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

t*2+16=10*t

8t=16

so  t=2
17

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

3
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
5
@partner it is also not working
1

Yes, it is not working now, unfortunately!

0
6
33 votes
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?

0
19 votes
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?
0
4 votes
  • 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
edited by

2 Comments

@aditi19

Good answer.

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

0

@aditi19 @`JEET

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.

 

0
3 votes
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.
0
0 votes

Answer is 2 sec...

1 comment

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

Direct formula based question

This formula always works.

0 votes

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.

 

Answer:

Related questions