Numericals on Token Bucket

Question

Question

For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 mega byte and the maximum output rate is 20 mega bytes per second. Tokens arrive at a rate to sustain output at a rate of 10 mega bytes per second. The token bucket is currently full and the machine needs to send 12 mega bytes of data. The minimum time required to transmit the data is _____________ seconds.

My Approach

Initially token bucket is full. the rate at which it is emptying is (20-10) Mbps. time take to empty token bucket of 1 mb is 1/10 i.e 0.1 sec

But answer is given as 1.2sec .

Answer 1

• Token bucket has a capacity of 1 mega byte (maximum capacity C )

Here one byte is considered as one token

⇒ C=1 M tokens

• output rate is 20 mega bytes per second (M=20MBps) Tokens arrive at a rate to sustain output at a rate of 10 mega bytes per second

⇒20-R=10

⇒ Input Rate R=10MBps

• Unlike Leaky Bucket , idle hosts can capture and save up c ≤ C tokens in order to send larger bursts later. s

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

ie. if initially 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

⇒ c+Rt = Mt

t= c/M-R =1/20-10 =0.1sec

• Given that Token bucket is full (c=C)

---

Now , We have got two cases

1. To transfer 1M tokens , Will it be instantly with t=0
2. 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. ⇒ c And then we are adding the R tokens produced in 't' time to finnaly get the INPUTFLOW

⇒ 1 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.1sec : 1MB (1 MB transfered)

at t=0.2sec : 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

More Information : Visit Gate Overflow - Gate 2016 Question on Token Bucket