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

0

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.

102 votes

Best answer

Initially token bucket is full.

Rate at which it is emptying is $(20-10)$ **MBps**.

Time taken to empty token bucket of $1$ **MB** is $\frac{1}{10}$ i.e $0.1$ sec.

Data send in this time is $0.1*20=2$ **MB** **(rate at which bucket is emptying is different from rate at which data is send**) .

Data left to send is $12-2=10$ **MB** .

Now bucket is empty and rate of token arriving is less than that of going out so effective data speed will be $10$**MBps**.

Time to send remaining $10$**MB** will be $1$ sec. So total time is $1+0.1$=$1.1 $sec

2

as the bucket was already filled so bw will be always 10MB Explanation given in ACE key is Maximum burst rate, M = 20 MB Token arrival rate, P = 10 MB Constant rate(bucket o/p), P = 10 MB Bucket capacity, C = 1 MB Time for 1 MB, S =C\(M-P)=1/(20-10)=0.1 For the total message of 12 MB is 1.2 sec. what do you say is it right or wrong?????

1

Hi Vaibhav , Can u pls be more precise. You told in 0.1 sec of time data sent is 0.1*20=2mb. But during that time data ll also come into the tocket bucket @10mbps right?.

And 0.1sec time time it takes to empty the token bucket. How can the data sent out simultaneously.

Please correct me if I am wrong.

And 0.1sec time time it takes to empty the token bucket. How can the data sent out simultaneously.

Please correct me if I am wrong.

1

That's wat... U have taken only out going in that 0.1 sec that is 0.1*20=2mb.. At the same time data comes into the token bucket right?.. What about that data.. U have mentioned " now that bucket is empty..... Effective data rate is 10 Mbps......"... Y so?.. Bucket ll be filled with tockens during that 0.2 sec rite?

4

yes you are right at during initial 0.1 sec data is coming and going out at the same time but rate at which data is coming is 10mbps and rate at which it is going out is 20 mbps so for bucket it is effectively emptying at rate of 10mbps. But during this time we have enough data so that we can send data at rate of 20mbps but once bucket is emptied then outgoing rate must be same as that of incoming rate.

1

@ Vaibhav .. My point here is at the effective rate (20-10) Mbps the token bucket gets emptied as the outgoing rate is higher... With the effective rate the bucket with 1mb will be emptied in 0.1 sec .. I.e actual work done is sending out 1mb data in 0.1 sec.. It is clear till now... Now again ur calculating 20*0.1 = 2mb outgoing... U have already calculated the effective rate na... Emptying 1mb is done during that 0.1 sec duration... How come outgoing data calculated during that time... Really confused wit ur statement... Pls clarify

1

since initially bucket is full and outing rate is more than that of incoming so bucket is emptying right. but the rate at which bucket is emptying and the rate at which data is sent are two different things.

1

Hi Vaibhav, Thanks for ur reply. I got your explanation but I have some basic doubts in this concept. Can u clarify:

Q1) When data packets arrives at a hop (say a router) they will be stored in a buffer if the data rate at the sender is more than the outgoing link capacity. Say the router is using tocken bucket concept. Does the same buffer is used for tockens and data packets or is it different?

Q2) in your answer you have mentioned that "rate at which bucket is emptying is different from rate at which data is send". As per my understanding burst rate or maximum output rate is the rate at which output link can send data. Then 20mbps rate is considered for tocken emptying and data sending. Does both work at a time I mean does the output link empty tokens and send data at a time?.

Q3) In ur answer "Now bucket is empty and rate of token arriving is less than that of going out so effective data speed will be 10Mbps". As per my understanding if there is a tocken available in the bucken then only u can send data. U have taken 10mbps which is token arrival rate to send data because tokens should be present in the bucket to send data. Please let me know whether my assumption is correct or not.

If possible please explain with a digram or let me know a good resource to understand the concept better.

Kindly help!!!

Q1) When data packets arrives at a hop (say a router) they will be stored in a buffer if the data rate at the sender is more than the outgoing link capacity. Say the router is using tocken bucket concept. Does the same buffer is used for tockens and data packets or is it different?

Q2) in your answer you have mentioned that "rate at which bucket is emptying is different from rate at which data is send". As per my understanding burst rate or maximum output rate is the rate at which output link can send data. Then 20mbps rate is considered for tocken emptying and data sending. Does both work at a time I mean does the output link empty tokens and send data at a time?.

