GATE CS 2016 Set 2 Q.65 (CS Q.55): Data Link Layer: Framing, Error Detection and Sliding Window

Consider a $128 \times 10^3$ bits/second satellite communication link with one way propagation delay of 150 milliseconds. Selective retransmission (repeat) protocol is used on this link to send data with a frame size of 1 kilobyte. Neglect the transmission time of acknowledgement. The minimum number of bits required for the sequence number field to achieve 100% utilization is _____.

Your answer

Official answer and solution

Official answer: 4
From: Official GATE 2016 answer key

Solution

Determine the required sender window size for 100% channel utilization and compute sequence number bits for Selective Repeat.

Given parameters:

Bandwidth $B = 128 \times 10^3\text{ bits/second}$
One-way propagation delay $T_p = 150\text{ ms} = 0.15\text{ s}$
Frame size $L = 1\text{ KB} = 1024\text{ bytes} = 8192\text{ bits}$ (or $1000\text{ bytes} = 8000\text{ bits}$ )
Acknowledgement transmission time $T_{\text{ack}} = 0$

Compute frame transmission time $T_t$ :

T_t = \frac{8192}{128 \times 10^3} = 0.064\text{ s} = 64\text{ ms}

(Using 8000 bits gives $T_t = 62.5\text{ ms}$ ).

For 100% link utilization ( $\eta = 1$ ):

W_s \ge 1 + 2a = 1 + \frac{2 T_p}{T_t} = 1 + \frac{300\text{ ms}}{64\text{ ms}} = 1 + 4.6875 = 5.6875

(Using $62.5\text{ ms}$ gives $1 + 4.8 = 5.8$ ).
Since window size must be an integer, the minimum sender window size is:

W_s = \lceil 5.6875 \rceil = 6

In Selective Repeat protocol, the sender window size $W_s$ and receiver window size $W_r$ are equal: $W_s = W_r = 6$ . To prevent overlap between sequence number spaces of new and retransmitted frames:

\text{Available sequence numbers } N \ge W_s + W_r = 2 W_s \ge 2 \times 6 = 12

If $k$ bits are allocated for the sequence number field:

2^k \ge 12

For $k = 3$ : $2^3 = 8 < 12$ (insufficient).
For $k = 4$ : $2^4 = 16 \ge 12$ (sufficient).
Therefore, the minimum number of bits required is 4.

Final answer

Common trap

Using the Go-Back-N formula $N \ge W_s + 1 = 7$ , which requires only 3 bits, instead of the Selective Repeat formula $N \ge 2 W_s = 12$ .

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 2
Question: 65 of 65, printed as CS Q.55
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