TCP擁塞控制算法的目的可以簡單概括為：公平競(jìng)爭、充分利用網(wǎng)絡(luò)帶寬集币、降低網(wǎng)絡(luò)延時(shí)、優(yōu)化用戶體驗(yàn)翠忠，然而就目前而言要實(shí)現(xiàn)這些目標(biāo)就難免有權(quán)衡和取舍鞠苟。

算法分類

基于丟包策略的傳統(tǒng)擁塞控制算法的幾個(gè)迭代版本，如圖所示：

基于丟包

與此同時(shí)還有一類算法是基于RTT延時(shí)策略來進(jìn)行控制的，但是這類算法在發(fā)包速率上可能不夠激進(jìn)当娱，競(jìng)爭性能不如其他算法吃既，因此在共享網(wǎng)絡(luò)帶寬時(shí)有失公平性，但是算法速率曲線卻是很平滑

基于RTT延時(shí)

基于鏈路容量的擁塞控制：實(shí)時(shí)測(cè)量網(wǎng)絡(luò)帶寬和時(shí)延跨细，認(rèn)為網(wǎng)絡(luò)上報(bào)文總量大于帶寬時(shí)延乘積時(shí)出現(xiàn)了擁塞鹦倚，如 BBR。

基于學(xué)習(xí)的擁塞控制：沒有特定的擁塞信號(hào)冀惭，而是借助評(píng)價(jià)函數(shù)震叙，基于訓(xùn)練數(shù)據(jù)，使用機(jī)器學(xué)習(xí)的方法形成一個(gè)控制策略云头，如 Remy捐友。

如何感知擁塞

基于各種擁塞策略的擁塞控制算法有不一樣的擁塞判斷標(biāo)準(zhǔn)：

1. 基于丟包

   丟包可以由重傳超時(shí)RTO和重復(fù)確認(rèn)來做判斷淫半。

   丟包判斷

2. 基于時(shí)延

3. 基于鏈路容量

4. 基于機(jī)器學(xué)習(xí)

   根據(jù)參數(shù)得出一個(gè)擁塞窗口值

擁塞控制基本策略

擁塞控制是一個(gè)動(dòng)態(tài)的過程溃槐，它既要提高帶寬利用率發(fā)送盡量多的數(shù)據(jù)又要避免網(wǎng)絡(luò)擁堵丟包RTT增大等問題，基于這種高要求并不是單一策略可以搞定的科吭，因此TCP的 擁塞控制策略實(shí)際上是分階段分策略的綜合過程：

擁塞控制的基本步驟

基于丟包的擁塞控制

Tahoe算法

如果收到三次重復(fù)確認(rèn)即第四次收到相同確認(rèn)號(hào)的分段確認(rèn)昏滴，并且分段對(duì)應(yīng)包無負(fù)載分段和無改變接收窗口的話，Tahoe算法則進(jìn)入快速重傳对人，將慢啟動(dòng)閾值改為當(dāng)前擁塞窗口的一半谣殊，將擁塞窗口降為1個(gè)MSS，并重新進(jìn)入慢啟動(dòng)階段牺弄。

擁塞控制過程大致如下：

Tahoe擁塞控制

Reno算法(我們當(dāng)前理解的算法)

如果收到三次重復(fù)確認(rèn)姻几，Reno算法則進(jìn)入快速重傳只將擁塞窗口減半來跳過慢啟動(dòng)階段，將慢啟動(dòng)閾值設(shè)為當(dāng)前新的擁塞窗口值势告，進(jìn)入一個(gè)稱為快速恢復(fù)的新設(shè)計(jì)階段蛇捌。

擁塞控制流程如下：

Reno 擁塞控制過程

Reno 算法將收到 ACK 這一信號(hào)作為擁塞窗口增長的依據(jù)，在早期低帶寬咱台、低時(shí)延的網(wǎng)絡(luò)中能夠很好的發(fā)揮作用络拌，但是隨著網(wǎng)絡(luò)帶寬和延時(shí)的增加，Reno 的缺點(diǎn)就漸漸體現(xiàn)出來了回溺，發(fā)送端從發(fā)送報(bào)文到收到 ACK 經(jīng)歷一個(gè) RTT春贸，在高帶寬延時(shí)（High Bandwidth-Delay Product，BDP）網(wǎng)絡(luò)中遗遵，RTT 很大萍恕，導(dǎo)致?lián)砣翱谠鲩L很慢，傳輸速度需要經(jīng)過很長時(shí)間才能達(dá)到最大帶寬车要，導(dǎo)致帶寬利用率將低雄坪。

