TCP 擁塞控制詳解

摘要：如上圖，數據包 A、B、C 可能沒有丟失只是被延遲接收，然而沒有 SACK 機制下無法判斷是 A、B、C 的重傳觸發的 3 次重複 ACK 還是新數據 1、2、3 丟失 1（或者 1、2 或者 1、2、3）導致的重複 ACK，兩種情況均會馬上把擁塞狀態機帶入到 Recovery 狀態，然而前一種是不必要的。當網絡中沒有發生丟包，也就不需要重傳，sender 按照慢啓動或者擁塞避免算法處理到來的 ACK。

作者：engleliu，騰訊 PCG 開發工程師

本文主要介紹 TCP 擁塞控制算法，內容多來自網上各個大佬的博客及《TCP/IP 詳解》一書，在此基礎上進行梳理總結，與大家分享。因水平有限，內容多有不足之處，敬請諒解。

一、TCP 首部格式

在瞭解 TCP 的擁塞控制之前，先來看看 TCP 的首部格式和一些基本概念。

TCP 頭部標準長度是 20 字節。包含源端口、目的端口、序列號、確認號、數據偏移、保留位、控制位、窗口大小、校驗和、緊急指針、選項等。

1.1 數據偏移（Data Offset）

該字段長 4 位，單位爲 4 字節。表示爲 TCP 首部的長度。所以 TCP 首部長度最多爲 60 字節。

1.2 控制位

目前的 TCP 控制位如下，其中 CWR 和 ECE 用於擁塞控制，ACK、RST、SYN、FIN 用於連接管理及數據傳輸。

CWR：用於 IP 首部的 ECN 字段。ECE 爲 1 時，則通知對方已將擁塞窗口縮小。
ECE：在收到數據包的 IP 首部中 ECN 爲 1 時將 TCP 首部中的 ECE 設置爲 1，表示從對方到這邊的網絡有擁塞。
URG：緊急模式
ACK：確認
PSH：推送，接收方應儘快給應用程序傳送這個數據。沒用到
RST：該位爲 1 表示 TCP 連接中出現異常必須強制斷開連接。
SYN：初始化一個連接的同步序列號
FIN：該位爲 1 表示今後不會有數據發送，希望斷開連接。

1.3 窗口大小（Window）

該字段長度位 16 位，即 TCP 數據包長度位 64KB。可以通過 Options 字段的 WSOPT 選項擴展到 1GB。

1.4 選項（Options）

受 Data Offset 控制，長度最大爲 40 字節。一般 Option 的格式爲 TLV 結構：

常見的 TCP Options 有，SACK 字段就位於該選項中。：

1.5 SACK 選項

SACK 包括了兩個 TCP 選項，一個選項用於標識是否支持 SACK，是在 TCP 連接建立時發送；另一種選項則包含了具體的 SACK 信息。

SACK_Permitted 選項，該選項只允許在 TCP 連接建立時，有 SYN 標誌的包中設置，也即 TCP 握手的前兩個包中，分別表示通信的兩方各自是否支持 SACK。

TCP SACK-Permitted Option:
Kind: 4
Length: Variable
+----------+----------+
| Kind=4   | Length=2 |
+----------+----------+

SACK(選擇性確認) 選項位於 Options 中。該選項參數告訴對方已經接收到並緩存的不連續的數據塊，發送方可根據此信息檢查究竟是哪些塊丟失，從而發送相應的數據塊。受 TCP 包長度限制，TCP 包頭最多包含四組 SACK 字段。

TCP SACK Option:
Kind: 5
Length: 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 的工作原理

如下圖所示，接收方收到 500-699 的數據包，但沒有收到 300-499 的數據包就會回 SACK(500-700) 給發送端，表示收到 500-699 的數據。

二、滑動窗口和包守恆原則

2.1 滑動窗口

爲了解決可靠傳輸以及包亂序的問題，TCP 引入滑動窗口的概念。在傳輸過程中，client 和 server 協商接收窗口 rwnd，再結合擁塞控制窗口 cwnd 計算滑動窗口 swnd。在 Linux 內核實現中，滑動窗口 cwnd 是以包爲單位，所以在計算 swnd 時需要乘上 mss（最大分段大小）。

如下圖所示滑動窗口包含 4 部分：

已收到 ack 確認的數據；
已發還沒收到 ack 的；
在窗口中還沒有發出的（接收方還有空間）；
窗口以外的數據（接收方沒空間）。

滑動後的示意圖如下（收到 36 的 ack，併發出了 46-51 的數據）：

2.2 包守恆原則

TCP 維護一個發送窗口，估計當前網絡鏈路上能容納的數據包數量，希望在有數據可發的情況下，回來一個確認包就發出一個數據包，總是保持發送窗口那麼多包在網絡中流動。

傳輸的理想情況是要同時達到最大的吞吐量和最小的往返延遲，要達到這個目的，連接必須同時滿足兩個條件：

以鏈路瓶頸帶寬 BtlBw 發包（帶寬利用率最高）
保證鏈路中沒有緩存隊列（延遲最低）

包守恆原則是擁塞控制的基礎。

三、TCP 重傳機制

本文重點介紹 TCP 擁塞控制相關，傳輸流程不在該範圍之內，有興趣的同學可以查閱相關文檔。不過 TCP 重傳邏輯和擁塞控制中的 快速重傳 有關，所以在真正介紹擁塞控制算法之前，先來了解下 TCP 重傳邏輯。

3.1 超時重傳 [RFC2988]

RTT（Round Trip Time）由三部分組成：鏈路的傳播時間（propagation delay）、末端系統的處理時間、路由器緩存中的排隊和處理時間（queuing delay）。TCP 發送端得到了基於時間變化的 RTT 測量值，就能據此設置 RTO。

當一個重傳報文段被再次重傳時，則增大 RTO 的退避因子。通常情況下值爲 1，多次重傳加倍增長爲 2，4，8 等。通常不能超過最大退避因子，Linux 下 RTO 不能超過 TCP_RTO_MAX（默認爲 120s）。一旦收到相應的 ACK，重置爲 1。

