Question

It is necessary to design a link-layer protocol between two hosts that are directly
connected over a lossless link of length 3000 kilometers. Assume that the link
bandwidth is \(10^8\) bits per second and that the propagation delay in the link is 5
nanoseconds per meter. Every transmitted data byte is assigned a unique sequence
number.
Let 𝑁 be the minimum number of bits needed for the sequence number field in the
protocol header such that
i.
the sequence numbers do not wrap around before 60 seconds, and
ii.
the maximum utilization of the link is achieved.
The value of 𝑁 is ______. (answer in integer)

Hint:

Maximum utilization means the link transmits continuously at the full bandwidth of \(10^{8}\) bits per second for the entire 60 seconds. Compute total bytes sent in that time, then find the smallest \(N\) with \(2^{N}\) at least that many bytes.

Answer 1

Correct Answer: 30

Here is a cleaner way to see why \(N = 30\) using logarithms directly instead of testing powers of 2 one by one.

First, the physical link details (3000 km length, 5 ns/m propagation speed, \(10^{8}\) bps bandwidth) are used to compute the round trip time, which only matters for sizing the transmission window, not for the wraparound requirement directly. The one-way delay works out to \(3 \times 10^{6}\ \text{m} \times 5 \times 10^{-9}\ \text{s/m} = 15\ \text{ms}\).

The key phrase is 'maximum utilization is achieved'. When utilization is 100 percent, the link never sits idle: it pushes out data continuously at its full rated bandwidth of \(10^{8}\) bits per second for the entire 60 second window. So the worst case (fastest) rate of sequence number consumption is exactly the link bandwidth.

Total bits pushed out in 60 seconds:

\[10^{8} \times 60 = 6 \times 10^{9}\ \text{bits}\]

Since numbering is per byte, divide by 8:

\[\frac{6 \times 10^{9}}{8} = 7.5 \times 10^{8}\ \text{bytes}\]

Now we need the sequence number space \(2^{N}\) to accommodate at least \(7.5 \times 10^{8}\) distinct values before repeating, i.e. \(N \geq \log_{2}(7.5 \times 10^{8})\).

\[\log_{2}(7.5 \times 10^{8}) \approx 29.48\]

Since \(N\) must be an integer number of bits, round up:

\[N = \lceil 29.48 \rceil = 30\]

Check: \(2^{29} \approx 5.37 \times 10^{8}\) bytes, which is less than the \(7.5 \times 10^{8}\) bytes needed, so 29 bits would wrap around before 60 seconds are up. \(2^{30} \approx 1.07 \times 10^{9}\) bytes comfortably covers the requirement.

So the minimum sequence number field size is:

\[N = 30\]