適用場(chǎng)景：

適用于低延時(shí)、低帶寬的網(wǎng)絡(luò)。

TCP New Reno是對(duì)TCP Reno中快速恢復(fù)階段的重傳進(jìn)行改善的一種改進(jìn)算法维哈，New Reno在低錯(cuò)誤率時(shí)運(yùn)行效率和選擇確認(rèn)SACK相當(dāng)绳姨，在高錯(cuò)誤率仍優(yōu)于Reno。

CUBIC算法

Cubic是 Linux 內(nèi)核 2.6 之后的默認(rèn) TCP 擁塞控制算法阔挠， 使用一個(gè)立方函數(shù)（cubic function）:

作為擁塞窗口的增長函數(shù)飘庄，其中，C 是調(diào)節(jié)因子购撼，t 是從上一次縮小擁塞窗口經(jīng)過的時(shí)間跪削，是上一次發(fā)生擁塞時(shí)的窗口大小，

β是乘法減小因子迂求。從函數(shù)中可以看出擁塞窗口的增長不再與 RTT 有關(guān)碾盐，而僅僅取決上次發(fā)生擁塞時(shí)的最大窗口和距離上次發(fā)生擁塞的時(shí)間間隔值。

Cubic 擁塞窗口增長曲線如下揩局，凸曲線部分為穩(wěn)定增長階段毫玖，凹曲線部分為最大帶寬探測(cè)階段。如圖下圖 所示凌盯，在剛開始時(shí)付枫，擁塞窗口增長很快，在接近 口時(shí)驰怎，增長速度變的平緩阐滩，避免流量突增而導(dǎo)致丟包；在 附近县忌，擁塞窗口不再增加掂榔；之后開始緩慢地探測(cè)網(wǎng)絡(luò)最大吞吐量，保證穩(wěn)定性（在 附近容易出現(xiàn)擁塞）症杏，在遠(yuǎn)離 后装获，增大窗口增長的速度，保證了帶寬的利用率鸳慈。

Cubic擁塞控制曲線

當(dāng)出現(xiàn)丟包時(shí)饱溢，將擁塞窗口進(jìn)行乘法減小(擁塞窗口減小到當(dāng)前的一半)，再繼續(xù)開始上述增長過程走芋。此方式可以使得擁塞窗口一直維持在 附近绩郎，從而保證了帶寬的利用率。Cubic 的擁塞控制過程：

Cubic 的擁塞控制

Cubic 算法的優(yōu)點(diǎn)在于只要沒有出現(xiàn)丟包翁逞，就不會(huì)主動(dòng)降低自己的發(fā)送速度肋杖，可以最大程度的利用網(wǎng)絡(luò)剩余帶寬，提高吞吐量挖函，在高帶寬状植、低丟包率的網(wǎng)絡(luò)中可以發(fā)揮較好的性能。

但是，Cubic 同之前的擁塞控制算法一樣津畸，無法區(qū)分擁塞丟包和傳輸錯(cuò)誤丟包振定，只要發(fā)現(xiàn)丟包，就會(huì)減小擁塞窗口肉拓，降低發(fā)送速率后频，而事實(shí)上傳輸錯(cuò)誤丟包時(shí)網(wǎng)絡(luò)不一定發(fā)生了擁塞，但是傳輸錯(cuò)誤丟包的概率很低暖途，所以對(duì) Cubic 算法的性能影響不是很大卑惜。

