Problem 50 - Computer Networking: A Top-Down Approach

Question

Consider a simplified TCP's AIMD algorithm where the congestion window size is measured in number of segments, not in bytes. In additive increase, the congestion window size increases by one segment in each RTT. In multiplicative decrease, the congestion window size decreases by half (if the result is not an integer, round down to the nearest integer). Suppose that two TCP connections, \(C_{1}\) and \(C_{2}\), share a single congested link of speed 30 segments per second. Assume that both \(\mathrm{C}_{1}\) and \(\mathrm{C}_{2}\) are in the congestion avoidance phase. Connection \(\mathrm{C}_{1}\) 's RTT is \(50 \mathrm{msec}\) and connection \(\mathrm{C}_{2}\) 's RTT is \(100 \mathrm{msec}\). Assume that when the data rate in the link exceeds the link's speed, all TCP connections experience data segment loss. a. If both \(\mathrm{C}_{1}\) and \(\mathrm{C}_{2}\) at time \(\mathrm{t}_{0}\) have a congestion window of 10 segments, what are their congestion window sizes after 1000 msec? b. In the long run, will these two connections get the same share of the bandwidth of the congested link? Explain.

Step-by-Step Solution

Answer

a. After 1000 msec, CWND sizes are 30 for C1 and 20 for C2. b. C1 will get a larger share of bandwidth due to its lower RTT.

Step 1: Convert Time and Calculate Round Trips

First, we need to calculate the number of Round-Trip Times (RTTs) each connection will complete in 1000 msec. For connection \(C_1\): \[ \text{Number of RTTs} = \frac{1000 \text{ msec}}{50 \text{ msec per RTT}} = 20 \] For connection \(C_2\): \[ \text{Number of RTTs} = \frac{1000 \text{ msec}}{100 \text{ msec per RTT}} = 10 \]

Step 2: Calculate Congestion Window Size for C1

For connection \(C_1\), the congestion window increases by one segment per RTT. Starting from 10 segments: The initial window is 10 segments. After 20 RTTs (calculated in step 1): \[ \text{CWND}_{C_1, 20} = 10 + 20 = 30 \text{ segments} \]

Step 3: Calculate Congestion Window Size for C2

For connection \(C_2\), the congestion window also increases by one segment per RTT. Starting from 10 segments: The initial window is 10 segments. After 10 RTTs: \[ \text{CWND}_{C_2, 10} = 10 + 10 = 20 \text{ segments} \]

Step 4: Determine Congestion Event Occurrence

Before 1000 msec and assuming no prior congestion events during the described time frame, the window sizes for both connections increase by the numbers calculated in steps 2 and 3. Both windows experience losses approximately coinciding when their cumulative use exceeds 30 segments per second, which occurs towards the end of this interval following initial gains.

Step 5: Evaluate Long-Term Bandwidth Share

In the long run, the bandwidth share allocation is determined by the AIMD algorithm's fraction of congestion window increment. With \(C_1\) having a lower RTT, it will outpace \(C_2\) in growing its congestion window faster on a per unit time basis, gaining a higher share of bandwidth. The lower RTT allows \(C_1\) more frequent increase opportunities alongside halves during congestion events.

Key Concepts

Congestion Window

The concept of the congestion window is essential in understanding TCP's AIMD (Additive Increase Multiplicative Decrease) mechanism. The congestion window, often abbreviated as CWND, controls the amount of data that can be sent over the network before needing an acknowledgment.
The AIMD algorithm works by adjusting the size of the congestion window based on network conditions. During the additive increase phase, the window size incrementally grows by one segment per RTT (Round Trip Time). This phase continues until packet loss occurs, signaling network congestion.
When congestion is detected, the multiplicative decrease phase kicks in, reducing the congestion window size by half. This decrease helps prevent network overload.

• Additive Increase: Slow and steady growth.
• Multiplicative Decrease: Responsive reduction to avoid load.

The congestion window thus acts as a dynamic throttle to data flow, balancing efficiency and fairness.

Round-Trip Time (RTT)

Round-trip time, or RTT, is a measurement of the time it takes for a signal to travel from the sender to the receiver and back. This metric is vital for understanding how fast data can be acknowledged and how quickly a sender can increase its congestion window.
In our scenario, connection \(C_1\) has an RTT of 50 msec, while connection \(C_2\) has an RTT of 100 msec. These times directly impact the growth rate of their congestion windows because the frequency of CWND increases is tied to RTT length.

• Connection with smaller RTT (\(C_1\)) can increase its window more often.
• Longer RTT for \(C_2\) means slower growth rate.

RTT not only affects how bandwidth is shared but also how quickly the network reacts to congestion.

Bandwidth Allocation

Bandwidth allocation refers to how network resources like the capacity of a link are distributed among competing traffic flows. TCP AIMD plays a crucial role in this distribution by continually balancing each connection's data flow based on network conditions.
In the given problem, two connections are vying for bandwidth over a shared link. The AIMD algorithm makes sure that each connection increases its share until congestion occurs. After a congestion event, each connection halves its congestion window, which determines their throughput.
Because \(C_1\) has a shorter RTT, it can increase its congestion window more rapidly, leading to a temporary advantage. Over time, \(C_1\) maintains a slightly larger share of the bandwidth due to its faster increase cycle, even though AIMD's fairness strives to equalize shares.

• Short RTT leads to aggressive bandwidth capture.
• AIMD balances the scale, promoting fairness over long-term use.

This dynamic results in an equitable, albeit not perfectly equal, allocation of network resources.