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 \(N\) 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 \(N\) is ____________.

Hint:

Find the bytes needed to fill the bandwidth-delay product for full utilization, and separately find the bytes sent in 60 seconds at full bandwidth; the sequence number field must be large enough to cover the larger of the two.

Answer 1

Correct Answer: 30

Step 1: Find the round trip propagation delay.
The cable stretches $3000$ km, which is $3 \times 10^6$ meters. At $5$ ns of delay for every meter, one pass across the link takes
\[ T_p = 3\times10^6 \times 5 \text{ ns} = 1.5\times10^7 \text{ ns} = 15 \text{ ms} \]
A signal and its acknowledgement together cross the link twice, so
\[ RTT = 2\times15 \text{ ms} = 30 \text{ ms} \]

Step 2: Start from the no wrap in 60 seconds requirement, since sending continues at full speed.
Because the second condition asks for maximum utilization, the sender is pushing bits onto the wire at the full link rate of $10^8$ bits per second without any gaps. Each byte gets one sequence number, and $8$ bits make one byte, so the byte rate is
\[ \frac{10^8}{8} = 1.25\times10^7 \text{ bytes per second} \]

Step 3: Multiply the byte rate by 60 seconds.
\[ 1.25\times10^7 \times 60 = 7.5\times10^8 \text{ bytes} \]
This is the number of unique sequence numbers consumed inside one minute of full speed sending. The sequence number space, of size $2^N$, has to be large enough to hand out a fresh number to every one of these bytes without looping back to an old value.

Step 4: Find the smallest $N$ that covers $7.5\times10^8$ values.
Try $N=29$: $2^{29}=536{,}870{,}912$, which is less than $7.5\times10^8$, so it falls short.
Try $N=30$: $2^{30}=1{,}073{,}741{,}824$, which comfortably covers $7.5\times10^8$.
So this condition alone forces
\[ N \geq 30 \]

Step 5: Now check the maximum utilization requirement on its own.
To keep the pipe full, the sender needs enough bytes in flight, sent but not yet acknowledged, to cover the full round trip time. The number of bits that fit in one RTT at full rate is
\[ 10^8 \times 0.03 \text{ s} = 3\times10^6 \text{ bits} \]
Dividing by $8$ to get bytes,
\[ \frac{3\times10^6}{8} = 375{,}000 \text{ bytes} \]
So the sequence number space must at least cover $375{,}000$ values for the window to be usable, which needs $2^N \geq 375{,}000$, and since $2^{19}=524{,}288$ already clears this while $2^{18}=262{,}144$ does not, this condition only needs
\[ N \geq 19 \]

Step 6: Take whichever requirement is stricter.
The field has to satisfy both requirements together, so the answer is the larger of the two lower bounds found in Step 4 and Step 5. Since $30$ is bigger than $19$, the no wrap around condition is the one that actually decides the answer.

Step 7: State the final bit count.
\[ \boxed{N=30} \]