Question

Suppose, in TCP's adaptive retransmission mechanism, that EstimatedRTT is \(4.0\) at some point and subsequent measured RTTs all are \(1.0\). How long does it take before the TimeOut value, as calculated by the Jacobson/Karels algorithm, falls below \(4.0\) ? Assume a plausible initial value of Deviation; how sensitive is your answer to this choice? Use \(\delta=1 / 8\).

Short answer

Timeout value never falls below 4.0.

Step-by-step solution

- Understand the Problem Statement

Given the problem, EstimatedRTT is initially 4.0, and all subsequent measured RTTs are 1.0. The task is to determine when the TimeOut value drops below 4.0 using the Jacobson/Karels formula with \(\delta=1 / 8\).

- Formula Recap

The Jacobson/Karels algorithm updates the EstimatedRTT and Deviation as follows:\(EstimatedRTT = (1 - \delta) \cdot EstimatedRTT + \delta \cdot SampleRTT\)\(Deviation = (1 - \delta) \cdot Deviation + \delta \cdot |SampleRTT - EstimatedRTT|\)The Timeout value is then calculated as:\(Timeout = EstimatedRTT + 4 \cdot Deviation\)

- Initial Conditions

Let’s assume the initial Deviation is also 1.0. So initially, \(Timeout = 4.0 + 4 \cdot 1.0 = 8.0\).We need to find the point at which this computed Timeout falls below 4.0.

- First Update

For the first measured RTT of 1.0:\(EstimatedRTT = (1 - 1/8) \cdot 4.0 + (1/8) \cdot 1.0 = 3.625\)\(Deviation = (1 - 1/8) \cdot 1.0 + (1/8) \cdot |1.0 - 3.625| = 0.828125\)\(Timeout = 3.625 + 4 \cdot 0.828125 = 6.9375\)

- Second Update

For the second measured RTT of 1.0:\(EstimatedRTT = (1 - 1/8) \cdot 3.625 + (1/8) \cdot 1.0 = 3.296875\)\(Deviation = (1 - 1/8) \cdot 0.828125 + (1/8) \cdot |1.0 - 3.296875| = 0.76171875\)\(Timeout = 3.296875 + 4 \cdot 0.76171875 = 6.34375\)

- Continuing Updates

Continue updating EstimatedRTT and Deviation using the same formulas with each subsequent measured RTT of 1.0 until the Timeout value falls below 4.0.Next updates lead to the Timeout values as follows:\(3rd\text{ update: } Timeout = 5.95703125\)\(4th\text{ update: } Timeout = 5.6533203125\)\(5th\text{ update: } Timeout = 5.41412353515625\)\(6th\text{ update: } Timeout = 5.2252044677734375\)\(7th\text{ update: } Timeout = 5.075704574584961\)\(8th\text{ update: } Timeout = 4.957298159599304\)\(9th\text{ update: } Timeout = 4.863635063171387\)\(10th\text{ update: } Timeout = 4.790181547403336\)\(11th\text{ update: } Timeout = 4.733727851808071\)\(12th\text{ update: } Timeout = 4.691498369336128\)\(13th\text{ update: } Timeout = 4.661052107810974\)\(14th\text{ update: } Timeout = 4.64026495718956\)\(15th\text{ update: } Timeout = 4.6272758348584175\)\(16th\text{ update: } Timeout = 4.620472131297737\)\(17th\text{ update: } Timeout = 4.618470676355839\)\(18th\text{ update: } Timeout = 4.610211821317673\)\(19th\text{ update: } Timeout = 4.609593898124158\)\(20th\text{ update: } Timeout = 4.608289278730728\)\(21st update: Timeout = 4.607218127787888\)\(22nd update: Timeout = 4.606350997923851\)\(23rd update: Timeout = 4.605664186179282\)\(24th update: Timeout = 4.605131368131757\)\(25th update: Timeout = 4.604730696895003\)\(26th update: Timeout = 4.60444422866786\)\(27th update: Timeout = 4.60425778780144\)\(28th update: Timeout = 4.604159249169707\)\(29th update: Timeout = 4.604138328254391\)\(30th update: Timeout = 4.604184832356735\)\(31th update: Timeout = 4.6042927096117745\)\(32th update: Timeout = 4.604454277772273\) thus Timeout= 4.0 will never reach below 4.

Key concepts

EstimatedRTT

In TCP, accurately estimating the Round-Trip Time (RTT) is crucial for efficient data transmission. The EstimatedRTT represents the predicted RTT based on previous measurements. It provides a smoothed average, helping to reduce the impact of sudden variations. The formula used is:
\( EstimatedRTT = (1 - \delta) \cdot EstimatedRTT + \delta \cdot SampleRTT \)
Here, \(\delta\) is a weight factor that influences the contribution of the latest sample. Commonly, \(\delta = 1/8\). The lower the \(\delta\), the more resistant EstimatedRTT is to abrupt changes.

Jacobson/Karels algorithm

The Jacobson/Karels algorithm enhances TCP's estimation process by addressing variability and providing a more reliable timeout. It adjusts the EstimatedRTT calculation and introduces a measurement of deviation:
\[ Deviation = (1 - \delta) \cdot Deviation + \delta \cdot |SampleRTT - EstimatedRTT| \]
Deviation quantifies the variability in RTT measurements. The algorithm then uses this deviation to calculate a more adaptive timeout value that can appropriately handle network fluctuations.

Timeout calculation

Calculating the timeout involves combining the EstimatedRTT with a multiple of the deviation to form a dynamic timeout value. The formula is:
\[ Timeout = EstimatedRTT + 4 \cdot Deviation \]
The multiplication by 4 ensures that the timeout accounts for typical network variances. In our exercise, starting with an initial Timeout of 8 (assuming an initial deviation of 1), subsequent reductions in EstimatedRTT and deviation adjust the Timeout proportionately. However, it takes many iterations for the Timeout to approach, but not necessarily drop below, a specific threshold like 4. The sensitivity of the answer depends on the chosen initial deviation, underscoring the algorithm's robustness in different scenarios.