BBR

**TCP 擁塞控制**是傳輸控制協定（英語：Transmission Control Protocol，縮寫 TCP）避免網路擁塞的演算法，是網際網路上主要的一個擁塞控制措施。它使用一套基於線增積減模式的多樣化網路擁塞控制方法（包括慢啟動和擁塞窗口等模式）來控制擁塞。在網際網路上應用中有相當多的具體實現演算法。

## 運作方法

TCP 使用多種擁塞控制策略來避免雪崩式擁塞。TCP 會為每條連接維護一個「擁塞窗口」來限制可能在端對端間傳輸的未確認分組總數量。這類似 TCP 流量控制機制中使用的滑動窗口。TCP 在一個連接初始化或逾時後使用一種「慢啟動」機制來增加擁塞窗口的大小。它的起始值一般為最大分段大小（Maximum segment size，MSS）的兩倍，雖然名為「慢啟動」，初始值也相當低，但其增長極快：當每個分段得到確認時，擁塞窗口會增加一個 MSS，使得在每次往返時間（round-trip time，RTT）內擁塞窗口能高效地雙倍增長。

當擁塞窗口超過慢啟動閾值（ssthresh）時，演算法就會進入一個名為「擁塞避免」的階段。在擁塞避免階段，只要未收到重複確認，擁塞窗口則在每次往返時間內線性增加一個 MSS 大小。

## 擁塞窗口

在 TCP 中，**擁塞窗口**（congestion window）是任何時刻內確定能被傳送出去的位元組數的控制因素之一，是阻止傳送方至接收方之間的鏈路變得擁塞的手段。他是由傳送方維護，通過估計鏈路的擁塞程度計算出來的，與由接收方維護的接收窗口大小並不衝突。

當一條連接建立後，每個主機獨立維護一個擁塞窗口並設定值為連接所能承受的 MSS 的最小倍數，之後的變化依靠線增積減機制來控制，這意味如果所有分段到達接收方和確認包準時地回到傳送方，擁塞窗口會增加一定數量。該窗口會保持指數增大，直到發生逾時或者超過一個稱為「慢啟動閾值（ssthresh）」的限值。如果傳送方到達這個閾值時，每收到一個新確認包，擁塞窗口只按照線性速度增加自身值的倒數。

當發生逾時的時候，慢啟動閾值降為逾時前擁塞窗口的一半大小、擁塞窗口會降為 1 個 MSS，並且重新回到慢啟動階段。

系統管理員可以設定窗口最大限值，或者調整擁塞窗口的增加量，來對 TCP 調優。

在流量控制中，接收方通過 TCP 的「窗口」值（Window Size）來告知傳送方，由傳送方通過對擁塞窗口和接收窗口的大小比較，來確定任何時刻內需要傳輸的資料量。

## 慢啟動

**慢啟動**（Slow-start）是用於結合其他階段演算法，來避免傳送過多資料到網路中而導致網路擁塞，演算法在 RFC 5681 中定義。

慢啟動初始啟動時設定擁塞窗口值（cwnd）為 1、2、4 或 10 個 MSS。擁塞窗口在每接收到一個確認包時增加，每個 RTT 內成倍增加，當然實際上並不完全是指數增長，因為接收方會延遲傳送確認，通常是每接收兩個分段則傳送一次確認包。傳送速率隨著慢啟動的進行而增加，直到遇到出現遺失、達到慢啟動閾值（ssthresh）、或者接收方的接收窗口進行限制。如果發生遺失，則 TCP 推斷網路出現了擁塞，會試圖採取措施來降低網路負載。這些是靠具體使用的 TCP 擁塞演算法來進行測量判斷。當達到慢啟動閾值（ssthresh）時，慢啟動演算法就會轉換為線性增長的階段，演算法控制每個 RTT 內擁塞窗口只增加 1 個分段量。雖然稱為「慢啟動」，但實際上比擁塞控制階段的窗口增加更為激進。

對於處理報文遺失這個事件上，不同擁塞控制演算法表現有所不同：

　
: **TCP Tahoe**
: 對於 TCP Tahoe 演算法，當發生遺失時，會進入「快速重傳」機制，慢啟動閾值設為之前擁塞窗口值的一半，擁塞窗口值降為初始值，重新進入慢啟動階段。當擁塞窗口值達到慢啟動閾值時，每 RTT 內擁塞窗口增加值則為「MSS 除以 CWND」的值，所以擁塞窗口按線性速度增加。

　
: **TCP Reno**
: TCP Reno 演算法實現了一個名為「快速恢復」的機制，慢啟動閾值設為之前擁塞窗口值的一半，和作為新的擁塞窗口值，並跳過慢啟動階段，直接進入擁塞控制階段。