Q3) In ur answer "Now bucket is empty and rate of token arriving is less than that of going out so effective data speed will be 10Mbps". As per my understanding if there is a tocken available in the bucken then only u can send data. U have taken 10mbps which is token arrival rate to send data because tokens should be present in the bucket to send data. Please let me know whether my assumption is correct or not.

If possible please explain with a digram or let me know a good resource to understand the concept better.

Kindly help!!!

0

@Vaibhav,

I undestood the whole thing but please please can u help me to digest why you multiplied 0.1s by 20MBps ?

In 0.1s 1MB of the bucket is removed at the rate 10MBps...so far so good.

While the bucket is emptying At the same time there is incoming data from the sender. Now sender is transmitting at the rate of 10MBps..so in 0.1sec, data transmitted by sender should be 0.1s * 1MBps..ri8?

Why u have taken 0.1s * 20MBps ? (20MBps is the output rate of bucket na ?)

Any Help will be much appreciated..

I undestood the whole thing but please please can u help me to digest why you multiplied 0.1s by 20MBps ?

In 0.1s 1MB of the bucket is removed at the rate 10MBps...so far so good.

While the bucket is emptying At the same time there is incoming data from the sender. Now sender is transmitting at the rate of 10MBps..so in 0.1sec, data transmitted by sender should be 0.1s * 1MBps..ri8?

Why u have taken 0.1s * 20MBps ? (20MBps is the output rate of bucket na ?)

Any Help will be much appreciated..

0

"if initally capacity of token bucket is **C** then C tokens will be immediately be present in the network "

How does this situation is considered in the answer give here ?

0

Why are we emptying the bucket,why cant we keep on producing data whenever we have space?I mean complete empty means 100% empty,but when it is 99% full,wven then why cant we utilizae the space?

Do we alwys need to empty bucket first?Please help

Do we alwys need to empty bucket first?Please help

0

@pc , @prajwal @rajes pradhan bro plz tell me if in case they dont mention bucket is full then answer will be 12*0.1 = 1.2s is it correct ??, and in the same question if bucket capacity is 5mega byte then answer will be =(12-5)*0.5=3.5 ?? plz verify once by which my above reading explanation going to be worth

2

Here there is better explanation

http://www.geeksforgeeks.org/gate-gate-cs-2016-set-1-question-64/

0

@bikram sir

reference to this answer https://gateoverflow.in/71906/token-bucket?show=71906#q71906

in the initial 0.1 sec the transmit rate is 20Mb/s ??

0

yes, transmit rate in this qstn is 20 MBps ... reference to that question, outgoing rate was given 10 Mbps But in this question outgoing rate is given 20 Mbps .

Rate at which bucket is emptying is different from rate at which data is send ( means transmission rate ) ......in this question , bucket empty at the rate of 10 MBps .

0

@Bikram Sir, I am getting 1.3 sec as:

Capacity = 1MB

Output rate = 20MBps

Input rate = 10MBps

since Outpur rate > Input rate it means data is continuously going out of the bucket at the rate of :

20-10 = 10 MBps

which means

1 sec ---------------- 10MB

so 1 MB data will take 0.1 sec.

Now it is given in the question that :

The token bucket is currently full

which means already 1MB of data is present in the bucket so, first we need to empty this data which takes

0.1 sec.

Now it is also mentioned that machine wants to send 12 MB of data.

So, for transferring 12 MB of it need

0.1*12 = 1.2 sec.

So, in total i.e. first empty the already filled data took 0.1 sec and for transferring 12 MB it take 1.2sec

So, finally it is 1.2 + 0.1 = 1.3 sec.

please tell what is wrong in this explanation.

1

Excellent explanation . This link contains an animation on this topic http://webmuseum.mi.fh-offenburg.de/index.php%3Fview=exh&src=8.html

0

Let C be the capacity of the buffer

Initially, the bucket is full

1. When Bucket is full, output speed = burst rate(M) and input speed = constant rate(ρ)

for a bucket to become empty after 's' sec (when initially it was full)

C-Ms+ρs = 0

s = C/M-ρ

On substituting values s=0.1s

This 0.1s is time taken for the bucket to become empty

In this process Data outs from the bucket at max speed

Data outlet from the bucket during this time = 0.1 * M = 2MB

So remaining data to be send = 12MB - 2MB = 10MB

As Bucket becomes empty accumulation of tokens takes place until bucket capacity was reached

Time spent in accumulation = C/ρ =0.1sec