下面介紹幾種常用的 RTT 算法。

3.1.1 rtt 經典算法 [RFC793]

1）首先，先採樣 RTT，記下最近幾次的 RTT 值。2）然後做平滑計算 SRTT（ Smoothed RTT）。公式爲：（其中的 α 取值在 0.8 到 0.9 之間，這個算法英文叫 Exponential weighted moving average，中文叫：加權移動平均）

3）開始計算 RTO。公式如下：

其中：

UBOUND 是最大的 timeout 時間，上限值；
LBOUND 是最小的 timeout 時間，下限值；
β 值一般在 1.3 到 2.0 之間。

該算法的問題在於重傳時，是用重傳的時間還是第一次發數據的時間和 ACK 回來的時間計算 RTT 樣本值，另外，delay ack 的存在也讓 rtt 不能精確測量。

3.1.2 rtt 標準算法（Jacobson / Karels 算法）

該算法 [RFC6298] 特點是引入了最新的 RTT 的採樣

和平滑過的的差值做參數來計算。公式如下：

1.計算平滑 RTT

2.計算平滑 RTT 和真實的差距（加權移動平均）

3.計算 RTO

4.考慮到時鐘粒度，給 RTO 設置一個下界。

這裏

爲計時器粒度，1000ms 爲整個 RTO 的下屆值。因此 RTO 至少爲 1s。在 Linux 下，α = 0.125，β = 0.25， μ = 1，∂ = 4 ——這就是算法中的“調得一手好參數”，nobody knows why, it just works…）（Linux 的源代碼在：

tcp_rtt_estimator）。

5.在首個 SYN 交換前，TCP 無法設置 RTO 初始值。根據 [RFC6298]，RTO 初始值爲 1s，而初始 SYN 報文段採用的超時間隔爲 3s。當計算出首個 RTT 測量結果，則按如下方法進行初始化：

3.1.3 Karn 算法

在 RTT 採樣測量過程中，如果一個數據包初傳後，RTO 超時重傳，接着收到這個數據包的 ACK 報文，那麼這個 ACK 報文是對應初傳 TCP 報文還是對應重傳 TCP 報文呢？這個問題就是重傳二義性的問題。當沒有使用 TSOPT 選項，單純的 ACK 報文並不會指示對應初傳包還是重傳包，因此就會發生這個問題。TCP Karn 算法是對經典算法在重傳二義性問題上的一種改進。該算法分兩部分。1) 當出現超時重傳，接收到重傳數據的確認信息時不更新 RTT。即忽略了重傳部分，避免重傳二義性問題。2) 對該數據之後的包採取退避策略，僅當接收到未經重傳的數據時，該 SRTT 才用於計算 RTO。

因爲單純忽略重傳數據時，如果在某一時間，網絡閃動，突然變慢了，產生了比較大的延時，這個延時導致要重轉所有的包（因爲之前的 RTO 很小），但因爲重轉的不算，RTO 就不會被更新，這是個災難。而且一發生重傳就對現有的 RTO 值翻倍的方式也很難估算出準確的 RTT。

3.1.4 TCP 時間戳選項（TSOPT）

根據 [RFC1323]，TSOPT 主要有兩個用途，一個是 RTTM(round-trip time measurement)，即根據 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                     4

RTT 測量（RTTM）

當使用這個選項的時候，發送方在 TSval 處放置一個時間戳，接收方則會把這個時間通過 TSecr 返回來。因爲接收端並不會處理這個 TSval 而只是直接從 TSecr 返回來，因此不需要雙方時鐘同步。這個時間戳一般是一個單調增的值，[RFC1323]建議這個時間戳每秒至少增加 1。其中在初始 SYN 包中因爲發送方沒有對方時間戳的信息，因此 TSecr 會以 0 填充，TSval 則填充自己的時間戳信息。

防迴繞序列號（PAWS）

TCP 判斷數據是新是舊的方法是檢查數據的序列號是否位於 sun.una 到 sun.una +的範圍內，而序列號空間的總大小爲，即約 4.29G。在萬兆局域網中，4.29G 字節數據迴繞只需幾秒鐘，這時 TCP 就無法準確判斷數據的新舊。

PAWS 假設接收到的每個 TCP 包中的 TSval 都是隨時間單調增的，基本思想就是如果接收到的一個 TCP 包中的 TSval 小於剛剛在這個連接上接收到的報文的 TSval，則可以認爲這個報文是一箇舊的重複包而丟掉。時間戳迴繞的速度只與對端主機時鐘頻率有關。Linux 以本地時鐘計數（jiffies）作爲時間戳的值，假設時鐘計數加 1 需要 1ms，則需要約 24.8 天才能迴繞一半，只要報文的生存時間小於這個值的話判斷新舊數據就不會出錯。

SYN Cookie 的選項信息

TCP 開啓 SYNCookie 功能時由於 Server 在收到 SYN 請求後不保存連接，故 SYN 包中攜帶的選項（WScale、SACK）無法保存，當 SYN Cookie 驗證通過、新連接建立之後，這些選項都無法開啓。

使用時間戳選項就可以解決上述問題。將 WScale 和 SACK 選項信息編碼進 32 bit 的時間戳值中，建立連接時會收到 ACK 報文，將報文的時間戳選項的回顯信息解碼就可以還原 WScale 和 SACK 信息。

3.2 Fast Retransmit（快速重傳）

快速重傳算法概括爲：TCP 發送端在觀測到至少 dupthresh（一般爲 3）個重複 ACK 後，即重傳可能丟失的數據分組，而不需等待重傳計時器超時。

3.2.1 SACK 重傳

未啓用 SACK 時，TCP 重複 ACK 定義爲收到連續相同的 ACK seq。[RFC5681]
啓用 SACK 時，攜帶 SACK 的 ACK 也被認爲重複 ACK。[RFC6675]