慢啟動假設分段的未確認是由於網路擁塞造成的，雖然大部分網路的確如此，但也有其他原因，例如一些鏈路品質差的網路，會導致分段包遺失。在一些網路環境，例如無線網路，慢啟動效率並不好。

慢啟動對於一些短暫的連接效能並不好，一些較舊的網頁瀏覽器會建立大量連續的短暫連結，通過快速開啟和關閉連結來請求獲得檔案，這使得大多數連結處於慢啟動模式，導致網頁回應時間差。所以現在新的網頁瀏覽器，會通過向特殊的伺服器，開啟一條連結來請求獲得全部的檔案，而避免頻繁新建大量短暫連結。不過這樣對一些非請求網站所提供的服務，例如廣告跟蹤指令碼、社交分享功能指令碼、網路分析指令碼等，並不適用。

## 和式增加，積式減少

和性增長 / 乘性降低（additive-increase/multiplicative-decrease，AIMD，這裡簡稱「線增積減」）是一種回饋控制演算法，其包含了對擁塞窗口線性增加，和當發生擁塞時對窗口積式減少。多個使用 AIMD 控制的 TCP 流最終會收斂到對線路的等量競爭使用。

## 快速重傳

**快速重傳**（Fast retransmit）是對 TCP 傳送方降低等待重發遺失分段用時的一種改進。TCP 傳送方每傳送一個分段都會啟動一個逾時計時器，如果沒能在特定時間內接收到相應分段的確認，傳送方就假設這個分段在網路上遺失了，需要重發。這也是 TCP 用來估計 RTT 的測量方法。

重複確認（duplicate cumulative acknowledgements，DupAcks）就是這個階段的基礎，其基於以下過程：如果接收方接收到一個資料分段，就會將該分段的序列號加上資料位元組長的值，作為分段確認的確認號，傳送回傳送方，表示期望傳送方傳送下一個序列號的分段。但是如果接收方提前收到更下一個序列號的分段 —— 或者說接收到無序到達的分段，即之前期望確認號對應的分段出現接收遺失 —— 接收方需要立即使用之前的確認號傳送分段確認。此時如果傳送方收到接收方相同確認號的分段確認超過 1 次，並且該對應序列號的分段逾時計時器仍沒逾時的話，則這就是出現重複確認，需要進入快速重傳。

快速重傳就是基於以下機制：如果假設重複閾值為 3，當傳送方收到 4 次相同確認號的分段確認（第 1 次收到確認期望序列號，加 3 次重複的期望序列號確認）時，則可以認為繼續傳送更高序列號的分段將會被接受方丟棄，而且會無法有序送達。傳送方應該忽略逾時計時器的等待重發，立即重發重複分段確認中確認號對應序列號的分段。

## 具體實現演算法

「TCP + 演算法名稱」這一 TCP 演算法命名方式最早出在凱文・福爾（Kevin Fall）和莎莉・弗洛伊德（Sally Floyd）在 1996 年發布的一篇論文中。

### TCP Tahoe 和 Reno

這兩個演算法是根據其第一次加入到 4.3BSD 的時間回溯命名的，兩個名字對應自其第一次出現時 BSD 的代號，而代號分別取自太浩湖（Lake Tahoe）和其附近的城市雷諾市。「Tahoe」演算法實現在 4.3BSD-Tahoe 中第一次加入，之後在 4.3BSD 網路發布第一版實現了脫 AT&T 授權版本，使其能更容易被廣泛再發布與實現。改進版「Reno」在 4.3BSD-Reno 中實現，並之後通過「4.3BSD 網路發布第二版」和 4.4BSD-Lite 發布。

兩者演算法大致一致，對於丟包事件判斷都是以重傳逾時（retransmission timeout，RTO）和重複確認為條件，但是對於重複確認的處理，兩者有所不同：

* Tahoe：如果收到三次重複確認 —— 即第四次收到相同確認號的分段確認，並且分段對應包無負載分段和無改變接收窗口 —— 的話，Tahoe 演算法則進入快速重傳，將慢啟動閾值改為當前擁塞窗口的一半，將擁塞窗口降為 1 個 MSS，並重新進入慢啟動階段。
* Reno：如果收到三次重複確認，Reno 演算法則進入快速重傳，只將擁塞窗口減半來跳過慢啟動階段，將慢啟動閾值設為當前新的擁塞窗口值，進入一個稱為「快速恢復」的新設計階段。

