這篇文章是下篇庸汗，所以如果你對(duì)TCP不熟悉的話，還請(qǐng)你先看看上篇《TCP協(xié)議的定義和丟包時(shí)的重傳機(jī)制》 上篇中手报，我們介紹了TCP的協(xié)議頭夫晌、狀態(tài)機(jī)、數(shù)據(jù)重傳中的東西昧诱。但是TCP要解決一個(gè)很大的事晓淀，那就是要在一個(gè)網(wǎng)絡(luò)根據(jù)不同的情況來(lái)動(dòng)態(tài)調(diào)整自己的發(fā)包的速度，小則讓自己的連接更穩(wěn)定盏档，大則讓整個(gè)網(wǎng)絡(luò)更穩(wěn)定凶掰。在你閱讀下篇之前，你需要做好準(zhǔn)備蜈亩，本篇文章有好些算法和策略懦窘，可能會(huì)引發(fā)你的各種思考，讓你的大腦分配很多內(nèi)存和計(jì)算資源稚配，所以畅涂，不適合在廁所中閱讀。
TCP的RTT算法
從前面的TCP重傳機(jī)制我們知道Timeout的設(shè)置對(duì)于重傳非常重要午衰。
- 設(shè)長(zhǎng)了，重發(fā)就慢冒萄，丟了老半天才重發(fā)臊岸，沒有效率，性能差尊流；
- 設(shè)短了帅戒，會(huì)導(dǎo)致可能并沒有丟就重發(fā)。于是重發(fā)的就快崖技，會(huì)增加網(wǎng)絡(luò)擁塞逻住，導(dǎo)致更多的超時(shí)，更多的超時(shí)導(dǎo)致更多的重發(fā)迎献。
而且瞎访，這個(gè)超時(shí)時(shí)間在不同的網(wǎng)絡(luò)的情況下，根本沒有辦法設(shè)置一個(gè)死的值忿晕。只能動(dòng)態(tài)地設(shè)置装诡。 為了動(dòng)態(tài)地設(shè)置，TCP引入了RTT——Round Trip Time践盼，也就是一個(gè)數(shù)據(jù)包從發(fā)出去到回來(lái)的時(shí)間鸦采。這樣發(fā)送端就大約知道需要多少的時(shí)間，從而可以方便地設(shè)置Timeout——RTO（Retransmission TimeOut）咕幻，以讓我們的重傳機(jī)制更高效渔伯。 聽起來(lái)似乎很簡(jiǎn)單，好像就是在發(fā)送端發(fā)包時(shí)記下t0肄程，然后接收端再把這個(gè)ack回來(lái)時(shí)再記一個(gè)t1锣吼，于是RTT = t1 – t0。沒那么簡(jiǎn)單蓝厌，這只是一個(gè)采樣玄叠，不能代表普遍情況。
經(jīng)典算法
RFC793 中定義的經(jīng)典算法是這樣的：
1）首先拓提，先采樣RTT读恃，記下最近好幾次的RTT值。
2）然后做平滑計(jì)算SRTT（ Smoothed RTT）代态。公式為：（其中的 α 取值在0.8 到 0.9之間寺惫，這個(gè)算法英文叫Exponential weighted moving average，中文叫：加權(quán)移動(dòng)平均）
SRTT = ( α * SRTT ) + ((1- α) * RTT)
3）開始計(jì)算RTO蹦疑。公式如下：
RTO = min [ UBOUND, max [ LBOUND, (β * SRTT) ] ]
其中：
- UBOUND是最大的timeout時(shí)間西雀，上限值
- LBOUND是最小的timeout時(shí)間，下限值
- β 值一般在1.3到2.0之間歉摧。
Karn / Partridge 算法
但是上面的這個(gè)算法在重傳的時(shí)候會(huì)出有一個(gè)終極問題——你是用第一次發(fā)數(shù)據(jù)的時(shí)間和ack回來(lái)的時(shí)間做RTT樣本值艇肴，還是用重傳的時(shí)間和ACK回來(lái)的時(shí)間做RTT樣本值？
這個(gè)問題無(wú)論你選那頭都是按下葫蘆起了瓢叁温。 如下圖所示：
- 情況（a）是ack沒回來(lái)豆挽，所以重傳。如果你計(jì)算第一次發(fā)送和ACK的時(shí)間券盅，那么帮哈，明顯算大了。
- 情況（b）是ack回來(lái)慢了锰镀，但是導(dǎo)致了重傳娘侍，但剛重傳不一會(huì)兒，之前ACK就回來(lái)了泳炉。如果你是算重傳的時(shí)間和ACK回來(lái)的時(shí)間的差憾筏，就會(huì)算短了。
所以1987年的時(shí)候花鹅，搞了一個(gè)叫Karn / Partridge Algorithm氧腰，這個(gè)算法的最大特點(diǎn)是——忽略重傳，不把重傳的RTT做采樣（你看，你不需要去解決不存在的問題）古拴。
但是箩帚，這樣一來(lái)，又會(huì)引發(fā)一個(gè)大BUG——如果在某一時(shí)間黄痪，網(wǎng)絡(luò)閃動(dòng)紧帕，突然變慢了，產(chǎn)生了比較大的延時(shí)桅打，這個(gè)延時(shí)導(dǎo)致要重轉(zhuǎn)所有的包（因?yàn)橹暗腞TO很惺鞘取），于是挺尾，因?yàn)橹剞D(zhuǎn)的不算鹅搪，所以，RTO就不會(huì)被更新遭铺，這是一個(gè)災(zāi)難涩嚣。 于是Karn算法用了一個(gè)取巧的方式——只要一發(fā)生重傳，就對(duì)現(xiàn)有的RTO值翻倍（這就是所謂的 Exponential backoff）掂僵，很明顯航厚，這種死規(guī)矩對(duì)于一個(gè)需要估計(jì)比較準(zhǔn)確的RTT也不靠譜。
Jacobson / Karels 算法
前面兩種算法用的都是“加權(quán)移動(dòng)平均”锰蓬，這種方法最大的毛病就是如果RTT有一個(gè)大的波動(dòng)的話幔睬，很難被發(fā)現(xiàn)，因?yàn)楸黄交袅饲叟ぁＫ裕?988年麻顶，又有人推出來(lái)了一個(gè)新的算法，這個(gè)算法叫Jacobson / Karels Algorithm（參看RFC6289）舱卡。這個(gè)算法引入了最新的RTT的采樣和平滑過的SRTT的差距做因子來(lái)計(jì)算辅肾。 公式如下：（其中的DevRTT是Deviation RTT的意思）
SRTT**** = S****RTT**** + α****(****RTT**** – S****RTT****) —— 計(jì)算平滑RTT
DevRTT**** = (1-β****)*****DevRTT**** + β*****(|****RTT-SRTT****|)——計(jì)算平滑RTT和真實(shí)的差距（加權(quán)移動(dòng)平均）
RTO= μ * SRTT + ? *DevRTT—— 神一樣的公式
（其中：在Linux下，α = 0.125轮锥，β = 0.25矫钓， μ = 1，? = 4 ——這就是算法中的“調(diào)得一手好參數(shù)”舍杜，nobody knows why, it just works…） 最后的這個(gè)算法在被用在今天的TCP協(xié)議中（Linux的源代碼在：tcp_rtt_estimator）新娜。
TCP滑動(dòng)窗口
需要說(shuō)明一下，如果你不了解TCP的滑動(dòng)窗口這個(gè)事既绩，你等于不了解TCP協(xié)議概龄。我們都知道，TCP必需要解決的可靠傳輸以及包亂序（reordering）的問題饲握，所以私杜，TCP必需要知道網(wǎng)絡(luò)實(shí)際的數(shù)據(jù)處理帶寬或是數(shù)據(jù)處理速度蚕键，這樣才不會(huì)引起網(wǎng)絡(luò)擁塞，導(dǎo)致丟包衰粹。
所以锣光，TCP引入了一些技術(shù)和設(shè)計(jì)來(lái)做網(wǎng)絡(luò)流控，Sliding Window是其中一個(gè)技術(shù)寄猩。 前面我們說(shuō)過，TCP頭里有一個(gè)字段叫Window骑疆，又叫Advertised-Window田篇，這個(gè)字段是接收端告訴發(fā)送端自己還有多少緩沖區(qū)可以接收數(shù)據(jù)。于是發(fā)送端就可以根據(jù)這個(gè)接收端的處理能力來(lái)發(fā)送數(shù)據(jù)箍铭，而不會(huì)導(dǎo)致接收端處理不過來(lái)泊柬。 為了說(shuō)明滑動(dòng)窗口，我們需要先看一下TCP緩沖區(qū)的一些數(shù)據(jù)結(jié)構(gòu)：
上圖中诈火，我們可以看到：
接收端LastByteRead指向了TCP緩沖區(qū)中讀到的位置兽赁，NextByteExpected指向的地方是收到的連續(xù)包的最后一個(gè)位置，LastByteRcved指向的是收到的包的最后一個(gè)位置冷守，我們可以看到中間有些數(shù)據(jù)還沒有到達(dá)刀崖，所以有數(shù)據(jù)空白區(qū)。
發(fā)送端的LastByteAcked指向了被接收端Ack過的位置（表示成功發(fā)送確認(rèn)）拍摇，LastByteSent表示發(fā)出去了亮钦，但還沒有收到成功確認(rèn)的Ack，LastByteWritten指向的是上層應(yīng)用正在寫的地方充活。
于是：
接收端在給發(fā)送端回ACK中會(huì)匯報(bào)自己的AdvertisedWindow = MaxRcvBuffer – LastByteRcvd – 1;
而發(fā)送方會(huì)根據(jù)這個(gè)窗口來(lái)控制發(fā)送數(shù)據(jù)的大小蜂莉，以保證接收方可以處理抄腔。
下面我們來(lái)看一下發(fā)送方的滑動(dòng)窗口示意圖：
上圖中分成了四個(gè)部分萄焦，分別是：（其中那個(gè)黑模型就是滑動(dòng)窗口）
- 1：已收到ack確認(rèn)的數(shù)據(jù)眶掌。
- 2：發(fā)還沒收到ack的糙箍。
- 3：在窗口中還沒有發(fā)出的（接收方還有空間）筏勒。
- 4：窗口以外的數(shù)據(jù)（接收方?jīng)]空間）
下面是個(gè)滑動(dòng)后的示意圖（收到36的ack茅逮，并發(fā)出了46-51的字節(jié)）：
下面我們來(lái)看一個(gè)接受端控制發(fā)送端的圖示：
Zero Window
上圖憔购，我們可以看到一個(gè)處理緩慢的Server（接收端）是怎么把Client（發(fā)送端）的TCP Sliding Window給降成0的焦匈。此時(shí)赘淮，你一定會(huì)問枢赔，如果Window變成0了，TCP會(huì)怎么樣拥知？是不是發(fā)送端就不發(fā)數(shù)據(jù)了踏拜？是的，發(fā)送端就不發(fā)數(shù)據(jù)了低剔，你可以想像成“Window Closed”速梗，那你一定還會(huì)問肮塞，如果發(fā)送端不發(fā)數(shù)據(jù)了，接收方一會(huì)兒Window size 可用了姻锁，怎么通知發(fā)送端呢枕赵？
解決這個(gè)問題，TCP使用了Zero Window Probe技術(shù)位隶，縮寫為ZWP拷窜，也就是說(shuō)，發(fā)送端在窗口變成0后涧黄，會(huì)發(fā)ZWP的包給接收方篮昧，讓接收方來(lái)ack他的Window尺寸，一般這個(gè)值會(huì)設(shè)置成3次笋妥，第次大約30-60秒（不同的實(shí)現(xiàn)可能會(huì)不一樣）懊昨。如果3次過后還是0的話，有的TCP實(shí)現(xiàn)就會(huì)發(fā)RST把鏈接斷了春宣。
注意：只要有等待的地方都可能出現(xiàn)DDoS攻擊酵颁，Zero Window也不例外，一些攻擊者會(huì)在和HTTP建好鏈發(fā)完GET請(qǐng)求后月帝，就把Window設(shè)置為0躏惋，然后服務(wù)端就只能等待進(jìn)行ZWP，于是攻擊者會(huì)并發(fā)大量的這樣的請(qǐng)求嚷辅，把服務(wù)器端的資源耗盡其掂。（關(guān)于這方面的攻擊，大家可以移步看一下Wikipedia的SockStress詞條）
另外潦蝇，Wireshark中款熬，你可以使用tcp.analysis.zero_window來(lái)過濾包，然后使用右鍵菜單里的follow TCP stream攘乒，你可以看到ZeroWindowProbe及ZeroWindowProbeAck的包贤牛。
Silly Window Syndrome
Silly Window Syndrome翻譯成中文就是“糊涂窗口綜合癥”。正如你上面看到的一樣则酝，如果我們的接收方太忙了殉簸，來(lái)不及取走Receive Windows里的數(shù)據(jù)，那么沽讹，就會(huì)導(dǎo)致發(fā)送方越來(lái)越小般卑。到最后，如果接收方騰出幾個(gè)字節(jié)并告訴發(fā)送方現(xiàn)在有幾個(gè)字節(jié)的window爽雄，而我們的發(fā)送方會(huì)義無(wú)反顧地發(fā)送這幾個(gè)字節(jié)蝠检。
要知道，我們的TCP+IP頭有40個(gè)字節(jié)挚瘟，為了幾個(gè)字節(jié)叹谁，要達(dá)上這么大的開銷饲梭，這太不經(jīng)濟(jì)了。
另外焰檩，你需要知道網(wǎng)絡(luò)上有個(gè)MTU憔涉，對(duì)于以太網(wǎng)來(lái)說(shuō)，MTU是1500字節(jié)析苫，除去TCP+IP頭的40個(gè)字節(jié)兜叨，真正的數(shù)據(jù)傳輸可以有1460，這就是所謂的MSS（Max Segment Size）注意衩侥，TCP的RFC定義這個(gè)MSS的默認(rèn)值是536国旷，這是因?yàn)?RFC 791里說(shuō)了任何一個(gè)IP設(shè)備都得最少接收576尺寸的大小（實(shí)際上來(lái)說(shuō)576是撥號(hào)的網(wǎng)絡(luò)的MTU顿乒，而576減去IP頭的20個(gè)字節(jié)就是536）议街。
如果你的網(wǎng)絡(luò)包可以塞滿MTU泽谨，那么你可以用滿整個(gè)帶寬璧榄，如果不能，那么你就會(huì)浪費(fèi)帶寬吧雹。（大于MTU的包有兩種結(jié)局骨杂，一種是直接被丟了，另一種是會(huì)被重新分塊打包發(fā)送） 你可以想像成一個(gè)MTU就相當(dāng)于一個(gè)飛機(jī)的最多可以裝的人雄卷，如果這飛機(jī)里滿載的話搓蚪，帶寬最高，如果一個(gè)飛機(jī)只運(yùn)一個(gè)人的話丁鹉，無(wú)疑成本增加了妒潭，也而相當(dāng)二。
所以揣钦，Silly Windows Syndrome這個(gè)現(xiàn)像就像是你本來(lái)可以坐200人的飛機(jī)里只做了一兩個(gè)人雳灾。 要解決這個(gè)問題也不難，就是避免對(duì)小的window size做出響應(yīng)冯凹，直到有足夠大的window size再響應(yīng)谎亩，這個(gè)思路可以同時(shí)實(shí)現(xiàn)在sender和receiver兩端。
如果這個(gè)問題是由Receiver端引起的宇姚，那么就會(huì)使用 David D Clark’s 方案匈庭。在receiver端，如果收到的數(shù)據(jù)導(dǎo)致window size小于某個(gè)值浑劳，可以直接ack(0)回sender阱持，這樣就把window給關(guān)閉了，也阻止了sender再發(fā)數(shù)據(jù)過來(lái)魔熏，等到receiver端處理了一些數(shù)據(jù)后windows size 大于等于了MSS紊选，或者啼止，receiver buffer有一半為空，就可以把window打開讓send 發(fā)送數(shù)據(jù)過來(lái)兵罢。
如果這個(gè)問題是由Sender端引起的献烦，那么就會(huì)使用著名的 Nagle’s algorithm。這個(gè)算法的思路也是延時(shí)處理卖词，他有兩個(gè)主要的條件：1）要等到 Window Size>=MSS 或是 Data Size >=MSS巩那，2）收到之前發(fā)送數(shù)據(jù)的ack回包，他才會(huì)發(fā)數(shù)據(jù)此蜈，否則就是在攢數(shù)據(jù)即横。
另外，Nagle算法默認(rèn)是打開的裆赵，所以东囚，對(duì)于一些需要小包場(chǎng)景的程序——比如像telnet或ssh這樣的交互性比較強(qiáng)的程序，你需要關(guān)閉這個(gè)算法战授。你可以在Socket設(shè)置TCP_NODELAY選項(xiàng)來(lái)關(guān)閉這個(gè)算法（關(guān)閉Nagle算法沒有全局參數(shù)页藻，需要根據(jù)每個(gè)應(yīng)用自己的特點(diǎn)來(lái)關(guān)閉）
setsockopt(sock_fd, IPPROTO_TCP, TCP_NODELAY, (``char` `*)&value,``sizeof``(``int``));`
另外，網(wǎng)上有些文章說(shuō)TCP_CORK的socket option是也關(guān)閉Nagle算法植兰，這不對(duì)份帐。TCP_CORK其實(shí)是更新激進(jìn)的Nagle算漢，完全禁止小包發(fā)送楣导，而Nagle算法沒有禁止小包發(fā)送废境，只是禁止了大量的小包發(fā)送。最好不要兩個(gè)選項(xiàng)都設(shè)置筒繁。
TCP的擁塞處理 – Congestion Handling
上面我們知道了噩凹，TCP通過Sliding Window來(lái)做流控（Flow Control），但是TCP覺得這還不夠毡咏，因?yàn)镾liding Window需要依賴于連接的發(fā)送端和接收端驮宴，其并不知道網(wǎng)絡(luò)中間發(fā)生了什么。TCP的設(shè)計(jì)者覺得血当，一個(gè)偉大而牛逼的協(xié)議僅僅做到流控并不夠幻赚，因?yàn)榱骺刂皇蔷W(wǎng)絡(luò)模型4層以上的事，TCP的還應(yīng)該更聰明地知道整個(gè)網(wǎng)絡(luò)上的事臊旭。
具體一點(diǎn)落恼，我們知道TCP通過一個(gè)timer采樣了RTT并計(jì)算RTO，但是离熏，如果網(wǎng)絡(luò)上的延時(shí)突然增加佳谦，那么，TCP對(duì)這個(gè)事做出的應(yīng)對(duì)只有重傳數(shù)據(jù)滋戳，但是钻蔑，重傳會(huì)導(dǎo)致網(wǎng)絡(luò)的負(fù)擔(dān)更重啥刻，于是會(huì)導(dǎo)致更大的延遲以及更多的丟包，于是咪笑，這個(gè)情況就會(huì)進(jìn)入惡性循環(huán)被不斷地放大可帽。試想一下，如果一個(gè)網(wǎng)絡(luò)內(nèi)有成千上萬(wàn)的TCP連接都這么行事窗怒，那么馬上就會(huì)形成“網(wǎng)絡(luò)風(fēng)暴”映跟，TCP這個(gè)協(xié)議就會(huì)拖垮整個(gè)網(wǎng)絡(luò)。這是一個(gè)災(zāi)難扬虚。
所以努隙，TCP不能忽略網(wǎng)絡(luò)上發(fā)生的事情，而無(wú)腦地一個(gè)勁地重發(fā)數(shù)據(jù)辜昵，對(duì)網(wǎng)絡(luò)造成更大的傷害荸镊。對(duì)此TCP的設(shè)計(jì)理念是：TCP不是一個(gè)自私的協(xié)議，當(dāng)擁塞發(fā)生的時(shí)候堪置，要做自我犧牲躬存。就像交通阻塞一樣，每個(gè)車都應(yīng)該把路讓出來(lái)晋柱，而不要再去搶路了优构。
關(guān)于擁塞控制的論文請(qǐng)參看《Congestion Avoidance and Control》(PDF)
擁塞控制主要是四個(gè)算法：1）慢啟動(dòng)诵叁，2）擁塞避免雁竞，3）擁塞發(fā)生，4）快速恢復(fù)拧额。這四個(gè)算法不是一天都搞出來(lái)的碑诉，這個(gè)四算法的發(fā)展經(jīng)歷了很多時(shí)間，到今天都還在優(yōu)化中侥锦。 備注:
- 1988年进栽，TCP-Tahoe 提出了1）慢啟動(dòng)，2）擁塞避免恭垦，3）擁塞發(fā)生時(shí)的快速重傳
- 1990年快毛，TCP Reno 在Tahoe的基礎(chǔ)上增加了4）快速恢復(fù)
慢熱啟動(dòng)算法 – Slow Start
首先，我們來(lái)看一下TCP的慢熱啟動(dòng)番挺。慢啟動(dòng)的意思是唠帝，剛剛加入網(wǎng)絡(luò)的連接，一點(diǎn)一點(diǎn)地提速玄柏，不要一上來(lái)就像那些特權(quán)車一樣霸道地把路占滿襟衰。新同學(xué)上高速還是要慢一點(diǎn)，不要把已經(jīng)在高速上的秩序給搞亂了粪摘。
慢啟動(dòng)的算法如下(cwnd全稱Congestion Window)：
1）連接建好的開始先初始化cwnd = 1瀑晒，表明可以傳一個(gè)MSS大小的數(shù)據(jù)绍坝。
2）每當(dāng)收到一個(gè)ACK，cwnd++; 呈線性上升
3）每當(dāng)過了一個(gè)RTT苔悦，cwnd = cwnd*2; 呈指數(shù)讓升
4）還有一個(gè)ssthresh（slow start threshold）轩褐，是一個(gè)上限，當(dāng)cwnd >= ssthresh時(shí)玖详，就會(huì)進(jìn)入“擁塞避免算法”（后面會(huì)說(shuō)這個(gè)算法）
所以灾挨，我們可以看到，如果網(wǎng)速很快的話竹宋，ACK也會(huì)返回得快劳澄，RTT也會(huì)短，那么蜈七，這個(gè)慢啟動(dòng)就一點(diǎn)也不慢秒拔。下圖說(shuō)明了這個(gè)過程。
這里飒硅，我需要提一下的是一篇Google的論文《An Argument for Increasing TCP’s Initial Congestion Window》Linux 3.0后采用了這篇論文的建議——把cwnd 初始化成了 10個(gè)MSS砂缩。 而Linux 3.0以前，比如2.6三娩，Linux采用了RFC3390庵芭，cwnd是跟MSS的值來(lái)變的，如果MSS< 1095雀监，則cwnd = 4双吆；如果MSS>2190，則cwnd=2会前；其它情況下好乐，則是3。
擁塞避免算法 – Congestion Avoidance
前面說(shuō)過瓦宜，還有一個(gè)ssthresh（slow start threshold）蔚万，是一個(gè)上限，當(dāng)cwnd >= ssthresh時(shí)临庇，就會(huì)進(jìn)入“擁塞避免算法”反璃。一般來(lái)說(shuō)ssthresh的值是65535，單位是字節(jié)假夺，當(dāng)cwnd達(dá)到這個(gè)值時(shí)后淮蜈，算法如下：
1）收到一個(gè)ACK時(shí)，cwnd = cwnd + 1/cwnd
2）當(dāng)每過一個(gè)RTT時(shí)侄泽，cwnd = cwnd + 1
這樣就可以避免增長(zhǎng)過快導(dǎo)致網(wǎng)絡(luò)擁塞礁芦，慢慢的增加調(diào)整到網(wǎng)絡(luò)的最佳值。很明顯，是一個(gè)線性上升的算法柿扣。
擁塞狀態(tài)時(shí)的算法
前面我們說(shuō)過肖方，當(dāng)丟包的時(shí)候，會(huì)有兩種情況：
1）等到RTO超時(shí)未状，重傳數(shù)據(jù)包俯画。TCP認(rèn)為這種情況太糟糕，反應(yīng)也很強(qiáng)烈司草。
- sshthresh = cwnd /2
- cwnd 重置為 1
- 進(jìn)入慢啟動(dòng)過程
2）Fast Retransmit算法艰垂，也就是在收到3個(gè)duplicate ACK時(shí)就開啟重傳，而不用等到RTO超時(shí)埋虹。
TCP Tahoe的實(shí)現(xiàn)和RTO超時(shí)一樣猜憎。
-
TCP Reno的實(shí)現(xiàn)是：
- cwnd = cwnd /2
- sshthresh = cwnd
- 進(jìn)入快速恢復(fù)算法——Fast Recovery
上面我們可以看到RTO超時(shí)后，sshthresh會(huì)變成cwnd的一半搔课，這意味著胰柑，如果cwnd<=sshthresh時(shí)出現(xiàn)的丟包，那么TCP的sshthresh就會(huì)減了一半爬泥，然后等cwnd又很快地以指數(shù)級(jí)增漲爬到這個(gè)地方時(shí)柬讨，就會(huì)成慢慢的線性增漲。我們可以看到袍啡，TCP是怎么通過這種強(qiáng)烈地震蕩快速而小心得找到網(wǎng)站流量的平衡點(diǎn)的踩官。
快速恢復(fù)算法 – Fast Recovery
TCP Reno
這個(gè)算法定義在[RFC5681](http://tools.ietf.org/html/rfc5681 ""TCP Congestion Control"")【呈洌快速重傳和快速恢復(fù)算法一般同時(shí)使用蔗牡。快速恢復(fù)算法是認(rèn)為畴嘶，你還有3個(gè)Duplicated Acks說(shuō)明網(wǎng)絡(luò)也不那么糟糕蛋逾，所以沒有必要像RTO超時(shí)那么強(qiáng)烈集晚。 注意窗悯，正如前面所說(shuō)，進(jìn)入Fast Recovery之前偷拔，cwnd 和 sshthresh已被更新：
- cwnd = cwnd /2
- sshthresh = cwnd
然后蒋院，真正的Fast Recovery算法如下：
- cwnd = sshthresh + 3 * MSS （3的意思是確認(rèn)有3個(gè)數(shù)據(jù)包被收到了）
- 重傳Duplicated ACKs指定的數(shù)據(jù)包
- 如果再收到 duplicated Acks，那么cwnd = cwnd +1
- 如果收到了新的Ack莲绰，那么欺旧，cwnd = sshthresh ，然后就進(jìn)入了擁塞避免的算法了蛤签。
如果你仔細(xì)思考一下上面的這個(gè)算法辞友，你就會(huì)知道，上面這個(gè)算法也有問題，那就是——它依賴于3個(gè)重復(fù)的Acks称龙。注意留拾，3個(gè)重復(fù)的Acks并不代表只丟了一個(gè)數(shù)據(jù)包，很有可能是丟了好多包鲫尊。但這個(gè)算法只會(huì)重傳一個(gè)痴柔，而剩下的那些包只能等到RTO超時(shí)，于是疫向，進(jìn)入了惡夢(mèng)模式——超時(shí)一個(gè)窗口就減半一下咳蔚，多個(gè)超時(shí)會(huì)超成TCP的傳輸速度呈級(jí)數(shù)下降，而且也不會(huì)觸發(fā)Fast Recovery算法了搔驼。
通常來(lái)說(shuō)谈火，正如我們前面所說(shuō)的，SACK或D-SACK的方法可以讓Fast Recovery或Sender在做決定時(shí)更聰明一些舌涨，但是并不是所有的TCP的實(shí)現(xiàn)都支持SACK（SACK需要兩端都支持）堆巧，所以，需要一個(gè)沒有SACK的解決方案泼菌。而通過SACK進(jìn)行擁塞控制的算法是FACK（后面會(huì)講）
TCP New Reno
于是谍肤，1995年，TCP New Reno（參見 RFC 6582 ）算法提出來(lái)哗伯，主要就是在沒有SACK的支持下改進(jìn)Fast Recovery算法的——
當(dāng)sender這邊收到了3個(gè)Duplicated Acks荒揣，進(jìn)入Fast Retransimit模式，開發(fā)重傳重復(fù)Acks指示的那個(gè)包焊刹。如果只有這一個(gè)包丟了系任，那么，重傳這個(gè)包后回來(lái)的Ack會(huì)把整個(gè)已經(jīng)被sender傳輸出去的數(shù)據(jù)ack回來(lái)虐块。如果沒有的話俩滥，說(shuō)明有多個(gè)包丟了。我們叫這個(gè)ACK為Partial ACK贺奠。
一旦Sender這邊發(fā)現(xiàn)了Partial ACK出現(xiàn)霜旧，那么，sender就可以推理出來(lái)有多個(gè)包被丟了儡率，于是乎繼續(xù)重傳sliding window里未被ack的第一個(gè)包挂据。直到再也收不到了Partial Ack，才真正結(jié)束Fast Recovery這個(gè)過程
我們可以看到儿普，這個(gè)“Fast Recovery的變更”是一個(gè)非常激進(jìn)的玩法崎逃，他同時(shí)延長(zhǎng)了Fast Retransmit和Fast Recovery的過程。
算法示意圖
下面我們來(lái)看一個(gè)簡(jiǎn)單的圖示以同時(shí)看一下上面的各種算法的樣子：
FACK算法
FACK全稱Forward Acknowledgment 算法眉孩，論文地址在這里（PDF）Forward Acknowledgement: Refining TCP Congestion Control 這個(gè)算法是其于SACK的个绍，前面我們說(shuō)過SACK是使用了TCP擴(kuò)展字段Ack了有哪些數(shù)據(jù)收到勒葱，哪些數(shù)據(jù)沒有收到，他比Fast Retransmit的3 個(gè)duplicated acks好處在于巴柿，前者只知道有包丟了错森，不知道是一個(gè)還是多個(gè)，而SACK可以準(zhǔn)確的知道有哪些包丟了篮洁。 所以涩维，SACK可以讓發(fā)送端這邊在重傳過程中，把那些丟掉的包重傳袁波，而不是一個(gè)一個(gè)的傳瓦阐，但這樣的一來(lái)，如果重傳的包數(shù)據(jù)比較多的話篷牌，又會(huì)導(dǎo)致本來(lái)就很忙的網(wǎng)絡(luò)就更忙了睡蟋。所以，F(xiàn)ACK用來(lái)做重傳過程中的擁塞流控枷颊。
這個(gè)算法會(huì)把SACK中最大的Sequence Number 保存在snd.fack這個(gè)變量中戳杀，snd.fack的更新由ack帶秋，如果網(wǎng)絡(luò)一切安好則和snd.una一樣（snd.una就是還沒有收到ack的地方夭苗，也就是前面sliding window里的category #2的第一個(gè)地方）
然后定義一個(gè)awnd = snd.nxt – snd.fack（snd.nxt指向發(fā)送端sliding window中正在要被發(fā)送的地方——前面sliding windows圖示的category#3第一個(gè)位置）信卡，這樣awnd的意思就是在網(wǎng)絡(luò)上的數(shù)據(jù)。（所謂awnd意為：actual quantity of data outstanding in the network）
如果需要重傳數(shù)據(jù)题造，那么傍菇，awnd = snd.nxt – snd.fack + retran_data，也就是說(shuō)界赔，awnd是傳出去的數(shù)據(jù) + 重傳的數(shù)據(jù)丢习。
然后觸發(fā)Fast Recovery 的條件是： (** ( snd.fack – snd.una ) > (3*MSS) **) || (dupacks == 3) ) 。這樣一來(lái)淮悼，就不需要等到3個(gè)duplicated acks才重傳咐低，而是只要sack中的最大的一個(gè)數(shù)據(jù)和ack的數(shù)據(jù)比較長(zhǎng)了（3個(gè)MSS），那就觸發(fā)重傳袜腥。在整個(gè)重傳過程中cwnd不變见擦。直到當(dāng)?shù)谝淮蝸G包的snd.nxt<=snd.una（也就是重傳的數(shù)據(jù)都被確認(rèn)了），然后進(jìn)來(lái)?yè)砣苊鈾C(jī)制——cwnd線性上漲瞧挤。
我們可以看到如果沒有FACK在锡宋，那么在丟包比較多的情況下，原來(lái)保守的算法會(huì)低估了需要使用的window的大小特恬，而需要幾個(gè)RTT的時(shí)間才會(huì)完成恢復(fù)，而FACK會(huì)比較激進(jìn)地來(lái)干這事徐钠。 但是癌刽，F(xiàn)ACK如果在一個(gè)網(wǎng)絡(luò)包會(huì)被 reordering的網(wǎng)絡(luò)里會(huì)有很大的問題。
其它擁塞控制算法簡(jiǎn)介
TCP Vegas 擁塞控制算法
這個(gè)算法1994年被提出，它主要對(duì)TCP Reno 做了些修改显拜。這個(gè)算法通過對(duì)RTT的非常重的監(jiān)控來(lái)計(jì)算一個(gè)基準(zhǔn)RTT衡奥。然后通過這個(gè)基準(zhǔn)RTT來(lái)估計(jì)當(dāng)前的網(wǎng)絡(luò)實(shí)際帶寬，如果實(shí)際帶寬比我們的期望的帶寬要小或是要多的活远荠，那么就開始線性地減少或增加cwnd的大小矮固。如果這個(gè)計(jì)算出來(lái)的RTT大于了Timeout后，那么譬淳，不等ack超時(shí)就直接重傳档址。（Vegas 的核心思想是用RTT的值來(lái)影響擁塞窗口，而不是通過丟包） 這個(gè)算法的論文是《TCP Vegas: End to End Congestion Avoidance on a Global Internet》這篇論文給了Vegas和 New Reno的對(duì)比：
關(guān)于這個(gè)算法實(shí)現(xiàn)邻梆，你可以參看Linux源碼：/net/ipv4/tcp_vegas.h守伸， /net/ipv4/tcp_vegas.c
HSTCP(High Speed TCP) 算法
這個(gè)算法來(lái)自RFC 3649（Wikipedia詞條）。其對(duì)最基礎(chǔ)的算法進(jìn)行了更改浦妄，他使得Congestion Window漲得快尼摹，減得慢。其中：
- 擁塞避免時(shí)的窗口增長(zhǎng)方式： cwnd = cwnd + α(cwnd) / cwnd
- 丟包后窗口下降方式：cwnd = (1- β(cwnd))*cwnd
注：α(cwnd)和β(cwnd)都是函數(shù)剂娄，如果你要讓他們和標(biāo)準(zhǔn)的TCP一樣蠢涝，那么讓?duì)?cwnd)=1，β(cwnd)=0.5就可以了阅懦。 對(duì)于α(cwnd)和β(cwnd)的值是個(gè)動(dòng)態(tài)的變換的東西惠赫。 關(guān)于這個(gè)算法的實(shí)現(xiàn)，你可以參看Linux源碼：/net/ipv4/tcp_highspeed.c
TCP BIC 算法
2004年故黑，產(chǎn)內(nèi)出BIC算法《郏現(xiàn)在你還可以查得到相關(guān)的新聞《Google：美科學(xué)家研發(fā)BIC-TCP協(xié)議 速度是DSL六千倍》 BIC全稱Binary Increase Congestion control，在Linux 2.6.8中是默認(rèn)擁塞控制算法场晶。BIC的發(fā)明者發(fā)這么多的擁塞控制算法都在努力找一個(gè)合適的cwnd – Congestion Window混埠，而且BIC-TCP的提出者們看穿了事情的本質(zhì)，其實(shí)這就是一個(gè)搜索的過程诗轻，所以BIC這個(gè)算法主要用的是Binary Search——二分查找來(lái)干這個(gè)事钳宪。 關(guān)于這個(gè)算法實(shí)現(xiàn)，你可以參看Linux源碼：/net/ipv4/tcp_bic.c
TCP WestWood算法
westwood采用和Reno相同的慢啟動(dòng)算法扳炬、擁塞避免算法吏颖。westwood的主要改進(jìn)方面：在發(fā)送端做帶寬估計(jì)，當(dāng)探測(cè)到丟包時(shí)恨樟，根據(jù)帶寬值來(lái)設(shè)置擁塞窗口半醉、慢啟動(dòng)閾值。 那么劝术，這個(gè)算法是怎么測(cè)量帶寬的缩多？每個(gè)RTT時(shí)間呆奕，會(huì)測(cè)量一次帶寬，測(cè)量帶寬的公式很簡(jiǎn)單衬吆，就是這段RTT內(nèi)成功被ack了多少字節(jié)梁钾。因?yàn)椋@個(gè)帶寬和用RTT計(jì)算RTO一樣逊抡，也是需要從每個(gè)樣本來(lái)平滑到一個(gè)值的——也是用一個(gè)加權(quán)移平均的公式姆泻。 另外，我們知道冒嫡，如果一個(gè)網(wǎng)絡(luò)的帶寬是每秒可以發(fā)送X個(gè)字節(jié)拇勃，而RTT是一個(gè)數(shù)據(jù)發(fā)出去后確認(rèn)需要的時(shí)候，所以灯谣，X * RTT應(yīng)該是我們緩沖區(qū)大小潜秋。所以，在這個(gè)算法中胎许，ssthresh的值就是est_BD * min-RTT(最小的RTT值)峻呛，如果丟包是Duplicated ACKs引起的，那么如果cwnd > ssthresh辜窑，則 cwin = ssthresh钩述。如果是RTO引起的，cwnd = 1穆碎，進(jìn)入慢啟動(dòng)牙勘。 關(guān)于這個(gè)算法實(shí)現(xiàn)，你可以參看Linux源碼： /net/ipv4/tcp_westwood.c
其它
更多的算法所禀，你可以從Wikipedia的 TCP Congestion Avoidance Algorithm 詞條中找到相關(guān)的線索
后記
好了方面，到這里我想可以結(jié)束了，TCP發(fā)展到今天色徘，里面的東西可以寫上好幾本書恭金。本文主要目的，還是把你帶入這些古典的基礎(chǔ)技術(shù)和知識(shí)中褂策，希望本文能讓你了解TCP横腿，更希望本文能讓你開始有學(xué)習(xí)這些基礎(chǔ)或底層知識(shí)的興趣和信心。
當(dāng)然斤寂，TCP東西太多了耿焊，不同的人可能有不同的理解，而且本文可能也會(huì)有一些荒謬之言甚至錯(cuò)誤遍搞，還希望得到您的反饋和批評(píng)罗侯。
