GATE CS 2014 Set 1 Q.38 (CS Q.28): Data Link Layer: Framing, Error Detection and Sliding Window

Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.

Your answer

Official answer and solution

Official answer: 5
From: Official GATE 2014 answer key

Solution

Compute transmission delay and propagation delay parameter $a$ , determine sender window size for 60% efficiency, and find the minimum bits needed for sequence numbers in Selective Repeat.

Given parameters:

Frame size $L = 1\text{ KB} = 1024 \times 8\text{ bits} = 8192\text{ bits}$ .
Bandwidth $B = 1.5\text{ Mbps} = 1.5 \times 10^6\text{ bps}$ .
One-way latency $T_p = 50\text{ msec} = 0.05\text{ sec}$ .

Transmission delay:

T_t = \frac{L}{B} = \frac{8192}{1.5 \times 10^6} \approx 0.005461\text{ sec} = 5.461\text{ msec}

Propagation ratio $a$ :

a = \frac{T_p}{T_t} = \frac{50}{5.461} \approx 9.155

Link utilization formula for sliding window:

\eta = \frac{W_s}{1 + 2a} \ge 0.60

W_s \ge 0.60 \times (1 + 2 \times 9.155) = 0.60 \times 19.31 \approx 11.586

Thus, the minimum sender window size is $W_s = 12$ .

In Selective Repeat protocol, the receiver window equals the sender window ( $W_r = W_s$ ).
The sequence number space must satisfy:

W_s + W_r \le 2^k \implies 2 W_s \le 2^k

2 \times 12 = 24 \le 2^k

Taking the base-2 logarithm:

k \ge \lceil \log_2 24 \rceil = 5\text{ bits}

Thus, 5 bits are required.

Final answer

Common trap

Using Go-Back-N condition $W_s + 1 \le 2^k$ instead of Selective Repeat condition $W_s + W_r \le 2^k$ .

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

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 38 of 65, printed as CS Q.28
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