Question

Suppose that, when a TCP segment is sent more than once, we take SampleRTT to be the time between the original transmission and the ACK, as in Figure \(5.10(\mathrm{a}) .\) Show that if a connection with a 1-packet window loses every other packet (i.e., each packet is transmitted twice), then EstimatedRTT increases to infinity. Assume TimeOut = EstimatedRTT; both algorithms presented in the text always set TimeOut even larger. Hint: EstimatedRTT \(=\) EstimatedRTT \(+\beta \times(\) SampleRT \(-\) EstimatedRTT).

Short answer

EstimatedRTT increases exponentially due to retransmissions, and ultimately becomes infinite.

Step-by-step solution

Understand the given formula

The formula for EstimatedRTT is given by \( \text{EstimatedRTT} = \text{EstimatedRTT} + \beta \cdot (\text{SampleRTT} - \text{EstimatedRTT}) \). We need to understand how this formula behaves when packets are retransmitted due to loss.

Define initial conditions

Assume the initial EstimatedRTT is a finite value, say \( \text{EstimatedRTT}_0 \). Also, \( \beta \) is a constant value between 0 and 1 (typically \( \beta = 0.875 \)).

Analyze the time between retransmissions

When a packet is lost and retransmitted, SampleRTT is measured as the time interval from the original transmission to the acknowledgment (ACK) of the retransmitted packet. This interval includes the timeout period plus the time to send the retransmitted packet and receive its ACK. Hence, SampleRTT increases more than in the case of no loss.

Calculate SampleRTT for retransmitted packets

Given that each packet is retransmitted, SampleRTT becomes larger with each loss because it waits for an extra timeout period before the ACK. If the timeout period equals the EstimatedRTT, SampleRTT for a retransmitted packet is approximately \(2 \times \text{EstimatedRTT}_n\) where \( \text{EstimatedRTT}_n \) is the EstimatedRTT before the retransmission.

Show the update for EstimatedRTT

After receiving the ACK for the retransmitted packet, EstimatedRTT is updated using the formula: \( \text{EstimatedRTT}_{n+1} = \text{EstimatedRTT}_n + \beta \cdot (2 \times \text{EstimatedRTT}_n - \text{EstimatedRTT}_n) \). Simplifying, this becomes\( \text{EstimatedRTT}_{n+1} = \text{EstimatedRTT}_n + \beta \cdot \text{EstimatedRTT}_n \).

Observe the growth of EstimatedRTT

Notice that each update makes EstimatedRTT larger: \( \text{EstimatedRTT}_{n+1} = \text{EstimatedRTT}_n (1 + \beta) \).Given that \( \beta \) is a constant value between 0 and 1, this reveals exponential growth. Thus, as the number of retransmissions increases, EstimatedRTT will grow without bound, eventually increasing to infinity.

Key concepts

EstimatedRTT calculation

Estimated Round-Trip Time (EstimatedRTT) is critical in TCP to predict the time it takes for a packet to travel to the receiver and back. The formula to update EstimatedRTT after each new measurement is:\[\text{EstimatedRTT} = \text{EstimatedRTT}_{previous} + \beta \cdot (\text{SampleRTT} - \text{EstimatedRTT}_{previous})\]Here, \(\beta\) is a smoothing factor (typically 0.875). The goal is to gradually adjust EstimatedRTT based on new measurements (SampleRTT), maintaining a balance between past knowledge and new data. This helps anticipate network delays accurately.

Each time a new SampleRTT is recorded, EstimatedRTT gets updated, incorporating this new information while retaining the majority of the old value due to the factor \(\beta\). This weighted updating mechanism helps keep EstimatedRTT close to the true average RTT but smooths out any abrupt spikes.

TCP packet loss

TCP packet loss occurs when packets of data traveling across a network fail to reach their destination. In such cases, TCP must retransmit the lost packets. Packet loss can be caused by network congestion, hardware failures, or software issues.

When a packet is lost, TCP presumes the packet has not been received and retransmits it. However, this retransmission affects the dynamics of RTT calculations.

If every other packet is lost, each packet is sent twice. This causes delays and increases the SampleRTT because the lost packet waits for a timeout period before being resent. The retransmission ensures reliability but complicates the RTT estimation process since it introduces additional delay.

SampleRTT measurement

SampleRTT measures the time elapsed from sending a TCP packet until its acknowledgment (ACK) is received. It provides real-time data about current network conditions.

Ideally, SampleRTT is taken when packets are delivered successfully without retransmissions. However, in scenarios with packet loss, SampleRTT includes the timeout period and the time for retransmitted packets.

If a packet is lost and retransmitted, SampleRTT essentially becomes the initial sending time plus the timeout duration plus the transmission time of the retransmitted packet. This extended time increases the SampleRTT value, which can significantly affect the EstimatedRTT when continuous losses occur.

timeout period

The timeout period in TCP is the duration the sender waits for an acknowledgment before assuming the packet is lost and retransmitting it. This period is generally set based on the EstimatedRTT with an added safety margin.

.Timeout is crucial to TCP's reliability, ensuring lost packets are retransmitted. However, it complicates RTT calculations in the presence of packet loss. A longer timeout can mean more delay before retransmission, making SampleRTT measurements significantly larger.

When packets are consistently lost and retransmitted, the timeout period causes a cascading effect. Each SampleRTT after a lost packet will include this extended waiting time, thus disrupting the EstimatedRTT calculation by inflating it with each loss occurrence.

exponential growth in RTT

Due to the nature of the retransmission process and the way EstimatedRTT is calculated, consistent packet loss can lead to exponential growth in RTT.

Let's illustrate with the given formula update: \[\text{EstimatedRTT}_{n+1} = \text{EstimatedRTT}_n + \beta \cdot (2 \times \text{EstimatedRTT}_n - \text{EstimatedRTT}_n)\]This simplifies to: \[\text{EstimatedRTT}_{n+1} = \text{EstimatedRTT}_n (1 + \beta)\]Given a \(\beta\) of 0.875, each retransmission cycle multiplies the EstimatedRTT by 1.875. This multiplication causes the EstimatedRTT to grow exponentially, moving towards infinity as more packets are lost and retransmitted. The larger the EstimatedRTT, the more distorted the timeout period and SampleRTT values become, causing further cyclic amplification until it can no longer reflect meaningful RTT measurements.This exponential growth underscores TCP's vulnerability to packet loss scenarios.

Understanding these underlying mechanisms is crucial for improving TCP algorithms and developing resilient network systems.