閱讀須知：筆記為閱讀《TCP IP 詳解卷1：協定》後摘抄的一些知識點，其間也有加入一些根據英文原版的自己翻譯和結合網上知識後的了解，是以有些段落之間并不能夠串聯上或者知識點與書上略有差别(基本差别不大，參考的資料屬 RFC官方文檔
)。
第十四章：逾時與重傳
TCP協定為了提供可靠的資料傳輸服務，會啟動資料重傳來解決下層網絡層(IP)可能出現的資料包丢失。
逾時重傳介紹
TCP重傳由兩套獨立機制來完成重傳，基于時間的逾時重傳(RTO，TCP發送資料時會設定一個計時器，若至計時器逾時仍未收到資料确認資訊，則會引發相應的逾時和計時器重傳操作)，基于确認資訊的構成(通常在沒發生延時的情況下，若TCP累積确認無法傳回新的ACK，或者當ACK包含的選擇确認資訊(SACK)表明出現失序封包段時，快速重傳會推斷出現丢包，這時候發送端認為接收端可能出現資料丢失時，需要決定發送新資料還是重傳)。
對于逾時和重傳，之前有了一定的認識，如：
在ICMP目的不可達的時，采用UDP的TFTP用戶端使用簡單且低效的逾時和重傳政策：設定足夠大的逾時間隔，每5秒進行一次重傳；
第13章提到TCP所使用指數回退行為：在目的主機不存在的場景中，TCP在嘗試建立連接配接過程中，每次重傳時采用比上次更大的延時間隔。
TCP能不斷"學習"發送端與接收端之間的鍊路特征，以記錄一些狀态變量。早些的TCP中，當連接配接關閉，這些學習而得的狀态便會丢失；在較新的TCP中實作了維護這些路徑成本，即使連接配接斷開後，也能儲存之前存在的路由或轉發表項或其他一些系統資料結構。當創立一個新的連接配接時，首先檢視資料結構中是否存在與該目的端的先前通信資訊，如果存在則使用資訊來初始化連接配接的一些變量值。如在linux中，變量值更新為現存值中的最大值和最近測量的資料，可通過iproute2[IPR2]的相關工具來檢視變量值。這也稱為TCP連接配接的目的度量。
當TCP逾時重傳時，它并不需要完全重傳相同的封包段，TCP允許執行重新組包，發送一個更大的封包段來提高性能(但不能大于接收端通告的MSS和路徑MTU)。因為TCP是通過位元組号來識别發送和接收的資料的。
RTO值的計算
由于TCP需要适應不同環境進行操作，若TCP先于RTT開始重傳，可能會在網絡中引入不必要的重複資料；若延遲遠大于RTT的間隔發送重傳資料，整體網絡使用率(以及單個連接配接吞吐量)會随之下降。是以，RTO需要TCP動态設定，且RTO的設定是TCP性能的關鍵。
TCP在收到資料後會傳回确認資訊，是以可在該資訊中攜帶一個位元組的資料來測量傳輸該确認資訊所需的時間，每個此類的測量結果被稱為RTT樣本，TCP則根據這些樣本來給出RTO估值。每個TCP連接配接的RTT均獨立估算，并且重傳計時器會對任何占用序列号的在傳資料計時。
RTO計算的經典方法：
# 采用如下公式得到平滑的RTT估計值(稱為SRTT)：
SRTT ← α(SRTT)+(1-α)RTTs (s為下标)
# SRTT是基于現存值和新的樣本值RTTs得到的更新結果，常量α是平滑因子，推薦值為0.8~0.9，這個方法被稱為指數權重移動平均或者低通過濾器。
# 采用以下公式設定RTO：
RTO = min(ubound,max(1bound,(SRTT)β))
# β為時延離散因子，推薦值為1.3~2.0，ubound為RTO的上邊界(可設定建議值，如1分鐘)，lbound為RTO的下邊界(可設定建議值，如1秒)。它使得RTO的值設定為1秒或約2倍的SRTT。
# 相對于文檔的RTT來說，這種方法能取得不錯的性能，然而若TCP運作于RTT變化較大的網絡中，則無法獲得期望的效果。 RTO計算的标準方法(結合平均值和平均偏差來進行估算)：
srtt ← (1 - g)(srtt) + (g)M
rttvar ← (1 - h)(rttvar) + (h)(|M - srtt|)
RTO = srtt + 4(rttvar)
# srtt代替了之前的SRTT，且rttvar為平均偏差的EWMA，M代替了之前的RTTs。 這組等式也可以寫成另一種形式：
Err = M - srtt
srtt ← srtt + g(Err)
rttvar ← rttvar + h(|Err| - rttvar)
RTO = srtt + 4(rttvar)
# srtt為均值的EWMA，rttcar為絕對誤差|Err|的EWMA，Err為測量值M與目前RTT估計值srtt之間的偏差。 增量g為新RTT樣本M占srtt估計值的權重，取1/8，增量h為新平均偏差樣本(新樣本M與目前平均值srtt之間的絕對誤差)占偏差估計值rttvar的權重，取1/4。這種方法是迄今為止許多TCP實作計算RTO的方法。
在測量RTT的過程中，TCP始終始終處于運轉狀态，對初始序列号來說，TCP時鐘通常為某個變量，随着系統時鐘而做出更新。TCP時鐘一個"滴答"的時間長度稱為粒度，通常該值相對較大(約500ms)，但近期實作的時鐘使用更細的粒度(如linux的1ms)。
粒度會影響RTT的測量及RTO的設定，在[RFC6298]中，粒度用于優化RTO的更新情況，并給RTO設定了一個下界：
RTO = max(srtt + max(G,4(rttvar)),1000)
# G為計時器粒度，1000ms為整個RTO的下界值([RFC6298]的規則建議值)。是以，RTO至少為1s，同時也提供可選上界值，假設為60s。 對于RTO的初始值，根據[RFC6298]描述，為1s，而初始SYN封包段采用的逾時間隔為3s，當接收到收個RTT測量結果M，TCP按如下方式進行初始化：
srtt ← M
rttvar ← M/2 在測量RTT樣本過程中，可能會出現重傳的二義性，如假設一個包的傳輸出現逾時，該資料包被重傳，接着收到一個确認資訊，那麼這個資訊是對第一次還是第二次傳輸的确認就存在二義性。當出現逾時重傳時，接收到重傳資料的确認資訊時不能更新RTT估計值，這是Karn算法的第一部分，通過排除二義性資料來解決RTT估算中出現的二義性問題。
Karn算法的第二部分則在計算RTO過程中采用一個退避系數，每當重傳計時器出現逾時，退避系數加倍，該過程一直持續至接收到非重傳資料，此時退避系數重新設定為1(二進制指數退避取消)，重傳計時器傳回正常值。
TCP時間戳選項(TSOPT)可用作RTT測量[RFC1323]。時間戳值(TSV)攜帶于初始化SYN的TSOPT中，并在SYN+ACK的TSOPT的TSER部分傳回，以此設定srtt、rttvar與RTO的初始值。初始SYN也可看作資料，應測量其RTT值。
因為TCP并非對其接收到的每個封包段都傳回ACK，如傳輸大批量資料時，TCP通常采取每兩個封包段傳回一個ACK的方法，或者當資料出現丢失、失序或重傳成功時，TCP累積确認機制表明封包段與其ACK之間并非嚴格的一一對應，為解決這些問題，使用時間戳選項的TCP采用如下算法來測量RTT樣本值：、
1. TCP發送端在其發送的每個封包段的TSOPT的TSV部分攜帶一個32比特的時間戳值。該值包含資料發送時刻的TCP時鐘值。
2. 接收端記錄接收到的TSV值(名為TsRecent的變量)并在對應的ACK中傳回，并且記錄其上一個發送的ACK号(名為LastACK的變量)。
3. 當一個新的封包段到達(接收端)時，如果其序列号與LastACK的值吻合(即為下一個期望接收的封包段)，則将其TSV值存入TsRecent。
4. 接收端發送的任何一個ACK都包含TSOPT，TsRecent變量包含的時間戳值被寫入其TSER部分。
5. 發送端接收到ACK後，将目前TCP時鐘減去TSER值，得到的差即為新的RTT樣本估計值。
若在連接配接初始化過程中，TCP的通信一方啟用時間戳，則另一端将啟用時間戳。
linux的RTT測量過程與标準方法有所差別，使用更細的時鐘粒度和更頻繁的RTT測量。linux記錄兩個新的變量，mdev和mdev_mas，mdev為采用标準方法的瞬時平均偏差估計值，即之前的rttvar；mdev_max則記錄在測量RTT樣本過程中的最大mdev，其最小值不小于50ms。rttvar需定期更新以保證其不小于mdev_max，是以，RTO不會小于200ms。
TCP時間戳選項攜帶了發送端TCP時鐘的副本。接着ACK将該值傳回至接收端，通過計算兩者之差(目前時鐘減去傳回的時間戳)來更新其srtt與rttvar估計值。如下圖：
初始化RTO估算計算過程：
srtt = 16ms
mdev = (16/2)ms = 8ms
rttvar = mdev_max = max(mdev, TCP_RTO_MIN) = max(8,50) = 50ms
RTO = srtt + 4(rttvar) = 16 + 4(50) = 216ms 第二次RTO估算計算過程：
m = 223 - 127 = 96
mdev = mdev(3/4) + |m - srtt|(1/4) = 8(3/4) + |80|(1/4) = 26ms
mdev_max = max(mdev_max,mdev) = max(50,26) = 50ms
srtt = srtt(7/8) + m(1/8) = 16(7/8) + 96(1/8) = 14+12 = 26ms
rttvar = mdev_max = 50ms
RTO = srtt + 4(rttvar) = 26 + 4(50) = 226ms 針對RTT減小的情況，若新樣本值小于RTT估計範圍的下界(srtt - mdev)，則減小新樣本的權重：
if(m < (srtt - mdev))
mdev = (31/32) * mdev + (1/32) * |srtt - m|
else
mdev = (3/4) * mdev + (1/4) * |srtt - m| 該結果可以避免RTT減小導緻的RTO增大問題。
重傳的實作
基于計時器的重傳
一旦TCP發送端得到基于時間變化的RTT測量值，就能據此設定RTO，發送封包段時應確定重傳計時器設定合理。在設定計時器前，需記錄被計時的封包段序列号，若及時收到了該封包段的ACK，則計時器被取消。之後發送端發送一個新的資料包時，需設定一個新的計時器并記錄新的序列号。是以，每一個TCP連接配接的發送端不斷地設定和取消一個重傳計時器；如果沒有資料丢失，則不會出現計時器逾時。
對TCP而言，計時器需要有效的實作被設定、重新設定、取消的功能，若TCP正常工作，則計時器不會出現逾時的情況。
若在連接配接設定的RTO内，TCP沒有收到計時封包段的ACK，将會觸發逾時重傳。TCP将逾時重傳視為相當重要的事件，當發生這種情況時，它通過降低目前資料發送率來對此進行快速響應。實作有兩種方法：基于擁塞控制機制減小發送視窗大小；每當一個重傳封包段被再次重傳時，則增大RTO的退避因子。
RTO值乘上值γ來形成新的逾時退避值：
RTO = γRTO 通常情況下γ為1，随着多次重傳，γ呈加倍增長：2，4，8...。通常γ不能超過最大退避因子(linux確定其RTO設定不超過TCP_RTO_MAX，其預設值為120s)。一旦受到相應ACK，γ會重置為1。
快速重傳
快速重傳機制[RFC5681]基于接收端的回報資訊來引發重傳，而非重傳計時器的逾時，快速重傳能更加及時有效的修複丢包情況。
快速重傳概況如下：TCP發送端在觀測到至少dupthresh(重複ACK門檻值，一定數目的重複ACK，預設通常為3)，即重傳可能丢失的資料分組，而不必等到重傳計時器逾時。
流程如圖：
帶選擇确認的重傳
随着選擇确認選項的标準化[RFC2018]，TCP接收端可提供SACK功能，通過TCP頭部的累積ACK号字段來描述其接收到的資料。采用SACK選項時，一個ACK可包含三四個告知失序資料的SACK資訊。每個SACK資訊包含32位的序列号，代表接收端存儲的失序資料的起始至最後一個序列号(加1)。
SACK選項指定n個塊的長度為8n+2位元組，是以40位元組可包含最多4個塊。通常SACK會與TSOPT一同使用，是以需要額外的10個位元組(外加2位元組的填充資料)，是以每個ACK隻能包含3個塊。
SACK接收端行為：接收端在TCP連接配接建立期間受到SACK許可選項即可生成SACK。通常來說，每當緩存中存在失序資料時，接收端就可生成SACK。第一個SACK塊内包含的是最近接收到的封包段序列号範圍，其餘的SACK塊包含的内容按照接收的先後依次排列。也就是說，最新一個塊中包含的内容除了包含最近接收的序列号資訊，還需重複之前的SACK塊。
SACK發送端行為：在發送端也應提供SACK功能，并且合理地利用接收到的SACK塊來進行丢失重傳，該過程也稱選擇性重傳或選擇性重發。SACK發送端記錄接收到的累積ACK資訊，還需記錄接收到的SACK資訊，并利用該資訊來避免重傳正确接收的資料。一種方法是當接收到相應序列号範圍的ACK時，則在其重傳緩存中标記該封包段的選擇重傳成功。
僞逾時和重傳
在一些情況下，即使沒有出現資料丢失也可能引發重傳，這種不必要的重傳稱為僞重傳，其主要造成原因是僞逾時，即過早判定逾時，其他因素如包失序、包重複，或者ACK丢失也可能導緻該現象。為處理僞逾時問題提出許多方法，這些方法通常包含檢測算法和響應算法。檢測算法用于判斷某個逾時或基于計時器的重傳是否真實，一旦認定出現僞逾時則執行響應算法，用于撤銷或減輕該逾時帶來的影響。
下面介紹一些處理方法：
重複SACK(DSACK)擴充：基本的SACK機制對接收端收到重複資料段時怎樣運作沒有規定，這些重複資料可能是僞重傳、網絡中的重複或其他原因造成的。在接收端采用DSACK(重複SACK)，并結合通常的SACK發送端，可在第一個SACK塊中告知接收端收到的重複封包段序列号。DSACK的主要目的是判斷何時的重傳是不必要的，并了解網絡中的其他事項，是以發送端至少可以推斷是否發生了包失序、ACK丢失、包重複或僞重傳。
Eifel檢測算法：實驗性的Eifel檢測算法[RFC3522]利用了TCP的TSOPT來檢測僞重傳。在發生逾時重傳後，Eifel算法等待接收下一個ACK，若為針對第一次傳輸的确認，則判定該重傳是僞重傳。利用Eifel檢測算法能比僅用采用DSACK更早檢測到僞重傳行為，因為它判斷僞重傳的ACK是在啟動丢失恢複之前生成的。
前移RTO恢複：前移RTO恢複[RFC5682]是檢測僞重傳的标準算法，但隻檢測由重傳計時器逾時引發的僞重傳。F-RTO會修改TCP的行為，在逾時重傳後收到第一個ACK時，TCP會發送新的資料，之後再響應後一個到達的ACK。如果其中有一個為重複ACK，則認為此次重傳沒問題，如果兩個都不是重複ACK，則表示該重傳是僞重傳。如果新資料的傳輸得到了相應的ACK，就使得接收端視窗前移。如果新資料的發送導緻了重複ACK，那麼接收端至少有一個或更多的空缺。
Eifel響應算法：一旦判斷出現僞重傳，則會引發一套标準操作，即Eifel響應算法[RFC4015]。由于響應算法邏輯上與Eifel檢測算法分離，是以它可與前面的任一種檢測方法結合使用。原則上逾時重傳和快速重傳都可使用Eifel響應算法，但目前隻針對逾時重傳做了相關規定。Eifel響應算法根據是否能盡早或較遲檢測出僞逾時的不同而有所差別。字首稱為僞逾時，通過檢查ACK或原始傳輸來實作；後者稱為遲僞逾時，基于有逾時而引發的重傳所傳回的ACK來判定，響應算法隻針對第一種重傳事件。
在重傳計時器逾時後，它會檢視srtt和rttvar的值，并按如下方式記錄新的變量srtt_prev和rttvar_prev：
srtt_prev = srtt + 2(G)
rttvar_prev = rttvar 在任何一次計時器逾時後，都會指定這兩個變量，但隻要在判定出現僞逾時才會使用它們，用于設定新的RTO。在上式中，G代表TCP時鐘粒度。srtt_prev設為rtt加上兩倍的時鐘粒度是由于srtt的值過小，可能會出現僞逾時。
完成srtt_prev和rttvar_prev的存儲後，就要觸發某些檢測算法。運作檢測算法後可得到一個特殊的值，稱為僞恢複。如果檢測到一次僞逾時，則将僞恢複置為SPUR_TO。如果檢測到遲僞逾時，則将其置為LATE_SPUR_TO。
若僞恢複為SPUR_TO，TCP可在恢複階段完成之前進行操作，通過将下一個要發送封包段(稱為SND.NXT)的序列号修改為最新的未發送過的封包段(稱為SND.MAX)。這樣就可在首次重傳後避免不必要的"回退N"行為。如果檢測到一次遲僞逾時，此時已生成對首次重傳的ACK，則SND.NXT不變。在以上兩種情況下，都要重新設定擁塞控制狀态(第16章介紹)。一旦接收到重傳計時器逾時後發送的封包段的ACK，就按如下方式風險srtt、rttvar、RTO：
srtt ← max(srtt_prev,m)
rttvar ← max(rttvar_prev,m/2)
RTO ← srtt + max(G,4(rttvar)) m是一個RTT樣本值，它是基于逾時後收個發送資料收到的ACK計算得到的。
包失序和包重複
包失序
在IP網絡中出現包失序的原因有：在于IP層不能保證包傳輸是有序進行的；硬體方面一些高性能裝置(路由器)采用多個并行資料鍊路；不同的處理延時；等其他情況...
如果失序發生在反向(ACK)鍊路，就會使得TCP發送端視窗快速前移，接着又可能收到一些顯然重複而應被丢棄的ACK。由于TCP的擁塞控制行為，這種情況可能導緻發送端出現不必要的流量突發行為，影響可用網絡帶寬。
如果失序發生在正向鍊路，TCP可能無法識别失序和丢包。資料的丢失和失序都會導緻接收端收到無序的包，造成資料之間的空缺。當失序比較嚴重時(資料包的位元組值差距大)，TCP會誤認為資料已經丢失，進而觸發快速重傳，導緻僞重傳。
網際網路中嚴重的失序并不常見，且通過将dupthresh設為相對較小值(如3)就能處理大部分情況，或者一些方法得以動态調整dupthresh值。
參考圖如下：
包重複
包重複的情況比較少，當IP協定也可能出現将單個包傳輸多次的情況。如當鍊路層網絡協定執行一次重傳并生成同一個包的兩個副本(這種估計屬于誤操作了...)。這時候，TCP可能出現混淆。針對包重複現象，利用SACK(特别是DSACK)就可以簡單的忽略這個問題。
相關攻擊
有一類DoS攻擊稱為低速率DoS攻擊[KK03]，在這類攻擊中，攻擊者向網關或主機發送大量資料，使得受害系統持續處于重傳逾時的狀态。由于攻擊者可預知受害TCP何時啟動重傳，并在每次重傳時生成并發送大量資料。是以，受害TCP總能感覺到擁塞的存在，根據Karn算法不斷減小發送速率并退避發送，導緻無法正常使用網絡帶寬。針對此類攻擊的預防方法是随機選擇RTO，使得攻擊者無法預知确切的重傳時間。
與DoS相關但不同的一種攻擊為減慢受害TCP的發送，使得RTT估計值過大，使得受害者在丢包後不會立即重傳。相反的攻擊也是有可能的：攻擊者在資料發送完成但還未到達接收端時僞造ACK。這樣攻擊者就能使受害TCP認為連接配接的RTT遠小于實際值，導緻過分發送而造成大量的無效傳輸。