Cubic 算法的另一個(gè)不足之處是過于激進(jìn)，在沒有出現(xiàn)丟包時(shí)會(huì)不停地增加擁塞窗口的大小驻售，向網(wǎng)絡(luò)注入流量露久，將網(wǎng)絡(luò)設(shè)備的緩沖區(qū)填滿，出現(xiàn) Bufferbloat（緩沖區(qū)膨脹）欺栗。由于緩沖區(qū)長期趨于飽和狀態(tài)毫痕，新進(jìn)入網(wǎng)絡(luò)的的數(shù)據(jù)包會(huì)在緩沖區(qū)里排隊(duì)，增加無謂的排隊(duì)時(shí)延纸巷，緩沖區(qū)越大镇草，時(shí)延就越高眶痰。另外 Cubic 算法在高帶寬利用率的同時(shí)依然在增加擁塞窗口瘤旨，間接增加了丟包率，造成網(wǎng)絡(luò)抖動(dòng)加劇竖伯。

適用場(chǎng)景：

適用于高帶寬存哲、低丟包率網(wǎng)絡(luò)，能夠有效利用帶寬七婴。

基于鏈路容量的算法

BRR算法

BBR[4] 是谷歌在 2016 年提出的一種新的擁塞控制算法祟偷，已經(jīng)在 Youtube 服務(wù)器和谷歌跨數(shù)據(jù)中心廣域網(wǎng)上部署，據(jù) Youtube 官方數(shù)據(jù)稱打厘，部署 BBR 后修肠，在全球范圍內(nèi)訪問 Youtube 的延遲降低了 53%，在時(shí)延較高的發(fā)展中國家户盯，延遲降低了 80%嵌施。目前 BBR 已經(jīng)集成到 Linux 4.9 以上版本的內(nèi)核中。

BBR 算法不將出現(xiàn)丟包或時(shí)延增加作為擁塞的信號(hào)莽鸭，而是認(rèn)為當(dāng)網(wǎng)絡(luò)上的數(shù)據(jù)包總量大于瓶頸鏈路帶寬和時(shí)延的乘積時(shí)才出現(xiàn)了擁塞吗伤。

BBR 算法周期性地探測(cè)網(wǎng)絡(luò)的容量，交替測(cè)量一段時(shí)間內(nèi)的帶寬極大值和時(shí)延極小值硫眨，將其乘積作為作為擁塞窗口大凶阆（交替測(cè)量的原因是極大帶寬和極小時(shí)延不可能同時(shí)得到，帶寬極大時(shí)網(wǎng)絡(luò)被填滿造成排隊(duì)，時(shí)延必然極大巧号，時(shí)延極小時(shí)需要數(shù)據(jù)包不被排隊(duì)直接轉(zhuǎn)發(fā)族奢，帶寬必然極小）丹鸿，使得擁塞窗口始的值始終與網(wǎng)絡(luò)的容量保持一致歹鱼。

什么叫做BDP呢？它叫做帶寬時(shí)延積卜高，例如一條鏈路的帶寬是100Mbps弥姻，而RTT是40ms，那么

BDP=100Mbps*0.04s=4Mb=0.5MB

即平均每秒飛行中的報(bào)文應(yīng)當(dāng)是0.5MB掺涛。因此Linux的接收窗口緩存常參考此設(shè)置：

BDP

事實(shí)上庭敦，我們的傳輸速度在3個(gè)階段被不同的因素限制：

1. 應(yīng)用程序限制階段，此時(shí)RTT不變薪缆，隨著應(yīng)用程序開始發(fā)送大文件秧廉，速率直線上升；
2. BDP限制階段拣帽，此時(shí)RTT開始不斷上升疼电，但吞吐量不變，因?yàn)榇藭r(shí)瓶頸路由器已經(jīng)達(dá)到上限减拭，緩沖隊(duì)列正在不斷增加蔽豺；
3. 瓶頸路由器緩沖隊(duì)列限制階段，此時(shí)開始大量丟包拧粪。

如下所示：

image

如CUBIC這樣基于丟包的擁塞控制算法在第2條灰色豎線發(fā)生作用修陡，這已經(jīng)太晚了，更好的作用點(diǎn)是BDP上限開始發(fā)揮作用時(shí)可霎，也就是第1條灰色豎線魄鸦。

