TCP的RTT算法

從前面的TCP重傳機(jī)制我們知道Timeout的設(shè)置對于重傳非常重要。

• 設(shè)長了，重發(fā)就慢，丟了老半天才重發(fā)，沒有效率，性能差；
• 設(shè)短了，會導(dǎo)致可能并沒有丟就重發(fā)。于是重發(fā)的就快，會增加網(wǎng)絡(luò)擁塞，導(dǎo)致更多的超時，更多的超時導(dǎo)致更多的重發(fā)。

而且，這個超時時間在不同的網(wǎng)絡(luò)的情況下，根本沒有辦法設(shè)置一個死的值。只能動態(tài)地設(shè)置。 為了動態(tài)地設(shè)置，TCP引入了RTT——Round Trip Time，也就是一個數(shù)據(jù)包從發(fā)出去到回來的時間。這樣發(fā)送端就大約知道需要多少的時間，從而可以方便地設(shè)置Timeout——RTO（Retransmission TimeOut），以讓我們的重傳機(jī)制更高效。 聽起來似乎很簡單，好像就是在發(fā)送端發(fā)包時記下t0，然后接收端再把這個ack回來時再記一個t1，于是RTT = t1 – t0。沒那么簡單，這只是一個采樣，不能代表普遍情況。

經(jīng)典算法

RFC793?中定義的經(jīng)典算法是這樣的：

1）首先，先采樣RTT，記下最近好幾次的RTT值。

2）然后做平滑計算SRTT（ Smoothed RTT）。公式為：（其中的 α 取值在0.8 到 0.9之間，這個算法英文叫Exponential weighted moving average，中文叫：加權(quán)移動平均）

SRTT =?( α SRTT ) + ((1- α) RTT)

3）開始計算RTO。公式如下：

*RTO = min [ UBOUND, ?max [ LBOUND, ? (β SRTT) ] ?]**

其中：

• UBOUND是最大的timeout時間，上限值
• LBOUND是最小的timeout時間，下限值
• β 值一般在1.3到2.0之間。

Karn / Partridge 算法

但是上面的這個算法在重傳的時候會出有一個終極問題——你是用第一次發(fā)數(shù)據(jù)的時間和ack回來的時間做RTT樣本值，還是用重傳的時間和ACK回來的時間做RTT樣本值？

這個問題無論你選那頭都是按下葫蘆起了瓢。 如下圖所示：

• 情況（a）是ack沒回來，所以重傳。如果你計算第一次發(fā)送和ACK的時間，那么，明顯算大了。
• 情況（b）是ack回來慢了，但是導(dǎo)致了重傳，但剛重傳不一會兒，之前ACK就回來了。如果你是算重傳的時間和ACK回來的時間的差，就會算短了。

所以1987年的時候，搞了一個叫Karn / Partridge Algorithm，這個算法的最大特點(diǎn)是——忽略重傳，不把重傳的RTT做采樣（你看，你不需要去解決不存在的問題）。

但是，這樣一來，又會引發(fā)一個大BUG——如果在某一時間，網(wǎng)絡(luò)閃動，突然變慢了，產(chǎn)生了比較大的延時，這個延時導(dǎo)致要重轉(zhuǎn)所有的包（因?yàn)橹暗腞TO很?。?，于是，因?yàn)橹剞D(zhuǎn)的不算，所以，RTO就不會被更新，這是一個災(zāi)難。 于是Karn算法用了一個取巧的方式——只要一發(fā)生重傳，就對現(xiàn)有的RTO值翻倍（這就是所謂的?Exponential backoff），很明顯，這種死規(guī)矩對于一個需要估計比較準(zhǔn)確的RTT也不靠譜。

Jacobson / Karels 算法

前面兩種算法用的都是“加權(quán)移動平均”，這種方法最大的毛病就是如果RTT有一個大的波動的話，很難被發(fā)現(xiàn)，因?yàn)楸黄交袅?。所以?988年，又有人推出來了一個新的算法，這個算法叫Jacobson / Karels Algorithm（參看RFC6289）。這個算法引入了最新的RTT的采樣和平滑過的SRTT的差距做因子來計算。 公式如下：（其中的DevRTT是Deviation RTT的意思）

SRTT = SRTT + α (RTT – SRTT) —— 計算平滑RTT

