作者：engleliu，騰訊 PCG 開發(fā)工程師
本文主要介紹 TCP 擁塞控制算法，內(nèi)容多來自網(wǎng)上各個大佬的博客及《TCP/IP 詳解》一書，在此基礎(chǔ)上進行梳理總結(jié)，與大家分享。因水平有限，內(nèi)容多有不足之處， 敬請諒解。
在了解 TCP 的擁塞控制之前，先來看看 TCP 的首部格式和一些基本概念。
TCP 頭部標準長度是 20 字節(jié)。包含源端口、目的端口、序列號、確認號、數(shù)據(jù)偏移、保留位、控制位、窗口大小、校驗和、緊急指針、選項等。
TCP 首部格式
該字段長 4 位，單位為 4 字節(jié)。表示為 TCP 首部的長度。所以 TCP 首部長度最多為 60 字節(jié)。
目前的 TCP 控制位如下，其中 CWR 和 ECE 用于擁塞控制，ACK、RST、SYN、FIN 用于連接管理及數(shù)據(jù)傳輸。
CWR：用于 IP 首部的 ECN 字段。ECE 為 1 時，則通知對方已將擁塞窗口縮小。ECE：在收到數(shù)據(jù)包的 IP 首部中 ECN 為 1 時將 TCP 首部中的 ECE 設(shè)置為 1，表示從對方到這邊的網(wǎng)絡(luò)有擁塞。URG：緊急模式ACK：確認PSH：推送，接收方應(yīng)盡快給應(yīng)用程序傳送這個數(shù)據(jù)。沒用到RST：該位為 1 表示 TCP 連接中出現(xiàn)異常必須強制斷開連接。SYN：初始化一個連接的同步序列號FIN：該位為 1 表示今后不會有數(shù)據(jù)發(fā)送，希望斷開連接。該字段長度位 16 位，即 TCP 數(shù)據(jù)包長度位 64KB?？梢酝ㄟ^ Options 字段的 WSOPT 選項擴展到 1GB。
受 Data Offset 控制，長度最大為 40 字節(jié)。一般 Option 的格式為 TLV 結(jié)構(gòu)：
常見的 TCP Options 有，SACK 字段就位于該選項中。：
TCP Options
SACK 包括了兩個 TCP 選項，一個選項用于標識是否支持 SACK，是在 TCP 連接建立時發(fā)送；另一種選項則包含了具體的 SACK 信息。
TCP SACK-Permitted Option:Kind: 4Length: Variable+----------+----------+| Kind=4 | Length=2 |+----------+----------+TCP SACK Option:Kind: 5Length: Variable +--------+--------+ | Kind=5 | Length | +--------+--------+--------+--------+ | Left Edge Of lst Block | +--------+--------+--------+--------+ | Right Edge Of lst Block | +--------+--------+--------+--------+ | . . . | +--------+--------+--------+--------+ | Left Edge Of nth Block | +--------+--------+--------+--------+ | Right Edge Of nth Block | +--------+--------+--------+--------+
SACK 的工作原理
為了解決可靠傳輸以及包亂序的問題，TCP 引入滑動窗口的概念。在傳輸過程中，client 和 server 協(xié)商接收窗口 rwnd，再結(jié)合擁塞控制窗口 cwnd 計算滑動窗口 swnd。在 Linux 內(nèi)核實現(xiàn)中，滑動窗口 cwnd 是以包為單位，所以在計算 swnd 時需要乘上 mss（最大分段大?。?。
如下圖所示滑動窗口包含 4 部分：
TCP滑動窗口
滑動后的示意圖如下（收到 36 的 ack，并發(fā)出了 46-51 的數(shù)據(jù)）：
TCP滑動后示意圖
包守恒原則
TCP 維護一個發(fā)送窗口，估計當前網(wǎng)絡(luò)鏈路上能容納的數(shù)據(jù)包數(shù)量，希望在有數(shù)據(jù)可發(fā)的情況下，回來一個確認包就發(fā)出一個數(shù)據(jù)包，總是保持發(fā)送窗口那么多包在網(wǎng)絡(luò)中流動。
傳輸?shù)睦硐肭闆r是要同時達到最大的吞吐量和最小的往返延遲，要達到這個目的，連接必須同時滿足兩個條件：
包守恒原則是擁塞控制的基礎(chǔ)。
本文重點介紹 TCP 擁塞控制相關(guān)，傳輸流程不在該范圍之內(nèi)，有興趣的同學可以查閱相關(guān)文檔。不過 TCP 重傳邏輯和擁塞控制中的快速重傳有關(guān)，所以在真正介紹擁塞控制算法之前，先來了解下 TCP 重傳邏輯。
RTT（Round Trip Time）由三部分組成：鏈路的傳播時間（propagation delay）、末端系統(tǒng)的處理時間、路由器緩存中的排隊和處理時間（queuing delay）。TCP 發(fā)送端得到了基于時間變化的 RTT 測量值，就能據(jù)此設(shè)置 RTO。
當一個重傳報文段被再次重傳時，則增大 RTO 的退避因子γ。通常情況下γ值為 1，多次重傳γ加倍增長為 2，4，8 等。通常γ不能超過最大退避因子，Linux 下 RTO 不能超過 TCP_RTO_MAX（默認為 120s）。一旦收到相應(yīng)的 ACK，γ重置為 1。
下面介紹幾種常用的 RTT 算法。
3.1.1 rtt 經(jīng)典算法 [RFC793]
1）首先，先采樣 RTT，記下最近幾次的 RTT 值。2）然后做平滑計算 SRTT（ Smoothed RTT）。公式為：（其中的 α 取值在 0.8 到 0.9 之間，這個算法英文叫 Exponential weighted moving average，中文叫：加權(quán)移動平均）
3）開始計算 RTO。公式如下：
其中：
該算法的問題在于重傳時，是用重傳的時間還是第一次發(fā)數(shù)據(jù)的時間和 ACK 回來的時間計算 RTT 樣本值，另外，delay ack 的存在也讓 rtt 不能精確測量。
該算法 [RFC6298] 特點是引入了最新的 RTT 的采樣
和平滑過的
的差值做參數(shù)來計算。公式如下： 1.計算平滑 RTT
2.計算平滑 RTT 和真實的差距（加權(quán)移動平均）
3.計算 RTO
4.考慮到時鐘粒度，給 RTO 設(shè)置一個下界。
這里G為計時器粒度，1000ms 為整個 RTO 的下屆值。因此 RTO 至少為 1s。在 Linux 下，α = 0.125，β = 0.25， μ = 1，? = 4 ——這就是算法中的“調(diào)得一手好參數(shù)”，nobody knows why, it just works…）（Linux 的源代碼在：tcp_rtt_estimator）。
5.在首個 SYN 交換前，TCP 無法設(shè)置 RTO 初始值。根據(jù) [RFC6298]，RTO 初始值為 1s，而初始 SYN 報文段采用的超時間隔為 3s。當計算出首個 RTT 測量結(jié)果 ，則按如下方法進行初始化：
3.1.3 Karn 算法
在 RTT 采樣測量過程中，如果一個數(shù)據(jù)包初傳后，RTO 超時重傳，接著收到這個數(shù)據(jù)包的 ACK 報文，那么這個 ACK 報文是對應(yīng)初傳 TCP 報文還是對應(yīng)重傳 TCP 報文呢？這個問題就是重傳二義性的問題。當沒有使用 TSOPT 選項，單純的 ACK 報文并不會指示對應(yīng)初傳包還是重傳包，因此就會發(fā)生這個問題。TCP Karn 算法是對經(jīng)典算法在重傳二義性問題上的一種改進。該算法分兩部分。1) 當出現(xiàn)超時重傳，接收到重傳數(shù)據(jù)的確認信息時不更新 RTT。即忽略了重傳部分，避免重傳二義性問題。2) 對該數(shù)據(jù)之后的包采取退避策略，僅當接收到未經(jīng)重傳的數(shù)據(jù)時，該 SRTT 才用于計算 RTO。
因為單純忽略重傳數(shù)據(jù)時，如果在某一時間，網(wǎng)絡(luò)閃動，突然變慢了，產(chǎn)生了比較大的延時，這個延時導(dǎo)致要重轉(zhuǎn)所有的包（因為之前的 RTO 很?。?，但因為重轉(zhuǎn)的不算，RTO 就不會被更新，這是個災(zāi)難。而且一發(fā)生重傳就對現(xiàn)有的 RTO 值翻倍的方式也很難估算出準確的 RTT。
3.1.4 TCP 時間戳選項（TSOPT）
根據(jù) [RFC1323]，TSOPT 主要有兩個用途，一個是 RTTM(round-trip time measurement)，即根據(jù) ACK 報文中的這個選項測量往返時延；另外一個用途是 PAWS(protect against wrapped sequence numbers)，即防止同一個連接的系列號重疊。另外還有一些其他的用途，如 SYN-cookie、Eifel Detection Algorithm 等等。TSOPT 為 Options 選項中一種，格式如下：
Kind: 8 Length: 10 bytes +-------+-------+---------------------+---------------------+ Kind=8 | 10 | TS Value (TSval) |TS Echo Reply (TSecr)| +-------+-------+---------------------+---------------------+ 1 1 4 4RTT 測量（RTTM）
當使用這個選項的時候，發(fā)送方在 TSval 處放置一個時間戳，接收方則會把這個時間通過 TSecr 返回來。因為接收端并不會處理這個 TSval 而只是直接從 TSecr 返回來，因此不需要雙方時鐘同步。這個時間戳一般是一個單調(diào)增的值，[RFC1323]建議這個時間戳每秒至少增加 1。其中在初始 SYN 包中因為發(fā)送方?jīng)]有對方時間戳的信息，因此 TSecr 會以 0 填充，TSval 則填充自己的時間戳信息。
防回繞序列號（PAWS）
TCP 判斷數(shù)據(jù)是新是舊的方法是檢查數(shù)據(jù)的序列號是否位于 sun.una 到 sun.una + 的范圍內(nèi)，而序列號空間的總大小為 ，即約 4.29G。在萬兆局域網(wǎng)中，4.29G 字節(jié)數(shù)據(jù)回繞只需幾秒鐘，這時 TCP 就無法準確判斷數(shù)據(jù)的新舊。
PAWS 假設(shè)接收到的每個 TCP 包中的 TSval 都是隨時間單調(diào)增的，基本思想就是如果接收到的一個 TCP 包中的 TSval 小于剛剛在這個連接上接收到的報文的 TSval，則可以認為這個報文是一個舊的重復(fù)包而丟掉。時間戳回繞的速度只與對端主機時鐘頻率有關(guān)。Linux 以本地時鐘計數(shù)（jiffies）作為時間戳的值，假設(shè)時鐘計數(shù)加 1 需要 1ms，則需要約 24.8 天才能回繞一半，只要報文的生存時間小于這個值的話判斷新舊數(shù)據(jù)就不會出錯。
SYN Cookie 的選項信息
TCP 開啟 SYNCookie 功能時由于 Server 在收到 SYN 請求后不保存連接，故 SYN 包中攜帶的選項（WScale、SACK）無法保存，當 SYN Cookie 驗證通過、新連接建立之后，這些選項都無法開啟。
使用時間戳選項就可以解決上述問題。將 WScale 和 SACK 選項信息編碼進 32 bit 的時間戳值中，建立連接時會收到 ACK 報文，將報文的時間戳選項的回顯信息解碼就可以還原 WScale 和 SACK 信息。
快速重傳算法概括為：TCP 發(fā)送端在觀測到至少 dupthresh（一般為 3） 個重復(fù) ACK 后，即重傳可能丟失的數(shù)據(jù)分組，而不需等待重傳計時器超時。
如下圖所示（綠色為已發(fā)送并且被 ack 的數(shù)據(jù)包，黃色表示已發(fā)送還未確認的數(shù)據(jù)包，淺綠色為被 Sack 確認的數(shù)據(jù)包，藍色表示還未發(fā)送的數(shù)據(jù)包），設(shè) dupthresh = 3，SACKed_count = 6，從 unAcked 包開始的 SACKed_count - dupthresh 個數(shù)據(jù)包，即 3 個數(shù)據(jù)包會被標記為 LOST。
擁塞窗口狀態(tài)
記分板狀態(tài)如下，紅色表示該數(shù)據(jù)包丟失：
記分板狀態(tài)
FACK 是 SACK 的一個激進版本，它擁有標準 SACK 算法的一切性質(zhì)，除此之外，它假設(shè)網(wǎng)絡(luò)不會使數(shù)據(jù)包亂序，因此收到最大的被 SACK 的數(shù)據(jù)包之前，F(xiàn)ACK 均認為是丟失的。FACK 模式下，重傳時機為 被 SACKed 的包數(shù) + 空洞數(shù) > dupthresh。
如下圖所示，設(shè) dupthresh = 3，F(xiàn)ACKed_count = 12，從 unACKed 包開始的 FACKed_count
擁塞窗口狀態(tài)
記分板狀態(tài)如下，紅色表示該數(shù)據(jù)包丟失：
記分板狀態(tài)
3.2.3 RACK 重傳
基本思路 如果數(shù)據(jù)包 p1 在 p2 之前發(fā)送，沒有收到 p1 的確認，當收到 p2 的 Sack 時，推斷 p1 丟包。算法簡介 每一個 skb 記錄發(fā)送時間 xmit_time，傳輸控制塊維護全局變量：rack.xmit_time，rack.reo_wnd。rack.xmit_time 是接收方已經(jīng)收到的最新的那個 skb 的發(fā)送時間，rack.reo_wnd 是亂序的時間窗口大小。
1.每次收到新的 ACK 后，更新 reo_wnd，其中 rtt_min 為固定時間窗口的 rtt 最小值。
2.每當收到一個 ACK 或者 SACK 的時候，更新 rack.xmit_time。再去遍歷發(fā)送隊列上已經(jīng)發(fā)送但還沒有收到確認的數(shù)據(jù)包（skb），如果滿足如下條件，那么標記這個數(shù)據(jù)包丟了。
3.如果沒有收到確認，那么就用定時器每個一段時間看看有哪些包丟了，如果滿足如下條件，那么把這個 skb 標記為已經(jīng)丟了：
注：目前 linux 內(nèi)核中只實現(xiàn)了第一種判斷方法，定時器還沒有實現(xiàn)，這樣的話就還沒有解決對于尾部包丟失的問題。3.2.4 亂序檢測
亂序檢測的目的時探測網(wǎng)絡(luò)是否發(fā)生重排導(dǎo)致的丟包，并以此來更新 dupthresh 值。只要能收到一個 ACK 或者 SACK，其序列號位于當前已經(jīng)被 ACK 或 SACK 的數(shù)據(jù)包最大的序列號之前，就說明網(wǎng)絡(luò)發(fā)生了重排造成了亂序，此時如果涉及的數(shù)據(jù)包大小大于當前能容忍的網(wǎng)絡(luò)亂序值，即 dupthresh 值，就說明網(wǎng)絡(luò)亂序加重了，此時應(yīng)該更新 dupthresh 值。之所以保持 dupthresh 的值遞增，是考慮其初始值 3 只是一個經(jīng)驗值，既然真實檢測到亂序，如果其值比 3 小，并不能說明網(wǎng)絡(luò)的亂序度估計偏大，同時 TCP 保守地遞增亂序度，也是為了讓快速重傳的進入保持保守的姿態(tài)，從而增加友好性。
一旦發(fā)現(xiàn) dupthresh 值更新的情形，F(xiàn)ACK 的假設(shè)便不成立，必須在連接內(nèi)永久禁用 FACK 算法。
要解決的問題: 當無法收到足夠的 dupack 時，TCP 標準的 Fast Retransmit 機制無法被觸發(fā)，只能等待 RTO 超時才能進行丟包的重傳。而 RTO 超時不管是時間等待代價，還是性能損耗代價都很大。
解決方法: 檢測出無法收到足夠 dupack 的場景，進而降低 dupack threshold 來觸發(fā)快速重傳。從而避免等待 RTO 超時重傳，對性能造成較大的損耗。
總結(jié)出現(xiàn) dupack 不夠的情況：a. cwnd 較小 b. 發(fā)送窗口里大量的數(shù)據(jù)包都被丟失了 c.在數(shù)據(jù)發(fā)送的尾端發(fā)生丟包時
但是，上面各種極端的 case 有共同的特點：m. 無法產(chǎn)生足夠的 dupack n.沒有新的數(shù)據(jù)包可以發(fā)送進入網(wǎng)絡(luò)，ER 機制就是在判斷條件 m 和 n 都成立后，選擇降低觸發(fā) Fast Retransmit 的閾值，來避免只能通過 RTO 超時重傳的問題。
ER 算法解決了 dupack 較少時無法觸發(fā)快速重傳的問題，但當發(fā)生尾丟包時，由于尾包后沒有更多數(shù)據(jù)包，也就無法觸發(fā) dupack。TLP 算法通過發(fā)送一個 loss probe 包，以產(chǎn)生足夠的 SACK/FACK 數(shù)據(jù)包來觸發(fā)重傳。TLP 算法會在 TCP 還是 Open 態(tài)時設(shè)置一個 Probetimeout（PTO），當鏈路中有未被確認的數(shù)據(jù)包，同時在 PTO 時間內(nèi)未收到任何 ACK，則會觸發(fā) PTO 超時處理機制。TLP 會選擇傳輸序號最大的一個數(shù)據(jù)包作為 tail loss probe 包，這個序號最大的包可能是一個可以發(fā)送的新的數(shù)據(jù)包，也可能是一個重傳包。TLP 通過這樣一個 tail loss probe 包，如果能夠收到相應(yīng)的 ACK，則會觸發(fā) FR 機制，而不是 RTO 機制。
在很多情況下，即使沒有出現(xiàn)數(shù)據(jù)丟失也可能引發(fā)重傳。這種不必要的重傳稱為偽重傳，其主要造成原因是偽超時，即過早判定超時，其他因素如包失序、包重復(fù)，或 ACK 丟失也可能導(dǎo)致該現(xiàn)象。在實際 RTT 顯著增長，超過當前 RTO 時，可能出現(xiàn)偽超時。在下層協(xié)議性能變化較大的環(huán)境中（如無線環(huán)境），這種情況出現(xiàn)得比較多。
TCP 為處理偽超時問題提出了許多方法。這些方法通常包含檢測算法與響應(yīng)算法。檢測算法用于判斷某個超時或基于計時器的重傳是否真實，一旦認定出現(xiàn)偽超時則執(zhí)行響應(yīng)算法，用于撤銷或減輕該超時帶來的影響。檢測算法包含 DSACK 、Eifel 檢測算法、遷移 RTO 恢復(fù)算法(F-RTO) 三種。
DSACK 的主要目的是判斷何時的重傳是不必要的，并了解網(wǎng)絡(luò)中的其他事項。通過 DSACK 發(fā)送端至少可以推斷是否發(fā)生了包失序、 ACK 丟失、包重復(fù)或偽重傳。D-SACK 使用了 SACK 的第一個段來做標志， a. 如果 SACK 的第一個段的范圍被 ACK 所覆蓋，那么就是 D-SACK。b.如果 SACK 的第一個段的范圍被 SACK 的第二個段覆蓋，那么就是 D-SACK。RFC2883]沒有具體規(guī)定發(fā)送端對 DSACK 怎樣處理。[RFC3708]給出了一種實驗算法，利用 DSACK 來檢測偽重傳，響應(yīng)算法可采用 Eifel 響應(yīng)算法。
實驗性的 Eifel 檢測算法利用了 TCP 的 TSOPT 來檢測偽重傳。在發(fā)生超時重傳后，Eifel 算法等待接收下一個 ACK，若為針對第一次傳輸（即原始傳輸）的確認，則判定該重傳是偽重傳。
與 DSACK 的比較：利用 Eifel 檢測算法能比僅采用 DSACK更早檢測到偽重傳行為，因為它判斷偽重傳的 ACK 是在啟動丟失恢復(fù)之前生成的。相反， DSACK 只有在重復(fù)報文段到達接收端后才能發(fā)送，并且在 DSACK 返回至發(fā)送端后才能有所響應(yīng)。及早檢測偽重傳更為有利，它能使發(fā)送端有效避免“回退 N”行為。
前移 RTO 恢復(fù)（Forward-RTO Recovery，F(xiàn)-RTO）[RFC5682]是檢測偽重傳的標準算法。它不需要任何 TCP 選項，因此只要在發(fā)送端實現(xiàn)該方法后，即使針對不支持 TSOPT 的接收端也能有效地工作。該算法只檢測由重傳計時器超時引發(fā)的偽重傳，對之前提到的其他原因引起的偽重傳則無法判斷。
F-RTO 的工作原理如下：1. F-RTO 會修改 TCP 的行為，在超時重傳后收到第一個 ACK 時，TCP 會發(fā)送新（非重傳）數(shù)據(jù)，之后再響應(yīng)后一個到達的 ACK。2.如果其中有一個為重復(fù) ACK，則認為此次重傳沒問題。3. 如果這兩個都不是重復(fù) ACK，則表示該重傳是偽重傳。4.重復(fù) ACK 是在接收端收到失序的報文段產(chǎn)生的。這種方法比較直觀。如果新數(shù)據(jù)的傳輸?shù)玫搅讼鄳?yīng)的 ACK，就使得接收端窗口前移。如果新數(shù)據(jù)的發(fā)送導(dǎo)致了重復(fù) ACK，那么接收端至少有一個或更多的空缺。這兩種情況下，接收新數(shù)據(jù)都不會影響整體數(shù)據(jù)的傳輸性能。
TCP 通過擁塞狀態(tài)機來決定收到 ACK 時 cwnd 的行為（增長或者降低）。TCP 擁塞狀態(tài)機有 Open,Disorder,Recovery,Lost和CWR五種狀態(tài)。
TCP擁塞控制狀態(tài)機
當網(wǎng)絡(luò)中沒有發(fā)生丟包，也就不需要重傳，sender 按照慢啟動或者擁塞避免算法處理到來的 ACK。
當 sender 檢測到 dupack 或者 SACK，將會轉(zhuǎn)移到 Disorder 狀態(tài)，當處在這個這個狀態(tài)中時，cwnd 將維持不變。每收到一個 dupack 或 SACK，發(fā)送方將發(fā)送一個新包。
當 sender 收到 ACK 包含顯示擁塞通知（ECN），這個 ECN 由路由器寫在 IP 頭中，告訴 TCP sender 網(wǎng)絡(luò)擁塞，sender 不會立馬降低 cwnd，而是根據(jù)快速恢復(fù)算法進行降窗，直到減為之前的一半。當 cwnd 正在減小 cwnd，網(wǎng)絡(luò)中有沒有重傳包時，這個狀態(tài)就叫 CWR，CWR 可以被 Recovery 或者 Loss 中斷。
當 sender 因為快速重傳機制觸發(fā)丟包時，sender 會重傳第一個未被 ACK 的包，并進入 Recovery 狀態(tài)。在 Recovery 狀態(tài)期間，cwnd 的處理同 CWR 大致一樣，要么重傳標記了 lost 的包，要么根據(jù)保守原則發(fā)送新包。直到網(wǎng)絡(luò)中所有的包都被 ACK，才會退出 Recovery 進入 Open 狀態(tài)，Recovery 狀態(tài)可以被 loss 狀態(tài)打斷。
時退出 Recovery 狀態(tài)。
Reno 模式退出Recovery狀態(tài)
如上圖，數(shù)據(jù)包 A、B、C 可能沒有丟失只是被延遲接收，然而沒有 SACK 機制下無法判斷是 A、B、C 的重傳觸發(fā)的 3 次重復(fù) ACK 還是新數(shù)據(jù) 1、2、3 丟失 1（或者 1、2 或者 1、2、3）導(dǎo)致的重復(fù) ACK，兩種情況均會馬上把擁塞狀態(tài)機帶入到 Recovery 狀態(tài)，然而前一種是不必要的。如果在 SND_UNA== SND_HIGH 即轉(zhuǎn)為 Open 態(tài)，那么當發(fā)生上述 1、2、3 的延遲到達后，緊接著的 Recovery 狀態(tài)會再次將擁塞窗口減半，最終降低到一個極低值。
時退出 Recovery 狀態(tài)。 因為即使發(fā)生經(jīng)典 Reno 模式下的 A、B、C 失序到達，由于存在 SACK 信息，狀態(tài)機會將此三個重復(fù) ACK 記為三個重復(fù)的 DSACK，在 SACK 模式下，判斷是否進入 Recovery 狀態(tài)的條件是被 SACK 的數(shù)據(jù)包數(shù)量大于 dupthresh，而 DSACK 不被計入到 SACKed 數(shù)量中。FACK 模式下只影響進入 Recovery 狀態(tài)的時機，其核心仍建立在 SACK 之上，所以不影響退出的時機。
SACK/FACK模式退出Recovery狀態(tài)
4.5 Loss
當 RTO 后，TCPsender 進入 Loss 狀態(tài)，所有在網(wǎng)絡(luò)中的包被標記為 lost，cwnd 重置為 1，通過 slow start 重新增加 cwnd。Loss 與 Recovery 狀態(tài)的不同點在于，cwnd 會重置為 1，但是 Recovery 狀態(tài)不會，Recovery 狀態(tài)下?lián)砣刂仆ㄟ^快速恢復(fù)算法逐步降低 cwnd 至 sshthresh。Loss 狀態(tài)不能被其它任何狀態(tài)中斷，只有當網(wǎng)絡(luò)中所有的包被成功 ACK 后，才能重新進入 Open 狀態(tài)。
擁塞的發(fā)生是因為路由器緩存溢出，擁塞會導(dǎo)致丟包，但丟包不一定觸發(fā)擁塞。擁塞控制是快速傳輸?shù)幕A(chǔ)。一個擁塞控制算法一般包括慢啟動算法、擁塞避免算法、快速重傳算法、快速恢復(fù)算法四部分。
擁塞窗口示意圖
不同擁塞算法慢啟動的邏輯有所不同，經(jīng)典的 NewReno 慢啟動的算法如下：
Linux 3.0 后采用了 Google 的論文《An Argument for Increasing TCP’s Initial Congestion Window》的建議——把 cwnd 初始化成了 10 個 MSS。而 Linux 3.0 以前，比如 2.6，Linux 采用了[RFC3390] 的建議，cwnd 跟 MSS 的值來變，如果 MSS < 1095，則 cwnd = 4；如果 MSS >2190，則 cwnd = 2；其它情況下，則是 3。
當 cwnd 增長到 sshthresh 時，就會進入“擁塞避免算法”。擁塞避免算法下 cwnd 成線性增長，即每經(jīng)過一個往返時間 RTT 就把發(fā)送方的擁塞窗口 cwnd 加 1，而不是加倍。這樣就可以避免擁塞窗口快速增長的問題。
每收到一個 ack 時 cwnd 的變化：cwnd = cwnd + 1 / cwnd快速重傳算法主要用于丟包檢測，以便能更快重傳數(shù)據(jù)包，更早的調(diào)整擁塞狀態(tài)機狀態(tài)，從而達到持續(xù)升窗的目的。具體重傳策略見第三節(jié) 重傳機制。
當檢測到丟包時，TCP 會觸發(fā)快速重傳并進入降窗狀態(tài)。該狀態(tài)下 cwnd 會通過快速恢復(fù)算法降至一個合理值。從歷史發(fā)展來看，分為四個個階段。
優(yōu)點：在快速恢復(fù)期間，可以盡可能多的發(fā)送數(shù)據(jù)缺點：由于快速恢復(fù)未完成，盡可能多發(fā)送可能會加重擁塞。#### 5.4.2 [RFC3517]版本 1) 收到 3 次重復(fù) ACK，ssthresh 設(shè)為 cwnd/2，cwnd = cwnd / 2 + 3; 2)每收到一個重復(fù) ACK，窗口值加 1/cwnd; 3) 收到非重復(fù) ACK，窗口設(shè)為 ssthresh，退出。
優(yōu)點：在快速恢復(fù)期間，可以盡少量的發(fā)送數(shù)據(jù)（有利于擁塞恢復(fù)），且在快速恢復(fù)時間段的最后階段，突發(fā)有利于搶帶寬。
缺點：快速恢復(fù)末期的突發(fā)不利于公平性。
Linux 上并沒有按照 [RFC3517] 標準實現(xiàn)，而是做了一些修改并運用到內(nèi)核中。
1.收到 3 次重復(fù) ACK，sshthresh 設(shè)置為 cwnd/2，窗口維持不變。2.每收到兩個 ACK（不管是否重復(fù)），窗口值減 1：cwnd = cwnd - 1。3.新窗口值取 cwnd = MIN(cwnd, in_flight+1)。4.直到退出快速恢復(fù)狀態(tài)，cwnd = MIN(cwnd, ssthresh)。
優(yōu)點：在快速恢復(fù)期間，取消窗口陡降過程，可以更平滑的發(fā)送數(shù)據(jù) 缺點：降窗策略沒有考慮 PIPE 的容量特征，考慮一下兩點：
a.如果快速恢復(fù)沒有完成，窗口將持續(xù)下降下去 b.如果一次性 ACK/SACK 了大量數(shù)據(jù)，in_flight 會陡然減少，窗口還是會陡降，這不符合算法預(yù)期。
PRR 算法是最新 Linux 默認推薦的快速恢復(fù)算法。prr 算法是一種按比例降窗的算法，其最終效果是：
1.在快速恢復(fù)過程中，擁塞窗口非常平滑地向 ssthresh 收斂；2.在快速恢復(fù)結(jié)束后，擁塞窗口處在 ssthresh 附近
PRR 降窗算法實時監(jiān)控以下的變量：in_flight：它是窗口的一個度量，in_flight 的值任何時候都不能大于擁塞窗口的大小。
prr_delivered：本次收到 ACK 進入降窗函數(shù)的時候，一共被 ACK 或者 SACK 的數(shù)據(jù)段數(shù)量。它度量了本次從網(wǎng)絡(luò)中清空了哪些數(shù)據(jù)段，從而影響 in_flight。
prr_out：進入快速恢復(fù)狀態(tài)后已經(jīng)被發(fā)送了多少數(shù)據(jù)包。在 transmit 例程和 retransmit 例程中遞增。
to_be_out：當前還可以再發(fā)多少數(shù)據(jù)包。
算法原理根據(jù)數(shù)據(jù)包守恒原則，能夠發(fā)送的數(shù)據(jù)包總量是本次接收到的 ACK 中確認的數(shù)據(jù)包的總量，然而處在擁塞狀態(tài)要執(zhí)行的并不是這個守恒發(fā)送的過程，而是降窗的過程，因此需要在被 ACK 的數(shù)據(jù)包數(shù)量和可以發(fā)送的數(shù)據(jù)包數(shù)量之間打一個折扣，PRR 希望達到的目標是：
以此來將目標窗口收斂于 ssthresh。剛進入快速恢復(fù)的時候的時候，窗口尚未下降，在收斂結(jié)束之前，下面的不等式是成立的：
這意味著在收斂結(jié)束前，我們可以多發(fā)送 extra 這么多的數(shù)據(jù)包。
降窗流程 根據(jù)上述原理可以得到 prr 算法降窗流程如下：
1.收到多次（默認為 3）重復(fù) ACK，根據(jù)回調(diào)函數(shù)更新 ssthresh (reno 算法為 cwnd/2)，窗口維持不變;
2.每收到 ACK（不管是否重復(fù)），按上述算法計算 Extra; 3. 新窗口值取 cwnd = in_flight + Extra; 4. 直到退出快速恢復(fù)，cwnd = ssthresh;
優(yōu)點：在快速恢復(fù)期間，取消了窗口陡降過程，可以更平滑發(fā)送數(shù)據(jù)，且降窗速率與 PIPE 容量相關(guān)。缺點：不利于在擁塞恢復(fù)到正常時突發(fā)流量的發(fā)送。
記分板算法是為了統(tǒng)計網(wǎng)絡(luò)中正在傳輸?shù)陌鼣?shù)量，即tcp_packets_in_flight。只有當 cwnd > tcp_packets_in_flight 時，TCP 才允許發(fā)送重傳包或者新數(shù)據(jù)包到網(wǎng)絡(luò)中。tcp_packets_in_flight和packets_out, sacked_out, retrans_out,lost_out有關(guān)。其中packets_out表示發(fā)出去的包數(shù)量，sacked_out為sack的包數(shù)量，retrans_out為重傳的包數(shù)量，lost_out為loss的包數(shù)量，這里的loss包含rto,FR和RACK等機制判斷出來的丟失包。
為了可以正確統(tǒng)計這些數(shù)據(jù)，內(nèi)核給每個 tcp 包(tcp_skb_cb)添加了sacked字段標記該數(shù)據(jù)包當前的狀態(tài)。
__u8 sacked; /* State flags for SACK. */#define TCPCB_SACKED_ACKED 0x01 /* SKB ACK'd by a SACK block */#define TCPCB_SACKED_RETRANS 0x02 /* SKB retransmitted */#define TCPCB_LOST 0x04 /* SKB is lost */#define TCPCB_TAGBITS 0x07 /* All tag bits */#define TCPCB_REPAIRED 0x10 /* SKB repaired (no skb_mstamp_ns) */#define TCPCB_EVER_RETRANS 0x80 /* Ever retransmitted frame */#define TCPCB_RETRANS (TCPCB_SACKED_RETRANS|TCPCB_EVER_RETRANS| \ TCPCB_REPAIRED)需要在意的有TCPCB_SACKED_ACKED（被 SACK 塊 ACK'd）,TCPCB_SACKED_RETRANS(重傳),TCPCB_LOST（丟包），其狀態(tài)轉(zhuǎn)換圖如下：
sack 處理記分板
記分板狀態(tài)轉(zhuǎn)換邏輯如下：
在 [RFC2861] 中，區(qū)分了 TCP 連接數(shù)據(jù)傳輸?shù)娜N狀態(tài)：
cwnd 代表了對網(wǎng)絡(luò)擁塞狀態(tài)的一個評估，擁塞控制要根據(jù) ACK 來更新 cwnd 的前提條件是，當前的數(shù)據(jù)發(fā)送速率真實的反映了 cwnd 的狀況，也就是說當前傳輸狀態(tài)是 network-limited。假如 tcp 隔了很長時間沒有發(fā)送數(shù)據(jù)包，即進入 idle，那么當前真實的網(wǎng)絡(luò)擁塞狀態(tài)很可能就會與 cwnd 反映的網(wǎng)絡(luò)狀況有差距。另外在 application-limited 的場景下，受限數(shù)據(jù)的 ACK 報文還可能把 cwnd 增長到一個異常大的值，顯然是不合理的?；谏厦嫣岬降膬蓚€問題，[RFC2861]引入了擁塞窗口校驗(CWV，Congestion Window Validation)算法。
算法如下：當需要發(fā)送新數(shù)據(jù)時，首先看距離上次發(fā)送操作是否超過一個 RTO，如果超過，則 1. 更新 sshthresh 值，設(shè)為 max(ssthresh, (3/4) * cwnd)。2.每經(jīng)過一個空閑 RTT 時間，cwnd 值減半，但不小于 1 SMSS。
對于應(yīng)用受限階段（非空閑階段），執(zhí)行相似的操作：1. 已使用的窗口大小記為W used 。2. 更新 ssthresh 值，設(shè)為 max(ssthresh, (3/4) * cwnd)。
上述操作均減小了 cwnd，但 ssthresh 維護了 cwnd 的先前值。避免空閑階段可能發(fā)生的大數(shù)據(jù)量注入，可以減輕對有限的路由緩存的壓力，從而減少丟包情況的產(chǎn)生。注意 CWV 減小了 cwnd 值，但沒有減小 ssthresh，因此采用這種算法的通常結(jié)果是，在長時間發(fā)送暫停后，發(fā)送方會進入慢啟動階段。Linux TCP 實現(xiàn)了 CWV 算法并默認啟用。
New Reno 算法包含第五節(jié)中介紹的慢啟動算法、擁塞避免算法、快速重傳算法和 prr 算法。在此就不贅述。
Reno cwnd 圖
CUBIC 算法和 Reno 算法區(qū)別主要在于慢啟動和擁塞避免兩個階段。因為 Reno 算法進入擁塞避免后每經(jīng)過一個 RTT 窗口才加 1，擁塞窗口增長太慢，導(dǎo)致在高速網(wǎng)絡(luò)下不能充分利用網(wǎng)絡(luò)帶寬。所以為了解決這個問題，BIC 和 CUBIC 算法逐步被提了出來。
(BIC 算法基于二分查找，實現(xiàn)復(fù)雜，不看了。)
cubic 算法源碼見 tcp_cubic 文件。
cubic 窗口增長函數(shù)
CUBIC 的窗口增長函數(shù)是一個三次函數(shù)，非常類似于 BIC-TCP 的窗口增長函數(shù)。CUBIC 的詳細運行過程如下，當出現(xiàn)丟包事件時，CUBIC 同 BIC-TCP 一樣，會記錄這時的擁塞窗口大小作為 W max，接著通過因子 執(zhí)行擁塞窗口的乘法減小，這里β是一個窗口降低常數(shù)，并進行正常的 TCP 快速恢復(fù)和重傳。從快速恢復(fù)階段進入擁塞避免后，使用三次函數(shù)的凹輪廓增加窗口。三次函數(shù)被設(shè)置在 W max 處達到穩(wěn)定點，然后使用三次函數(shù)的凸輪廓開始探索新的最大窗口。
CUBIC 的窗口增長函數(shù)公式如下所示：
其中，*W(t)*代表在時刻 t 的窗口大小，C 是一個 CUBIC 的常量參數(shù)，t 是從上次丟包后到現(xiàn)在的時間，以秒為單位。K 是上述函數(shù)在沒有進一步丟包的情況下將 W 增加到 W max
經(jīng)歷的時間，其計算公式如下：
其中β 也是常量（默認為 0.2）。
static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked){ // ... if (ca->epoch_start == 0) { //丟包后，開啟一個新的時段 ca->epoch_start = tcp_jiffies32; /* record beginning */ ca->ack_cnt = acked; /* start counting */ ca->tcp_cwnd = cwnd; /* syn with cubic */ //取max(last_max_cwnd , cwnd)作為當前Wmax飽和點 if (ca->last_max_cwnd <= cwnd) { ca->bic_K = 0; ca->bic_origin_point = cwnd; } else { /* Compute new K based on * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ) */ ca->bic_K = cubic_root(cube_factor * (ca->last_max_cwnd - cwnd)); ca->bic_origin_point = ca->last_max_cwnd; } } //...}標準的慢啟動在 BDP 網(wǎng)絡(luò)環(huán)境下表現(xiàn)不好，不好的原因主要有兩個：
總結(jié)這些原因都是因為慢啟動過程過于盲目，不能及時的預(yù)測擁塞，導(dǎo)致了大量丟包，所以混合慢啟動機制的主要作用是在慢啟動階段試圖找到“合理”的退出慢啟動進入擁塞避免狀態(tài)點（safe exit point）。
Hystart 算法通過 ACK train 信息判斷一個 Safe Exit Point for Slow Start.同時為了避免計算帶寬，通過一個巧妙的轉(zhuǎn)換(具體建議看論文)，只要判斷時間差是否超過 Forward one-way delay()來決定是否退出慢啟動。
Hystart 算法通過以下兩個條件來判斷是否應(yīng)該退出慢啟動 1.一個窗口內(nèi)的數(shù)據(jù)包的總傳輸間隔是否超過 2. 數(shù)據(jù)包的 RTT sample(默認 8 個樣本)是否出現(xiàn)較大幅度的增長。如果前面 8 個樣本中的最小 rtt 大于全局最小 rtt 與閾值的和，那么表示網(wǎng)絡(luò)出現(xiàn)了擁塞，應(yīng)立馬進入擁塞避免階段
6.3 BBR 算法
BBR 全稱 bottleneck bandwidth and round-trip propagation time?；诎鼇G失檢測的 Reno、NewReno 或者 cubic 為代表，其主要問題有 Buffer bloat 和長肥管道兩種。和這些算法不同，bbr 算法會時間窗口內(nèi)的最大帶寬 max_bw 和最小 RTT min_rtt，并以此計算發(fā)送速率和擁塞窗口。
如下圖所示，當沒有足夠的數(shù)據(jù)來填滿管道時，RTprop 決定了流的行為；當有足夠的數(shù)據(jù)填滿時，那就變成了 BtlBw 來決定。這兩條約束交匯在點 inflight =BtlBw*RTprop，也就是管道的 BDP（帶寬與時延的乘積）。當管道被填滿時，那些超過的部分（inflight-BDP）就會在瓶頸鏈路中制造了一個隊列，從而導(dǎo)致了 RTT 的增大。當數(shù)據(jù)繼續(xù)增加直到填滿了緩存時，多余的報文就會被丟棄了。擁塞就是發(fā)生在 BDP 點的右邊，而擁塞控制算法就是來控制流的平均工作點離 BDP 點有多遠。
發(fā)送速率和RTT vs inflight
RTProp : round-trip propagation time BtlBW : bottleneck bandwidth
基于丟包的擁塞控制算法工作在 bandwidth-limited 區(qū)域的右邊界區(qū)域，盡管這種算法可以達到最大的傳輸速率，但是它是以高延遲和高丟包率作為代價的。在存儲介質(zhì)較為小的時候，緩存大小只比 BDP 大一點，此時這種算法的時延并不會很高。然而，當存儲介質(zhì)變得便宜之后，交換機的緩存大小已經(jīng)是 ISP 鏈路 BDP 的很多很多倍了，這導(dǎo)致了 bufferbloat，從而導(dǎo)致了 RTT 從毫秒級升到了秒級。
當一個連接滿足以下兩個條件時，它可以在達到最高的吞吐量的同時保持最低時延：
1)速率平衡：瓶頸帶寬的數(shù)據(jù)到達速率與 BtlBw 相等；
2)填滿管道：所有的在外數(shù)據(jù)（inflight data）與 BDP（帶寬與時延的乘積）相等
bbr 算法關(guān)于擁塞窗口的核心就是計算 BtlBW 和 RTprop，根據(jù)這兩者值計算 BDP。BtlBw 和 RTprop 可能是動態(tài)變化的，所以需要實時地對它們進行估計。
計算 RTprop
目前 TCP 為了檢測丟包，必須實時地跟蹤 RTT 的大小。在任意的時間 t，
表示“噪音”。造成噪聲的因素主要有：鏈路隊列，接收方的時延 ACK 配置，ACK 聚合等因素等待。RTprop 是路徑的物理特性，并且只有路徑變化才會改變。由于一般來說路徑變化的時間尺度遠遠大于 RTprop，所以 RTprop 可以由以下公式進行估計：
即，在一個時間窗口中對 RTT 取最小值。一般將該窗口大小設(shè)置為幾十秒至幾分鐘。
計算 BtlBW
bottleneck bandwidth 的估計不像 RTT 那樣方便，沒有一種 TCPspec 要求實現(xiàn)算法來跟蹤估計 bottleneck 帶寬，但是，可以通過跟蹤發(fā)送速率來估計 bottleneck 帶寬。當發(fā)送方收到一個 ACK 報文時，它可以計算出該報文的 RTT，并且從發(fā)出報文到收到 ack 報文這段時間的 data Inflight。這段時間內(nèi)的平均發(fā)送速率就可以以此計算出來：
這個計算出的速率必定小于 bottleneck 速率（因為 delta delivered 是確定的，但是 deltat 會較大）。因此，BtlBw 可以根據(jù)以下公式進行估計。
其中，時間窗口大小的值一般為 6~10 個 RTT。
TCP 必須記錄每個報文的離開時間從而計算 RTT。BBR 必須額外記錄已經(jīng)發(fā)送的數(shù)據(jù)大小，使得在收到每一個 ACK 之后，計算 RTT 及發(fā)送速率的值，最后得到 RTprop 和 BtlBw 的估計值。
bbr 算法輸出 pacing_rate 和 cwnd 兩個數(shù)據(jù)。pacing_rate 決定發(fā)包速率，cwnd 為窗口大小。每一次 ACK 都會根據(jù)當前的模式計算 pacing_rate 和 cwnd。注意在計算 pacing_rate 和 cwnd 時有 pacing_gain 和 cwnd_gain 兩個參數(shù)，
bottleneck_bandwidth = windowed_max(delivered / elapsed, 10 round trips)min_rtt = windowed_min(rtt, 10 seconds)pacing_rate = pacing_gain * bottleneck_bandwidthcwnd = max(cwnd_gain * bottleneck_bandwidth * min_rtt, 4)BBR 和 Pacing rate
BBR 算法也是基于狀態(tài)機。狀態(tài)機有STARTUP、DRAIN、PROBE_BW、PROBE_RTT四種狀態(tài)。不同狀態(tài)下pacing_gain 和 cwnd_gain 的取值會有所不同。
bbr 狀態(tài)機
STARTUP：初始狀態(tài)，該狀態(tài)下類似于傳統(tǒng)擁塞控制的慢啟動階段。該狀態(tài)下pacing_gain和cwnd_gain為2/ln(2)+1。因為這是最小的能夠達到 Reno 或者 CUBIC 算法啟動速度的值。
/* We use a high_gain value of 2/ln(2) because it's the smallest pacing gain * that will allow a smoothly increasing pacing rate that will double each RTT * and send the same number of packets per RTT that an un-paced, slow-starting * Reno or CUBIC flow would: */static const int bbr_high_gain = BBR_UNIT * 2885 / 1000 + 1;DRAIN：該狀態(tài)為排除狀態(tài)。在STARTUP狀態(tài)下三輪沒有漲幅超過 25%時會進入該狀態(tài)。該狀態(tài)下BtlBw會根據(jù)bbr_drain_gain逐漸降低，直到 inflight 降到 BDP 為止。
/* The pacing gain of 1/high_gain in BBR_DRAIN is calculated to typically drain * the queue created in BBR_STARTUP in a single round: */static const int bbr_drain_gain = BBR_UNIT * 1000 / 2885;PROBE_BW：該狀態(tài)下會照常計算當前的 bw，即瞬時帶寬。然而在計算 pacing rate 以及 cwnd 時，并不會像在 STARTUP 狀態(tài)時那樣用一個很大的增益系數(shù)去擴張 pacing rate 和 cwnd，而是順序的在[5/4，3/4，1，1，1，1，1，1]中選一個，感官上 bw 就在其停止增長的地方上下徘徊了。
/* The gain for deriving steady-state cwnd tolerates delayed/stretched ACKs: */static const int bbr_cwnd_gain = BBR_UNIT * 2;/* The pacing_gain values for the PROBE_BW gain cycle, to discover/share bw: */static const int bbr_pacing_gain[] = { BBR_UNIT * 5 / 4, /* probe for more available bw */ BBR_UNIT * 3 / 4, /* drain queue and/or yield bw to other flows */ BBR_UNIT, BBR_UNIT, BBR_UNIT, /* cruise at 1.0*bw to utilize pipe, */ BBR_UNIT, BBR_UNIT, BBR_UNIT /* without creating excess queue... */};PROBE_RTT：當 PROBE_BW 檢測到連續(xù) 10s 沒有更新 min rtt 時就會進入該狀態(tài)。該狀態(tài)的目標是保持 BBR 的公平性并定期排空瓶頸隊列，以收斂到真實的 min_rtt。進入該模式時，BBR 會將 cwnd 的上限設(shè)置為 4 個數(shù)據(jù)包。在 flight pkg <= 4 后開始進行 rtt 探測，探測時間為 200ms，探測結(jié)束后 BBR 便會記錄 min rtt，并離開 PROBE_RTT 進入相應(yīng)的模式。代碼見bbr_update_min_rtt函數(shù)。
Q：為什么 PROBE_BW 階段 bbr_cwnd_gain 為 2？ 保證極端情況下，按照 pacing_rate 發(fā)送的數(shù)據(jù)包全部丟包時也有數(shù)據(jù)繼續(xù)發(fā)送，不會產(chǎn)生空窗期。
Q：為什么在探測最小 RTT 的時候最少要保持 4 個數(shù)據(jù)包4 個包的窗口是合理的，infilght 分別是：剛發(fā)出的包，已經(jīng)到達接收端等待延遲應(yīng)答的包，馬上到達的應(yīng)答了 2 個包的 ACK。一共 4 個，只有 1 個在鏈路上，另外 1 個在對端主機里，另外 2 個在 ACK 里。路上只有 1 個包。
BBR 將它的大部分時間的在外發(fā)送數(shù)據(jù)都保持為一個 BDP 大小，并且發(fā)送速率保持在估計得 BtlBw 值，這將會最小化時延。但是這會把網(wǎng)絡(luò)中的瓶頸鏈路移動到 BBR 發(fā)送方本身，所以 BBR 無法察覺 BtlBw 是否上升了。所以，BBR 周期性的在一個 RTprop 時間內(nèi)將 pacing_gain 設(shè)為一個大于 1 的值，這將會增加發(fā)送速率和在外報文。如果 BtlBw 沒有改變，那么這意味著 BBR 在網(wǎng)絡(luò)中制造了隊列，增大了 RTT，而 deliveryRate 仍然沒有改變。（這個隊列將會在下個 RTprop 周期被 BBR 使用小于 1 的 pacing_gain 來消除）。如果 BtlBw 增大了，那么 deliveryRate 增大了，并且 BBR 會立即更新 BtlBw 的估計值，從而增大了發(fā)送速率。通過這種機制，BBR 可以以指數(shù)速度非?？斓厥諗康狡款i鏈路。
如下圖所示，在 1 條 10Mbps，40ms 的流在 20s 穩(wěn)定運行之后將 BtlBw 提高了 1 倍（20Mbps），然后在第 40s 又將 BtlBw 恢復(fù)至 20Mbps。
bbr 帶寬變化
下圖展示了 1 個 10Mbps，40ms 的 BBR 流在一開始的 1 秒內(nèi)，發(fā)送方（綠線）和接收方（藍線）的過程。紅線表示的是同樣條件下的 CUBIC 發(fā)送。垂直的灰線表示了 BBR 狀態(tài)的轉(zhuǎn)換。下方圖片展示了兩種連接的 RTT 在這段時間的變化。注意，只有收到了 ACK（藍線）之后才能確定出 RTT，所以在時間上有點偏移。圖中標注了 BBR 何時學習到 RTT 和如何反應(yīng)。
10Mbps、40ms鏈路上BBR流的第一秒
下圖展示了在上圖中展示的 BBR 和 CUBIC 流在開始 8 秒的行為。CUBIC（紅線）填滿了緩存之后，周期性地在 70%~100%的帶寬范圍內(nèi)波動。然而 BBR（綠線）在啟動過程結(jié)束后，就非常穩(wěn)定地運行，并且不會產(chǎn)生任何隊列。
在10Mbps、40ms鏈路上的BBR流和CUBIC流的前8秒對比
下圖展示了在一條 100Mbps，100ms 的鏈路上，BBR 和 CUBIC 在 60 秒內(nèi)的吞吐量與隨機丟包率（從 0.001%~50%）的關(guān)系。在丟包率只有 0.1%的時候，CUBIC 的吞吐量就已經(jīng)下降了 10 倍，并且在丟包率為 1%的時候就幾乎炸了。而理論上的最大吞吐量是鏈路速率乘以（1-丟包率）。BBR 在丟包率為 5%以下時還能基本維持在最大吞吐量附近，在 15%丟包率的時候雖然有所下降但還是不錯。
BBC和CUBIC的吞吐量與丟包率的關(guān)系
TCP Westwood 算法簡稱 TCPW，和 bbr 算法類似是基于帶寬估計的一種擁塞控制算法。TCPW 采用和 Reno 相同的慢啟動算法、擁塞避免算法。區(qū)別在于當檢測到丟包時，根據(jù)帶寬值來設(shè)置擁塞窗口、慢啟動閾值。
和 bbr 算法不同，tcpw 帶寬計算相當粗糙。tcpw 每經(jīng)過一個 RTT 測量一次帶寬。假設(shè)經(jīng)過時間為 delta，該時間內(nèi)發(fā)送完成的數(shù)據(jù)量為 bk，則采樣值為 bk / delta。然后和 rtt 一樣，帶寬采樣值會經(jīng)過一個平滑處理算出最終的帶寬值。
6.4.2 如何確認單位時間的發(fā)送量 bk
tcpw 采用一種粗糙的估算方式。在收到回包后，會根據(jù)當前的 snd_una 和之前的 snd_una 之間的差值來估算被 ACK 的字節(jié)數(shù)，即關(guān)于 SACK 的信息會被丟失。具體邏輯見westwood_acked_count函數(shù)。
static inline u32 westwood_acked_count(struct sock *sk){ const struct tcp_sock *tp = tcp_sk(sk); struct westwood *w = inet_csk_ca(sk); w->cumul_ack = tp->snd_una - w->snd_una; /* If cumul_ack is 0 this is a dupack since it's not moving * tp->snd_una. */ if (!w->cumul_ack) { w->accounted += tp->mss_cache; w->cumul_ack = tp->mss_cache; } if (w->cumul_ack > tp->mss_cache) { /* Partial or delayed ack */ if (w->accounted >= w->cumul_ack) { w->accounted -= w->cumul_ack; w->cumul_ack = tp->mss_cache; } else { w->cumul_ack -= w->accounted; w->accounted = 0; } } w->snd_una = tp->snd_una; return w->cumul_ack;}計算 ssthresh 公式很簡單：
源碼如下：
/* * TCP Westwood * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it * in packets we use mss_cache). Rttmin is guaranteed to be >= 2 * so avoids ever returning 0. */static u32 tcp_westwood_bw_rttmin(const struct sock *sk){ const struct tcp_sock *tp = tcp_sk(sk); const struct westwood *w = inet_csk_ca(sk); return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2);}聯(lián)系客服