After accumulation gets completed and the buffer is full again The system outputs at burst rate(M)

i.e, as in the previous case

for next 0.1 sec - 2MB data gets transfered

0.1 | 2MB |

0.1 | Accumulation |

0.1 | 2MB |

0.1 | Accumulation |

0.1 | 2MB |

0.1 | Accumulation |

0.1 | 2MB |

0.1 | Accumulation |

0.1 | 2MB |

0.1 | Accumulation |

0.1 | 2MB |

so total 12 MB transfer takes 1.1 sec

Is my reasoning was wrong?

0

@shubhanshu

when you are emptying the bucket it means you are sending data at that time but in your explanation you did not calculate the data send at that time . and the data send in 0.1 second =0.1*maximum output rate=0.1*20=2MB

so first subtract 2MB from 12MB after that your explanation is right

when you are emptying the bucket it means you are sending data at that time but in your explanation you did not calculate the data send at that time . and the data send in 0.1 second =0.1*maximum output rate=0.1*20=2MB

so first subtract 2MB from 12MB after that your explanation is right

41 votes

**Short answer**

The total time to transmit data in Token Bucket algorithm is the sum of two times -

- T
_{1}= Time to transmit data with max. transmission rate as long as the bucket is not empty. - T
_{2}= Time to transmit the remaining data after the bucket is empty. During this time, data can only be sent at the rate at which the tokens are generated.

[If size of data is less than or equal to the bucket capacity then all data will be transmitted before the bucket becomes empty. Therefore, only the first component gives the answer in this case.]

Calculating T_{1} -

This is simple, but can be a bit tricky for some people like me. Since, the bucket's capacity is 1 MB, and the effective rate of token removal is 20 - 10 = 10 MBps, therefore the bucket will be emptied in 1 MB /10 MBps = 0.1 s. But, this does not mean that 1 MB data is transmitted in 0.1 s. During this time, 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.

Here, because of the relative nature of the formula used to calculate the time to empty the bucket, some people get confused. To clear the confusion, consider this simple problem.

**Q.** Two cars A and B start moving at the same time in the same direction at the speeds of 20 kmph and 10 kmph respectively. If B has a head start of 1 km, then what is the distance traveled by A to overtake B.

**Ans**:- Since both cars start moving at the same time, A must travel the same amount of time as B. So, the answer is simply the product of this time and A's speed, i.e., 20 kmph.

