Question

Consider the TCP procedure for estimating RTT. Suppose that \(\alpha=0.1\). Let SampleRTT \(_{1}\) be the most recent sample RTT, let SampleRTT \(_{2}\) be the next most recent sample RTT, and so on. a. For a given TCP connection, suppose four acknowledgments have been returned with corresponding sample RTTs: SampleRTT \(_{4}\), SampleRTT \(_{3}\), SampleRTT \(_{2}\), and SampleRTT \(_{1}\). Express EstimatedRTT in terms of the four sample RTTs. b. Generalize your formula for \(n\) sample RTTs. c. For the formula in part (b) let \(n\) approach infinity. Comment on why this averaging procedure is called an exponential moving average.

Short answer

The formula for EstimatedRTT is an exponential moving average because it exponentially decreases the weight of older samples as new samples are added.

Step-by-step solution

Understand the Exponential Moving Average Formula

The formula for updating the estimated round-trip time (RTT) using an exponential moving average is given by: \[\text{EstimatedRTT}_{i} = (1 - \alpha) \cdot \text{EstimatedRTT}_{i-1} + \alpha \cdot \text{SampleRTT}_{i}\]where \(\alpha\) is a smoothing factor between 0 and 1, and \(\text{EstimatedRTT}_{i}\) is the new estimate after incorporating the \(i\)-th sample.

Calculate EstimatedRTT for Four Sample RTTs

Using the exponential moving average formula, we can express EstimatedRTT after four samples as:\[\text{EstimatedRTT}_4 = (1 - \alpha) \cdot ((1 - \alpha) \cdot ((1 - \alpha) \cdot \text{Initial EstimatedRTT} + \alpha \cdot \text{SampleRTT}_1) + \alpha \cdot \text{SampleRTT}_2) + \alpha \cdot \text{SampleRTT}_3) + \alpha \cdot \text{SampleRTT}_4\] Assuming the initial estimated RTT is just the first SampleRTT \(\text{SampleRTT}_1\), we unfold the expression starting from the most recent SampleRTT \(\text{SampleRTT}_4\).

Generalize for n Sample RTTs

We can generalize the formula for \(n\) sample RTTs as follows:\[\text{EstimatedRTT}_n = (1 - \alpha)^{n-1} \cdot \text{Initial EstimatedRTT} + \sum_{i=1}^n \alpha \cdot (1 - \alpha)^{n-i} \cdot \text{SampleRTT}_i\]This formula iteratively reduces the impact of older samples using the factor \((1 - \alpha)^{n-i}\).

Consider n Approaching Infinity

As \(n\) approaches infinity, the influence of the initial EstimatedRTT and older sample RTTs diminishes considerably due to the factor \((1 - \alpha)^{n-1}\), which approaches zero. Hence, more recent SampleRTTs have a more significant weight. This property of diminishing influence of older terms gives this method its name, an exponential moving average, because it exponentially weighs down older samples while giving more weight to recent ones.

Key concepts

TCP Round-Trip Time Estimation

When computers communicate over a network, one important metric they try to estimate is the Round-Trip Time (RTT). This is the time it takes for a packet to travel from the sender to the receiver and back again. In TCP (Transmission Control Protocol), estimating the accurate RTT is crucial because it helps in determining the optimal time for computers to wait before resending a packet.
This RTT estimation is not simple. Network conditions change all the time, like cars on a road. So, TCP uses an exponential moving average to predict RTT.
This process involves:

• Using past RTT samples, known as SampleRTT.
• Applying a special formula to calculate the new estimate, called EstimatedRTT.

EstimatedRTT is updated over time, giving more importance to recent samples while gradually lessening the effect of older ones. This is crucial as it allows TCP to react quickly to new changes in the network conditions.

Smoothing Factor Alpha

An integral component of the exponential moving average used in TCP is the Smoothing Factor, commonly denoted as \( \alpha \). This value determines how much emphasis is placed on the most recent SampleRTT when updating the EstimatedRTT.
Alpha ranges between 0 and 1. Think of it as a balance scale:

• A smaller \( \alpha \) (closer to 0) means older SampleRTTs have more influence. It smooths out fluctuations but can react slowly to changes.
• A larger \( \alpha \) (closer to 1) means recent SampleRTTs are more influential, allowing TCP to quickly react to new network changes.

Choosing the right \( \alpha \) is essential. If it’s too low, the response can be sluggish. If too high, the system may react overly to noise or short-term anomalies. In practice, \( \alpha \) is often set around 0.1 as a compromise, providing a good balance between stability and responsiveness.

SampleRTT Calculation

The concept of SampleRTT is foundational for understanding how TCP updates its RTT estimate. A SampleRTT is simply a recorded response time measurement: the time it takes for a packet to be sent, acknowledged, and returned.
In practice, for each outgoing packet, TCP records the time it was sent. Upon receiving an acknowledgment, TCP calculates the time taken and labels this as the SampleRTT.
These calculations are ongoing as packets travel, creating a constant stream of fresh data points to refine the EstimatedRTT. By leveraging a series of these SampleRTT values, TCP can dynamically adjust and predict the most accurate network conditions over time. This allows for efficient data flow management, as it helps avoid unnecessary delays or packet loss by setting suitable timeout conditions.