對於 RTO，兩個演算法都是將擁塞窗口降為 1 個 MSS，然後進入慢啟動階段。

#### 快速恢復

**快速恢復**（Fast recovery）是 Reno 演算法新引入的一個階段，在將遺失的分段重傳後，啟動一個逾時定時器，並等待該遺失分段包的分段確認後，再進入擁塞控制階段。如果仍然逾時，則回到慢啟動階段。

### TCP Vegas

至 1990 年代中期，TCP 量度延遲和 RTT 都是以傳輸快取中最後一個被傳送的分段包為準。亞利桑那大學的研究人員拉里・彼得森和勞倫斯・布拉科夫提出了新的 TCP 擁塞演算法「TCP Vegas」，其實通過度量傳輸快取中每個傳送分段包來代替只量度一個分段包，根據每次度量的平均值來增加擁塞窗口。該演算法取名自內華達州最大的城市拉斯維加斯。不過由於一些資源公平性原因，該演算法並沒有在彼得森的實驗室之外廣泛部署。一些研究認為該演算法和其他擁塞演算法混合使用，可能會導致效能競爭不及其他演算法。在各種 TCP 擁塞演算法的比較研究中，Vegas 被認為是最平滑的控制演算法，其次為 CUBIC。

DD-WRT 在 v24 SP2 開始將該演算法作為其預設的 TCP 擁塞控制演算法。

### TCP New Reno

TCP New Reno 是對 TCP Reno 中快速恢復階段的重傳進行改善的一種改進演算法，其定義於 RFC 6582，覆蓋了原有在 RFC 3782 和 RFC 2582 的舊定義。

在 Reno 的快速恢復中，一旦出現 3 次重複確認，TCP 傳送方會重發重複確認對應序列號的分段並設定定時器等待該重發分段包的分段確認包，當該分段確認包收到後，就立即登出快速恢復階段，進入擁塞控制階段，但如果某個導致重複確認的分段包到遇到重複確認期間所傳送的分段包存在多個遺失的話，則這些遺失只能等待逾時重發，並且導致擁塞窗口多次進入擁塞控制階段而多次下降。而 New Reno 的快速恢復中，一旦出現 3 次重複確認，TCP 傳送方先記下 3 次重複確認時已傳送但未確認的分段的最大序列號，然後重發重複確認對應序列號的分段包。如果只有該重複確認的分段遺失，則接收方接收該重發分段包後，會立即返回最大序列號的分段確認包，從而完成重發；但如果重複確認期間的傳送包有多個遺失，接收方在接收該重發分段後，會返回非最大序列號的分段確認包，從而傳送方繼續保持重發這些遺失的分段，直到最大序列號的分段確認包的返回，才登出快速恢復階段。

New Reno 在低錯誤率時執行效率和「選擇確認」（Selective ACKnowledgement，SACK）相當，在高錯誤率仍優於 Reno。

### TCP Hybla

TCP Hybla 旨在消除由於高延遲地面線路或者衛星無線鏈路下導致的 RTT 過長而對 TCP 連結的影響。它通過對擁塞窗口動態分析來修改，來減少對 RTT 的效能依賴。

### TCP BIC 和 CUBIC

TCP BIC（Binary Increase Congestion control）旨在最佳化高速高延遲網路（即根據 RFC 1072 所定義的「長肥網路」（long fat network，LFN））的擁塞控制，其擁塞窗口演算法使用二分搜尋演算法嘗試找到能長時間保持擁塞窗口最大值的值。Linux 核心在 2.6.8 至 2.6.18 使用該演算法作為預設 TCP 擁塞演算法。

CUBIC 則是比 BIC 更溫和和系統化的分支版本，其使用三次函式代替二分演算法作為其擁塞窗口演算法，並且使用函式拐點作為擁塞窗口的設定值。Linux 核心在 2.6.19 後使用該演算法作為預設 TCP 擁塞演算法。

### TCP Westwood 和 Westwood+

