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 108 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

We must find the minimum number of bits \(N\) for the sequence number field so that (i) sequence numbers do not repeat before 60 seconds and (ii) the link achieves maximum utilization.

Step 1: Compute the one-way propagation delay.

Link length \(= 3000\ \text{km} = 3 \times 10^{6}\ \text{m}\), and propagation delay per meter \(= 5\ \text{ns/m} = 5 \times 10^{-9}\ \text{s/m}\).

\[T_{prop} = 3 \times 10^{6} \times 5 \times 10^{-9} = 1.5 \times 10^{-2}\ \text{s} = 15\ \text{ms}\]

Step 2: Interpret the maximum utilization condition.

If the link achieves maximum (100 percent) utilization, the sender is continuously transmitting new data at the full link bandwidth \(B = 10^{8}\) bits per second, with no idle time. This means the fastest possible rate at which sequence numbers get consumed equals the link bandwidth itself, since every transmitted byte gets a unique sequence number and the link is never idle.

Step 3: Compute the total data sent in 60 seconds at full bandwidth.

\[\text{Total bits in 60 s} = B \times 60 = 10^{8} \times 60 = 6 \times 10^{9}\ \text{bits}\]

Converting to bytes (since sequence numbers are assigned per byte):

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

Step 4: Find the smallest \(N\) such that the sequence number space covers this many bytes.

We need \(2^{N} \geq 750{,}000{,}000\).

\[2^{29} = 536{,}870{,}912 \quad (\text{too small, less than } 750{,}000{,}000)\]\[2^{30} = 1{,}073{,}741{,}824 \quad (\text{sufficient, greater than } 750{,}000{,}000)\]

Step 5: Conclusion.

Since \(2^{29}\) is not enough to number every byte sent in 60 seconds at full utilization but \(2^{30}\) is, the minimum sequence number field width is \(N = 30\) bits. Note that the propagation delay and bandwidth-delay product values (used for window sizing) are much smaller than this requirement, so the binding constraint here is purely the no-wraparound-before-60-seconds condition combined with sending at maximum utilization.

Final Answer:

\[\boxed{N = 30}\]