DevRTT = (1-β)DevRTT + β(|RTT-SRTT|) ——計算平滑RTT和真實(shí)的差距（加權(quán)移動平均）

RTO= μ SRTT + ? DevRTT —— 神一樣的公式

（其中：在Linux下，α = 0.125，β = 0.25， μ = 1，??= 4 ——這就是算法中的“調(diào)得一手好參數(shù)”，nobody knows why, it just works…） 最后的這個算法在被用在今天的TCP協(xié)議中（Linux的源代碼在：tcp_rtt_estimator）。

TCP滑動窗口

需要說明一下，如果你不了解TCP的滑動窗口這個事，你等于不了解TCP協(xié)議。我們都知道，TCP必需要解決的可靠傳輸以及包亂序（reordering）的問題，所以，TCP必需要知道網(wǎng)絡(luò)實(shí)際的數(shù)據(jù)處理帶寬或是數(shù)據(jù)處理速度，這樣才不會引起網(wǎng)絡(luò)擁塞，導(dǎo)致丟包。

所以，TCP引入了一些技術(shù)和設(shè)計來做網(wǎng)絡(luò)流控，Sliding Window是其中一個技術(shù)。 前面我們說過，TCP頭里有一個字段叫Window，又叫Advertised-Window，這個字段是接收端告訴發(fā)送端自己還有多少緩沖區(qū)可以接收數(shù)據(jù)。于是發(fā)送端就可以根據(jù)這個接收端的處理能力來發(fā)送數(shù)據(jù)，而不會導(dǎo)致接收端處理不過來。 為了說明滑動窗口，我們需要先看一下TCP緩沖區(qū)的一些數(shù)據(jù)結(jié)構(gòu)：

上圖中，我們可以看到：

• 接收端LastByteRead指向了TCP緩沖區(qū)中讀到的位置，NextByteExpected指向的地方是收到的連續(xù)包的最后一個位置，LastByteRcved指向的是收到的包的最后一個位置，我們可以看到中間有些數(shù)據(jù)還沒有到達(dá)，所以有數(shù)據(jù)空白區(qū)。

• 發(fā)送端的LastByteAcked指向了被接收端Ack過的位置（表示成功發(fā)送確認(rèn)），LastByteSent表示發(fā)出去了，但還沒有收到成功確認(rèn)的Ack，LastByteWritten指向的是上層應(yīng)用正在寫的地方。

于是：

• 接收端在給發(fā)送端回ACK中會匯報自己的AdvertisedWindow = MaxRcvBuffer – LastByteRcvd – 1;

• 而發(fā)送方會根據(jù)這個窗口來控制發(fā)送數(shù)據(jù)的大小，以保證接收方可以處理。

下面我們來看一下發(fā)送方的滑動窗口示意圖：

（圖片來源）

上圖中分成了四個部分，分別是：（其中那個黑模型就是滑動窗口）

• 1已收到ack確認(rèn)的數(shù)據(jù)。

• 2發(fā)還沒收到ack的。

• 3在窗口中還沒有發(fā)出的（接收方還有空間）。

• 4窗口以外的數(shù)據(jù)（接收方?jīng)]空間）

下面是個滑動后的示意圖（收到36的ack，并發(fā)出了46-51的字節(jié)）：

下面我們來看一個接受端控制發(fā)送端的圖示：

（圖片來源）

Zero Window

上圖，我們可以看到一個處理緩慢的Server（接收端）是怎么把Client（發(fā)送端）的TCP Sliding Window給降成0的。此時，你一定會問，如果Window變成0了，TCP會怎么樣？是不是發(fā)送端就不發(fā)數(shù)據(jù)了？是的，發(fā)送端就不發(fā)數(shù)據(jù)了，你可以想像成“Window Closed”，那你一定還會問，如果發(fā)送端不發(fā)數(shù)據(jù)了，接收方一會兒Window size 可用了，怎么通知發(fā)送端呢？

解決這個問題，TCP使用了Zero Window Probe技術(shù)，縮寫為ZWP，也就是說，發(fā)送端在窗口變成0后，會發(fā)ZWP的包給接收方，讓接收方來ack他的Window尺寸，一般這個值會設(shè)置成3次，第次大約30-60秒（不同的實(shí)現(xiàn)可能會不一樣）。如果3次過后還是0的話，有的TCP實(shí)現(xiàn)就會發(fā)RST把鏈接斷了。

