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

Consider a network connecting two systems located 8000 kilometers apart. The bandwidth of the network is $500 \times 10^6$ bits per second. The propagation speed of the media is $4 \times 10^6$ meters per second. It is needed to design a Go-Back-N sliding window protocol for this network. The average packet size is $10^7$ bits. The network is to be used to its full capacity. Assume that processing delays at nodes are negligible. Then, the minimum size in bits of the sequence number field has to be _____.

Your answer

Official answer and solution

Official answer: 8
From: Official GATE 2015 answer key

Solution

Calculate propagation delay and transmission delay to find the sender window size for 100% link utilization, then determine sequence number bits.

Given network parameters:

Distance $d = 8000\text{ km} = 8 \times 10^6\text{ m}$
Propagation speed $v = 4 \times 10^6\text{ m/s}$
Bandwidth $B = 500 \times 10^6\text{ bps}$
Packet size $L = 10^7\text{ bits}$

Compute delays:

Transmission time per packet: $T_t = \frac{L}{B} = \frac{10^7}{500 \times 10^6} = \frac{1}{50}\text{ s} = 0.02\text{ s} = 20\text{ ms}$
One-way propagation delay: $T_p = \frac{d}{v} = \frac{8 \times 10^6}{4 \times 10^6} = 2\text{ s} = 2000\text{ ms}$

For 100% link capacity utilization in a sliding window protocol, the window size $W$ must cover the round-trip propagation time:

W \ge 1 + 2a = 1 + \frac{2 T_p}{T_t} = 1 + \frac{2 \times 2000}{20} = 1 + 200 = 201\text{ packets}

Thus, the minimum sender window size is $W = 201$ .

In the Go-Back-N protocol, the sequence number space must be strictly greater than the sender window size to avoid ambiguity between successive window cycles:

\text{Available sequence numbers } N \ge W + 1 = 201 + 1 = 202

With $k$ sequence number bits, $2^k \ge 202$ .
Since $2^7 = 128 < 202$ and $2^8 = 256 \ge 202$ , the minimum sequence number field size is 8 bits.

Final answer

Common trap

Using 2^k >= W without adding 1, though in this specific case 2^7 = 128 < 201, so both require 8 bits.

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

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
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