如下圖所示（綠色爲已發送並且被 ack 的數據包，黃色表示已發送還未確認的數據包，淺綠色爲被 Sack 確認的數據包，藍色表示還未發送的數據包），設 dupthresh = 3，SACKed_count = 6，從 unAcked 包開始的 SACKed_count - dupthresh 個數據包，即 3 個數據包會被標記爲 LOST。

記分板狀態如下，紅色表示該數據包丟失：

記分板狀態

3.2.2 FACK 重傳

FACK 是 SACK 的一個激進版本，它擁有標準 SACK 算法的一切性質，除此之外，它 假設網絡不會使數據包亂序 ，因此收到最大的被 SACK 的數據包之前，FACK 均認爲是丟失的。FACK 模式下，重傳時機爲 被 SACKed 的包數 + 空洞數 > dupthresh 。

如下圖所示，設 dupthresh = 3，FACKed_count = 12，從 unACKed 包開始的 FACKed_count

dupthresh 個數據包，即 9 個包會被標記爲 LOST。

記分板狀態如下，紅色表示該數據包丟失：

3.2.3 RACK 重傳

基本思路如果數據包 p1 在 p2 之前發送，沒有收到 p1 的確認，當收到 p2 的 Sack 時，推斷 p1 丟包。 算法簡介 每一個 skb 記錄發送時間 xmit_time，傳輸控制塊維護全局變量：rack.xmit_time，rack.reo_wnd。rack.xmit_time 是接收方已經收到的最新的那個 skb 的發送時間，rack.reo_wnd 是亂序的時間窗口大小。

1.每次收到新的 ACK 後，更新 reo_wnd，其中 rtt_min 爲固定時間窗口的 rtt 最小值。

2.每當收到一個 ACK 或者 SACK 的時候，更新 rack.xmit_time。再去遍歷發送隊列上已經發送但還沒有收到確認的數據包（skb），如果滿足如下條件，那麼標記這個數據包丟了。

3.如果沒有收到確認，那麼就用定時器每個一段時間看看有哪些包丟了，如果滿足如下條件，那麼把這個 skb 標記爲已經丟了：

注：目前 linux 內核中只實現了第一種判斷方法，定時器還沒有實現，這樣的話就還沒有解決對於尾部包丟失的問題。

3.2.4 亂序檢測

亂序檢測的目的時探測網絡是否發生重排導致的丟包，並以此來更新 dupthresh 值。只要能收到一個 ACK 或者 SACK，其序列號位於當前已經被 ACK 或 SACK 的數據包最大的序列號之前，就說明網絡發生了重排造成了亂序，此時如果涉及的數據包大小大於當前能容忍的網絡亂序值，即 dupthresh 值，就說明網絡亂序加重了，此時應該更新 dupthresh 值。之所以保持 dupthresh 的值遞增，是考慮其初始值 3 只是一個經驗值，既然真實檢測到亂序，如果其值比 3 小，並不能說明網絡的亂序度估計偏大，同時 TCP 保守地遞增亂序度，也是爲了讓快速重傳的進入保持保守的姿態，從而增加友好性。

一旦發現 dupthresh 值更新的情形，FACK 的假設便不成立，必須在連接內永久禁用 FACK 算法。

3.3 Early Retransmit for TCP（ER 機制）

要解決的問題:當無法收到足夠的 dupack 時，TCP 標準的 Fast Retransmit 機制無法被觸發，只能等待 RTO 超時才能進行丟包的重傳。而 RTO 超時不管是時間等待代價，還是性能損耗代價都很大。

解決方法:檢測出無法收到足夠 dupack 的場景，進而降低 dupack threshold 來觸發快速重傳。從而避免等待 RTO 超時重傳，對性能造成較大的損耗。

總結出現 dupack 不夠的情況：a. cwnd 較小 b. 發送窗口裏大量的數據包都被丟失了 c.在數據發送的尾端發生丟包時

但是，上面各種極端的 case 有共同的特點：m. 無法產生足夠的 dupack n.沒有新的數據包可以發送進入網絡，ER 機制就是在判斷條件 m 和 n 都成立後，選擇降低觸發 Fast Retransmit 的閾值，來避免只能通過 RTO 超時重傳的問題。

3.4 TCP Tail Loss Probe（TLP 算法）

ER 算法解決了 dupack 較少時無法觸發快速重傳的問題，但當發生尾丟包時，由於尾包後沒有更多數據包，也就無法觸發 dupack。TLP 算法通過發送一個 loss probe 包，以產生足夠的 SACK/FACK 數據包來觸發重傳。TLP 算法會在 TCP 還是 Open 態時設置一個 Probetimeout（PTO），當鏈路中有未被確認的數據包，同時在 PTO 時間內未收到任何 ACK，則會觸發 PTO 超時處理機制。TLP 會選擇傳輸序號最大的一個數據包作爲 tail loss probe 包，這個序號最大的包可能是一個可以發送的新的數據包，也可能是一個重傳包。TLP 通過這樣一個 tail loss probe 包，如果能夠收到相應的 ACK，則會觸發 FR 機制，而不是 RTO 機制。

3.5 僞超時與重傳

在很多情況下，即使沒有出現數據丟失也可能引發重傳。這種不必要的重傳稱爲僞重傳，其主要造成原因是僞超時，即過早判定超時，其他因素如包失序、包重複，或 ACK 丟失也可能導致該現象。在實際 RTT 顯著增長，超過當前 RTO 時，可能出現僞超時。在下層協議性能變化較大的環境中（如無線環境），這種情況出現得比較多。

TCP 爲處理僞超時問題提出了許多方法。這些方法通常包含檢測算法與響應算法。檢測算法用於判斷某個超時或基於計時器的重傳是否真實，一旦認定出現僞超時則執行響應算法，用於撤銷或減輕該超時帶來的影響。檢測算法包含 DSACK 、Eifel 檢測算法、遷移 RTO 恢復算法(F-RTO) 三種。