注意：只要有等待的地方都可能出現(xiàn)DDoS攻擊，Zero Window也不例外，一些攻擊者會在和HTTP建好鏈發(fā)完GET請求后，就把Window設(shè)置為0，然后服務(wù)端就只能等待進(jìn)行ZWP，于是攻擊者會并發(fā)大量的這樣的請求，把服務(wù)器端的資源耗盡。（關(guān)于這方面的攻擊，大家可以移步看一下Wikipedia的SockStress詞條）

另外，Wireshark中，你可以使用tcp.analysis.zero_window來過濾包，然后使用右鍵菜單里的follow TCP stream，你可以看到ZeroWindowProbe及ZeroWindowProbeAck的包。

Silly Window Syndrome

Silly Window Syndrome翻譯成中文就是“糊涂窗口綜合癥”。正如你上面看到的一樣，如果我們的接收方太忙了，來不及取走Receive Windows里的數(shù)據(jù)，那么，就會導(dǎo)致發(fā)送方越來越小。到最后，如果接收方騰出幾個字節(jié)并告訴發(fā)送方現(xiàn)在有幾個字節(jié)的window，而我們的發(fā)送方會義無反顧地發(fā)送這幾個字節(jié)。

要知道，我們的TCP+IP頭有40個字節(jié)，為了幾個字節(jié)，要達(dá)上這么大的開銷，這太不經(jīng)濟(jì)了。

另外，你需要知道網(wǎng)絡(luò)上有個MTU，對于以太網(wǎng)來說，MTU是1500字節(jié)，除去TCP+IP頭的40個字節(jié)，真正的數(shù)據(jù)傳輸可以有1460，這就是所謂的MSS（Max Segment Size）注意，TCP的RFC定義這個MSS的默認(rèn)值是536，這是因?yàn)?RFC 791里說了任何一個IP設(shè)備都得最少接收576尺寸的大小（實(shí)際上來說576是撥號的網(wǎng)絡(luò)的MTU，而576減去IP頭的20個字節(jié)就是536）。

如果你的網(wǎng)絡(luò)包可以塞滿MTU，那么你可以用滿整個帶寬，如果不能，那么你就會浪費(fèi)帶寬。（大于MTU的包有兩種結(jié)局，一種是直接被丟了，另一種是會被重新分塊打包發(fā)送） 你可以想像成一個MTU就相當(dāng)于一個飛機(jī)的最多可以裝的人，如果這飛機(jī)里滿載的話，帶寬最高，如果一個飛機(jī)只運(yùn)一個人的話，無疑成本增加了，也而相當(dāng)二。

所以，Silly Windows Syndrome這個現(xiàn)像就像是你本來可以坐200人的飛機(jī)里只做了一兩個人。 要解決這個問題也不難，就是避免對小的window size做出響應(yīng)，直到有足夠大的window size再響應(yīng)，這個思路可以同時實(shí)現(xiàn)在sender和receiver兩端。

• 如果這個問題是由Receiver端引起的，那么就會使用?David D Clark’s 方案。在receiver端，如果收到的數(shù)據(jù)導(dǎo)致window size小于某個值，可以直接ack(0)回sender，這樣就把window給關(guān)閉了，也阻止了sender再發(fā)數(shù)據(jù)過來，等到receiver端處理了一些數(shù)據(jù)后windows size 大于等于了MSS，或者，receiver buffer有一半為空，就可以把window打開讓send 發(fā)送數(shù)據(jù)過來。

• 如果這個問題是由Sender端引起的，那么就會使用著名的?Nagle’s algorithm。這個算法的思路也是延時處理，他有兩個主要的條件（更多的條件可以看一下tcp_nagle_check函數(shù)）：1）要等到 Window Size>=MSS 或是 Data Size >=MSS，2）等待時間或是超時200ms，這兩個條件有一個滿足，他才會發(fā)數(shù)據(jù)，否則就是在攢數(shù)據(jù)。

另外，Nagle算法默認(rèn)是打開的，所以，對于一些需要小包場景的程序——比如像telnet或ssh這樣的交互性比較強(qiáng)的程序，你需要關(guān)閉這個算法。你可以在Socket設(shè)置TCP_NODELAY選項(xiàng)來關(guān)閉這個算法（關(guān)閉Nagle算法沒有全局參數(shù)，需要根據(jù)每個應(yīng)用自己的特點(diǎn)來關(guān)閉）

