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 ____________.

Question

cdquestions Admin · Accepted Answer

Step 1: Find the one way propagation delay on the link. The link length is $$ d = 3000 \text{ km} = 3{,}000{,}000 \text{ m} $$ The propagation delay is given as $5$ nanoseconds per meter, so the one way propagation delay is $$ T_p = 3{,}000{,}000 \times 5 \text{ ns} = 15{,}000{,}000 \text{ ns} = 15 \text{ ms} $$ Step 2: Find the round trip time. Data flows one way and an acknowledgement must come back before the sender is sure the frame arrived, so the round trip time is twice the one way propagation delay. The transmission time of an acknowledgement is treated as negligible here since it is tiny compared to the propagation delay: $$ RTT = 2 T_p = 2 \times 15 \text{ ms} = 30 \text{ ms} = 0.03 \text{ s} $$ Step 3: Work out the window size needed for maximum link utilization. To keep the link continuously busy with no idle time, the sender must have enough unacknowledged data in flight to cover the entire round trip time. In bits, this required window is $$ W_{\text{bits}} = \text{Bandwidth} \times RTT = 10^8 \times 0.03 = 3{,}000{,}000 \text{ bits} $$ Since every byte gets its own sequence number, convert this to bytes by dividing by $8$: $$ W_{\text{bytes}} = \frac{3{,}000{,}000}{8} = 375{,}000 \text{ bytes} $$ This means at least $375{,}000$ distinct sequence numbers must be available at any instant, so that this many unacknowledged bytes can be outstanding without two different bytes sharing the same sequence number. Step 4: Convert the window requirement into a bound on $N$. With an $N$ bit sequence number field, there are $2^N$ distinct sequence numbers available. For the window from Step 3 to fit, we need $$ 2^N \geq 375{,}000 $$ Checking powers of $2$: $2^{18} = 262{,}144$, which is too small, while $2^{19} = 524{,}288$, which is big enough. So condition (ii) alone requires $$ N \geq 19 $$ Step 5: Work out how many bytes are sent in 60 seconds at full link utilization. Condition (ii) requires the link to run at maximum utilization, which means data is being sent continuously at the full bandwidth of $10^8$ bits per second. Converting to bytes per second: $$ \text{Bytes per second} = \frac{10^8}{8} = 12{,}500{,}000 \text{ bytes/s} $$ Over $60$ seconds, the total number of bytes transmitted, and hence the total number of sequence numbers used, is $$ 12{,}500{,}000 \times 60 = 750{,}000{,}000 \text{ bytes} $$ Step 6: Convert the no wrap around requirement into a bound on $N$. For the sequence numbers to not repeat before $60$ seconds have passed, the total pool of $2^N$ sequence numbers must be at least this many: $$ 2^N \geq 750{,}000{,}000 $$ Checking powers of $2$: $2^{29} = 536{,}870{,}912$, which is too small, while $2^{30} = 1{,}073{,}741{,}824$, which is big enough. So condition (i) alone requires $$ N \geq 30 $$ Step 7: Combine both conditions. The value of $N$ must satisfy both bounds at the same time, from Step 4 and Step 6: $$ N \geq 19 \quad \text{and} \quad N \geq 30 $$ Values of $N$ that satisfy condition (ii) but are less than $30$ do not satisfy condition (i), so the binding requirement is the larger one. The minimum $N$ that satisfies both is $$ N = \max(19, 30) = 30 $$ Step 8: Final Answer. The minimum number of bits needed for the sequence number field is 30. $$ \boxed{30} $$

Show Hint

Correct Answer: 30

Solution and Explanation

Top GATE CS Computer Networks Questions

Top GATE CS Questions