The Gateway to Computer Science Excellence

+58 votes

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

+1

According to official key answer for the above question should be 1.1 sec. Can someone explain the correct procedure.

+3

dear downvoters, it was in syllabus. So i dnt know the reason behind downvoting. And token bucket question came in 2008 also when IISC made the paper.

+26

This diagram might help. For a packet to get transmitted into the network it needs to remove a token. If the token bucket is empty packet has to wait.

Because token generation rate is 'r', the maximum no of packets that can enter the network at **any** interval of time 't' is given by

**r.t + b**

So, here I have considered packets to be of size 1MB.

b = 1MB (given)

r = 10MBps

Data to transfer = 12MB.

Therefore,

10.t + 1 = 12

=> 10.t = 11

=> t = 1.1sec (ans)

0

here tokens arrive at a rate to sustain an output rate of 10mbps doesnt mean the net rate

at time t tends to infinity the (C+r*t)/t becomes r which is the input rate hence the rate to sustain at 10 we should maintain an inflow of 10 inflow will become outflow as time tends to infinity and maximum output rate is determined by the network we can only send that much though we can send more we can send only at that rate

so the notion of 20-R=10 is wrong according to this

however this doesnt affect the answer or R value of 10 remains the same

please correct me if i am wrong but the procedure is same

at time t tends to infinity the (C+r*t)/t becomes r which is the input rate hence the rate to sustain at 10 we should maintain an inflow of 10 inflow will become outflow as time tends to infinity and maximum output rate is determined by the network we can only send that much though we can send more we can send only at that rate

so the notion of 20-R=10 is wrong according to this

however this doesnt affect the answer or R value of 10 remains the same

please correct me if i am wrong but the procedure is same

+1

Here in this question it is mentioned that

"Tokens arrive at a rate to sustain output at a rate of 10megabytes per second"

Does not this means that output of token bucket is 10 mb/sec ? And tokens have to arrive in such a rate that this output rate of 10mbps is sustained?

"Tokens arrive at a rate to sustain output at a rate of 10megabytes per second"

Does not this means that output of token bucket is 10 mb/sec ? And tokens have to arrive in such a rate that this output rate of 10mbps is sustained?

0

Token Bucket is already filled with 1 MB of tokens and machine needs to send 12 MB of data. Since we already have 1 MB of tokens in the bucket we can immediately transfer 1 MB of the data.

Now we are remaining with 11 MB of data to be transferred for which we need to generate tokens. To generate 11 MB of tokens time taken = $\dfrac{11 MB}{10 MBps} = 1.1s$

This entire thing is possible bcz output rate is higher than token generation rate and so we are only bothered about token generation rate

Now we are remaining with 11 MB of data to be transferred for which we need to generate tokens. To generate 11 MB of tokens time taken = $\dfrac{11 MB}{10 MBps} = 1.1s$

This entire thing is possible bcz output rate is higher than token generation rate and so we are only bothered about token generation rate

0

'The token bucket is currently full'and the machine needs to send 12 megabytes of data.

$\\ Max\ rate=\dfrac{c+rt}{t}\\ \\ 20Mbps=\dfrac{11Mb+10Mbps\times t}{t}\\ \\ 20Mbps\times t-10Mbps\times t=11Mb\\ \\ 10Mbps\times t=11Mb\\ \\ t=1.1sec$

Ans: 1.1 sec

0

@Syedarshadali Yes you might be right, I must have taken that value wrongly. Let me verify and then change the comment. Thanks.

0 votes

TIME |
TOTAL TOKENS IN BUCKET |
TOKENS SEND | TOKENS LEFT IN BUCKET |
---|---|---|---|

1 (First second) |
1MB(capacity)+10MB(generated in 1 second)=11MB 11MB<12MB..so generate more. |
NOT send because 12 MB have to be send at once. | 11MB |

2(next second) t second |
11MB+10MB=21MB 21MB>20MB So time is less than a second for the generation of 12 MB. 11MB+t*10MB=12MB t=0.1 sec |
- now we have 12MB Tokens in bucket |
- 0 MB in bucket. |

Hence in total time of 1+0.1 sec=1.1 we are able to send 12 MB .

0 votes

we know formulae

( Capacity of token bucket + input Token Rate * Burst Time) / Burst Time = Burst speed

(1 + 10 * T ) /T = 20 => T= 0.1 sec

hence for 0.1 sec burst speed was 20MBps , In this much time we can send 0.1 * 20 MBps = 2MB

After this bust time speed become 10 MBps and we want to send remaining 10 MB

It will take 10MB / 10 MBps = 1 sec

Total 1.1 sec

( Capacity of token bucket + input Token Rate * Burst Time) / Burst Time = Burst speed

(1 + 10 * T ) /T = 20 => T= 0.1 sec

hence for 0.1 sec burst speed was 20MBps , In this much time we can send 0.1 * 20 MBps = 2MB

After this bust time speed become 10 MBps and we want to send remaining 10 MB

It will take 10MB / 10 MBps = 1 sec

Total 1.1 sec

0 votes

I will simplify the question.......Firstly since the output rate is more than incoming rate, we will calculate the time when the bucket will be empty, that is

capacity +(input rate x S) =(output rate x S)

1+ (10 x S) =(20 x S)

S=0.1 sec .............at this time bucket will be empty, till this time we have transferred data at max rate of 20 MB/sec, thus we have transferred 0.1 x 20 =2 MB , now we have to transfer 10 MB more, since the bucket is empty, now the output rate will be equal to input rate, thus

to transfer 10 MB at speed 10 MB/sec, it will require 1 sec.

Thus ans= 1 + .1 =1.1 sec

capacity +(input rate x S) =(output rate x S)

1+ (10 x S) =(20 x S)

S=0.1 sec .............at this time bucket will be empty, till this time we have transferred data at max rate of 20 MB/sec, thus we have transferred 0.1 x 20 =2 MB , now we have to transfer 10 MB more, since the bucket is empty, now the output rate will be equal to input rate, thus

to transfer 10 MB at speed 10 MB/sec, it will require 1 sec.

Thus ans= 1 + .1 =1.1 sec

0 votes

**Let, C= Capacity of token bucket=1MB,**

**M= Maximum number of packets that can enter in ****network**** during a time interval 't'= C+rt**

**M=C+rt**

**12MB=1MB+10MB/sec*tsec**

**12 = 1 +10t**

**t=1.1sec**

0 votes

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

0 votes

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,497 answers

195,493 comments

100,826 users