3.5.1 DSACK 擴展

DSACK 的主要目的是判斷何時的重傳是不必要的，並瞭解網絡中的其他事項。通過 DSACK 發送端至少可以推斷是否發生了包失序、 ACK 丟失、包重複或僞重傳。D-SACK 使用了 SACK 的第一個段來做標誌， a. 如果 SACK 的第一個段的範圍被 ACK 所覆蓋，那麼就是 D-SACK。b.如果 SACK 的第一個段的範圍被 SACK 的第二個段覆蓋，那麼就是 D-SACK。RFC2883]沒有具體規定發送端對 DSACK 怎樣處理。[RFC3708]給出了一種實驗算法，利用 DSACK 來檢測僞重傳，響應算法可採用 Eifel 響應算法。

3.5.2 Eifel 檢測算法 [RFC3522]

實驗性的 Eifel 檢測算法利用了 TCP 的 TSOPT 來檢測僞重傳。在發生超時重傳後，Eifel 算法等待接收下一個 ACK，若爲針對第一次傳輸（即原始傳輸）的確認，則判定該重傳是僞重傳。

與 DSACK 的比較：利用 Eifel 檢測算法能比僅採用 DSACK 更早檢測到僞重傳行爲 ，因爲它判斷僞重傳的 ACK 是在啓動丟失恢復之前生成的。相反， DSACK 只有在重複報文段到達接收端後才能發送，並且在 DSACK 返回至發送端後纔能有所響應。及早檢測僞重傳更爲有利，它能使發送端有效避免“回退 N”行爲。

3.5.3 遷移 RTO 恢復算法(F-RTO)

前移 RTO 恢復（Forward-RTO Recovery，F-RTO）[RFC5682]是檢測僞重傳的標準算法。它不需要任何 TCP 選項，因此只要在發送端實現該方法後，即使針對不支持 TSOPT 的接收端也能有效地工作。該算法 只檢測由重傳計時器超時引發的僞重傳 ，對之前提到的其他原因引起的僞重傳則無法判斷。

F-RTO 的工作原理如下：1. F-RTO 會修改 TCP 的行爲，在超時重傳後收到第一個 ACK 時，TCP 會發送新（非重傳）數據，之後再響應後一個到達的 ACK。2.如果其中有一個爲重複 ACK，則認爲此次重傳沒問題。3. 如果這兩個都不是重複 ACK，則表示該重傳是僞重傳。4.重複 ACK 是在接收端收到失序的報文段產生的。這種方法比較直觀。如果新數據的傳輸得到了相應的 ACK，就使得接收端窗口前移。如果新數據的發送導致了重複 ACK，那麼接收端至少有一個或更多的空缺。這兩種情況下，接收新數據都不會影響整體數據的傳輸性能。

四、擁塞狀態機

TCP 通過擁塞狀態機來決定收到 ACK 時 cwnd 的行爲（增長或者降低）。TCP 擁塞狀態機有 Open , Disorder , Recovery , Lost 和 CWR 五種狀態。

4.1 Open

當網絡中沒有發生丟包，也就不需要重傳，sender 按照 慢啓動 或者 擁塞避免算法 處理到來的 ACK。

4.2 Disorder

當 sender 檢測到 dupack 或者 SACK，將會轉移到 Disorder 狀態，當處在這個這個狀態中時，cwnd 將維持不變。每收到一個 dupack 或 SACK，發送方將發送一個新包。

4.3 CWR

當 sender 收到 ACK 包含顯示擁塞通知（ECN），這個 ECN 由路由器寫在 IP 頭中，告訴 TCP sender 網絡擁塞，sender 不會立馬降低 cwnd，而是根據 快速恢復算法 進行降窗，直到減爲之前的一半。當 cwnd 正在減小 cwnd，網絡中有沒有重傳包時，這個狀態就叫 CWR，CWR 可以被 Recovery 或者 Loss 中斷。

4.4 Recovery

當 sender 因爲 快速重傳機制 觸發丟包時，sender 會重傳第一個未被 ACK 的包，並進入 Recovery 狀態。在 Recovery 狀態期間，cwnd 的處理同 CWR 大致一樣，要麼重傳標記了 lost 的包，要麼根據保守原則發送新包。直到網絡中所有的包都被 ACK，纔會退出 Recovery 進入 Open 狀態，Recovery 狀態可以被 loss 狀態打斷。

經典 Reno 模式（非 SACK 模式）下，時退出 Recovery 狀態。

如上圖，數據包 A、B、C 可能沒有丟失只是被延遲接收，然而沒有 SACK 機制下無法判斷是 A、B、C 的重傳觸發的 3 次重複 ACK 還是新數據 1、2、3 丟失 1（或者 1、2 或者 1、2、3）導致的重複 ACK，兩種情況均會馬上把擁塞狀態機帶入到 Recovery 狀態，然而前一種是不必要的。如果在 SND_UNA== SND_HIGH 即轉爲 Open 態，那麼當發生上述 1、2、3 的延遲到達後，緊接着的 Recovery 狀態會再次將擁塞窗口減半，最終降低到一個極低值。

SACK/FACK 模式下，時退出 Recovery 狀態。因爲即使發生經典 Reno 模式下的 A、B、C 失序到達，由於存在 SACK 信息，狀態機會將此三個重複 ACK 記爲三個重複的 DSACK，在 SACK 模式下，判斷是否進入 Recovery 狀態的條件是被 SACK 的數據包數量大於 dupthresh，而 DSACK 不被計入到 SACKed 數量中。FACK 模式下隻影響進入 Recovery 狀態的時機，其核心仍建立在 SACK 之上，所以不影響退出的時機。

4.5 Loss