setsockopt(sock_fd, IPPROTO_TCP, TCP_NODELAY, (char *)&value,sizeof(int));

另外，網(wǎng)上有些文章說TCP_CORK的socket option是也關(guān)閉Nagle算法，這個還不夠準(zhǔn)確。TCP_CORK是禁止小包發(fā)送，而Nagle算法沒有禁止小包發(fā)送，只是禁止了大量的小包發(fā)送。最好不要兩個選項(xiàng)都設(shè)置。?老實(shí)說，我覺得Nagle算法其實(shí)只加了個延時，沒有別的什么，我覺得最好還是把他關(guān)閉，然后由自己的應(yīng)用層來控制數(shù)據(jù)，我個覺得不應(yīng)該什么事都去依賴內(nèi)核算法。

TCP的擁塞處理 –?Congestion Handling

上面我們知道了，TCP通過Sliding Window來做流控（Flow Control），但是TCP覺得這還不夠，因?yàn)镾liding Window需要依賴于連接的發(fā)送端和接收端，其并不知道網(wǎng)絡(luò)中間發(fā)生了什么。TCP的設(shè)計者覺得，一個偉大而牛逼的協(xié)議僅僅做到流控并不夠，因?yàn)榱骺刂皇蔷W(wǎng)絡(luò)模型4層以上的事，TCP的還應(yīng)該更聰明地知道整個網(wǎng)絡(luò)上的事。

具體一點(diǎn)，我們知道TCP通過一個timer采樣了RTT并計算RTO，但是，如果網(wǎng)絡(luò)上的延時突然增加，那么，TCP對這個事做出的應(yīng)對只有重傳數(shù)據(jù)，但是，重傳會導(dǎo)致網(wǎng)絡(luò)的負(fù)擔(dān)更重，于是會導(dǎo)致更大的延遲以及更多的丟包，于是，這個情況就會進(jìn)入惡性循環(huán)被不斷地放大。試想一下，如果一個網(wǎng)絡(luò)內(nèi)有成千上萬的TCP連接都這么行事，那么馬上就會形成“網(wǎng)絡(luò)風(fēng)暴”，TCP這個協(xié)議就會拖垮整個網(wǎng)絡(luò)。這是一個災(zāi)難。

所以，TCP不能忽略網(wǎng)絡(luò)上發(fā)生的事情，而無腦地一個勁地重發(fā)數(shù)據(jù)，對網(wǎng)絡(luò)造成更大的傷害。對此TCP的設(shè)計理念是：TCP不是一個自私的協(xié)議，當(dāng)擁塞發(fā)生的時候，要做自我犧牲。就像交通阻塞一樣，每個車都應(yīng)該把路讓出來，而不要再去搶路了。

關(guān)于擁塞控制的論文請參看《Congestion Avoidance and Control》(PDF)

擁塞控制主要是四個算法：1）慢啟動，2）擁塞避免，3）擁塞發(fā)生，4）快速恢復(fù)。這四個算法不是一天都搞出來的，這個四算法的發(fā)展經(jīng)歷了很多時間，到今天都還在優(yōu)化中。 備注:

• 1988年，TCP-Tahoe 提出了1）慢啟動，2）擁塞避免，3）擁塞發(fā)生時的快速重傳
• 1990年，TCP Reno 在Tahoe的基礎(chǔ)上增加了4）快速恢復(fù)

慢熱啟動算法 – Slow Start

首先，我們來看一下TCP的慢熱啟動。慢啟動的意思是，剛剛加入網(wǎng)絡(luò)的連接，一點(diǎn)一點(diǎn)地提速，不要一上來就像那些特權(quán)車一樣霸道地把路占滿。新同學(xué)上高速還是要慢一點(diǎn)，不要把已經(jīng)在高速上的秩序給搞亂了。

慢啟動的算法如下(cwnd全稱Congestion Window)：

1）連接建好的開始先初始化cwnd = 1，表明可以傳一個MSS大小的數(shù)據(jù)。

2）每當(dāng)收到一個ACK，cwnd++; 呈線性上升

3）每當(dāng)過了一個RTT，cwnd = cwnd*2; 呈指數(shù)讓升

4）還有一個ssthresh（slow start threshold），是一個上限，當(dāng)cwnd >= ssthresh時，就會進(jìn)入“擁塞避免算法”（后面會說這個算法）