Now, one way to calculate this time is to use the concept of relative speeds. If B is put to rest (i.e, B's speed is decreased by 10 kmph), then A's speed also decreases by the same amount, thus resulting in a relative speed of 20 - 10 = 10 kmph. Since, B is at rest, therefore to overtake B, A only needs to cover the head start distance of 1 km. Therefore, time taken by A to overtake B = 1 km / 10 kmph = 0.1 hr. Clearly, this does not mean that A travels only 1 km. Since, A's actual speed is 20 kmph, therefore distance covered by A = 20 kmph x 0.1 hr = 2 km.

Now, one way to calculate this time is to use the concept of relative speeds. If B is put to rest (i.e, B's speed is decreased by 10 kmph), then A's speed also decreases by the same amount, thus resulting in a relative speed of 20 - 10 = 10 kmph. Since, B is at rest, therefore to overtake B, A only needs to cover the head start distance of 1 km. Therefore, time taken by A to overtake B = 1 km / 10 kmph = 0.1 hr. Clearly, this does not mean that A travels only 1 km. Since, A's actual speed is 20 kmph, therefore distance covered by A = 20 kmph x 0.1 hr = 2 km.

Calculating T_{2} -

This is straightforward. Since, the remaining data is 12 - 2 = 10 MB, and the rate of transmission of this data is equal to the rate of token arrival, i.e., 10 MBps, therefore time taken to transmit 10 MB = 10 MB / 10 MBps = 1 s.

Therefore, total time = T_{1} + T_{2} = 0.1 s + 1 s = 1.1 s

**Long Answer**

The concept is simple -

- Tokens are produced by the system at a fixed rate, and stored in a bucket having fixed capacity.
- Whenever a packet is transmitted, some tokens are removed from the bucket. How many are removed ? It depends. If all packets are of same size, then one token per packet is OK. Otherwise, one token per byte is deleted. By default, it is one token per byte.
- Transmission can be performed ONLY IF tokens are available in the bucket. If bucket is empty, then packets are queued until sufficient tokens are available.

the rate at which tokens are removed from the bucket is ALWAYS equal to the rate at which the packets are transmitted by the system.

Now comes the central question. "Why are the tokens STORED in a bucket ?" To understand this, consider what would happen if we don't store them !! If tokens are not stored, then the system will always transmit the packets at the same rate at which the tokens are produced. And, this is nothing but the "Leaky Bucket" algorithm, where the packet transmission rate is always fixed.

The "Token Bucket" algorithm with a zero bucket capacity is nothing but the "Leaky Bucket" algorithm.

If the tokens are stored, however, then the system is not limited to the token generation/arrival rate, and can transmit the packets at the maximum transmission rate. The max. transmission rate is generally greater than the token arrival rate.

As long as the bucket contains tokens, they can be removed at the max. possible rate, and so, the system transmits the data at max. transmission rate. But, since the rate of token removal is greater than the rate of token arrival, the bucket eventually becomes empty. After that, the tokens can be removed only at the rate at which they are produced. Therefore, when the bucket becomes empty, the system transmits data at the rate of token arrival.

On pg. no. 409 of the book **"Computer Networks" (5th edition) by Tanenbaum**, it is clearly stated that -

The host can send full throttle at the maximum transmission rate for a short while until it has drained the bucket...

When it (no. of tokens in the bucket) reaches zero, new packets can be sent only at the rate at which the buffer is filling; there can be no more bursts until the bucket has recovered...

26 votes

Reffer: Token-Bucket .

- Token bucket has a capacity of 1 mega
**byte**(maximum capacity $C$ )

Here one

byteis considered as one token$\Rightarrow C=1 \text{M tokens}$

- output rate is 20 mega bytes per second ($M=20\text{MBps}$)
- Tokens arrive at a rate to
**sustain output**at a rate of 10 mega bytes per second

$20-R=10$

$\Rightarrow$ Input Rate $R=10\text{MBps}$

Unlike Leaky Bucket , idle hosts can capture and save up $ c \leq C $ tokens in order to send larger bursts later.

When we begin transfer the tokens present in token buckt is transmitted at once to the network

ie. if initally capacity of token bucket is

'c'then c tokens will be instantly be present in the network.

**Time to Empty the token bucket**

$c$: is the inital capacity of token bucket

$R$: every sec we are getting R tokens

$M$ : evey seconds M tokens are produced

INPUT FLOW : Then the number of packets that are ready to enter the network during a time interval 't' is $c+Rt$* *

OUTPUT FLOW : Then the number of packets that are ready to enter the network during a time interval 't' is $Mt$

INPUT FLOW = OUTPUT FLOW

$\Rightarrow c+Rt = Mt$

$\begin{align*} t&= \frac{c}{M-R} \\ &=\frac{1}{20-10} \\ &=0.1\text{sec} \end{align*}$

- Given that Token bucket is full ($c=C$)

Now , We have got two cases

- To transfer 1M tokens , Will it be instantly with t=0
- Or to transfer 1M tokens , we take 10/ 20-10 = 0.1sec ?

**To transfer 1M (inital token) tokens , Will it be instantly with t=0**

Consider the equation

INPUTFLOW = c+Rt

This means that

*" c tokens (initally contained in token bucket ) are transmitted without any delays "*

Unlike Leaky bucket , token buckets can keep on reserving token if the sender is idle .Once it is ready to send the packets . Packets will take the token and will be transmitted to the network. $\Rightarrow c $ And then we are adding the $R$ tokens produced in $'t'$ time to finnaly get the INPUTFLOW

$\Rightarrow 1 \text{MB}$ is *transmitted instantly* . Now we are left with 11 MB to transmit

To trnasfer remaining 11 MB

at $t=0$ we begin transmitting 11 MB data.

at $t=0.1$sec : 1MB (1 MB transfered)

at $t=0.2$sec : 1MB (2 MB transfered)

..

..

at $t=1.1$ sec : 1MB (11 MB transfered )

Therefore to transfer 12MB it takes **1.1sec + 0 sec = 1.1 sec**

**Transfer 1M (inital token) tokens , we take = 0.1sec**

( if it take 0.1 sec for 1MB i could argue that it will take 1.2ssec for 12MB )

then during 0.1sec . 01 *10MBps = 1M tokens are fulled up .

t=0s : begin to transfer 12 MB data.

t=0.1s : 1MB

t=0.2s : 1MB (2 MB transfered)

t=0.3s : 1MB (3 MB transfered)

..

..

t=1.2s : 1MB (12 MB transfered)

Therefore to transfer 12MB it takes **1.2sec**

Question does clearly mention about this part . Hence it is common practice to always follw the best case .

Therefore the answer would be **1.1 sec**

Reference

- http://www.slideshare.net/vimal25792/leaky-bucket-tocken-buckettraffic-shaping
- http://web.mst.edu/~saifullaha/courses/lecture19.pdf
- https://onl.wustl.edu/Tutorial/Filters,_Queues_and_Bandwidth/NSP_Architecture/Link_Rate.html
- http://quiz.geeksforgeeks.org/gate-gate-cs-2016-set-1-question-64/
- http://www.slideshare.net/UmeshGupta3/leaky-bucket-algorithm

0

@pC I didn't get this statement

"1MB is transmitted instantly . Now we are left with 11 MB to transmit"

how it is interpreted like that ,please explain ?

"1MB is transmitted instantly . Now we are left with 11 MB to transmit"

how it is interpreted like that ,please explain ?

4

I got till t= 0.1

but my doubt is, we 12MB to send why not 12*0.1 =1.2 sec (but you said 1MB is transferred instanstaneously)

What am i missing here ?

but my doubt is, we 12MB to send why not 12*0.1 =1.2 sec (but you said 1MB is transferred instanstaneously)

What am i missing here ?

2

@Prajwal_Bhat ,

Consider the equation

c+Rt

This means that

*" c tokens (initally contained in token bucket ) are transmitted without any delays "*

Unlike Leaky bucket token buckets can keep on reserving token if the sender is idle .Once it is ready to send the packets . Packets will take the token and will be transmitted to the network.

Correct me if wrong

0

So that means at starting of 0th second only it starts tranferring the tokens out of the bucket and at the end of 1.1th second 12MB would have been come out ...right?

0

What is the use of 0.1 sec that has been calculated? What happens during that 0.1 second if 1mb is sent instantly and the rest of the data is sent at 10mbps in 1.1 seconds?

6

@Manasi

Capacity of the bucket is **1MB**,

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

Question clearly says that the **bucket is full**, that means that it has **1MB** of data with it. Since it is full,1MB is **immediately **flushed. Here, we need to send 12MB totally, but initial contents of the bucket which is of size 1MB is already sent as the bucket was full, now we need to send **11MB** more of data.

Since the intial contents of the bucket is flushed, we need to wait till some contents to come into the bucket(Only when there is something in the bucket, we can empty the bucket!). So there will be a **delay in output**. This delay depends on input flow and output flow. This delay is** 0.1s**.(Calculation of this well explained by @pc). The data is transmitted as soon as received by the bucket i.e **every 0.1s 1MB of data arrives** and we transmit it. So for **11MB** of data it takes **1.1s **to transmit.

3

pc,

in the second part -

**Transfer 1M (inital token) tokens , we take = 0.1sec**

we found that it takes 0.1 secs to empty the bucket , which means that the bucket will spit out tokens at a rate of 20Mbps for the first 0.1 secs.

Now I read this statement from Debashish Deka's Answer -

*The system removes one token for every cell (or byte) of data sent.*

so for the first 0.1 secs there will be 20Mbps * 0.1 = 2MB tokens removed from the bucket , and from the above statement that means we will send equivalent 2MB data. So remaining data = 12-2 =10MB

Now, after the bucket is empty the tokens coming out will be dictated by the input rate ( = 10Mbps) , so it will take 1 more second to send the remaining 10MB data.

Thus 1 + 0.1 = 1.1

I think for this question in both cases -

- To transfer 1M tokens , Will it be instantly with t=0
- Or to transfer 1M tokens , we take 10/ 20-10 = 0.1sec

The answer comes out to be 1.1 secs

0

I am not getting if question says bucket is filled initially with 512 KB (half of 1MB) then what will be the minimum time required to transmit the data??

In other words if bucket is not full initially. Then how much time will it take as for 12 MB and initially full bucket we calculated for remaining 11 MB.

In other words if bucket is not full initially. Then how much time will it take as for 12 MB and initially full bucket we calculated for remaining 11 MB.

10 votes

`Tokens arrive at 10MB/sec, i.e 1 MB in 0.10 sec
`

Tokens output at 20MB/sec, i.e 1 MB in 0.05 sec

`Initially we have 1 MB in token bucket. Lets see what happens using timeline.
Please pay attention. This may seem confusing, understand what happens in between 0 - 0.1 sec
`

4 votes

The token bucket is currently full so, time to send 10 MB = 1 second and one MB already full in bucket so total = 1+10=11 MB in one second, because maximum output rate is 20 MB given, Now remaining 1 MB. 10 MB= 1 second 1 MB= 1/10= 0.1 second total time 1 second for 11 MB + 0.1 second for 1 MB= 1.1 second for 12 MB so, the minimum time required to transmit the data is 1.1 seconds

0

Sir there is one confusion in my mind. Host machine is using token bucket to transmit its data. so, we should consider the output rate (20 MBps) of the token bucket rather than the input rate(10MBps).

As you are considering here input rate is this correct ?

please give me clear idea where i am lacking. thank you.

1 vote

We need to calculate the time it takes to send 12mb and there is already 1mb present in the bucket.

The time it takes to receive 11mb more @10mbps is 1.1 sec

Now after 1.1 sec the 12th mb has entered the bucket but to send it, it will take additional time @20mbps

So additional time = 0.05sec

Therefore, total time taken to transmit 12mb = 1.1 + 0.05 = 1.15

The time it takes to receive 11mb more @10mbps is 1.1 sec

Now after 1.1 sec the 12th mb has entered the bucket but to send it, it will take additional time @20mbps

So additional time = 0.05sec

Therefore, total time taken to transmit 12mb = 1.1 + 0.05 = 1.15

1 vote

First of all we need to understand why we needed token bucket when leaky bucket was working fine(Really?) :

(1)When the bucket became full, packets loss used to occur, but in token bucket, token loss occurs and packets remain safe.

(2)Leaky bucket does not allow hosts to send bursts of data or in simpler terms when a host is idle, in leaky bucket a host cannot save up on bytes and send data at full throughput when data appears whereas in token bucket idle hosts can save up on permission to send large bursts of data for short periods of time.

Let us Understand with help of diagram. (Reference-Tannenbaum)

Fig 5.25(a) Shows host wants to send data at 25MB/sec for 40msec (1MB of bursty data)

Consider leaky bucket which has the output rate of 2MB/sec, the leaky bucket as you can see in Fig 5.25(b) smoothes out the data rate at 2MB/sec for 500msec.

Now consider a token bucket of capacity 250KB(Fig-5.25(c)) with token arriving at a rate allowing output at 2MB/sec- this means that the token arrival rate is 2MB/sec.

**Assuming that token bucket is full **when the 1MB burst arrives,

**Now token bucket provides host the advantage that the host can transmit at full 25MB/sec for burst period say 'S' Sec.**

This burst period is given by the expression

**S = C/(M-R)**

Where C=capacity of the bucket

M=Maximum allowable data rate(Here 25MB/sec)

R=Token arrival rate (Here 2MB/sec)

Now, for 'S' second, our host can transmit at full 25MB/sec.

Here S = 1MB/(23MBPS) = 10.869ms which is shown to be approximately 11ms in Fig 5.25(c)

In this 10.869 msec at 25MB/sec, total data sent= 271.739KB(Appx.)

Data remaining to b sent = 1MB-271.739KB=728.261KB

This data will now be sent evenly at the token arrival rate i.e. 2MB/sec.

And this will be sent for 728.261/2MB/sec = 364.1 msec which is shown as 364 msec in Fig 5.25(C).

So, the main difference here arises is that the token bucket has allowed our host to send some part of data at full 25MB/sec which was not the case with leaky bucket and this was when the token bucket was full before our burst data of 1MB had arrived.

Now coming to this question :

Capacity C=1MB

"**Tokens are arriving at a rate to sustain output at rate of 10 ****mega bytes**** per second**"

Means simply token arrival rate is 10MB/sec (R)

Maximum Output rate of the host is 20MB/sec.

**It is said that the bucket is full.**

So, when burst of 12MB data arrives,

For how much time considering that bucket was full before arrival of bursty data, our host is allowed to transmit at full 20MB/sec?

S = 1/(20-10)MBps = 0.1sec.

In 0.1 sec, data sent on network at 20MB/sec = 20*0.1=2MB.

Data remaining to be sent=12-2=10MB.

Now, this remaining 10MB data will be sent at the rate of token arrival rate i.e. 10MB/sec and this will take 1sec.

**So, ****total**** time ****taken**** to send 12 MB data=1+0.1=1.1sec. (ANS)**

Also, if the question had only asked that for what duration of time host is allowed to send at full capacity, then in this case answer would have been 0.1 sec.