Link-Layer Protocol Design: Sequence Number Calculation

This problem requires determining the minimum number of bits N for a sequence number field in a link-layer protocol header. Two conditions must be met:

• Sequence numbers must not wrap around within 60 seconds.
• Maximum link utilization must be achieved.

Calculate Link Parameters

First, calculate the propagation delay and transmission time.

• Link Length: 3000 kilometers = $3000 \times 10^3$ meters = $3 \times 10^6$ meters.
• Propagation Delay per meter: 5 nanoseconds/meter = $5 \times 10^{-9}$ seconds/meter.
• Total Propagation Delay ($T_{prop}$): $T_{prop} = \text{Link Length} \times \text{Propagation Delay per meter}$ $T_{prop} = (3 \times 10^6 \text{ m}) \times (5 \times 10^{-9} \text{ s/m}) = 15 \times 10^{-3}$ seconds = 15 milliseconds (ms).
• Link Bandwidth (B): $10^8$ bits per second.
• Data Unit Size: 1 byte = 8 bits.
• Transmission Delay for one byte ($T_{trans, byte}$): $T_{trans, byte} = \frac{\text{Data Unit Size (bits)}}{\text{Bandwidth (bps)}} = \frac{8 \text{ bits}}{10^8 \text{ bps}} = 8 \times 10^{-8}$ seconds = 0.08 microseconds ($\mu$s).
• Round Trip Time (RTT): Assuming data and acknowledgment travel the link. $RTT = 2 \times T_{prop} = 2 \times 15 \text{ ms} = 30 \text{ ms} = 0.03$ seconds.

Condition 1: Sequence Number Wrap-Around Time

The sequence number space ($2^N$) must be large enough to accommodate all unique data bytes transmitted within 60 seconds without repeating.

• Total bits transmitted in 60 seconds: $\text{Total Bits} = \text{Bandwidth} \times \text{Time} = (10^8 \text{ bps}) \times (60 \text{ s}) = 6 \times 10^9$ bits.
• Total bytes transmitted in 60 seconds: $\text{Total Bytes} = \frac{\text{Total Bits}}{8 \text{ bits/byte}} = \frac{6 \times 10^9 \text{ bits}}{8 \text{ bits/byte}} = 7.5 \times 10^8$ bytes.
• For sequence numbers not to wrap around, the total number of unique sequence numbers available must be greater than or equal to the total bytes transmitted in 60 seconds: $2^N \ge 7.5 \times 10^8$.
• To find the minimum integer N: $N \ge \log_2(7.5 \times 10^8)$. Since $2^{29} \approx 5.36 \times 10^8$ and $2^{30} \approx 1.07 \times 10^9$, the smallest integer N satisfying this is 30.
• Thus, Condition 1 requires $N \ge 30$.

Condition 2: Maximum Link Utilization

Maximum link utilization in a sliding window protocol is achieved when the sender can continuously transmit data, keeping the link busy during the RTT. This requires a window size (W) large enough to fill the network pipe.

• The number of bytes that can be in flight concurrently to fill the pipe over the RTT is determined by the link's capacity during the RTT. $\text{Capacity (bits)} = \text{Bandwidth} \times RTT = (10^8 \text{ bps}) \times (0.03 \text{ s}) = 3 \times 10^6$ bits.
• $\text{Capacity (bytes)} = \frac{3 \times 10^6 \text{ bits}}{8 \text{ bits/byte}} = 375,000$ bytes.
• For maximum utilization, the window size W must be at least this capacity. So, $W \ge 375,000$ bytes.
• Since each transmitted data byte is assigned a unique sequence number, the sequence number space must be able to accommodate W distinct numbers. $2^N \ge W$.
• $2^N \ge 375,000$.
• To find the minimum integer N: $N \ge \log_2(375,000)$. Since $2^{18} \approx 2.62 \times 10^5$ and $2^{19} \approx 5.24 \times 10^5$, the smallest integer N satisfying this is 19.
• Thus, Condition 2 requires $N \ge 19$.

Determine Minimum N

To satisfy both conditions, N must be the maximum of the values derived from each condition.

• From Condition 1: $N \ge 30$.
• From Condition 2: $N \ge 19$.
• The minimum N is $\max(30, 19) = 30$.

Therefore, the minimum number of bits needed for the sequence number field is 30.