所以，我們可以看到，如果網(wǎng)速很快的話，ACK也會返回得快，RTT也會短，那么，這個慢啟動就一點(diǎn)也不慢。下圖說明了這個過程。

這里，我需要提一下的是一篇Google的論文《An Argument for Increasing TCP’s Initial Congestion Window》Linux 3.0后采用了這篇論文的建議——把cwnd 初始化成了 10個MSS。?而Linux 3.0以前，比如2.6，Linux采用了RFC3390，cwnd是跟MSS的值來變的，如果MSS2190，則cwnd=2；其它情況下，則是3。

?擁塞避免算法 –?Congestion Avoidance

前面說過，還有一個ssthresh（slow start threshold），是一個上限，當(dāng)cwnd >= ssthresh時，就會進(jìn)入“擁塞避免算法”。一般來說ssthresh的值是65535，單位是字節(jié)，當(dāng)cwnd達(dá)到這個值時后，算法如下：

1）收到一個ACK時，cwnd = cwnd + 1/cwnd

2）當(dāng)每過一個RTT時，cwnd = cwnd + 1

這樣就可以避免增長過快導(dǎo)致網(wǎng)絡(luò)擁塞，慢慢的增加調(diào)整到網(wǎng)絡(luò)的最佳值。很明顯，是一個線性上升的算法。

擁塞狀態(tài)時的算法

前面我們說過，當(dāng)丟包的時候，會有兩種情況：

1）等到RTO超時，重傳數(shù)據(jù)包。TCP認(rèn)為這種情況太糟糕，反應(yīng)也很強(qiáng)烈。

• sshthresh = ?cwnd /2
• cwnd 重置為 1
• 進(jìn)入慢啟動過程

2）Fast Retransmit算法，也就是在收到3個duplicate ACK時就開啟重傳，而不用等到RTO超時。

• TCP Tahoe的實(shí)現(xiàn)和RTO超時一樣。

• TCP Reno的實(shí)現(xiàn)是：
  • cwnd = cwnd /2
  • sshthresh = cwnd
  • 進(jìn)入快速恢復(fù)算法——Fast Recovery

上面我們可以看到RTO超時后，sshthresh會變成cwnd的一半，這意味著，如果cwnd<=sshthresh時出現(xiàn)的丟包，那么TCP的sshthresh就會減了一半，然后等cwnd又很快地以指數(shù)級增漲爬到這個地方時，就會成慢慢的線性增漲。我們可以看到，TCP是怎么通過這種強(qiáng)烈地震蕩快速而小心得找到網(wǎng)站流量的平衡點(diǎn)的。

快速恢復(fù)算法 – Fast Recovery

TCP Reno

這個算法定義在RFC5681?？焖僦貍骱涂焖倩謴?fù)算法一般同時使用?？焖倩謴?fù)算法是認(rèn)為，你還有3個Duplicated Acks說明網(wǎng)絡(luò)也不那么糟糕，所以沒有必要像RTO超時那么強(qiáng)烈。?注意，正如前面所說，進(jìn)入Fast Recovery之前，cwnd 和 sshthresh已被更新：

• cwnd = cwnd /2
• sshthresh = cwnd

然后，真正的Fast Recovery算法如下：

• cwnd = sshthresh ?+ 3 * MSS （3的意思是確認(rèn)有3個數(shù)據(jù)包被收到了）
• 重傳Duplicated ACKs指定的數(shù)據(jù)包
• 如果再收到 duplicated Acks，那么cwnd = cwnd +1
• 如果收到了新的Ack，那么，cwnd = sshthresh ，然后就進(jìn)入了擁塞避免的算法了。

如果你仔細(xì)思考一下上面的這個算法，你就會知道，上面這個算法也有問題，那就是——它依賴于3個重復(fù)的Acks。注意，3個重復(fù)的Acks并不代表只丟了一個數(shù)據(jù)包，很有可能是丟了好多包。但這個算法只會重傳一個，而剩下的那些包只能等到RTO超時，于是，進(jìn)入了惡夢模式——超時一個窗口就減半一下，多個超時會超成TCP的傳輸速度呈級數(shù)下降，而且也不會觸發(fā)Fast Recovery算法了。

