For a host machine that uses the token bucket algorithm for congestion…
2016
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per second. Tokens arrive at a rate to sustain output at a rate of 10 megabytes per second. The token bucket is currently full and the machine needs to send 12 megabytes of data. The minimum time required to transmit the data is ________ seconds.
Attempted by 75 students.
Show answer & explanation
Correct answer: 1.1
Key idea: while transmitting at the peak rate, tokens continue to arrive, so the bucket drains at the difference between the peak output rate and the token arrival rate.
During an initial burst at the maximum output rate of 20 megabytes per second, tokens arrive at 10 megabytes per second. The net token depletion rate is 20 − 10 = 10 megabytes per second. With an initial bucket of 1 megabyte, the burst can last for 1 / 10 = 0.1 seconds.
Amount of data sent during this burst = 20 MB/s × 0.1 s = 2 megabytes. Remaining data = 12 − 2 = 10 megabytes.
After the bucket is empty, the sender can only be sustained by the token arrival rate of 10 megabytes per second. Time to send the remaining 10 megabytes = 10 / 10 = 1.0 second.
Total minimum transmission time = burst time + sustained time = 0.1 + 1.0 = 1.1 seconds.
Final answer: 1.1 seconds.