# TCP - Timeout Calculation

[TOC]

## 課程影片

### 第 8F 講 TCP 與網路阻塞偵測與控制技術 L08 6

{%youtube S5aCki1LcGM %}

### How TCP Works - The Timestamps Option

{%youtube 4EFEdAyxemk %}

## Timeout

為了確認封包是否遺失，TCP 在每個封包送出去時會設置一個計時器。如果有在這個這個計時器的時限之內收到對方的 ACK，就可以確認對方有收到這個封包。否則就視為封包遺失，需要重新傳輸。

這個計時器倒數計時的時間區間不能太短，因為封包來回需要時間，如果 ACK 還沒到時，計時器的時間就先到了，那麼就會引發很多不必要的重傳。反之，如果這個時間設的太長，那麼就要花很長的時間才可以確認封包遺失。

過小的 Timeout 會造成不必要的重送; 大量而不必要的重送反而會變成壅塞的原因。

## 定義：RTT

首先，定義「發出一個封包」到「收到這個封包的 ACK」的這段時間間隔為 `SampleRTT`。這個數值可能會因為網路壅塞的程度不同而隨時間變，不是一個常數。

## 標準中的演算法

最原始的演算法是這樣。假定上一次估計的結果是 `EstRTT(n)`，而現在量測到的 RTT 是 `SampleRTT(n+1)`，則定義下一個估計的 RTT 值，是把兩者加權平均：

$$
\begin{align}
&\mathtt{EstRTT(n + 1)}
\newline
&= \alpha \cdot \mathtt{EstRTT(n)} + (1 - \alpha) \cdot \mathtt{SampleRTT(n+1)}
\end{align}
$$

其中，$\alpha$ 是一個介於 $0$ 到 $1$ 之間的數，不過經驗上通常是取 $0.8$ 到 $0.9$ 之間。在這個估計中，`EstRTT(n)` 其實就包含著過去所有的 RTT 累計影響，而 `SampleRTT(n)` 表示目前的壅塞程度。

不過，有了這個估計的 RTT 時間還不夠，因為實際上封包傳遞的時間不會每次剛好都是這個 RTT。所以為了保險起見，`TimeOut` 就設定為「2 倍的 `EstRTT`」。即：

$$
\mathtt{TimeOut(n+1)} = 2 \cdot \mathtt{EstRTT(n+1)}
$$

## 問題：重送時的時間計算

這個 `SampleRTT` 的定義在重送時會有一些狀況。因為重送時，表示同一個封包會被傳送多次，也可能會收到多個 ACK，這時候就會難以認定 `SampleRTT` 該以「哪次傳送」與「哪次 ACK」的間隔計算。下面舉出兩個例子：


在第一個例子中，封包因為沒收到 ACK 而重送了一次，並且只有重送時收到 ACK。這時，如果使用第一次失敗的傳輸作為的起點，那計算兩者時間差得到的 `SampleRTT` 就會是錯誤的 RTT。

而在第二個狀況中，因為第一次傳輸的 ACK 延遲抵達而導致重送。但是重送之後，第一次傳送的 ACK 就到了。如果這時候使用「重送」與「第一次傳送的 ACK」作為 RTT，那麼這個 RTT 也會是錯誤的 RTT（應該要用「第一次傳送」跟「回應第一次傳送的 ACK」來計算）。

### 解法一：Karn/Patridge Algorithm

若在一個給定的 `TimeOut(n)` 下發生重送時，計算這一次的 `TimeOut(n+1)` 時就不使用 `SampleRTT(n+1)` 而是直接把 `TimeOut(n)` 加倍作為 `TimeOut(n+1)`。也就是說，與其使用剛剛的 `TimeOut = 2*EstSample`，現在是使用：

$$
\mathtt{TimeOut(n+1)} =
\begin{cases}
\mathtt{2 \cdot TimeOut(n)} & \text{if retransmits}
\newline
2 \cdot \mathtt{EstRTT(n+1)} & \text{otherwise}
\end{cases}
$$

### 解法二：Jacobson/Karels Algorithm

這個作法將每一次 `SampleRTT` 的「變異數」考慮進去。這是因為：如果網路很不穩定，那麼每一次的 `SampleRTT` 可能會差異很大，所以 `TimeOut` 就不應該使用單次的 `SampleRTT` 作為依據，而是要取一個使多數 `SampleRTT` 可以落在裡面的長度，也就是使用「變異數」作為估計 RTT 的依據。

在每一步中，首先計算現在得到的 `SampleRTT`，跟過去估計的 `EstRTT` 有多少差距。假定這個差距叫做 `diff`：

$$
\begin{align}
&\mathtt{diff(n+1)}
\newline
&= \mathtt{SampleRTT(n+1)} - \mathtt{EstRTT(n)}
\end{align}
$$

接著，依照這個偏差值，加權計算新的 `EstRTT` 與 `Deviation`。即：

$$
\begin{align}
&\mathtt{EstRTT(n+1)}
\newline
&= \mathtt{EstRTT(n)} + \delta \cdot \mathtt{diff(n+1)}
\end{align}
$$

以及：

$$
\begin{align}
&\mathtt{Deviation(n+1)}
\newline
&= \delta \cdot \mathtt{diff(n+1)} + (1 - \delta)\cdot \mathtt{Deviation(n)}
\end{align}
$$

其中，$0 \leq \delta \leq 1$。最後，依照 `Deviation` 與 `EstRTT` 的值，計算 `TimeOut`：

$$
\begin{align}
&\mathtt{TimeOut(n+1)}
\newline
&= \mu \cdot \mathtt{EstRTT(n+1)} + \phi\cdot \mathtt{Deviation(n+1)}
\end{align}
$$

其中，經驗上常用的數值為 $\mu=1$、$\phi = 4$。

在這個 `TimeOut` 的計算中，若網路很穩定，則 `Deviation` 就會很小，所以計算結果就會接近 `EstRTT` 的值; 反之，若 `Deviation` 很大，那麼 `TimeOut` 就會接近 `Deviation`，也就是這個變動的區間有多大。因此 RTT 如果有劇烈的變動，也可以確 `TimeOut` 對於多數的傳輸來說不會太短。