通常來說，正如我們前面所說的，SACK或D-SACK的方法可以讓Fast Recovery或Sender在做決定時更聰明一些，但是并不是所有的TCP的實(shí)現(xiàn)都支持SACK（SACK需要兩端都支持），所以，需要一個沒有SACK的解決方案。而通過SACK進(jìn)行擁塞控制的算法是FACK（后面會講）

TCP New Reno

于是，1995年，TCP New Reno（參見?RFC 6582?）算法提出來，主要就是在沒有SACK的支持下改進(jìn)Fast Recovery算法的——

• 當(dāng)sender這邊收到了3個Duplicated Acks，進(jìn)入Fast Retransimit模式，開發(fā)重傳重復(fù)Acks指示的那個包。如果只有這一個包丟了，那么，重傳這個包后回來的Ack會把整個已經(jīng)被sender傳輸出去的數(shù)據(jù)ack回來。如果沒有的話，說明有多個包丟了。我們叫這個ACK為Partial ACK。

• 一旦Sender這邊發(fā)現(xiàn)了Partial ACK出現(xiàn)，那么，sender就可以推理出來有多個包被丟了，于是乎繼續(xù)重傳sliding window里未被ack的第一個包。直到再也收不到了Partial Ack，才真正結(jié)束Fast Recovery這個過程

我們可以看到，這個“Fast Recovery的變更”是一個非常激進(jìn)的玩法，他同時延長了Fast Retransmit和Fast Recovery的過程。

算法示意圖

下面我們來看一個簡單的圖示以同時看一下上面的各種算法的樣子：

FACK算法

FACK全稱Forward Acknowledgment 算法，論文地址在這里（PDF）Forward Acknowledgement: Refining TCP Congestion Control?這個算法是其于SACK的，前面我們說過SACK是使用了TCP擴(kuò)展字段Ack了有哪些數(shù)據(jù)收到，哪些數(shù)據(jù)沒有收到，他比Fast Retransmit的3 個duplicated acks好處在于，前者只知道有包丟了，不知道是一個還是多個，而SACK可以準(zhǔn)確的知道有哪些包丟了。 所以，SACK可以讓發(fā)送端這邊在重傳過程中，把那些丟掉的包重傳，而不是一個一個的傳，但這樣的一來，如果重傳的包數(shù)據(jù)比較多的話，又會導(dǎo)致本來就很忙的網(wǎng)絡(luò)就更忙了。所以，F(xiàn)ACK用來做重傳過程中的擁塞流控。

• 這個算法會把SACK中最大的Sequence Number 保存在snd.fack這個變量中，snd.fack的更新由ack帶秋，如果網(wǎng)絡(luò)一切安好則和snd.una一樣（snd.una就是還沒有收到ack的地方，也就是前面sliding window里的category #2的第一個地方）

• 然后定義一個awnd = snd.nxt – snd.fack（snd.nxt指向發(fā)送端sliding window中正在要被發(fā)送的地方——前面sliding windows圖示的category#3第一個位置），這樣awnd的意思就是在網(wǎng)絡(luò)上的數(shù)據(jù)。（所謂awnd意為：actual quantity of data outstanding in the network）

• 如果需要重傳數(shù)據(jù)，那么，awnd =?snd.nxt – snd.fack + retran_data，也就是說，awnd是傳出去的數(shù)據(jù) + 重傳的數(shù)據(jù)。

• 然后觸發(fā)Fast Recovery 的條件是：?(*?( snd.fack – snd.una ) > (3MSS)?**) || (dupacks == 3) ) 。這樣一來，就不需要等到3個duplicated acks才重傳，而是只要sack中的最大的一個數(shù)據(jù)和ack的數(shù)據(jù)比較長了（3個MSS），那就觸發(fā)重傳。在整個重傳過程中cwnd不變。直到當(dāng)?shù)谝淮蝸G包的snd.nxt<=snd.una（也就是重傳的數(shù)據(jù)都被確認(rèn)了），然后進(jìn)來擁塞避免機(jī)制——cwnd線性上漲。

我們可以看到如果沒有FACK在，那么在丟包比較多的情況下，原來保守的算法會低估了需要使用的window的大小，而需要幾個RTT的時間才會完成恢復(fù)，而FACK會比較激進(jìn)地來干這事。 但是，F(xiàn)ACK如果在一個網(wǎng)絡(luò)包會被 reordering的網(wǎng)絡(luò)里會有很大的問題。

