GATE CS 2021 Set 1 Q.59 (CS Q.49): Data Link Layer: Framing, Error Detection and Sliding Window

Consider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following:

The time taken for processing the data frame by the receiver is negligible.
The time taken for processing the acknowledgement frame by the sender is negligible.
The sender has infinite number of frames available for transmission.
The size of the data frame is 2,000 bits and the size of the acknowledgement frame is 10 bits.
The link data rate in each direction is 1 Mbps ( $= 10^6$ bits per second).
One way propagation delay of the link is 100 milliseconds.

The minimum value of the sender's window size in terms of the number of frames, (rounded to the nearest integer) needed to achieve a link utilization of 50% is __________

Your answer

Official answer and solution

Accepted answers: 50 to 52
From: Official GATE 2021 answer key

Solution

Compute transmission and propagation delays to express link utilization as a function of the sender window size.

Given parameters:

Data frame size $L = 2000\text{ bits}$
ACK frame size $L_{\text{ack}} = 10\text{ bits}$
Bandwidth $B = 1\text{ Mbps} = 10^6\text{ bps}$
One-way propagation delay $T_p = 100\text{ ms} = 0.1\text{ s}$

Calculate component delays:

Data frame transmission delay: $T_t = \frac{2000}{10^6}\text{ s} = 2\text{ ms}$
ACK transmission delay: $T_{\text{ack}} = \frac{10}{10^6}\text{ s} = 0.01\text{ ms}$
Total round-trip cycle time for a single frame: $T_{\text{total}} = T_t + 2 T_p + T_{\text{ack}} = 2 + 200 + 0.01 = 202.01\text{ ms}$

Link utilization $\eta$ for a sender window size $W$ is:

\eta = \frac{W \cdot T_t}{T_{\text{total}}} = \frac{W \times 2}{202.01}

Setting $\eta \ge 50\% = 0.5$ :

\frac{2W}{202.01} \ge 0.5 \implies W \ge \frac{0.5 \times 202.01}{2} = 50.5025

Rounding to the nearest integer gives $W = 51$ (the official answer key accepts values between 50 and 52).

Final answer

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

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 59 of 65, printed as CS Q.49
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