GATE CS 2016 Set 1 Q.64 (CS Q.54): Transport Layer: UDP, TCP Flow and Congestion Control, Sockets

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.

Your answer

Official answer and solution

Official answer: 1.1
From: Official GATE 2016 answer key

Solution

Determine the burst duration at maximum output rate while consuming bucket capacity, and add the time needed to transmit remaining data at the token generation rate.

Given parameters:

Token bucket capacity $C = 1\text{ MB}$ .
Maximum transmission rate $M = 20\text{ MB/s}$ .
Token arrival rate $\rho = 10\text{ MB/s}$ .
Initial bucket state: full ( $1\text{ MB}$ of tokens).
Total data to transmit $D = 12\text{ MB}$ .

Phase 1: Burst transmission at maximum rate $M$ :

Let $t_b$ be the duration of the burst.
During $t_b$ , data is transmitted at rate $M$ , while tokens arrive at rate $\rho$ .
The bucket empties when the total tokens consumed equal initial tokens plus newly arrived tokens:

M \cdot t_b = C + \rho \cdot t_b

t_b (M - \rho) = C \implies t_b = \frac{C}{M - \rho} = \frac{1}{20 - 10} = \frac{1}{10} = 0.1\text{ seconds}

Phase 2: Remaining data transmission:

Data transmitted during burst $= M \cdot t_b = 20 \times 0.1 = 2\text{ MB}$ .
Remaining data to transmit $= 12 - 2 = 10\text{ MB}$ .
Once the bucket is empty, data can only be transmitted as fast as tokens arrive, which is at rate $\rho = 10\text{ MB/s}$ :

t_{\text{remaining}} = \frac{10\text{ MB}}{10\text{ MB/s}} = 1.0\text{ second}

Total minimum time required:

T = t_b + t_{\text{remaining}} = 0.1 + 1.0 = 1.1\text{ seconds}

Final answer

1.1

Common trap

Ignoring token regeneration during the initial burst, calculating burst time as $1 / 20 = 0.05$ s and remaining $11 / 10 = 1.1$ s, totaling $1.15$ s.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 64 of 65, printed as CS Q.54
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source