其它擁塞控制算法簡介

TCP Vegas 擁塞控制算法

這個算法1994年被提出，它主要對TCP Reno 做了些修改。這個算法通過對RTT的非常重的監(jiān)控來計算一個基準(zhǔn)RTT。然后通過這個基準(zhǔn)RTT來估計當(dāng)前的網(wǎng)絡(luò)實(shí)際帶寬，如果實(shí)際帶寬比我們的期望的帶寬要小或是要多的活，那么就開始線性地減少或增加cwnd的大小。如果這個計算出來的RTT大于了Timeout后，那么，不等ack超時就直接重傳。（Vegas 的核心思想是用RTT的值來影響擁塞窗口，而不是通過丟包） 這個算法的論文是《TCP Vegas: End to End Congestion Avoidance on a Global Internet》這篇論文給了Vegas和 New Reno的對比：

關(guān)于這個算法實(shí)現(xiàn)，你可以參看Linux源碼：/net/ipv4/tcp_vegas.h，?/net/ipv4/tcp_vegas.c

HSTCP(High Speed TCP) 算法

這個算法來自RFC 3649（Wikipedia詞條）。其對最基礎(chǔ)的算法進(jìn)行了更改，他使得Congestion Window漲得快，減得慢。其中：

• 擁塞避免時的窗口增長方式： cwnd = cwnd + α(cwnd) / cwnd
• 丟包后窗口下降方式：cwnd = (1- β(cwnd))*cwnd

注：α(cwnd)和β(cwnd)都是函數(shù)，如果你要讓他們和標(biāo)準(zhǔn)的TCP一樣，那么讓α(cwnd)=1，β(cwnd)=0.5就可以了。 對于α(cwnd)和β(cwnd)的值是個動態(tài)的變換的東西。 關(guān)于這個算法的實(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ā)這么多的擁塞控制算法都在努力找一個合適的cwnd – Congestion Window，而且BIC-TCP的提出者們看穿了事情的本質(zhì)，其實(shí)這就是一個搜索的過程，所以BIC這個算法主要用的是Binary Search——二分查找來干這個事。 關(guān)于這個算法實(shí)現(xiàn)，你可以參看Linux源碼：/net/ipv4/tcp_bic.c

TCP WestWood算法

westwood采用和Reno相同的慢啟動算法、擁塞避免算法。westwood的主要改進(jìn)方面：在發(fā)送端做帶寬估計，當(dāng)探測到丟包時，根據(jù)帶寬值來設(shè)置擁塞窗口、慢啟動閾值。?那么，這個算法是怎么測量帶寬的？每個RTT時間，會測量一次帶寬，測量帶寬的公式很簡單，就是這段RTT內(nèi)成功被ack了多少字節(jié)。因?yàn)?，這個帶寬和用RTT計算RTO一樣，也是需要從每個樣本來平滑到一個值的——也是用一個加權(quán)移平均的公式。 另外，我們知道，如果一個網(wǎng)絡(luò)的帶寬是每秒可以發(fā)送X個字節(jié)，而RTT是一個數(shù)據(jù)發(fā)出去后確認(rèn)需要的時候，所以，X RTT應(yīng)該是我們緩沖區(qū)大小。所以，在這個算法中，ssthresh的值就是est_BD min-RTT(最小的RTT值)，如果丟包是Duplicated ACKs引起的，那么如果cwnd > ssthresh，則 cwin = ssthresh。如果是RTO引起的，cwnd = 1，進(jìn)入慢啟動。 ? 關(guān)于這個算法實(shí)現(xiàn)，你可以參看Linux源碼：?/net/ipv4/tcp_westwood.c

其它

更多的算法，你可以從Wikipedia的?TCP Congestion Avoidance Algorithm?詞條中找到相關(guān)的線索

?后記

好了，到這里我想可以結(jié)束了，TCP發(fā)展到今天，里面的東西可以寫上好幾本書。本文主要目的，還是把你帶入這些古典的基礎(chǔ)技術(shù)和知識中，希望本文能讓你了解TCP，更希望本文能讓你開始有學(xué)習(xí)這些基礎(chǔ)或底層知識的興趣和信心。

當(dāng)然，TCP東西太多了，不同的人可能有不同的理解，而且本文可能也會有一些荒謬之言甚至錯誤，還希望得到您的反饋和批評。

（全文完）