當 RTO 後，TCPsender 進入 Loss 狀態，所有在網絡中的包被標記爲 lost，cwnd 重置爲 1，通過 slow start 重新增加 cwnd。Loss 與 Recovery 狀態的不同點在於，cwnd 會重置爲 1，但是 Recovery 狀態不會，Recovery 狀態下擁塞控制通過 快速恢復 算法逐步降低 cwnd 至 sshthresh。Loss 狀態不能被其它任何狀態中斷，只有當網絡中所有的包被成功 ACK 後，才能重新進入 Open 狀態。

五、擁塞控制

擁塞的發生是因爲路由器緩存溢出，擁塞會導致丟包，但丟包不一定觸發擁塞。擁塞控制是快速傳輸的基礎。一個擁塞控制算法一般包括 慢啓動算法 、 擁塞避免算法 、 快速重傳算法 、 快速恢復算法 四部分。

5.1 慢啓動算法

不同擁塞算法慢啓動的邏輯有所不同，經典的 NewReno 慢啓動的算法如下：

連接建好的開始先初始化 cwnd = 10，表明可以傳 10 個 MSS 大小的數據。
每當收到一個 ACK，cwnd 加 1。這樣每當過了一個 RTT，cwnd 翻倍，呈指數上升。
還有一個 ssthresh（slow start threshold），是一個上限。當 cwnd >=ssthresh 時，就會進入“擁塞避免算法”。

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。

5.2 擁塞避免算法

當 cwnd 增長到 sshthresh 時，就會進入“擁塞避免算法”。擁塞避免算法下 cwnd 成線性增長，即每經過一個往返時間 RTT 就把發送方的擁塞窗口 cwnd 加 1，而不是加倍。這樣就可以避免擁塞窗口快速增長的問題。

每收到一個 ack 時 cwnd 的變化：
cwnd = cwnd + 1 / cwnd

5.3 快速重傳算法

快速重傳算法主要用於丟包檢測，以便能更快重傳數據包，更早的調整擁塞狀態機狀態，從而達到持續升窗的目的。具體重傳策略見第三節 重傳機制 。

5.4 快速恢復算法

當檢測到丟包時，TCP 會觸發快速重傳並進入降窗狀態。該狀態下 cwnd 會通過快速恢復算法降至一個合理值。從歷史發展來看，分爲四個個階段。

5.4.1 BSD 初始版本

收到 3 次重複 ACK，ssthresh 設爲 cwnd/2，cwnd = cwnd / 2 + 3;
每收到一個重複 ACK，窗口值加 1;
收到非重複 ACK，窗口設爲 ssthresh，退出

優點：在快速恢復期間，可以儘可能多的發送數據缺點：由於快速恢復未完成，儘可能多發送可能會加重擁塞。#### 5.4.2 [RFC3517]版本 1) 收到 3 次重複 ACK，ssthresh 設爲 cwnd/2，cwnd = cwnd / 2 + 3; 2) 每收到一個重複 ACK，窗口值加 1/cwnd ; 3) 收到非重複 ACK，窗口設爲 ssthresh，退出。

優點：在快速恢復期間，可以盡少量的發送數據（有利於擁塞恢復），且在快速恢復時間段的最後階段，突發有利於搶帶寬。

缺點：快速恢復末期的突發不利於公平性。

5.4.2 Linux rate halving 算法

Linux 上並沒有按照 [RFC3517] 標準實現，而是做了一些修改並運用到內核中。

1.收到 3 次重複 ACK， sshthresh 設置爲 cwnd/2，窗口維持不變 。2.每收到兩個 ACK（不管是否重複），窗口值減 1：cwnd = cwnd - 1。3.新窗口值取 cwnd = MIN(cwnd, in_flight+1)。4.直到退出快速恢復狀態，cwnd = MIN(cwnd, ssthresh)。

優點：在快速恢復期間，取消窗口陡降過程，可以更平滑的發送數據缺點：降窗策略沒有考慮 PIPE 的容量特徵，考慮一下兩點：

a.如果快速恢復沒有完成，窗口將持續下降下去 b.如果一次性 ACK/SACK 了大量數據，in_flight 會陡然減少，窗口還是會陡降，這不符合算法預期。

5.4.3 prr 算法 [RFC6937]

PRR 算法是最新 Linux 默認推薦的快速恢復算法。prr 算法是一種按比例降窗的算法，其最終效果是：

1.在快速恢復過程中，擁塞窗口非常平滑地向 ssthresh 收斂；2.在快速恢復結束後，擁塞窗口處在 ssthresh 附近

PRR 降窗算法實時監控以下的變量：in_flight：它是窗口的一個度量，in_flight 的值任何時候都不能大於擁塞窗口的大小。

prr_delivered：本次收到 ACK 進入降窗函數的時候，一共被 ACK 或者 SACK 的數據段數量。它度量了本次從網絡中清空了哪些數據段，從而影響 in_flight。

prr_out：進入快速恢復狀態後已經被髮送了多少數據包。在 transmit 例程和 retransmit 例程中遞增。

to_be_out：當前還可以再發多少數據包。

算法原理根據 數據包守恆原則 ，能夠發送的數據包總量是本次接收到的 ACK 中確認的數據包的總量，然而處在擁塞狀態要執行的並不是這個守恆發送的過程，而是降窗的過程，因此需要在被 ACK 的數據包數量和可以發送的數據包數量之間打一個折扣，PRR 希望達到的目標是：

進一步

即：

以此來將目標窗口收斂於 ssthresh。剛進入快速恢復的時候的時候，窗口尚未下降，在收斂結束之前，下面的不等式是成立的：

因此：

考慮到數據包的守恆，設

這意味着在收斂結束前，我們可以多發送 extra 這麼多的數據包。

降窗流程根據上述原理可以得到 prr 算法降窗流程如下：

1.收到多次（默認爲 3）重複 ACK，根據回調函數更新 ssthresh (reno 算法爲 cwnd/2)，窗口維持不變;

2.每收到 ACK（不管是否重複），按上述算法計算 Extra; 3. 新窗口值取 cwnd = in_flight + Extra; 4. 直到退出快速恢復，cwnd = ssthresh;

