Question

Consider a simple congestion-control algorithm that uses linear increase and multiplicative decrease but not slow start, that works in units of packets rather than bytes, and that starts each connection with a congestion window equal to one packet. Give a detailed sketch of this algorithm. Assume the delay is latency only, and that when a group of packets is sent, only a single ACK is returned. Plot the congestion window as a function of round-trip times for the situation in which the following packets are lost: \(9,25,30,38\), and 50 . For simplicity, assume a perfect timeout mechanism that detects a lost packet exactly 1 RTT after it is transmitted.

Short answer

Plot the congestion window by increasing CWND linearly each RTT until loss, then halve CWND at losses of packets 9, 25, 30, 38, and 50.

Step-by-step solution

Initialize the Congestion Window

At the start of the connection, set the congestion window (CWND) to 1 packet.

Linear Increase

For each round-trip time (RTT) without packet loss, increase the CWND by one packet. This represents the linear increase part of the algorithm.

Handle Packet Loss

When packet loss is detected (in this case, packets 9, 25, 30, 38, and 50), immediately reduce the CWND by half (multiplicative decrease). Assume the CWND after reduction must be at least 1 packet.

Plot Congestion Window

Create a plot of the congestion window as a function of RTTs. Mark the RTTs where packet loss occurs and adjust the CWND accordingly.

Key concepts

Linear Increase

The concept of linear increase in congestion control refers to the gradual growth of the congestion window (CWND) over time. Here's how it works in simple terms. When a data connection starts, it begins cautiously, usually with a CWND set to one packet. This is to avoid overwhelming the network. For each Round Trip Time (RTT) where no packet loss occurs, the CWND is increased by one packet. This slow and steady increase helps to probe the available bandwidth without causing sudden spikes in network traffic. Imagine a driver slowly accelerating on an empty road, going one mile per hour faster every minute. Similarly, linear increase helps data flow smoothly, accommodating more data packets as the network proves that it can handle them.

Multiplicative Decrease

Multiplicative decrease is the counterbalance to linear increase in congestion control. When packet loss is detected, it indicates that the network is congested and cannot handle the current load. In response, the algorithm cuts the congestion window (CWND) by half immediately. This aggressive reduction helps to quickly reduce the load on the network to alleviate congestion. For example, if the CWND was 16 packets just before packet loss, it will be reduced to 8 packets right after the loss is detected. This approach resembles a driver hitting the brakes hard when noticing a traffic jam ahead; the idea is to quickly scale back to prevent further issues.

Congestion Window

The congestion window (CWND) is a crucial parameter in congestion control algorithms. It signifies the maximum number of data packets the sender can have unacknowledged at any given time. Think of it as a measuring cup for data. A larger CWND means more data can be sent before waiting for an acknowledgment. Conversely, a smaller CWND slows down the data flow. Ideally, the CWND adjusts dynamically based on the network conditions. Starting with a small CWND helps ensure that the network is not overwhelmed from the get-go. As the network proves it can handle more traffic (i.e., no packet loss), the CWND is increased. When packet loss occurs, the CWND is reduced to throttle down the data flow.

RTT (Round Trip Time)

Round Trip Time (RTT) is the duration it takes for a signal to go from the sender to the receiver and back again. In the context of congestion control, RTT is a vital measure. Suppose it takes 100 milliseconds to send a packet and receive an acknowledgment. This 100 milliseconds is the RTT. The congestion control algorithm adjusts the CWND based on the RTT. For instance, in linear increase, the CWND is incrementally increased every RTT without packet loss. On the flip side, if a packet loss is detected, the CWND is reduced upon the next RTT completion. Monitoring RTT helps the algorithm to react appropriately to the current network conditions.

Packet Loss Detection

Packet loss detection is a key component in congestion control algorithms. When a data packet is sent but not acknowledged within a certain timeframe (equal to one RTT for our algorithm), it indicates packet loss. In our specific exercise, this mechanism kicks in perfectly after one RTT. Packet loss often signals network congestion or errors, prompting the algorithm to reduce the CWND multiplicatively (by half) to alleviate the congestion. Detecting packet loss in a timely and accurate manner is essential for maintaining robust and efficient network performance. It ensures that the sender reduces its load on the network quickly, helping to restore normal data flow. This timely detection aids in not just managing but also preventing prolonged congestive states on the network.