TCP Westwood 改良自 New Reno，不同於以往其他擁塞控制演算法使用遺失來測量，其通過對確認包測量來確定一個「合適的傳送速度」，並以此調整擁塞窗口和慢啟動閾值。其改良了慢啟動階段演算法為「敏捷探測（Agile Probing）」，和設計了一種持續探測擁塞窗口的方法來控制進入「敏捷探測」，使連結儘可能地使用更多的頻寬。Westwood + 使用更長的頻寬估計間隔和最佳化的濾波器來修正 Westwood 對 ACK 壓縮場景對頻寬估計過高的問題。通過以上改良，TCP Westwood 系列演算法在有線網路和無線網路的擁塞控制上取得平衡，尤其研究中針對於無線通信網路上。

### Compound TCP

複合 TCP（Compound TCP）是微軟自己實現的 TCP 擁塞控制演算法，通過同時維護兩個擁塞窗口，來實現在長肥網路有較好的效能而又不損失公平性。該演算法在 Windows Vista 和 Windows Server 2008 開始廣泛部署，並通過修補程式的方式回溯支援到 Windows XP 和 Windows Server 2003。在 Linux 上也有一個舊版本的移植實現。

### TCP PRR

TCP PRR（TCP Proportional Rate Reduction ）是旨在恢復期間提高傳送資料的準確性。該演算法確保恢復後的擁塞窗口大小儘可能接近慢啟動閾值。在 Google 進行的測試中，能將平均延遲降低 3~10%，恢復的逾時減少 5%。PRR 演算法之後作為 Linux 核心 3.2 版本的預設擁塞演算法。

### TCP BBR

TCP BBR（Bottleneck Bandwidth and Round-trip propagation time）是由 Google 設計，於 2016 年發布的擁塞演算法。以往大部分擁塞演算法是基於丟包來作為降低傳輸速率的訊號，而 BBR 則基於模型主動探測。該演算法使用網路最近出站資料分組當時的最大頻寬和往返時間來建立網路的顯式模型。封包傳輸的每個累積或選擇性確認用於生成記錄在封包傳輸過程和確認返回期間的時間內所傳送資料量的取樣率。該演算法認為隨著網路介面控制器逐漸進入千兆速度時，與緩衝膨脹相關的延遲相比丟包更應該被認為是辨識擁塞的主要決定因素，所以基於延遲模型的擁塞控制演算法（如 BBR）會有更高的吞吐量和更低的延遲，可以用 BBR 來替代其他流行的擁塞演算法，例如 CUBIC。Google 在 YouTube 上應用該演算法，將全球平均的 YouTube 網路吞吐量提高了 4%，在一些國家超過了 14%。

BBR 之後移植入 Linux 核心 4.9 版本，並且對於 QUIC 可用。

BBR 效率很高，速度也很快，但是它與非 BBR 的流的公平性有爭議。雖然 Google 的展示顯示 BBR 與 CUBIC 共存良好，但像傑夫・休斯頓和霍克、布利斯和齊特巴特等研究者發現它對其他流不公平，並且不可延伸。霍克等人還發現，在 Linux 4.9 的 BBR 實現中「存在一些嚴重的原生問題，如排隊延遲增加、不公平和大量封包遺失」。

索海爾・阿巴斯洛等人（C2TCP 的作者）指出，BBR 在動態環境中表現不佳，比如蜂巢式網路。他們還表明 BBR 存在不公平問題。例如，當一個 CUBIC 流（在 Linux、Android 和 MacOS 中是預設的 TCP 實現）與網路中的 BBR 流共存時，BBR 流可以支配 CUBIC 流並從中獲得整個鏈路頻寬。

## 註腳

## 參考文獻

## 外部連結

* Approaches to Congestion Control in Packet Networks (PDF), [2018-04-19], （原始內容存檔 (PDF) 於 2014-02-21）
* 一些關於擁塞控制的論文（頁面存檔備份，存於網際網路檔案館）
* TCP Vegas 的介紹首頁
* Mark Allman, Vern Paxson, W. Richard Stevens. Fast Retransmit/Fast Recovery. TCP Congestion Control. IETF. April 1999: sec. 3.2 [2010-05-01]. RFC 2581.
* TCP Congestion Handling and Congestion Avoidance Algorithms（頁面存檔備份，存於網際網路檔案館） – The TCP/IP Guide
* TCP 的 NewReno 快速重傳和快速恢復演算法（頁面存檔備份，存於網際網路檔案館）
* TCP 擁塞控制：Tahoe、Reno、NewReno 與 SACK 演算法概述與比較（頁面存檔備份，存於網際網路檔案館）