在TCP的演程序序中，出現了很多優秀的思想和演算法，以實作網路傳輸程序中，在公平競爭性的前提下，盡可能地利用帶寬資源，本文介紹TCP發展程序中出現的幾種擁塞控制演算法，

需要解決的問題：檢測、控速、重傳

• 檢測：丟失超時、3個冗余ACK、網路反饋、延遲變化
  • Tahoe、Reno、New Reno、SACK演算法，基于事件，基于丟包，超時、3個冗余ACK，網路已經出現擁塞，反應慢
  • ECN，基于網路顯式反饋，網路反饋
  • 延遲變化，基于RTT
• 控速：
• 重傳：重傳的時機和物件

擁塞控制前言

1、公平性

公平性是在發生擁塞時各源端（或同一源端建立的不同TCP連接或UDP資料報）能公平地共享同一網路資源（如帶寬、快取等），處于相同級別的源端應該得到相同數量的網路資源，產生公平性的根本原因在于擁塞發生必然導致資料包丟失，而資料包丟失會導致各資料流之間為爭搶有限的網路資源發生競爭，爭搶能力弱的資料流將受到更多損害，因此，沒有擁塞，也就沒有公平性問題，

TCP層上的公平性問題表現在兩方面：

（1）面向連接的TCP和無連接的UDP在擁塞發生時對擁塞指示的不同反應和處理，導致對網路資源的不公平使用問題，在擁塞發生時，有擁塞控制機制的TCP會按擁塞控制步驟進入擁塞避免階段，從而主動減小發送到網路的資料量，但對無連接的資料報UDP，由于沒有端到端的擁塞控制機制，即使網路出現了擁塞，也不會減少向網路發送的資料量，結果遵守擁塞控制的TCP資料流得到的網路資源越來越少，沒有擁塞控制的UDP則會得到越來越多的網路資源，

（2）TCP連接之間也存在公平性問題，產生問題的原因在于使用了不同的擁塞控制演算法，一些TCP在擁塞前使用了大視窗尺寸，或者它們的RTT較小，或者資料包比其他TCP大，這樣它們也會多占帶寬，

主要四個程序

1）慢啟動；2）擁塞避免；3）擁塞發生，快重傳；4）快速恢復，

經典概念

1. RTT：資料包從發出去到收到對它的ack的來回時間，采用平滑方式計算RTT
2. RTO：重傳超時，簡單的如RTO=n*RTT, n=3（或其他RTO計算方法）
3. SACK：TCP Option攜帶多組ACK資訊
4. FR：Fast Retransmission，收到3個dup ack后，即可認為發生了丟包，不需要等待RTO超時即可重傳丟失的包，
5. ER：Early Retransmission，無法產生足夠的dupack和沒有新的資料包可以發送進入網路的情況下，減少觸發FR的dup ack數量，以達到觸發FR的目的，
6. TLP：如果發生了尾丟包，由于尾包后面沒有更多的資料包，也就沒有辦法觸發任何的dupack，實際上，Google統計超過70%的RTO是尾丟包導致沒有任何dup ack，TLP演算法是通過發送一個loss probe包，來產生足夠的SACK/FACK的資訊以觸發RF，
7. Pacing：控制發送速率，防止bursting
8. 流量控制：Flow control站在單條TCP連接的維度，目的是讓發送方發包的速度，不超過接收方收包的能力，所以流控解決的問題是，如何在接收方可承受的范圍內，讓單條 TCP 連接的速度最大化，通過滑動視窗機制實作，
9. 擁塞控制：Congestion control站在整個互聯網的維度，讓網路里所有TCP連接最大化共享網路通道的同時，盡可能的少出現網路擁塞現象，讓網路世界里的每一個參與者既公平又高效，
10. cwnd：發送視窗，擁塞視窗；在擁塞控制程序中視窗大小值變化，
11. rwnd：接收視窗，通知發送者能夠發送的資料大小，
12. sliding window：滑動視窗，只是一種抽象機制概念；在發送請求及收到ack的程序中滑動，

TCP擁塞控制演算法分類

1、基于丟包的擁塞控制：Tahoe、Reno、New Reno

因為Reno等演算法是后續演算法的基礎，這里詳細的描述下Reno演算法的程序，

（1）慢熱啟動演算法 – Slow Start

• 連接建好的開始先初始化cwnd = 1，表明可以傳一個MSS大小的資料，
• 每當收到一個ACK，cwnd++; 呈線性上升，
• 每當過了一個RTT，cwnd = cwnd*2; 呈指數讓升，
• 還有一個ssthresh（slow start threshold），是一個上限，當cwnd >= ssthresh時，就會進入“擁塞避免演算法”，

（2）擁塞避免演算法 – Congestion Avoidance

