70 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.

4

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.

33

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

2

'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$ $(Wrong:X)$

`Edited:`

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

`Data is transmitted at the rate of 20 Mbps, not at the effective rate of 10 Mbps. So, data sent is 20 Mbps x 0.1 s = 2 MB.`

`Remaining data=10 MB`

`It will be transmitted at token arrival rate & not the maximum output rate.Hence 1sec more is required to transmit the remaining data of 10 MB`

$\therefore0.1sec+1sec=1.1sec$ $\checkmark$

0

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

1

Initially if the bucket is completely full then it has 1 MB of data. (if nothing is given about token take 1 Byte = 1 token).

Now whenever we take the maximum output rate (M) then it's equal to initial window size (C) completely full means 1 MB in this case + output rate * time .....Now here the output rate is rate at which the data goes out from the sender, these is the real output rate. But if we want to calculate Maximum output rate,

$M = \frac{C+RT}{T}$

where C = Window Size

R = actual output Rate

M = maximum output rate

difference between maximum and actual output rate is in maximum rate is we take the window size full initially + data sent in time T ..means R*T (as rate is R bytes per sec. then in time T how much will be sent? it's nothing but R*T)

now as we are talking about rate which is nothing but per unit time therefore we have divided by T in the formula...

So this formula says in time T we can send C (window size which is full) + data sent in time T which is R*T

Now, from these we can calculate time ,

$T = \frac{C}{M-R}$

now if put values given in question we get,

$T=\frac{1}{20-10}$ = .1 Sec.

means in .1 sec we have sent 1 MB (initial window is full) and .1*10 = 1 MB

so total 2 MB sent in 0.1 sec.

now to sent remaining 10 MB , Here is where actual output rate will be used which is 10 MB/s so ,

in 1 sec we can send 10 MB means only 1 sec reqd. for remaining 10 MB

so total time to sent 12 MB = .1 sec (for 2 MB) + 1 Sec (for remaining 10 MB)

= 1.1 sec ans.

Now whenever we take the maximum output rate (M) then it's equal to initial window size (C) completely full means 1 MB in this case + output rate * time .....Now here the output rate is rate at which the data goes out from the sender, these is the real output rate. But if we want to calculate Maximum output rate,

$M = \frac{C+RT}{T}$

where C = Window Size

R = actual output Rate

M = maximum output rate

difference between maximum and actual output rate is in maximum rate is we take the window size full initially + data sent in time T ..means R*T (as rate is R bytes per sec. then in time T how much will be sent? it's nothing but R*T)

now as we are talking about rate which is nothing but per unit time therefore we have divided by T in the formula...

So this formula says in time T we can send C (window size which is full) + data sent in time T which is R*T

Now, from these we can calculate time ,

$T = \frac{C}{M-R}$

now if put values given in question we get,

$T=\frac{1}{20-10}$ = .1 Sec.

means in .1 sec we have sent 1 MB (initial window is full) and .1*10 = 1 MB

so total 2 MB sent in 0.1 sec.

now to sent remaining 10 MB , Here is where actual output rate will be used which is 10 MB/s so ,

in 1 sec we can send 10 MB means only 1 sec reqd. for remaining 10 MB

so total time to sent 12 MB = .1 sec (for 2 MB) + 1 Sec (for remaining 10 MB)

= 1.1 sec ans.

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

0 votes

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.

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.