優點：在快速恢復期間，取消了窗口陡降過程，可以更平滑發送數據，且降窗速率與 PIPE 容量相關。缺點：不利於在擁塞恢復到正常時突發流量的發送。

5.5 記分板算法

記分板算法是爲了統計網絡中正在傳輸的包數量，即 tcp_packets_in_flight 。只有當 cwnd > tcp_packets_in_flight 時，TCP 才允許發送重傳包或者新數據包到網絡中。 tcp_packets_in_flight 和 packets_out , sacked_out , retrans_out , lost_out 有關。其中 packets_out 表示發出去的包數量， sacked_out 爲 sack 的包數量， retrans_out 爲重傳的包數量， lost_out 爲 loss 的包數量，這裏的 loss 包含 rto , FR 和 RACK 等機制判斷出來的丟失包。

爲了可以正確統計這些數據，內核給每個 tcp 包( tcp_skb_cb )添加了 sacked 字段標記該數據包當前的狀態。

__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 （丟包），其狀態轉換圖如下：

記分板狀態轉換邏輯如下：

首先判定丟包，打 L tag，lost_out++，即 L
如果需要重傳，打 R tag，retrans_out++，即 L|R
如果再次丟包，取消 R tag，retrans_out–，lost_out 維持不變，go to step2，此時標記位爲 L
當 SACKED 時，取消 L|R ，retrans_out–，lost_out–，此時爲 S
當 snd_una 向右更新時，packet_out–

5.6 擁塞窗口校驗

在 [RFC2861] 中，區分了 TCP 連接數據傳輸的三種狀態：

network-limited：TCP 的數據傳輸受限於擁塞窗口而不能發送更多的數據。
application-limited：TCP 的數據傳輸速率受限於應用層的數據寫入速率，並沒有到達擁塞窗口上限。
idle：發送端沒有額外的數據等待發送，當數據發送間隔超過一個 RTO 的時候就認爲是 ilde 態。

cwnd 代表了對網絡擁塞狀態的一個評估，擁塞控制要根據 ACK 來更新 cwnd 的前提條件是，當前的數據發送速率真實的反映了 cwnd 的狀況，也就是說當前傳輸狀態是 network-limited。假如 tcp 隔了很長時間沒有發送數據包，即進入 idle，那麼當前真實的網絡擁塞狀態很可能就會與 cwnd 反映的網絡狀況有差距。另外在 application-limited 的場景下，受限數據的 ACK 報文還可能把 cwnd 增長到一個異常大的值，顯然是不合理的。基於上面提到的兩個問題，[RFC2861]引入了擁塞窗口校驗(CWV，Congestion Window Validation)算法。

算法如下：當需要發送新數據時，首先看距離上次發送操作是否超過一個 RTO，如果超過，則 1. 更新 sshthresh 值，設爲 max(ssthresh, (3/4) * cwnd)。2.每經過一個空閒 RTT 時間，cwnd 值減半，但不小於 1 SMSS。

對於應用受限階段（非空閒階段），執行相似的操作：1. 已使用的窗口大小記爲。2. 更新 ssthresh 值，設爲 max(ssthresh, (3/4) * cwnd)。

cwnd 設爲 cwnd 和的平均值。

上述操作均減小了 cwnd，但 ssthresh 維護了 cwnd 的先前值。避免空閒階段可能發生的大數據量注入，可以減輕對有限的路由緩存的壓力，從而減少丟包情況的產生。注意 CWV 減小了 cwnd 值，但沒有減小 ssthresh，因此採用這種算法的通常結果是，在長時間發送暫停後，發送方會進入慢啓動階段。Linux TCP 實現了 CWV 算法並默認啓用。

六、常見的擁塞算法

6.1 New Reno 算法

New Reno 算法包含第五節中介紹的慢啓動算法、擁塞避免算法、快速重傳算法和 prr 算法。在此就不贅述。

6.2 CUBIC 算法

CUBIC 算法和 Reno 算法區別主要在於慢啓動和擁塞避免兩個階段。因爲 Reno 算法進入擁塞避免後每經過一個 RTT 窗口才加 1，擁塞窗口增長太慢，導致在高速網絡下不能充分利用網絡帶寬。所以爲了解決這個問題，BIC 和 CUBIC 算法逐步被提了出來。

(BIC 算法基於二分查找，實現複雜，不看了。)

cubic 算法源碼見 tcp_cubic 文件。

6.2.1 CUBIC 算法原理

CUBIC 的窗口增長函數是一個三次函數，非常類似於 BIC-TCP 的窗口增長函數。CUBIC 的詳細運行過程如下，當出現丟包事件時，CUBIC 同 BIC-TCP 一樣，會記錄這時的擁塞窗口大小作爲，接着通過因子執行擁塞窗口的乘法減小，這裏是一個窗口降低常數，並進行正常的 TCP 快速恢復和重傳。從快速恢復階段進入擁塞避免後，使用三次函數的凹輪廓增加窗口。三次函數被設置在處達到穩定點，然後使用三次函數的凸輪廓開始探索新的最大窗口。

CUBIC 的窗口增長函數公式如下所示：

其中，*W(t)*代表在時刻 t 的窗口大小，C 是一個 CUBIC 的常量參數，t 是從上次丟包後到現在的時間，以秒爲單位。K 是上述函數在沒有進一步丟包的情況下將 W 增加到

經歷的時間，其計算公式如下：

其中也是常量（默認爲 0.2）。

6.2.2 Wmax 的更新

每次丟包後，CUBIC-TCP 會開啓一個新的時段，並取作爲當前飽和點，記錄在 bic_origin_point 字段中，源碼如下：

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;
        }
    }
    //...
}

6.2.3 hystart 混合啓動算法

標準的慢啓動在 BDP 網絡環境下表現不好，不好的原因主要有兩個：

