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 ______. (answer in integer)
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.
Important Questions from Data Link Layer
Which of the following protocols is responsible for converting higher level protocol addresses to physical network addresses?
Which of the following devices takes data sent from one network device and forwards it to the destination node based on MAC address?
Which of the following statements is/are true with regard to various layers in the Internet stack?
P: At the data link layer, a packet of transmitted information is called a frame
Q: At the network layer, a packet of transmitted information is called a segment
Given below are two statements:
Statement I: The laws of nature put two fundamental limits on data rate of a channel. The H.Nyquist limit restricts the number of independent samples per second to twice the band-width in a Noiseless channel.
Statement II: Shannon's major result about noised channel is that maximum data rate of a channel whose band width is H Hz, and whose signal-to-noise ratio is S/N is given by:
Maximum number of bits/sec \(= H \;log_2 \left(1+\frac{S}{N}\right)\) is given by:
In the light of the above statements. choose the correct answer from the options given below
Which of the following statements are true?
(a) Three broad categories of Networks are:
(i) Circuit Switched Networks
(ii) Packet Switched Networks
(iii) Message Switched Networks
(b) Circuit Switched Network resources need not be reserved during the set up phase.
(c) In packet switching there is no resource allocation for packets.