而BBR通過檢測(cè)RTprop和_BtlBw來實(shí)現(xiàn)擁塞控制。什么是RTprop呢癣朗？這是鏈路的物理時(shí)延拾因，因?yàn)镽TT里含有報(bào)文在路由器隊(duì)列里的排隊(duì)時(shí)間、ACK的延遲確認(rèn)時(shí)間等旷余。什么叫延遲確認(rèn)呢绢记？TCP每個(gè)報(bào)文必須被確認(rèn)，確認(rèn)動(dòng)作是通過接收端發(fā)送ACK報(bào)文實(shí)現(xiàn)的荣暮，但由于TCP和IP頭部有40個(gè)字節(jié)庭惜，如果不攜帶數(shù)據(jù)只為發(fā)送ACK網(wǎng)絡(luò)效率過低，所以會(huì)讓獨(dú)立的ACK報(bào)文等一等穗酥，看看有沒有數(shù)據(jù)發(fā)的時(shí)候順便帶給對(duì)方护赊，或者等等看多個(gè)ACK一起發(fā)惠遏。所以，可以用下列公式表示RTT與RTprop的差別：

RTT我們可以測(cè)量得出骏啰，RTprop呢节吮，我們只需要找到瓶頸路由器隊(duì)列為空時(shí)多次RTT測(cè)量的最小值即可

而BtlBw全稱是bottleneck bandwith，即瓶頸帶寬判耕，我們可以通過測(cè)量已發(fā)送但未ACK確認(rèn)的飛行中字節(jié)除以飛行時(shí)間deliveryRate來測(cè)量

早在1979年Leonard Kleinrock就提出了第1條豎線是最好的擁塞控制點(diǎn)透绩，但被Jeffrey M. Jaffe證明不可能實(shí)現(xiàn)，因?yàn)闆]有辦法判斷RTT變化到底是不是因?yàn)殒溌纷兓吮谙ǎ瑥亩煌脑O(shè)備瓶頸導(dǎo)致的帚豪，還是瓶頸路由器上的其他TCP連接的流量發(fā)生了大的變化。但我們有了RTprop和BtlBw后草丧，當(dāng)RTprop升高時(shí)我們便得到了BtlBw狸臣，這便找到第1條灰色豎線最好的擁塞控制點(diǎn)，也有了后續(xù)發(fā)送速率的依據(jù)昌执。

由于 BBR 的擁塞窗口是精確測(cè)量出來的烛亦，不會(huì)無限的增加擁塞窗口，也就不會(huì)將網(wǎng)絡(luò)設(shè)備的緩沖區(qū)填滿懂拾，避免了出現(xiàn) Bufferbloat (緩沖區(qū)膨脹)問題煤禽，使得時(shí)延大大降低。

如下圖所示岖赋，網(wǎng)絡(luò)緩沖區(qū)被填滿時(shí)時(shí)延為 250ms檬果，Cubic 算法會(huì)繼續(xù)增加擁塞窗口，使得時(shí)延持續(xù)增加到 500ms 并出現(xiàn)丟包贾节，整個(gè)過程 Cubic 一直處于高時(shí)延狀態(tài)汁汗，而 BBR 由于不會(huì)填滿網(wǎng)絡(luò)緩沖區(qū)衷畦，時(shí)延一直處于較低狀態(tài)栗涂。

比較BBR算法與Cubic算法的時(shí)延

由于 BBR 算法不將丟包作為擁塞信號(hào)，所以在丟包率較高的網(wǎng)絡(luò)中祈争，BBR 依然有極高的吞吐量斤程，如圖 5下圖所示，在 1% 丟包率的網(wǎng)絡(luò)環(huán)境下菩混，Cubic 的吞吐量已經(jīng)降低 90% 以上忿墅，而 BBR 的吞吐量幾乎沒有受到影響，當(dāng)丟包率大于 15% 時(shí)沮峡，BBR 的吞吐量才大幅下降疚脐。

比較BBR算法與Cubic算法的吞吐量

BBR 算法是反饋驅(qū)動(dòng)的，有自主調(diào)節(jié)機(jī)制邢疙，不受 TCP 擁塞控制狀態(tài)機(jī)的控制棍弄，通過測(cè)量網(wǎng)絡(luò)容量來調(diào)整擁塞窗口望薄，發(fā)送速率由自己掌控，而傳統(tǒng)的擁塞控制算法只負(fù)責(zé)計(jì)算擁塞窗口呼畸，而不管發(fā)送速率（pacing rate）痕支，怎么發(fā)由 TCP 自己決定，這樣會(huì)在瓶頸帶寬附近因發(fā)送速率的激增導(dǎo)致數(shù)據(jù)包排隊(duì)或出現(xiàn)丟包蛮原。

