GATE | GATE-CS-2016 (Set 1) | Question 64

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.
(A) 1.1
(B) 0.1
(C) 2.1
(D) 2.0

Answer: (A)

Explanation: Token bucket is a congestion control algorithm for data transfer. It takes tokens to synchronize between the rate of incoming and outgoing data.

According to the token bucket algorithm, the minimum time required 
to send 1 MB of data or the maximum rate of data transmission is 
given by:

   S = C / (M - P)

M = Maximum burst rate,
P = Rate of arrival of a token,
C = capacity of the bucket

Using the above formula for the given question we can say that:

M = 20 MB
P = 10 MB
C = 1 MB
S = 1 / (20- 10) = 0.1 sec

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), i.e. 11 MB of data to be transmitted.

Time required to send the 11 MB will be 11 * 0.1 = 1.1 sec

The above image is adopted from here.

Leave a Reply

Your email address will not be published. Required fields are marked *