當cwnd >= ssthresh時，就會進入“擁塞避免演算法”，演算法如下：

• 收到一個ACK時，cwnd = cwnd + 1/cwnd
• 當每過一個RTT時，cwnd = cwnd + 1

（3）擁塞狀態演算法 – Fast Retransmit

Tahoe是等RTO超時，FR是在收到3個duplicate ACK時就開啟重傳，而不用等到RTO超時，擁塞發生時：

• cwnd = cwnd /2
• sshthresh = cwnd

（4）快速恢復 – Fast Recovery

• cwnd = sshthresh + 3 * MSS （3的意思是確認有3個資料包被收到了）
• 重傳Duplicated ACKs指定的資料包
• 如果再收到 duplicated Acks，那么cwnd = cwnd +1
• 如果收到了新的Ack，那么，cwnd = sshthresh ，然后進入擁塞避免演算法，

Reno演算法以其簡單、有效和魯棒性，應用最廣泛，該演算法所包含的慢啟動、擁塞避免和快速重傳、快速恢復機制，是現有的眾多演算法的基礎，

從Reno運行機制中很容易看出，為了維持一個動態平衡，必須周期性地產生一定量的丟失，再加上AIMD機制--減少快，增長慢，尤其是在大視窗環境下，由于一個資料報的丟失所帶來的視窗縮小要花費很長的時間來恢復，這樣，帶寬利用率不可能很高且隨著網路的鏈路帶寬不斷提升，這種弊端將越來越明顯，另外，丟包并不一定是網路擁塞，可能是網路常態，但是基于丟包的擁塞控制并不能區分，

2、基于時延RTT的帶寬預測：vegas

vegas通過對RTT的非常重的監控來計算一個基準RTT，然后通過這個基準RTT來估計當前的網路實際帶寬，如果實際帶寬比我們的期望的帶寬要小或是要多的活，那么就開始線性地減少或增加cwnd的大小，

中間路由器快取資料導致RTT變大，認為發生擁塞；RTT不公平性，當不同的資料流對網路瓶頸帶寬進行競爭時，具有較小RTT的TCP資料流的擁塞視窗增加速率將會快于具有大RTT的TCP資料流，從而將會占有更多的網路帶寬資源，

3、基于丟包和RTT：westwood

在發送端做帶寬估計，當探測到丟包時，根據帶寬值來設定擁塞視窗、慢啟動閾值， 那么，這個演算法是怎么測量帶寬的？每個RTT時間，會測量一次帶寬，測量帶寬的公式很簡單，就是這段RTT內成功被ACK了多少位元組，Westwood會根據RTT變化來判斷丟包是否是網路擁塞造成的，還是網路常態的丟包，如果時延變化不明顯，就認為是非網路擁塞，此時cwnd減少的比較小，

4、二分搜索最佳cwnd：BIC-TCP

BIC-TCP是Linux 2.6.18默認擁塞控制演算法，依賴丟包條件觸發，BIC-TCP認為TCP擁塞視窗調整的本質就是找到最適合當前網路的一個發送視窗，為了找到這個視窗值，TCP采取的方式是(擁塞避免階段)每RTT加1，緩慢上升，丟包時下降一半，接著再來慢慢上升，BIC-TCP的提出者們看穿了事情的本質，其實這就是一個搜索的程序，而TCP的搜索方式類似于逐個遍歷搜索方法，可以認為這個值是在1和一個比較大的數(large_window)之間，既然在這個區間內需要搜索一個最佳值，那么顯然最好的方式就是二分搜索思想，

BIC-TCP就是基于這樣一個二分思想的：當出現丟包的時候，說明最佳視窗值應該比這個值小，那么BIC就把此時的cwnd設定為max_win，把乘法減小后的值設定為min_win，然后BIC就開始在這兩者之間執行二分思想--每次跳到max_win和min_win的中點，

BIC-TCP 演算法仿真曲線

BIC也具備RTT的不公平性，RTT小的連接，視窗調整發生的速度越快，因此可能更快的搶占帶寬，

5、連續擁塞間隔：CUBIC

CUBIC在設計上簡化了BIC-TCP的視窗調整演算法，在BIC-TCP的視窗調整中會出現一個凹和凸(這里的凹和凸指的是數學意義上的凹和凸，凹函式/凸函式)的增長曲線，CUBIC使用了一個三次函式(即一個立方函式)，在三次函式曲線中同樣存在一個凹和凸的部分，該曲線形狀和BIC-TCP的曲線圖十分相似，于是該部分取代BIC-TCP的增長曲線，另外，CUBIC中最關鍵的點在于它的視窗增長函式僅僅取決于連續的兩次擁塞事件的時間間隔值，從而視窗增長完全獨立于網路的時延RTT，使得連接之間保持良好的RRTT公平性，