標準慢啓動的擁塞窗口指數式的增長方式過於激進容易導致大量丟包，丟包恢復性能損耗太大。在 ssthreshold 值設置的過高時，慢啓動一段時間後，cwnd 的指數增長會顯得過快。有可能在上一個 RTT，cwnd 剛好等於 BDP；下一個 RTT，cwnd 就等於 2BDP 了。這樣就可能導致多出的一個 BDP 的數據包被丟棄。這類丟包屬於突發丟包（burst packet losses）。
被優化過的慢啓動機制，丟包時在數據包重傳恢復的時候碰巧試圖去減小服務器的負載，導致數據包恢復慢。

總結這些原因都是因爲慢啓動過程過於盲目，不能及時的預測擁塞，導致了大量丟包，所以混合慢啓動機制的主要作用是在慢啓動階段試圖找到“合理”的退出慢啓動進入擁塞避免狀態點（safe exit point）。

Hystart 算法通過 ACK train 信息判斷一個 Safe Exit Point for Slow Start.同時爲了避免計算帶寬，通過一個巧妙的轉換(具體建議看論文)，只要判斷時間差是否超過 Forward one-way delay()來決定是否退出慢啓動。

Hystart 算法通過以下兩個條件來判斷是否應該退出慢啓動 1.一個窗口內的數據包的總傳輸間隔是否超過2. 數據包的 RTT sample(默認 8 個樣本)是否出現較大幅度的增長。如果前面 8 個樣本中的最小 rtt 大於全局最小 rtt 與閾值的和，那麼表示網絡出現了擁塞，應立馬進入擁塞避免階段

6.3 BBR 算法

BBR 全稱 bottleneck bandwidth and round-trip propagation time。基於包丟失檢測的 Reno、NewReno 或者 cubic 爲代表，其主要問題有 Buffer bloat 和長肥管道兩種。和這些算法不同，bbr 算法會時間窗口內的最大帶寬 max_bw 和最小 RTT min_rtt，並以此計算發送速率和擁塞窗口。

6.3.1 BBR 算法原理

如下圖所示，當沒有足夠的數據來填滿管道時，RTprop 決定了流的行爲；當有足夠的數據填滿時，那就變成了 BtlBw 來決定。這兩條約束交匯在點 inflight =BtlBw*RTprop，也就是管道的 BDP（帶寬與時延的乘積）。當管道被填滿時，那些超過的部分（inflight-BDP）就會在瓶頸鍊路中製造了一個隊列，從而導致了 RTT 的增大。當數據繼續增加直到填滿了緩存時，多餘的報文就會被丟棄了。擁塞就是發生在 BDP 點的右邊，而擁塞控制算法就是來控制流的平均工作點離 BDP 點有多遠。

RTProp : round-trip propagation time BtlBW : bottleneck bandwidth

基於丟包的擁塞控制算法工作在 bandwidth-limited 區域的右邊界區域，儘管這種算法可以達到最大的傳輸速率，但是它是以高延遲和高丟包率作爲代價的。在存儲介質較爲小的時候，緩存大小隻比 BDP 大一點，此時這種算法的時延並不會很高。然而，當存儲介質變得便宜之後，交換機的緩存大小已經是 ISP 鏈路 BDP 的很多很多倍了，這導致了 bufferbloat，從而導致了 RTT 從毫秒級升到了秒級。

當一個連接滿足以下兩個條件時，它可以在達到最高的吞吐量的同時保持最低時延：

1)速率平衡：瓶頸帶寬的數據到達速率與 BtlBw 相等；

2)填滿管道：所有的在外數據（inflight data）與 BDP（帶寬與時延的乘積）相等

bbr 算法關於擁塞窗口的核心就是計算 BtlBW 和 RTprop，根據這兩者值計算 BDP。BtlBw 和 RTprop 可能是動態變化的，所以需要實時地對它們進行估計。

計算 RTprop

目前 TCP 爲了檢測丟包，必須實時地跟蹤 RTT 的大小。在任意的時間 t，

其中

表示“噪音”。造成噪聲的因素主要有：鏈路隊列，接收方的時延 ACK 配置，ACK 聚合等因素等待。 RTprop 是路徑的物理特性，並且只有路徑變化纔會改變。

由於一般來說路徑變化的時間尺度遠遠大於 RTprop，所以 RTprop 可以由以下公式進行估計：

即，在一個時間窗口中對 RTT 取最小值。一般將該窗口大小設置爲幾十秒至幾分鐘。

計算 BtlBW

bottleneck bandwidth 的估計不像 RTT 那樣方便，沒有一種 TCPspec 要求實現算法來跟蹤估計 bottleneck 帶寬，但是，可以通過跟蹤發送速率來估計 bottleneck 帶寬。當發送方收到一個 ACK 報文時，它可以計算出該報文的 RTT，並且從發出報文到收到 ack 報文這段時間的 data Inflight。這段時間內的平均發送速率就可以以此計算出來：

這個計算出的速率必定小於 bottleneck 速率（因爲 delta delivered 是確定的，但是 deltat 會較大）。因此，BtlBw 可以根據以下公式進行估計。

其中，時間窗口大小的值一般爲 6~10 個 RTT。

TCP 必須記錄每個報文的離開時間從而計算 RTT。BBR 必須額外記錄已經發送的數據大小，使得在收到每一個 ACK 之後，計算 RTT 及發送速率的值，最後得到 RTprop 和 BtlBw 的估計值。

6.3.2 pacing_rate 和 cwnd

bbr 算法輸出 pacing_rate 和 cwnd 兩個數據。pacing_rate 決定發包速率，cwnd 爲窗口大小。每一次 ACK 都會根據當前的模式計算 pacing_rate 和 cwnd。注意在計算 pacing_rate 和 cwnd 時有 pacing_gain 和 cwnd_gain 兩個參數，

bottleneck_bandwidth = windowed_max(delivered / elapsed, 10 round trips)
min_rtt = windowed_min(rtt, 10 seconds)

