Question

Consider the implementation of sliding window protocol over a lossless link, with a window size of \(W\) frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (\(1\text{k} = 10^3\)) and the one-way propagation delay is 100 milliseconds. Assume that processing times at the sender and receiver are zero and the transmission time of acknowledgements is also zero. Which one of the following options gives the minimum size of \(W\) (in number of frames) required to achieve 100% link utilization?

• A. 10
• B. 21
• C. 20
• D. 11

Hint:

Utilization is 100% only when the window can supply frames continuously for the entire send-plus-round-trip cycle: minimum W = 1 + 2(Tp/Tt).

Answer 1

The Correct Option is B

Step 1: Compute the frame transmission time \(T_t\).
\(T_t = \dfrac{\text{Frame size}}{\text{Bandwidth}} = \dfrac{1000 \text{ bits}}{100 \times 10^3 \text{ bps}} = \dfrac{1000}{100000} = 0.01\text{ s} = 10\text{ ms}\)

Step 2: Compute the round-trip contribution.
One-way propagation delay \(T_p = 100\) ms, so the round-trip propagation delay is \(2T_p = 200\) ms. Since processing times and acknowledgement transmission time are zero, the time from when the sender starts sending the first frame of a window until it receives the acknowledgement for that frame is \(T_t + 2T_p = 10 + 200 = 210\) ms.

Step 3: Apply the sliding window utilization formula.
For a window of \(W\) frames, the sender can transmit continuously (100% utilization) only if it can keep sending frames for the entire round-trip cycle before it must stop and wait, i.e. if the time to transmit \(W\) frames is at least the round-trip cycle time: \[ W \cdot T_t \ge T_t + 2T_p \] \[ W \ge 1 + \dfrac{2T_p}{T_t} = 1 + 2a, \quad \text{where } a = \dfrac{T_p}{T_t} \]

Step 4: Substitute the numbers.
\(a = \dfrac{T_p}{T_t} = \dfrac{100}{10} = 10\) \[ W \ge 1 + 2(10) = 21 \]

Step 5: Check that this bound is tight.
Since \(1+2a = 21\) is already an integer, \(W=21\) frames exactly fill the 210 ms round-trip cycle (\(21 \times 10\text{ms} = 210\text{ms}\)), giving exactly 100% utilization. A smaller \(W\), such as \(W=20\), transmits for only \(200\)ms out of every \(210\)ms cycle, giving utilization \(200/210 \approx 95.2\%\), which is less than 100%.

Step 6: Conclusion.
The minimum window size required for 100% link utilization is 21 frames. \[ \boxed{W = 21} \]