HackMD
TCP - Timeout Calculation
課程影片
第 8F 講 TCP 與網路阻塞偵測與控制技術 L08 6
How TCP Works - The Timestamps Option
Timeout
為了確認封包是否遺失，TCP 在每個封包送出去時會設置一個計時器。如果有在這個這個計時器的時限之內收到對方的 ACK，就可以確認對方有收到這個封包。否則就視為封包遺失，需要重新傳輸。
這個計時器倒數計時的時間區間不能太短，因為封包來回需要時間，如果 ACK 還沒到時，計時器的時間就先到了，那麼就會引發很多不必要的重傳。反之，如果這個時間設的太長，那麼就要花很長的時間才可以確認封包遺失。
過小的 Timeout 會造成不必要的重送; 大量而不必要的重送反而會變成壅塞的原因。
定義：RTT
首先，定義「發出一個封包」到「收到這個封包的 ACK」的這段時間間隔為 SampleRTT。這個數值可能會因為網路壅塞的程度不同而隨時間變，不是一個常數。
標準中的演算法
最原始的演算法是這樣。假定上一次估計的結果是 EstRTT(n)，而現在量測到的 RTT 是 SampleRTT(n+1)，則定義下一個估計的 RTT 值，是把兩者加權平均：
其中， 是一個介於 到 之間的數，不過經驗上通常是取 到 之間。在這個估計中，EstRTT(n) 其實就包含著過去所有的 RTT 累計影響，而 SampleRTT(n) 表示目前的壅塞程度。
不過，有了這個估計的 RTT 時間還不夠，因為實際上封包傳遞的時間不會每次剛好都是這個 RTT。所以為了保險起見，TimeOut 就設定為「2 倍的 EstRTT」。即：
問題：重送時的時間計算
這個 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，現在是使用：
解法二：Jacobson/Karels Algorithm
這個作法將每一次 SampleRTT 的「變異數」考慮進去。這是因為：如果網路很不穩定，那麼每一次的 SampleRTT 可能會差異很大，所以 TimeOut 就不應該使用單次的 SampleRTT 作為依據，而是要取一個使多數 SampleRTT 可以落在裡面的長度，也就是使用「變異數」作為估計 RTT 的依據。
在每一步中，首先計算現在得到的 SampleRTT，跟過去估計的 EstRTT 有多少差距。假定這個差距叫做 diff：
接著，依照這個偏差值，加權計算新的 EstRTT 與 Deviation。即：
以及：
其中，。最後，依照 Deviation 與 EstRTT 的值，計算 TimeOut：
其中，經驗上常用的數值為 、。
在這個 TimeOut 的計算中，若網路很穩定，則 Deviation 就會很小，所以計算結果就會接近 EstRTT 的值; 反之，若 Deviation 很大，那麼 TimeOut 就會接近 Deviation，也就是這個變動的區間有多大。因此 RTT 如果有劇烈的變動，也可以確 TimeOut 對於多數的傳輸來說不會太短。