來看下具體細節：當某次擁塞事件發生時，Wmax設定為此時發生擁塞時的視窗值，然后把視窗進行乘法減小，乘法減小因子設為β，當從快速恢復階段退出然后進入到擁塞避免階段，此時CUBIC的視窗增長開始按照“凹”式增長曲線進行增長，該程序一直持續直到視窗再次增長到Wmax，緊接著，該函式轉入“凸”式增長階段，該方式的增長可以使得視窗一直維持在Wmax附近，從而可以達到網路帶寬的高利用率和協議本身的穩定性，

CUBIC視窗的增長函式：W(t) = C * (t-K)3 + Wmax, 其中C和β為常量，

t為當前時間距上一次視窗減小的時間差，而K就代表該函式從W增長到Wmax的時間周期，

CUBIC演算法仿真曲線（來源CUBIC RFC）

通俗一點講，假如我們知道了Wmax，那么CUBIC的核心思想就是需要在連續兩次擁塞期間執行完上面的三次函式增長曲線，

6、基于精準帶寬計算：BBR

BBR通過實時計算帶寬和最小RTT來決定發送速率pacing rate和視窗大小cwnd，完全摒棄丟包作為擁塞控制的直接反饋因素，

TCP擁塞控制概述

在不擁塞的前提下提高吞吐量

演變程序

Tahoe演算法

只有兩個狀態，慢啟動狀態slow start(SS)，擁塞避免狀態congestion avoidance(CA)

一開始的閾值ssthresh默認為64k位元組，

程序：

• 開始慢啟動程序從1mss開始指數增長，到擁塞的閾值ssthresh后進入擁塞避免狀態線性增長，
• 如果出現超時，擁塞的閥值ssthresh變成當前擁塞視窗cw的一半，同時超時重傳超時的段，重新慢啟動程序，強制擁塞視窗從1個mss開始指數增長，到擁塞的閥值ssthresh后進入擁塞避免狀態線性增長，
• 如果發生三個冗余ACK，擁塞的閾值ssthresh變成當前擁塞視窗cw的一半，同時快速重傳三個冗余ACK的段，重新慢啟動程序，強制擁塞視窗從1個mss開始指數增長，到擁塞的閥值ssthresh后進入擁塞避免狀態線性增長，

超時和發生三個冗余ACK的操作是基本一樣的，區別是超時的話就超時重傳超時的段，發生三個冗余ACK的話就快速重傳三個冗余ACK的段，

Tahoe演算法的問題就是在發生三個冗余ACK時，強制擁塞視窗變成1個mss，代價比較大，因為沒有發生超時，說明網路還有通訊能力；而發生三個冗余ACK，代表網路能正常接受丟失的mss的后三個，需要改進，在Tahoe演算法基礎上增加快速恢復的階段，就有了Reno演算法

Reno演算法

三個狀態，慢啟動狀態slow start(SS)，擁塞避免狀態congestion avoidance(CA)，快恢復狀態fast recovery(FR)

無論是在慢啟動狀態(SS)還是擁塞避免狀態(CA)，只要發生三個冗余ACK，快速重傳，cw減半（注意不是變成1了），閾值等于cw，進入快恢復狀態，在快恢復狀態下有三個情況：

• 繼續接到舊的冗余ACK，維持快恢復狀態，快速重傳，擁塞視窗cw加一，cw=cw+1MSS
• 接收到新的ACK，冗余ACK數=0，進入擁塞避免狀態(CA)線性增加而不是慢啟動階段，但是擁塞視窗cw等于閾值加三，cw=ssthresh+3，為什么是3，因為已經收到三個冗余ack，因此網路有能力，
• 超時，和Tahoe處理一樣，

Tahoe和Reno總結和區別

區別

New Reno演算法

Reno的存在的問題，適合單個段丟失的情況，但是經常性擁塞時，快速重傳完后可能會導致后續的段超時，從而進入ss階段，使得cw降到1，

New Reno演算法改進：

New Reno存在的問題：效率低，一個RTT間隙里面發來一個部分確認PACK，那就發送一個丟失的段，

SACK演算法

選擇性確認，給定一些標記， 一個RTT可以重傳丟失段

使用pipe和ScoreBoard，把什么時候發（pipe<cw）和發什么（先ScoreBoard，后新段）解耦

TCP是累計確認，沒有tcp option的話，tcp頭部長度為20B/4=5

SACK選擇確認，在tcp option標出亂序被接受的段

因此通過這個方法，接收方可以表述亂序段被接受的情況

發送方接到SACK后，在ScoreBoard計分板中存放需要重發的段的序列，在FR階段重傳（CW允許）

程序：

先重發計分板中丟失的段，再發新段

收到確認分為三種，是否為冗余ACK，是否在SACK選項中，是否為PACK新段得到確認，是否為RACK恢復ACK，組合成5種情況，