pacing_rate = pacing_gain * bottleneck_bandwidth
cwnd = max(cwnd_gain * bottleneck_bandwidth * min_rtt, 4)

6.3.3 BBR 狀態機

BBR 算法也是基於狀態機。狀態機有 STARTUP 、 DRAIN 、 PROBE_BW 、 PROBE_RTT 四種狀態。不同狀態下 pacing_gain 和 cwnd_gain 的取值會有所不同。

STARTUP ：初始狀態，該狀態下類似於傳統擁塞控制的慢啓動階段。該狀態下 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 ：該狀態爲排除狀態。在 STARTUP 狀態下三輪沒有漲幅超過 25%時會進入該狀態。該狀態下 BtlBw 會根據 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 ：該狀態下會照常計算當前的 bw，即瞬時帶寬。然而在計算 pacing rate 以及 cwnd 時，並不會像在 STARTUP 狀態時那樣用一個很大的增益係數去擴張 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 檢測到連續 10s 沒有更新 min rtt 時就會進入該狀態。該狀態的目標是保持 BBR 的公平性並定期排空瓶頸隊列，以收斂到真實的 min_rtt。進入該模式時，BBR 會將 cwnd 的上限設置爲 4 個數據包。在 flight pkg <= 4 後開始進行 rtt 探測，探測時間爲 200ms，探測結束後 BBR 便會記錄 min rtt，並離開 PROBE_RTT 進入相應的模式。代碼見 bbr_update_min_rtt 函數。

Q：爲什麼 PROBE_BW 階段 bbr_cwnd_gain 爲 2？保證極端情況下，按照 pacing_rate 發送的數據包全部丟包時也有數據繼續發送，不會產生空窗期。

Q：爲什麼在探測最小 RTT 的時候最少要保持 4 個數據包4 個包的窗口是合理的，infilght 分別是：剛發出的包，已經到達接收端等待延遲應答的包，馬上到達的應答了 2 個包的 ACK。一共 4 個，只有 1 個在鏈路上，另外 1 個在對端主機裏，另外 2 個在 ACK 裏。路上只有 1 個包。

6.3.4 BBR 算法表現

BBR 將它的大部分時間的在外發送數據都保持爲一個 BDP 大小，並且發送速率保持在估計得 BtlBw 值，這將會最小化時延。但是這會把網絡中的瓶頸鍊路移動到 BBR 發送方本身，所以 BBR 無法察覺 BtlBw 是否上升了。所以，BBR 週期性的在一個 RTprop 時間內將 pacing_gain 設爲一個大於 1 的值，這將會增加發送速率和在外報文。如果 BtlBw 沒有改變，那麼這意味着 BBR 在網絡中製造了隊列，增大了 RTT，而 deliveryRate 仍然沒有改變。（這個隊列將會在下個 RTprop 週期被 BBR 使用小於 1 的 pacing_gain 來消除）。如果 BtlBw 增大了，那麼 deliveryRate 增大了，並且 BBR 會立即更新 BtlBw 的估計值，從而增大了發送速率。通過這種機制，BBR 可以以指數速度非常快地收斂到瓶頸鍊路。

如下圖所示，在 1 條 10Mbps，40ms 的流在 20s 穩定運行之後將 BtlBw 提高了 1 倍（20Mbps），然後在第 40s 又將 BtlBw 恢復至 20Mbps。

下圖展示了 1 個 10Mbps，40ms 的 BBR 流在一開始的 1 秒內，發送方（綠線）和接收方（藍線）的過程。紅線表示的是同樣條件下的 CUBIC 發送。垂直的灰線表示了 BBR 狀態的轉換。下方圖片展示了兩種連接的 RTT 在這段時間的變化。注意，只有收到了 ACK（藍線）之後才能確定出 RTT，所以在時間上有點偏移。圖中標註了 BBR 何時學習到 RTT 和如何反應。

下圖展示了在上圖中展示的 BBR 和 CUBIC 流在開始 8 秒的行爲。CUBIC（紅線）填滿了緩存之後，週期性地在 70%~100%的帶寬範圍內波動。然而 BBR（綠線）在啓動過程結束後，就非常穩定地運行，並且不會產生任何隊列。

下圖展示了在一條 100Mbps，100ms 的鏈路上，BBR 和 CUBIC 在 60 秒內的吞吐量與隨機丟包率（從 0.001%~50%）的關係。在丟包率只有 0.1%的時候，CUBIC 的吞吐量就已經下降了 10 倍，並且在丟包率爲 1%的時候就幾乎炸了。而理論上的最大吞吐量是鏈路速率乘以（1-丟包率）。BBR 在丟包率爲 5%以下時還能基本維持在最大吞吐量附近，在 15%丟包率的時候雖然有所下降但還是不錯。

6.4 Westwood 算法

TCP Westwood 算法簡稱 TCPW，和 bbr 算法類似是基於帶寬估計的一種擁塞控制算法。TCPW 採用和 Reno 相同的慢啓動算法、擁塞避免算法。區別在於當檢測到丟包時，根據帶寬值來設置擁塞窗口、慢啓動閾值。

6.4.1 如何測量帶寬 bw_est

和 bbr 算法不同，tcpw 帶寬計算相當粗糙。tcpw 每經過一個 RTT 測量一次帶寬。假設經過時間爲 delta，該時間內發送完成的數據量爲 bk，則採樣值爲 bk / delta。然後和 rtt 一樣，帶寬採樣值會經過一個平滑處理算出最終的帶寬值。

6.4.2 如何確認單位時間的發送量 bk

tcpw 採用一種粗糙的估算方式。在收到回包後，會根據當前的 snd_una 和之前的 snd_una 之間的差值來估算被 ACK 的字節數，即關於 SACK 的信息會被丟失。具體邏輯見 westwood_acked_count 函數。

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;
}

6.4.3 計算 ssthresh

計算 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);
}