Question

You are hired to design a reliable byte-stream protocol that uses a sliding window (like TCP). This protocol will run over a 1-Gbps network. The RTT of the network is \(140 \mathrm{~ms}\), and the maximum segment lifetime is 60 seconds. How many bits would you include in the AdvertisedWindow and SequenceNum fields of your protocol header?

Short answer

AdvertisedWindow field: 25 bits. SequenceNum field: 26 bits.

Step-by-step solution

Understand the Problem

We need to calculate the number of bits required for the AdvertisedWindow and SequenceNum fields in a sliding window byte-stream protocol over a 1-Gbps network with specific RTT and segment lifetime.

Calculate the Bandwidth-Delay Product

The bandwidth-delay product is used to determine the amount of data in transit at any one time. This is calculated by multiplying the bandwidth of the network by the round-trip time (RTT). The bandwidth is 1 Gbps, which is equal to 1,000,000,000 bits per second. The RTT is 140 ms, or 0.140 seconds. Therefore, the bandwidth-delay product is: \[ \text{Bandwidth-Delay Product} = 1,000,000,000 \text{ bps} \times 0.140 \text{ s} = 140,000,000 \text{ bits} \]

Convert the Bandwidth-Delay Product to Bytes

Since the window size is typically considered in bytes, we need to convert the bandwidth-delay product from bits to bytes: \[ 140,000,000 \text{ bits} \times \frac{1 \text{ byte}}{8 \text{ bits}} = 17,500,000 \text{ bytes} \]

Calculate the AdvertisedWindow Size

The advertised window size should be at least as large as the bandwidth-delay product to ensure full utilization of the network. This means the AdvertisedWindow size in bytes is 17,500,000 bytes. To find the number of bits needed to represent this size, we use: \[ \text{Number of bits} = \text{log}_2 (17,500,000) \] Using a calculator, \[ \text{log}_2 (17,500,000) \ \text{≈ 24.39 bits} \] Since we can't have a fraction of a bit, round up to 25 bits.

Determine Sequence Number Space

The sequence number space must be large enough to accommodate all outstanding bytes in transit, plus the maximum segment lifetime. You need enough sequence numbers to cover the window size plus the maximum segment size times the segment lifetime. This ensures no two segments will interfere: This gives us: \[ \text{Maximum sequence number space} = 2 \times \text{Bandwidth-Delay Product} \]Therefore, \[ \text{Maximum sequence number space} = 2 \times 140,000,000 \text{ bits} = 280,000,000 \text{ bits} \ 280,000,000 \text{ bits} \times \frac{1 \text{ byte}}{8 \text{ bits}} = 35,000,000 \text{ bytes} \ \text{Number of bits} = \text{log}_2 (35,000,000) \ \text{≈ 25.06 bits} \] Again, round up to 26 bits.

Key concepts

Sliding Window Protocol

The Sliding Window Protocol is a key technique in reliable data transfer protocols. It allows multiple packets to be sent by the sender before needing an acknowledgment for the first packet. This technique is efficient for high-speed networks. The sliding window ensures that data flow remains constant, avoiding idle time between packets.

This protocol works by maintaining a window of sent but not yet acknowledged packets, which moves or 'slides' forward as acknowledgments are received. There are three main types of sliding window protocols:

• Stop-and-Wait: Simple but inefficient as only one packet is sent at a time.
• Go-Back-N: Sender can send several packets before needing an acknowledgment.
• Selective Repeat: Only the missing packets are retransmitted, improving efficiency.

Bandwidth-Delay Product

The Bandwidth-Delay Product (BDP) is an important concept for understanding the performance of data transfer in networks. It represents the amount of data that can be 'in-flight' (i.e., sent but not yet acknowledged) at any time. BDP is calculated by multiplying the network's bandwidth (rate of data transfer) by the network's round-trip time (RTT).

The formula is:
\[ BDP = Bandwidth \times RTT \] For example, in a network with a 1-Gbps bandwidth and 140-ms RTT, the BDP is:

\[ BDP = 1,000,000,000 \text{ bps} \times 0.140 \text{ s} = 140,000,000 \text{ bits} \]

Understanding BDP helps in setting the appropriate advertised window size to fully utilize the network capacity without overwhelming it.

Round-Trip Time (RTT)

Round-Trip Time (RTT) is the time it takes for a signal to travel from the sender to the receiver and back again. RTT is a crucial metric for network performance because it affects the efficiency of data transmission. High RTT values can lead to delays and reduced throughput.

To calculate RTT, you typically use the

Sequence Number Space

Sequence Number Space is used to uniquely identify each byte or segment of data sent over the network, ensuring the correct sequence of data packets.

In protocols like TCP, the sequence number is necessary to rearrange segments in the correct order and handle any packet loss or duplication. The size of the sequence number space must be large enough to cover the bandwidth-delay product and the maximum segment lifetime:

\[ S = 2 \times \text{BDP} \]For a BDP of 140,000,000 bits, the sequence number space requirement would be:

\[ 2 \times 140,000,000 \text{ bits} = 280,000,000 \text{ bits} \]
Converting to bytes and determining needed bits to represent it:

\[ 280,000,000 \text{ bits} \times \frac{1 \text{ byte}}{8 \text{ bits}} = 35,000,000 \text{ bytes} \] To represent this, we need:
\[ \text{log}_2 (35,000,000) \text{≈ 25.06 bits} \] After rounding up, we get 26 bits.

Advertised Window Size

The Advertised Window Size is a mechanism to control the flow of data in a network. It informs the sender how much data the receiver's buffer can accommodate, ensuring efficient data transmission without overwhelming either party.

For optimal performance, the advertised window size should be at least equal to the bandwidth-delay product to maximize network capacity. Calculating the number of bits needed to represent this window:

\[ \text{Number of bits} = \text{log}_2 (\text{BDP}) \] In our example with a BDP of 140,000,000 bits, converted to bytes:

\[ \text{log}_2 (17,500,000) \text{≈ 24.39 bits} \] After rounding up, this gives us 25 bits.

By setting a proper advertised window, we ensure that the sender knows how much data can be sent without overflowing the receiver, maintaining a smooth data flow.