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 .
Here one byte is considered as one token
⇒ C=1 M tokens
⇒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
Now , We have got two cases
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