經(jīng)過測(cè)試卧须，在高延時(shí)、高丟包率的環(huán)境下儒陨，BBR 相對(duì)于 Cubic 算法在傳輸速度上有較大的提升花嘶，具體的測(cè)試結(jié)果如下表所示：

200ms 延時(shí)下 Cubic 與 BBR 傳輸速度對(duì)比

BBR 算法的不足之處在于設(shè)備隊(duì)列緩存較大時(shí)，BBR 可能會(huì)競(jìng)爭不過 Cubic 等比較激進(jìn)算法蹦漠，原因是 BBR 不主動(dòng)去占據(jù)隊(duì)列緩存察绷，如果 Cubic 的流量長期占據(jù)隊(duì)列緩存，會(huì)使得 BBR 在多個(gè)周期內(nèi)測(cè)量的極小 RTT 增大津辩，進(jìn)而使 BBR 的帶寬減小拆撼。

適用場(chǎng)景：

適用于高帶寬、高時(shí)延喘沿、有一定丟包率的長肥網(wǎng)絡(luò)闸度，可以有效降低傳輸時(shí)延，并保證較高的吞吐量蚜印。

基于學(xué)習(xí)的算法

Remy

Remy 也稱為計(jì)算機(jī)生成的擁塞控制算法（computer-generated congestion-control algorithm）莺禁，采用機(jī)器學(xué)習(xí)的方式生成擁塞控制算法模型。

略了吧......??

基于時(shí)延的算法

Vegas算法

Vegas將時(shí)延 RTT 的增加作為網(wǎng)絡(luò)出現(xiàn)擁塞的信號(hào)窄赋，RTT 增加哟冬，擁塞窗口減小，RTT 減小忆绰，擁塞窗口增加浩峡。具體來說，Vegas 通過比較實(shí)際吞吐量和期望吞吐量來調(diào)節(jié)擁塞窗口的大小.

期望吞吐量為：

實(shí)際吞吐量為：

定義一個(gè)它們之間的差距diff:

BaseRTT 是所有觀測(cè)來回響應(yīng)時(shí)間的最小值错敢，一般是建立連接后所發(fā)的第一個(gè)數(shù)據(jù)包的 RTT翰灾，cwnd 是目前的擁塞窗口的大小。Vegas 定義了兩個(gè)閾值 a稚茅，b纸淮，當(dāng) diff > b 時(shí)，擁塞窗口減小亚享，當(dāng) a <= diff <=b 時(shí)咽块，擁塞窗口不變，當(dāng) diff < a 時(shí)欺税，擁塞窗口增加侈沪。

Vegas 算法采用 RTT 的改變來判斷網(wǎng)絡(luò)的可用帶寬飒货，能精確地測(cè)量網(wǎng)絡(luò)的可用帶寬，效率比較好峭竣。但是塘辅，網(wǎng)絡(luò)中 Vegas 與其它算法共存的情況下，基于丟包的擁塞控制算法會(huì)嘗試填滿網(wǎng)絡(luò)中的緩沖區(qū)皆撩，導(dǎo)致 Vegas 計(jì)算的 RTT 增大扣墩，進(jìn)而降低擁塞窗口，使得傳輸速度越來越慢扛吞，因此 Vegas 未能在 Internet 上普遍采用呻惕。

適用場(chǎng)景：

適用于網(wǎng)絡(luò)中只存在 Vegas 一種擁塞控制算法，競(jìng)爭公平的情況滥比。

歡迎dajia訂閱我的博客??:hugo.jiahongw.com

參考：

1. 萬字長文|全網(wǎng)最強(qiáng) TCP/IP 擁塞控制總結(jié)...
2. 萬字詳文：TCP 擁塞控制詳解
3. 淺談 TCP 擁塞控制算法
4. 一文解釋清楚google-bbr擁塞控制算法原理