淺談 TCP 擁塞控制演算法
本篇文章介紹了幾種經典的TCP擁塞控制演算法，包括演算法原理及各自適用場景。
回顧上篇文章： 淺談 redis 延遲
前言
TCP 通過維護一個擁塞視窗來進行擁塞控制，擁塞控制的原則是，只要網路中沒有出現擁塞，擁塞視窗的值就可以再增大一些，以便把更多的資料包傳送出去，但只要網路出現擁塞，擁塞視窗的值就應該減小一些，以減少注入到網路中的資料包數。
TCP 擁塞控制演算法發展的過程中出現瞭如下幾種不同的思路：
-
基於丟包的擁塞控制：將丟包視為出現擁塞，採取緩慢探測的方式，逐漸增大擁塞視窗，當出現丟包時，將擁塞視窗減小，如 Reno、Cubic 等。
-
基於時延的擁塞控制：將時延增加視為出現擁塞，延時增加時增大擁塞視窗，延時減小時減小擁塞視窗，如 Vegas、FastTCP 等。
-
基於鏈路容量的擁塞控制：實時測量網路頻寬和時延，認為網路上報文總量大於頻寬時延乘積時出現了擁塞，如 BBR。
-
基於學習的擁塞控制：沒有特定的擁塞訊號，而是藉助評價函式，基於訓練資料，使用機器學習的方法形成一個控制策略，如 Remy。
擁塞控制演算法的核心是選擇一個有效的策略來控制擁塞視窗的變化，下面介紹幾種經典的擁塞控制演算法。
Vegas
Vegas [1] 將時延 RTT 的增加作為網路出現擁塞的訊號，RTT 增加，擁塞視窗減小，RTT 減小，擁塞視窗增加。具體來說，Vegas 通過比較實際吞吐量和期望吞吐量來調節擁塞視窗的大小，
期望吞吐量：Expected = cwnd / BaseRTT，
實際吞吐量： Actual = cwnd / RTT，
diff = (Expected-Actual) * BaseRTT，
BaseRTT 是所有觀測來回響應時間的最小值，一般是建立連線後所發的第一個資料包的 RTT，cwnd 是目前的擁塞視窗的大小。Vegas 定義了兩個閾值 a，b，當 diff > b 時，擁塞視窗減小，當 a <= diff <=b 時，擁塞視窗不變，當 diff < a 時，擁塞視窗增加。
Vegas 演算法採用 RTT 的改變來判斷網路的可用頻寬，能精確地測量網路的可用頻寬，效率比較好。但是，網路中 Vegas 與其它演算法共存的情況下，基於丟包的擁塞控制演算法會嘗試填滿網路中的緩衝區，導致 Vegas 計算的 RTT 增大，進而降低擁塞視窗，使得傳輸速度越來越慢，因此 Vegas 未能在 Internet 上普遍採用。
適用場景：
適用於網路中只存在 Vegas 一種擁塞控制演算法，競爭公平的情況。
Reno
Reno [2] 將擁塞控制的過程分為四個階段：慢啟動、擁塞避免、快重傳和快恢復，是現有的眾多擁塞控制演算法的基礎，下面詳細說明這幾個階段。
慢啟動階段，在沒有出現丟包時每收到一個 ACK 就將擁塞視窗大小加一（單位是 MSS，最大單個報文段長度），每輪次傳送視窗增加一倍，呈指數增長，若出現丟包，則將擁塞視窗減半，進入擁塞避免階段；當視窗達到慢啟動閾值或出現丟包時，進入擁塞避免階段，視窗每輪次加一，呈線性增長；當收到對一個報文的三個重複的 ACK 時，認為這個報文的下一個報文丟失了，進入快重傳階段，立即重傳丟失的報文，而不是等待超時重傳；快重傳完成後進入快恢復階段，將慢啟動閾值修改為當前擁塞視窗值的一半，同時擁塞視窗值等於慢啟動閾值，然後進入擁塞避免階段，重複上訴過程。Reno 擁塞控制過程如圖 1 所示。
圖 1、TCP Reno 擁塞控制過程
Reno 演算法將收到 ACK 這一訊號作為擁塞視窗增長的依據，在早期低頻寬、低時延的網路中能夠很好的發揮作用，但是隨著網路頻寬和延時的增加，Reno 的缺點就漸漸體現出來了，傳送端從傳送報文到收到 ACK 經歷一個 RTT，在高頻寬延時（High Bandwidth-Delay Product，BDP）網路中，RTT 很大，導致擁塞視窗增長很慢，傳輸速度需要經過很長時間才能達到最大頻寬，導致頻寬利用率將低。
適用場景：
適用於低延時、低頻寬的網路。
Cubic
Cubic [3] 是 Linux 核心 2.6 之後的預設 TCP 擁塞控制演算法， 使用一個立方函式（cubic function）
作為擁塞視窗的增長函式，其中，C 是調節因子，t 是從上一次縮小擁塞視窗經過的時間，W max 是上一次發生擁塞時的視窗大小，
β是乘法減小因子。從函式中可以看出擁塞視窗的增長不再與 RTT 有關，而僅僅取決上次發生擁塞時的最大視窗和距離上次發生擁塞的時間間隔值。
Cubic 擁塞視窗增長曲線如下，凸曲線部分為穩定增長階段，凹曲線部分為最大頻寬探測階段。如圖 2 所示，在剛開始時，擁塞視窗增長很快，在接近 W max 口時，增長速度變的平緩，避免流量突增而導致丟包；在 W max 附近，擁塞視窗不再增加；之後開始緩慢地探測網路最大吞吐量，保證穩定性（在 W max 附近容易出現擁塞），在遠離 W max 後，增大視窗增長的速度，保證了頻寬的利用率。
圖 2、TCP Cubic 擁塞視窗增長函式
當出現丟包時，將擁塞視窗進行乘法減小，再繼續開始上述增長過程。此方式可以使得擁塞視窗一直維持在 Wmax 附近，從而保證了頻寬的利用率。Cubic 的擁塞控制過程如圖 3 所示：
圖 3、TCP Cubic 擁塞控制過程
Cubic 演算法的優點在於只要沒有出現丟包，就不會主動降低自己的傳送速度，可以最大程度的利用網路剩餘頻寬，提高吞吐量，在高頻寬、低丟包率的網路中可以發揮較好的效能。
但是，Cubic 同之前的擁塞控制演算法一樣，無法區分擁塞丟包和傳輸錯誤丟包，只要發現丟包，就會減小擁塞視窗，降低傳送速率，而事實上傳輸錯誤丟包時網路不一定發生了擁塞，但是傳輸錯誤丟包的概率很低，所以對 Cubic 演算法的效能影響不是很大。
Cubic 演算法的另一個不足之處是過於激進，在沒有出現丟包時會不停地增加擁塞視窗的大小，向網路注入流量，將網路裝置的緩衝區填滿，出現 Bufferbloat（緩衝區膨脹）。由於緩衝區長期趨於飽和狀態，新進入網路的的資料包會在緩衝區裡排隊，增加無謂的排隊時延，緩衝區越大，時延就越高。另外 Cubic 演算法在高頻寬利用率的同時依然在增加擁塞視窗，間接增加了丟包率，造成網路抖動加劇。
適用場景：
適用於高頻寬、低丟包率網路，能夠有效利用頻寬。
BBR
BBR [4 ] 是谷歌在 2016 年提出的一種新的擁塞控制演算法，已經在 Youtube 伺服器和谷歌跨資料中心廣域網上部署，據 Youtube 官方資料稱，部署 BBR 後，在全球範圍內訪問 Youtube 的延遲降低了 53%，在時延較高的發展中國家，延遲降低了 80%。目前 BBR 已經整合到 Linux 4.9 以上版本的核心中。
BBR 演算法不將出現丟包或時延增加作為擁塞的訊號，而是認為當網路上的資料包總量大於瓶頸鍊路頻寬和時延的乘積時才出現了擁塞，所以 BBR 也稱為基於擁塞的擁塞控制演算法（Congestion-Based Congestion Control）。BBR 演算法週期性地探測網路的容量，交替測量一段時間內的頻寬極大值和時延極小值，將其乘積作為作為擁塞視窗大小（交替測量的原因是極大頻寬和極小時延不可能同時得到，頻寬極大時網路被填滿造成排隊，時延必然極大，時延極小時需要資料包不被排隊直接轉發，頻寬必然極小），使得擁塞視窗始的值始終與網路的容量保持一致。
由於 BBR 的擁塞視窗是精確測量出來的，不會無限的增加擁塞視窗，也就不會將網路裝置的緩衝區填滿，避免了出現 Bufferbloat 問題，使得時延大大降低。如圖 4 所示，網路緩衝區被填滿時時延為 250ms，Cubic 演算法會繼續增加擁塞視窗，使得時延持續增加到 500ms 並出現丟包，整個過程 Cubic 一直處於高時延狀態，而 BBR 由於不會填滿網路緩衝區，時延一直處於較低狀態。
圖 4、Cubic 和 BBR RTT 對比
由於 BBR 演算法不將丟包作為擁塞訊號，所以在丟包率較高的網路中，BBR 依然有極高的吞吐量，如圖 5 所示，在 1% 丟包率的網路環境下，Cubic 的吞吐量已經降低 90% 以上，而 BBR 的吞吐量幾乎沒有受到影響，當丟包率大於 15% 時，BBR 的吞吐量才大幅下降。
圖 5、Cubic 和 BBR 傳輸速率與丟包率關係對比
BBR 演算法是反饋驅動的，有自主調節機制，不受 TCP 擁塞控制狀態機的控制，通過測量網路容量來調整擁塞視窗，傳送速率由自己掌控，而傳統的擁塞控制演算法只負責計算擁塞視窗，而不管傳送速率（pacing rate），怎麼發由 TCP 自己決定，這樣會在瓶頸頻寬附近因傳送速率的激增導致資料包排隊或出現丟包。
經過測試，在高延時、高丟包率的環境下，BBR 相對於 Cubic 演算法在傳輸速度上有較大的提升，具體的測試結果表 1 所示：
表1 200ms 延時下 Cubic 與 BBR 傳輸速度對比
BBR 演算法的不足之處在於裝置佇列快取較大時，BBR 可能會競爭不過 Cubic 等比較激進演算法，原因是 BBR 不主動去佔據佇列快取，如果 Cubic 的流量長期佔據佇列快取，會使得 BBR 在多個週期內測量的極小 RTT 增大，進而使 BBR 的頻寬減小。
適用場景：
適用於高頻寬、高時延、有一定丟包率的長肥網路，可以有效降低傳輸時延，並保證較高的吞吐量。
Remy
Remy [5] 也稱為計算機生成的擁塞控制演算法（computer-generated congestion-control algorithm），採用機器學習的方式生成擁塞控制演算法模型。通過輸入各種引數模型（如瓶頸鍊路速率、時延、瓶頸鍊路上的傳送者數量等），使用一個目標函式定量判斷演算法的優劣程度，在生成演算法的過程中，針對不同的網路狀態採用不同的方式調整擁塞視窗，反覆修改調節方式，直到目標函式最優，最終會生成一個網路狀態到調節方式的對映表，在真實的網路中，根據特定的網路環境從對映表直接選取擁塞視窗的調節方式。
Remy 試圖遮蔽底層網路環境的差異，採用一個通用的擁塞控制演算法模型來處理不同的網路環境。這種方式比較依賴輸入的訓練集（歷史網路模型），如果訓練集能夠全面覆蓋所有可能出現的網路環境及擁塞調節演算法，Remy 演算法在應用到真實的網路環境中時能夠表現的很好，但是如果真實網路與訓練網路差異較大，Remy 演算法的效能會比較差。
適用場景：網路環境為複雜的異構網路，希望計算機能夠針對不同網路場景自動選擇合適的擁塞控制方式，要求現有的網路模型能夠覆蓋所有可能出現情況。
總結
每一種擁塞控制演算法都是在一定的網路環境下誕生的，適合特定的場景，沒有一種一勞永逸的演算法。網路環境越來越複雜，擁塞控制演算法也在不斷地演進。本文不是要去選擇一個最好的演算法，只是簡單介紹了幾種典型演算法的設計思路、優缺點以及適用場景，希望能給大家帶來一些啟發。
參考論文
[1] S.O. L. Brakmo and L. Peterson. TCP Vegas: New techniques for congestiondetection and avoidance. In SIGCOMM, 1994. Proceedings. 1994 InternationalConference on. ACM, 1994.
[2] V.Jacobson, “Congestion avoidance and control,” in ACM SIGCOMM ComputerCommunication Review, vol. 18. ACM, 1988, pp. 314–329.
[3] L. X. I. R. Sangtae Ha. Cubic: A new TCP -friendlyhigh-speed TCP variant. In SIGOPS-OSR, July 2008. ACM, 2008.
[4] C.S. G. S. H. Y. Neal Cardwell, Yuchung Cheng and V. Jacobson. BBR:congestion-based congestion control. ACM Queue, 14(5):20{53, 2016.
[5] K.Winstein and H. Balakrishnan. TCP Ex Machina: Computer-generated Congestion Control.In Proceedings of the ACM SIGCOMM 2013 Conference, 2013.