有兩種情況：

CUBIC演算法

遇到的問題：Reno在CA階段，線性加1過于保守，不利于吞吐量的提升，（擁塞控制的目的是在在不擁塞的前提下提高吞吐量）

快速定位計算出視窗的最大值

ECN演算法

Explicit Congestion Notifacation，網路輔助資訊擁塞控制

Tahoe和Reno都是靠事件來判斷是否擁塞，比如定時器超時，收到三個冗余ACK，

上述兩個演算法都是通過端自身來統計和計算資訊的，那么能否由網路反饋一些資訊，那就需要修改TCP/IP協議，

IP資料報中兩個標志位：

• CE，Congestion Experienced，擁塞經歷，給路由器使用，如果該路由器發生擁塞，經過該路由器的IP資料報CE位置1
• ECT，ECN Capable Transport，ECN使能，使用ECN特性時需要將ECT位置1

TCP段中兩個標志位：

• CWR，Cogestion Window Reduce，源主機發現網路發生擁塞，源主機將擁塞視窗cw減半或者降低，那么就要將這個標志位置一
• ECE，ECN-Echo，目標主機通過網路的反饋發現網路發生擁塞，目標主機將ECE置一，回傳給源主機

程序：

在網路中經過擁塞的路由器：

源主機得到ECE的反饋，降速

ECN存在的問題：

1. 兩個ECN使能的物體建立連接時，標志位不同，造成TCP三次握手時和其他物體不同
2. 安全性問題，有攻擊者在中間鏈路的路由器惡意修改ECN和CE位
3. 只解決了擁塞時降速問題，沒有解決不擁塞時增速問題

Vegas演算法（基于延遲的擁塞控制 ）

Reno類演算法的問題：

• 靠擁塞視窗的增加來探測，直到擁塞（SS狀態指數增加，CA狀態持續增加）
• 發生擁塞時，反復降低擁塞視窗，導致速率波動，造成帶寬利用率不高，因為這類演算法利用擁塞是一種探測可用帶寬的方式
• 段的連續丟失，造成視窗反復降低，懲罰很重
• 同時延遲比冗余ACK、超時來的更加敏感
• Reno演算法中的RTO，retransmit timeout，超時時間是基于500ms計時顆粒度計算的，先3個冗余ACK，后超時

事件發生順序：冗余ACK事件 ->細顆粒度的超時事件 ->3個冗余ACK事件 ->細顆粒度的超時事件

程序：

BaseRTT是最小的RTT

Reno演算法在慢啟動狀態下是一個RTT倍增cw，vegas是兩個RTT倍增cw，溫和一些

重傳的時機

vegas存在的問題，導致互聯網使用的不多：

• 路徑變化帶來的RTT變化，誤認為是擁塞，作出誤操作
• 如果網路中全部都是用vegas演算法，那么整個網路會慢慢趨于平緩，但是與其他CUBIC、Reno演算法協同作業時出現不公平性，vegas太敏感和太溫和，主要用于可控的固定的場景，如機房間

BBR演算法

BtlBW(Bottleneck link) and RTT based Congestion Control

• Reno、CUBIC等演算法，基于丟失的擁塞控制：吞吐震蕩，延遲大，侵略性強
  • 有線低帶寬時，丟失=擁塞，但是無線高帶寬時，丟失=50%擁塞+50%出錯，出現帶寬震蕩
  • 之前的網路交換節點buffer不大，現在的buffer大容量，造成延遲大，
• BBR，基于模型的擁塞控制，不是基于丟失也不是基于延遲

模型概述：

• 兩個階段：應用受限階段和帶寬受限階段
• 測量瓶頸鏈路帶寬BtlBW和往返時延RTT，計算出BDP，反映網路路由和通信量的變化
• 按照瓶頸鏈路帶寬BtlBW控制主機的注入速率，按照BDP控制inflight數量

模型會出現的三種狀態

應用受限： 應用本身沒有太多資料，pipe沒充滿

帶寬受限：pipe充滿，瓶頸鏈路占滿，有資料段在排隊，但是buffer能承受這個隊伍長度，出現擁塞，

緩沖受限：pipe充滿，buffer充滿，出現丟包，

最核心問題：瓶頸鏈路帶寬BtlBW和往返時延RTT不可同時測量，測量RTT時pipe需要處于輕載狀態，但是測量BtlBW時pipe需要處于充滿狀態，

BtlBW，瓶頸鏈路帶寬，RTT，往返時延，BDP

資料參考：

1. 《TCP/IP詳解》卷1
2. 中科大-鄭烇教授，視頻和教材
3. 騰訊云社區文章，TCP擁塞控制及BBR原理分析 - 云+社區 - 騰訊云