新reno演算法的擁塞避免

Ⅰ 安卓cpu優化tcp擁塞演算法cubic和reno怎麼選擇

1. 上述具體的論文可以參考：CUBIC: A New TCP-Friendly High-Speed TCP Variant
   

2. 1. tcp cubic數學模型

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

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

5. 

6. 窗口的增長函數如下：

7. W(t)=C*(t-K)3+Wmax,其中C和β為常量。

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

9. 當收到ACK後，CUBIC計算利用該演算法計算下一個RTT內的窗口增長速度，即計算W(t+RTT)，該值將作為cwnd的目標值，根據cwnd的大小，CUBIC將進入三種不同模式，如果cwnd會小於在標准TCP下經過上次擁塞之後的時刻t窗口將會達到的值(該值是通過標准TCP的窗口增長函數計算出來的)，那麼CUBIC就處於標准TCP模式，如果小於Wmax，那麼位於凹階段的，如果大於Wmax，那麼處於凸階段。

10. tcp cubic 內核源代碼調用邏輯

11. CUBIC整體架構調用的邏輯如下：

12. 1. 連接每收到一個ack，則調用tcp_ack

13. 2. tcp_ack會調用bictcp_acked，用來更新cnt和delayed_ack（用來消除delay包的影響）

14. 3. tcp_ack會調用bictcp_cong_avoid，這是分兩種情況：

15. （1）snd_cwnd小於慢啟動閾值，處於慢啟動階段，則調用tcp_slow_start

16. （2）snd_cwnd大於慢啟動閾值，處於擁塞避免階段，則調用bictcp_update來更新bictcp，再調用tcp_cong_avoid_ai

17. 4. tcp_ack中如果檢測到丟包，進入擁塞處理階段，則調用bictcp_recalc_ssthresh來更新慢啟動閾值

18. 5. tcp_ack中完成丟包重傳後，退出擁塞處理階段，則調用bictcp_undo_cwnd來更新
    

19. 快速重傳：tcp_ack中的丟包檢測，即檢測到連續3個重復ACK。

20. 快速恢復：bictcp_undo_cwnd，直接把snd_cwnd更新為max(snd_cwnd，last_max_cwnd)，和掉包前相差不大。

Ⅱ TCP協議總結

Transmission Control Protocol，傳輸控制協議，是一種面向連接的、可靠的、基於位元組流的傳輸層通信協議

TCP協議的目的是： 在不可靠傳輸的IP層之上建立一套可靠傳輸的機制。 TCP的可靠只是對於它自身來說的, 甚至是對於socket介面層, 兩個系統就不是可靠的了, 因為發送出去的數據, 沒有確保對方真正的讀到（所以要在業務層做重傳和確認機制）。

可靠傳輸的第一要素是 確認 , 第二要素是 重傳 , 第三要素是 順序 。 任何一個可靠傳輸的系統, 都必須包含這三個要素。 數據校驗 也是必要的。

傳輸是一個廣義的概念, 不局限於狹義的網路傳輸, 應該理解為通信和交互. 任何涉及到通信和交互的東西, 都可以借鑒TCP的思想。無論是在UDP上實現可靠傳輸或者創建自己的通信系統，無論這個系統是以API方式還是服務方式，只要是一個通信系統，就要考慮這三個要素。

SeqNum的增加是和傳輸的位元組數相關的。 上圖中，三次握手後，來了兩個Len:1440的包，而第二個包的SeqNum就成了1441。然後第一個ACK回的是1441（下一個待接收的位元組號），表示第一個1440收到了。

網路上的傳輸是沒有連接的，包括TCP也是一樣的 。而TCP所謂的「連接」，其實只不過是在通訊的雙方維護一個「連接狀態」，讓它看上去好像有連接一樣。所以，TCP的狀態變換是非常重要的。

查看各種狀態的數量
ss -ant | awk '{++s[$1]} END {for(k in s) print k,s[k]}'

通過三次握手完成連接的建立

三次握手的目的是交換通信雙方的初始化序號，以保證應用層接收到的數據不會亂序，所以叫SYN(Synchronize Sequence Numbers)。

ISN是不能hard code的，不然會出問題的。比如：如果連接建好後始終用1來做ISN，如果client發了30個segment過去，但是網路斷了，於是client重連，又用了1做ISN，但是之前連接的那些包到了，於是就被當成了新連接的包，此時，client的Sequence Number可能是3，而Server端認為client端的這個號是30了。全亂了。RFC793中說，ISN會和一個假的時鍾綁在一起，這個時鍾會在每4微秒對ISN做加一操作，直到超過232，又從0開始。這樣，一個ISN的周期大約是4.55個小時。因為，我們假設我們的TCP Segment在網路上的存活時間不會超過Maximum Segment Lifetime（MSL），所以，只要MSL的值小於4.55小時，那麼，我們就不會重用到ISN。

如果Server端接到了Clien發的SYN後回了SYN-ACK，之後Client掉線了，Server端沒有收到Client返回的ACK，那麼，這個連接就處於一個中間狀態，即沒成功，也沒失敗。於是，Server端如果在一定時間內沒有收到的ACK會重發SYN-ACK。在Linux下，默認重試次數為5次，重試的間隔時間從1s開始每次都翻番，5次的重試時間間隔為1s, 2s, 4s, 8s, 16s，總共31s，第5次發出後還要等32s都知道第5次也超時了，所以，總共需要 1s + 2s + 4s+ 8s+ 16s + 32s = 26 -1 = 63s，TCP才會斷開這個連接。

客戶端給伺服器發了一個SYN後，就下線了，於是伺服器需要默認等63s才會斷開連接，這樣，攻擊者就可以把伺服器的SYN連接的隊列耗盡，讓正常的連接請求不能處理。
於是，Linux下給了一個叫tcp_syncookies的參數來應對這個事：當SYN隊列滿了後，TCP會通過源地址埠、目標地址埠和時間戳打造出一個特別的Sequence Number發回去（又叫cookie），此時伺服器並沒有保留客戶端的SYN包。如果是攻擊者則不會有響應，如果是正常連接，則會把這個SYN Cookie發回來，然後服務端可以通過cookie建連接（即使你不在SYN隊列中）。
千萬別用tcp_syncookies來處理正常的大負載的連接的情況。因為sync cookies是妥協版的TCP協議，並不嚴謹。應該調整三個TCP參數：tcp_synack_retries減少重試次數，tcp_max_syn_backlog增大SYN連接數，tcp_abort_on_overflow處理不過來乾脆就直接拒絕連接

因為TCP是全雙工的，因此斷開連接需要4次揮手，發送方和接收方都需要發送Fin和Ack。如果兩邊同時斷連接，那就會就進入到CLOSING狀態，然後到達TIME_WAIT狀態。

指的是報文段的最大生存時間，如果報文段在網路中活動了MSL時間，還沒有被接收，那麼會被丟棄。關於MSL的大小，RFC 793協議中給出的建議是兩分鍾，不過實際上不同的操作系統可能有不同的設置，以Linux為例，通常是半分鍾，兩倍的MSL就是一分鍾，也就是60秒

主動關閉的一方會進入TIME_WAIT狀態，並且在此狀態停留兩倍的MSL時長。由於TIME_WAIT的存在，大量短連接會佔有大量的埠，造成無法新建連接。

主動關閉的一方發出 FIN包，被動關閉的一方響應ACK包，此時，被動關閉的一方就進入了CLOSE_WAIT狀態。如果一切正常，稍後被動關閉的一方也會發出FIN包，然後遷移到LAST_ACK狀態。

CLOSE_WAIT狀態在伺服器停留時間很短，如果你發現大量的 CLOSE_WAIT狀態，那麼就意味著被動關閉的一方沒有及時發出FIN包。

TCP要保證所有的數據包都可以到達，所以，必需要有重傳機制。

接收端給發送端的Ack確認只會確認最後一個連續的包 ，比如，發送端發了1,2,3,4,5一共五份數據，接收端收到了1，2，於是回ack 3，然後收到了4（注意此時3沒收到），此時的TCP會怎麼辦？我們要知道，因為正如前面所說的，SeqNum和Ack是以位元組數為單位，所以ack的時候，不能跳著確認，只能確認最大的連續收到的包，不然，發送端就以為之前的都收到了

但總體來說都不好。因為都在等timeout，timeout可能會很長

不以時間驅動，而以數據驅動重傳
如果包沒有連續到達，就ack最後那個可能被丟了的包，如果發送方連續收到3次相同的ack，就重傳

Selective Acknowledgment, 需要在TCP頭里加一個SACK的東西，ACK還是Fast Retransmit的ACK，SACK則是匯報收到的數據碎版，在發送端就可以根據回傳的SACK來知道哪些數據到了，哪些沒有收到

重復收到數據的問題，使用了SACK來告訴發送方有哪些數據被重復接收了

經典演算法：Karn/Partridge演算法，Jacobson/Karels演算法

TCP必需要知道網路實際的數據處理帶寬或是數據處理速度，這樣才不會引起網路擁塞，導致丟包

Advertised-Window ：接收端告訴發送端自己還有多少緩沖區可以接收數據。於是發送端就可以根據這個接收端的處理能力來發送數據，而不會導致接收端處理不過來

接收端LastByteRead指向了TCP緩沖區中讀到的位置，NextByteExpected指向的地方是收到的連續包的最後一個位置，LastByteRcved指向的是收到的包的最後一個位置，我們可以看到中間有些數據還沒有到達，所以有數據空白區。

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

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

收到36的ack，並發出了46-51的位元組

如果Window變成0了，發送端就不發數據了

如果發送端不發數據了，接收方一會兒Window size 可用了，怎麼通知發送端呢：TCP使用了Zero Window Probe技術，縮寫為ZWP，也就是說，發送端在窗口變成0後，會發ZWP的包給接收方，讓接收方來ack他的Window尺寸，一般這個值會設置成3次，每次大約30-60秒。如果3次過後還是0的話，有的TCP實現就會發RST把鏈接斷了。

如果你的網路包可以塞滿MTU，那麼你可以用滿整個帶寬，如果不能，那麼你就會浪費帶寬。避免對小的window size做出響應，直到有足夠大的window size再響應。

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

如果這個問題是由Sender端引起的，那麼就會使用著名的 Nagle』s algorithm。這個演算法的思路也是延時處理，他有兩個主要的條件：1）要等到 Window Size >= MSS 或是 Data Size >= MSS，2）等待時間或是超時200ms，這兩個條件有一個滿足，他才會發數據，否則就是在攢數據。

TCP_CORK是禁止小包發送，而Nagle演算法沒有禁止小包發送，只是禁止了大量的小包發送

TCP不是一個自私的協議，當擁塞發生的時候，要做自我犧牲

擁塞控制的論文請參看 《Congestion Avoidance and Control》

主要演算法有：慢啟動，擁塞避免，擁塞發生，快速恢復，TCP New Reno，FACK演算法，TCP Vegas擁塞控制演算法

TCP網路協議及其思想的應用
TCP 的那些事兒（上）
TCP 的那些事兒（下）
tcp為什麼是三次握手，為什麼不是兩次或四次？
記一次TIME_WAIT網路故障
再敘TIME_WAIT
tcp_tw_recycle和tcp_timestamps導致connect失敗問題
tcp短連接TIME_WAIT問題解決方法大全（1）- 高屋建瓴
tcp短連接TIME_WAIT問題解決方法大全（2）- SO_LINGER
tcp短連接TIME_WAIT問題解決方法大全（3）- tcp_tw_recycle
tcp短連接TIME_WAIT問題解決方法大全（4）- tcp_tw_reuse
tcp短連接TIME_WAIT問題解決方法大全（5）- tcp_max_tw_buckets
TCP的TIME_WAIT快速回收與重用
淺談CLOSE_WAIT
又見CLOSE_WAIT
PHP升級導致系統負載過高問題分析
Coping with the TCP TIME-WAIT state on busy Linux servers

Ⅲ TCP那些事兒

目錄：

以前我也認為TCP是相當底層的東西，我永遠不需要去了解它。雖然差不多是這樣，但是實際生活中，你依然可能遇見和TCP演算法相關的bug，這時候懂一些TCP的知識就至關重要了。（ 本文也可以引申為，系統調用，操作系統這些都很重要，這個道理適用於很多東西 ）
這里推薦一篇小短文， 人人都應該懂點TCP

使用TCP協議通信的雙方必須先建立TCP連接，並在內核中為該連接維持一些必要的數據結構，比如連接的狀態、讀寫緩沖區、定時器等。當通信結束時，雙方必須關閉連接以釋放這些內核數據。TCP服務基於流，源源不斷從一端流向另一端，發送端可以逐位元組寫入，接收端可以逐位元組讀出，無需分段。

需要注意的幾點：

TCP狀態（11種）：
eg.

以上為TCP三次握手的狀態變遷

以下為TCP四次揮手的狀態變遷

伺服器通過 listen 系統調用進入 LISTEN 狀態，被動等待客戶端連接，也就是所謂的被動打開。一旦監聽到SYN（同步報文段）請求，就將該連接放入內核的等待隊列，並向客戶端發送帶SYN的ACK（確認報文段），此時該連接處於 SYN_RECVD 狀態。如果伺服器收到客戶端返回的ACK，則轉到 ESTABLISHED 狀態。這個狀態就是連接雙方能進行全雙工數據傳輸的狀態。
而當客戶端主動關閉連接時，伺服器收到FIN報文，通過返回ACK使連接進入 CLOSE_WAIT 狀態。此狀態表示——等待伺服器應用程序關閉連接。通常，伺服器檢測到客戶端關閉連接之後，也會立即給客戶端發送一個FIN來關閉連接，使連接轉移到 LAST_ACK 狀態，等待客戶端對最後一個FIN結束報文段的最後一次確認，一旦確認完成，連接就徹底關閉了。

客戶端通過 connect 系統調用主動與伺服器建立連接。此系統調用會首先給伺服器發一個SYN，使連接進入 SYN_SENT 狀態。
connect 調用可能因為兩種原因失敗：1. 目標埠不存在（未被任何進程監聽）護著該埠被 TIME_WAIT 狀態的連接佔用（ 詳見後文 ）。2. 連接超時，在超時時間內未收到伺服器的ACK。
如果 connect 調用失敗，則連接返回初始的 CLOSED 狀態，如果調用成功，則轉到 ESTABLISHED 狀態。
客戶端執行主動關閉時，它會向伺服器發送一個FIN，連接進入 TIME_WAIT_1 狀態，如果收到伺服器的ACK，進入 TIME_WAIT_2 狀態。此時伺服器處於 CLOSE_WAIT 狀態，這一對狀態是可能發生辦關閉的狀態（詳見後文）。此時如果伺服器發送FIN關閉連接，則客戶端會發送ACK進行確認並進入 TIME_WAIT 狀態。

流量控制是為了控制發送方發送速率，保證接收方來得及接收。

接收方發送的確認報文中的窗口欄位可以用來控制發送方窗口大小，從而影響發送方的發送速率。將窗口欄位設置為 0，則發送方不能發送數據。

如果網路出現擁塞，分組將會丟失，此時發送方會繼續重傳，從而導致網路擁塞程度更高。因此當出現擁塞時，應當控制發送方的速率。這一點和流量控制很像，但是出發點不同。 流量控制是為了讓接收方能來得及接收，而擁塞控制是為了降低整個網路的擁塞程度。

TCP 主要通過四種演算法來進行擁塞控制： 慢開始、擁塞避免、快重傳、快恢復。

在Linux下有多種實現，比如reno演算法，vegas演算法和cubic演算法等。
發送方需要維護一個叫做擁塞窗口（cwnd）的狀態變數，注意擁塞窗口與發送方窗口的區別：擁塞窗口只是一個狀態變數，實際決定發送方能發送多少數據的是發送方窗口。
為了便於討論，做如下假設：

發送的最初執行慢開始，令 cwnd=1，發送方只能發送 1 個報文段；當收到確認後，將 cwnd 加倍，因此之後發送方能夠發送的報文段數量為：2、4、8 ...

注意到慢開始每個輪次都將 cwnd 加倍，這樣會讓 cwnd 增長速度非常快，從而使得發送方發送的速度增長速度過快，網路擁塞的可能也就更高。設置一個慢開始門限 ssthresh，當 cwnd >= ssthresh 時，進入擁塞避免，每個輪次只將 cwnd 加 1。

如果出現了超時，則令 ssthresh = cwnd/2，然後重新執行慢開始。

在接收方，要求每次接收到報文段都應該對最後一個已收到的有序報文段進行確認。例如已經接收到 M1 和 M2，此時收到 M4，應當發送對 M2 的確認。

在發送方，如果收到三個重復確認，那麼可以知道下一個報文段丟失，此時執行快重傳，立即重傳下一個報文段。例如收到三個 M2，則 M3 丟失，立即重傳 M3。

在這種情況下，只是丟失個別報文段，而不是網路擁塞。因此執行快恢復，令 ssthresh = cwnd/2 ，cwnd = ssthresh，注意到此時直接進入擁塞避免。

慢開始和快恢復的快慢指的是 cwnd 的設定值，而不是 cwnd 的增長速率。慢開始 cwnd 設定為 1，而快恢復 cwnd 設定為 ssthresh。

  發送端的每個TCP報文都必須得到接收方的應答，才算傳輸成功。

  TCP為每個TCP報文段都維護一個重傳定時器。
  發送端在發出一個TCP報文段之後就啟動定時器，如果在定時時間類未收到應答，它就將重發該報文段並重置定時器。

  因為TCP報文段最終在網路層是以IP數據報的形式發送，而IP數據報到達接收端可能是亂序或者重復的。TCP協議會對收到的TCP報文進行重排、整理，確保順序正確。

TCP報文段所攜帶的應用程序數據按照長度分為兩種： 交互數據 和 成塊數據

對於什麼是粘包、拆包問題，我想先舉兩個簡單的應用場景：

對於第一種情況，服務端的處理流程可以是這樣的：當客戶端與服務端的連接建立成功之後，服務端不斷讀取客戶端發送過來的數據，當客戶端與服務端連接斷開之後，服務端知道已經讀完了一條消息，然後進行解碼和後續處理...。對於第二種情況，如果按照上面相同的處理邏輯來處理，那就有問題了，我們來看看 第二種情況 下客戶端發送的兩條消息遞交到服務端有可能出現的情況：

第一種情況：

服務端一共讀到兩個數據包，第一個包包含客戶端發出的第一條消息的完整信息，第二個包包含客戶端發出的第二條消息，那這種情況比較好處理，伺服器只需要簡單的從網路緩沖區去讀就好了，第一次讀到第一條消息的完整信息，消費完再從網路緩沖區將第二條完整消息讀出來消費。

第二種情況：

服務端一共就讀到一個數據包，這個數據包包含客戶端發出的兩條消息的完整信息，這個時候基於之前邏輯實現的服務端就蒙了，因為服務端不知道第一條消息從哪兒結束和第二條消息從哪兒開始，這種情況其實是發生了TCP粘包。

第三種情況：

服務端一共收到了兩個數據包，第一個數據包只包含了第一條消息的一部分，第一條消息的後半部分和第二條消息都在第二個數據包中，或者是第一個數據包包含了第一條消息的完整信息和第二條消息的一部分信息，第二個數據包包含了第二條消息的剩下部分，這種情況其實是發送了TCP拆，因為發生了一條消息被拆分在兩個包裡面發送了，同樣上面的伺服器邏輯對於這種情況是不好處理的。

我們知道tcp是以流動的方式傳輸數據，傳輸的最小單位為一個報文段（segment）。tcp Header中有個Options標識位，常見的標識為mss(Maximum Segment Size)指的是，連接層每次傳輸的數據有個最大限制MTU(Maximum Transmission Unit)，一般是1500比特，超過這個量要分成多個報文段，mss則是這個最大限制減去TCP的header，光是要傳輸的數據的大小，一般為1460比特。換算成位元組，也就是180多位元組。

tcp為提高性能，發送端會將需要發送的數據發送到緩沖區，等待緩沖區滿了之後，再將緩沖中的數據發送到接收方。同理，接收方也有緩沖區這樣的機制，來接收數據。

發生TCP粘包、拆包主要是由於下面一些原因：

既然知道了tcp是無界的數據流，且協議本身無法避免粘包，拆包的發生，那我們只能在應用層數據協議上，加以控制。通常在制定傳輸數據時，可以使用如下方法：

寫了一個簡單的 golang 版的tcp伺服器實例，僅供參考：
例子

參考和推薦閱讀書目：

注釋：

eg.

Ⅳ TCP協議採取了哪些機制來進行擁塞控制

最初的TCP協議只有基於窗口的流控制（flow control）機制而沒有擁塞控制機制，流控制是一種局部控制機制，其參與者僅僅是發送方和接收方，它只考慮了接收端的接收能力，而沒有考慮到網路的傳輸能力；而擁塞控制則注重於整體，其考慮的是整個網路的傳輸能力，是一種全局控制機制。 擁塞控制機制使得TCP連接在網路發生擁塞時回退（back off），也就是說TCP源端會對網路發出的擁塞指示（congestion notification）（例如丟包、重復的ACK等）作出響應。 針對TCP在控制網路擁塞方面的不足，後來又提出了「慢啟動」（Slow Start）和「擁塞避免」（Congestion Avoidance）演算法。 TCP Reno版本增加了「快速重傳 」（Fast Retransmit）、「快速恢復」（Fast Recovery）演算法，避免了網路擁塞不嚴重時採用「慢啟動」演算法而造成過大地減小發送窗口尺寸的現象，這樣TCP的擁塞控制就由這4個核心部分組成。 近幾年又出現TCP的改進版本如NewReno和選擇性應答（selective acknowledgement，SACK）等。

Ⅳ TCP擁塞控制

我們看到TCP連接的雙方都包含一個接收緩沖區，一個發送緩沖區和幾個變數（LastByteRead，rwnd等）。 TCP擁塞控制機制運行在發送者對擁塞窗口的跟蹤上。 擁塞窗口（表示為cwnd）對TCP發送方可以發送到網路的速率施加約束。具體而言，發送者的未確認數據量不得超過cwnd和rwnd之間的較小值：

ssthresh 慢啟動閾值（show start threshold）

別被「慢啟動」這個名字所迷惑了，實際上這是cwnd增長最快的階段。

在慢啟動狀態下，cwnd的值從1 MSS開始，並且當每個被傳輸的報文段第一次ACK時，cwnd都會+1MSS

在進入擁塞避免狀態時，cwnd的值大約是上次遇到擁塞時的值的一半

在慢啟動階段每個RTT都會將cwnd值加倍，而在擁塞避免階段TCP採用更保守的方法，並且每個RTT只增加cwnd一個MSS的值[RFC 5681]。 這可以通過幾種方式實現。 一種常見的方法是TCP發送器在新的確認到達時通過MSS位元組（MSS / cwnd）增加cwnd。 例如，如果MSS是1,460位元組而cwnd是14,600位元組，則在RTT內發送10個段。 每個到達的ACK（假設每個段一個ACK）將擁塞窗口大小增加1/10MSS，因此，當10個段都ACK後，cwnd才累計增加了一個MSS。

在快速恢復中，對於導致TCP進入快速恢復狀態的丟失段的每個重復ACK，cwnd的值增加1 MSS。 最終，當丟失的段的ACK到達時，TCP在 放空cwnd 後進入擁塞避免狀態。 如果發生超時事件，則執行與慢啟動和擁塞避免相同的操作後，快速恢復將轉換為慢啟動狀態：cwnd的值設置為1 MSS，ssthresh的值設置為值的一半。

快速恢復是TCP [RFC 5681]的推薦但不是必需的組件。 有趣的是，早期版本的TCP（稱為TCP Tahoe）無條件地將其擁塞窗口切換為1 MSS，並在超時指示或三重復ACK指示丟失事件後進入慢啟動階段。 較新版本的TCP，TCP Reno，整合了快速恢復。

TCP tahoe 無快速恢復
TCP reno 有快速恢復

忽略連接開始時的初始慢啟動時段並假設丟失由三次重復ACK而不是超時觸發的，TCP的擁塞控制包括每個RTT 1個MSS的cwnd線性（附加）增加然後減半 （三次重復ACK事件）的cwnd的（乘法減少）。 出於這個原因，TCP擁塞控制通常被稱為加法增加，乘法減少（AIMD）形式的擁塞控制。AIMD擁塞控制引起了「鋸齒」行為，如圖3.54所示，這也很好地說明了我們早期對TCP「探測」帶寬的直覺 - TCP線性增加了它的擁塞窗口大小（以及它的傳輸速率），直到 發生三重復ACK事件。 然後它將擁塞窗口大小減少兩倍，然後再次開始線性增加，探測是否有額外的可用帶寬。

如前所述，許多TCP實現使用Reno演算法[Padhye 2001]。已經提出了Reno演算法的許多變體[RFC 3782; RFC 2018]。 TCP Vegas演算法[Brakmo 1995; Ahn 1995]試圖在保持良好吞吐量的同時避免擁擠。 Vegas的基本思想是（1）在發生丟包之前檢測源和目的地之間的路由器中的擁塞，以及（2）當檢測到即將發生的丟包時，線性地降低速率。通過觀察RTT預測即將發生的分組丟失。數據包的RTT越長，路由器的擁塞就越大。 Linux支持許多擁塞控制演算法（包括TCP Reno和TCP Vegas），並允許系統管理員配置將使用哪個版本的TCP。 Linux版本2.6.18中的TCP的默認版本設置為CUBIC [Ha 2008]，這是為高帶寬應用程序開發的TCP版本。有關TCP的許多風格的最新調查，請參閱[Afanasyev 2010]。 TCP的AIMD演算法是基於大量的工程洞察力和運營網路中的擁塞控制實驗而開發的。

Ⅵ 常見的tcp擁塞控制有哪幾種演算法

慢啟動：最初的TCP在連接建立成功後會向網路中發送大量的數據包，這樣很容易導致網路中路由器緩存空間耗盡，從而發生擁塞。因此新建立的連接不能夠一開始就大量發送數據包，而只能根據網路情況逐步增加每次發送的數據量，以避免上述現象的發生。具體來說，當新建連接時，cwnd初始化為1個最大報文段(MSS)大小，發送端開始按照擁塞窗口大小發送數據，每當有一個報文段被確認，cwnd就增加1個MSS大小。這樣cwnd的值就隨著網路往返時間(Round Trip Time,RTT)呈指數級增長，事實上，慢啟動的速度一點也不慢，只是它的起點比較低一點而已。我們可以簡單計算下：
開始 ---> cwnd = 1
經過1個RTT後 ---> cwnd = 2*1 = 2
經過2個RTT後 ---> cwnd = 2*2= 4
經過3個RTT後 ---> cwnd = 4*2 = 8
如果帶寬為W，那麼經過RTT*log2W時間就可以占滿帶寬。
擁塞避免：從慢啟動可以看到，cwnd可以很快的增長上來，從而最大程度利用網路帶寬資源，但是cwnd不能一直這樣無限增長下去，一定需要某個限制。TCP使用了一個叫慢啟動門限(ssthresh)的變數，當cwnd超過該值後，慢啟動過程結束，進入擁塞避免階段。對於大多數TCP實現來說，ssthresh的值是65536(同樣以位元組計算)。擁塞避免的主要思想是加法增大，也就是cwnd的值不再指數級往上升，開始加法增加。此時當窗口中所有的報文段都被確認時，cwnd的大小加1，cwnd的值就隨著RTT開始線性增加，這樣就可以避免增長過快導致網路擁塞，慢慢的增加調整到網路的最佳值。
上面討論的兩個機制都是沒有檢測到擁塞的情況下的行為，那麼當發現擁塞了cwnd又該怎樣去調整呢？
首先來看TCP是如何確定網路進入了擁塞狀態的，TCP認為網路擁塞的主要依據是它重傳了一個報文段。上面提到過，TCP對每一個報文段都有一個定時器，稱為重傳定時器(RTO)，當RTO超時且還沒有得到數據確認，那麼TCP就會對該報文段進行重傳，當發生超時時，那麼出現擁塞的可能性就很大，某個報文段可能在網路中某處丟失，並且後續的報文段也沒有了消息，在這種情況下，TCP反應比較「強烈」：
1.把ssthresh降低為cwnd值的一半
2.把cwnd重新設置為1
3.重新進入慢啟動過程。
從整體上來講，TCP擁塞控制窗口變化的原則是AIMD原則，即加法增大、乘法減小。可以看出TCP的該原則可以較好地保證流之間的公平性，因為一旦出現丟包，那麼立即減半退避，可以給其他新建的流留有足夠的空間，從而保證整個的公平性。
其實TCP還有一種情況會進行重傳：那就是收到3個相同的ACK。TCP在收到亂序到達包時就會立即發送ACK，TCP利用3個相同的ACK來判定數據包的丟失，此時進行快速重傳，快速重傳做的事情有：
1.把ssthresh設置為cwnd的一半
2.把cwnd再設置為ssthresh的值(具體實現有些為ssthresh+3)
3.重新進入擁塞避免階段。
後來的「快速恢復」演算法是在上述的「快速重傳」演算法後添加的，當收到3個重復ACK時，TCP最後進入的不是擁塞避免階段，而是快速恢復階段。快速重傳和快速恢復演算法一般同時使用。快速恢復的思想是「數據包守恆」原則，即同一個時刻在網路中的數據包數量是恆定的，只有當「老」數據包離開了網路後，才能向網路中發送一個「新」的數據包，如果發送方收到一個重復的ACK，那麼根據TCP的ACK機制就表明有一個數據包離開了網路，於是cwnd加1。如果能夠嚴格按照該原則那麼網路中很少會發生擁塞，事實上擁塞控制的目的也就在修正違反該原則的地方。
具體來說快速恢復的主要步驟是：
1.當收到3個重復ACK時，把ssthresh設置為cwnd的一半，把cwnd設置為ssthresh的值加3，然後重傳丟失的報文段，加3的原因是因為收到3個重復的ACK，表明有3個「老」的數據包離開了網路。
2.再收到重復的ACK時，擁塞窗口增加1。
3.當收到新的數據包的ACK時，把cwnd設置為第一步中的ssthresh的值。原因是因為該ACK確認了新的數據，說明從重復ACK時的數據都已收到，該恢復過程已經結束，可以回到恢復之前的狀態了，也即再次進入擁塞避免狀態。
快速重傳演算法首次出現在4.3BSD的Tahoe版本，快速恢復首次出現在4.3BSD的Reno版本，也稱之為Reno版的TCP擁塞控制演算法。
可以看出Reno的快速重傳演算法是針對一個包的重傳情況的，然而在實際中，一個重傳超時可能導致許多的數據包的重傳，因此當多個數據包從一個數據窗口中丟失時並且觸發快速重傳和快速恢復演算法時，問題就產生了。因此NewReno出現了，它在Reno快速恢復的基礎上稍加了修改，可以恢復一個窗口內多個包丟失的情況。具體來講就是：Reno在收到一個新的數據的ACK時就退出了快速恢復狀態了，而NewReno需要收到該窗口內所有數據包的確認後才會退出快速恢復狀態，從而更一步提高吞吐量。
SACK就是改變TCP的確認機制，最初的TCP只確認當前已連續收到的數據，SACK則把亂序等信息會全部告訴對方，從而減少數據發送方重傳的盲目性。比如說序號1，2，3，5，7的數據收到了，那麼普通的ACK只會確認序列號4，而SACK會把當前的5，7已經收到的信息在SACK選項裡面告知對端，從而提高性能，當使用SACK的時候，NewReno演算法可以不使用，因為SACK本身攜帶的信息就可以使得發送方有足夠的信息來知道需要重傳哪些包，而不需要重傳哪些包。

Ⅶ TCP擁塞控制及BBR原理分析

導語：TCP擁塞控制不僅僅是網路層的概念，可以將其歸屬於控制論的范疇。在TCP的演進過程中，出現了很多優秀的思想和演算法，以實現網路傳輸過程中，在公平競爭性的前提下，盡可能地利用帶寬資源。本文介紹TCP發展過程中出現的幾種擁塞控制演算法，並著重介紹BBR的原理。

TCP擁塞控制不僅僅是網路層的概念，可以將其歸屬於控制論的范疇。在TCP的演進過程中，出現了很多優秀的思想和演算法，以實現網路傳輸過程中，在公平競爭性的前提下，盡可能地利用帶寬資源。

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

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

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

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

擁塞控制主要包括四個過程：1）慢啟動；2）擁塞避免；3）擁塞發生；4）快速恢復。

RTT ：數據包從發出去到收到對它的ack的來回時間，採用平滑方式計算RTT

RTO ：重傳超時。簡單的如RTO=n*RTT, n=3（或其他RTO計算方法）

SACK ：TCP Option攜帶多組ACK信息

FR ：Fast Retransmission，收到3個p ack後，即可認為發生了丟包。不需要等待RTO超時即可重傳丟失的包。

ER ：Early Retransmission，無法產生足夠的pack和沒有新的數據包可以發送進入網路的情況下，減少觸發FR的p ack數量，以達到觸發FR的目的。

TLP ：如果發生了尾丟包，由於尾包後面沒有更多的數據包，也就沒有辦法觸發任何的pack。實際上，Google統計超過70%的RTO是尾丟包導致沒有任何p

ack 。TLP演算法是通過發送一個loss probe包，來產生足夠的SACK/FACK的信息以觸發RF。

Pacing ：控制發送速率，防止bursting

流控 ：Flow control站在單條TCP連接的維度，目的是讓發送方發包的速度，不超過接收方收包的能力。所以流控解決的問題是，如何在接收方可承受的范圍內，讓單條 TCP 連接的速度最大化。通過滑動窗口機制實現。

擁塞控制 ：Congestion control站在整個互聯網的維度，讓網路里所有TCP連接最大化共享網路通道的同時，盡可能的少出現網路擁塞現象，讓網路世界裡的每一個參與者既公平又高效。

cwnd ：發送窗口，擁塞窗口；在擁塞控制過程中窗口大小值變化。

rwnd ：接收窗口，通知發送者能夠發送的數據大小。

sliding window ：滑動窗口，只是一種抽象機制概念；在發送請求及收到ack的過程中滑動。

歷史上出現的各種TCP擁塞控制演算法，其本質是針對擁塞控制的四個過程做策略調整。按照演算法依據的因素，可以簡單的分為以下類型：

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

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

（2）擁塞避免演算法 – Congestion Avoidance
當cwnd >= ssthresh時，就會進入「擁塞避免演算法」。演算法如下：

（3）擁塞狀態演算法 – Fast Retransmit
Tahoe是等RTO超時，FR是在收到3個plicate ACK時就開啟重傳，而不用等到RTO超時。擁塞發生時：

（4）快速恢復 – Fast Recovery

Reno演算法以其簡單、有效和魯棒性，應用最廣泛。該演算法所包含的慢啟動、擁塞避免和快速重傳、快速恢復機制，是現有的眾多演算法的基礎。從Reno運行機制中很容易看出，為了維持一個動態平衡，必須周期性地產生一定量的丟失，再加上AIMD機制--減少快，增長慢，尤其是在大窗口環境下，由於一個數據報的丟失所帶來的窗口縮小要花費很長的時間來恢復，這樣，帶寬利用率不可能很高且隨著網路的鏈路帶寬不斷提升，這種弊端將越來越明顯。另外，丟包並不一定是網路擁塞，可能是網路常態，但是基於丟包的擁塞控制並不能區分。

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

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

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

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也具備RTT的不公平性。RTT小的連接，窗口調整發生的速度越快，因此可能更快的搶占帶寬。

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的時間周期。

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

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

傳統的擁塞控制演算法是計算cwnd值來規定當前可以發送多少數據，但是並不關注以什麼樣的速度發送數據。如果簡單而粗暴地將窗口大小（send.cwnd、recv.cwnd的最小值）數據全部突發出去，這往往會造成路由器的排隊，在深隊列的情況下，會測量出rtt劇烈地抖動。bbr在計算cwnd的同時，還計算了一個與之適配的pacing rate，該pacing rate規定cwnd指示的一窗數據的數據包之間，以多大的時間間隔發送出去。

我們知道，網路工作的最優點是在物理鏈路延遲狀態下，以最大速率傳輸數據。傳統的擁塞控制演算法思想是根據數據傳輸及ACK來確定RTT，但是這個RTT並不是物理鏈路延時，可能包含了路由器緩存耗時，也可能是擁塞狀態下的耗時。傳統的帶寬計算也是在不斷的試探逼近最優發送窗口，並在RTT或者統計周期內計算帶寬。這種情況下，RTT並不是真正的物理鏈路延遲，帶寬也有可能是在有路由緩存或丟包狀況下計算得到，那麼必然得到的不是精準的值。

BBR摒棄了丟包和實時RTT作為擁塞控制因素。引入BDP管道容量來衡量鏈路傳輸水平。BBR追求的是在鏈路最小RTT（物理鏈路延遲）的狀態下，找到最大帶寬。

首先我們認為網路最優點是可以達到的。下面描述RTT及收包速率與數據包投遞速率的關系。

圖中上半部分的過程可以描述為：隨著數據包投遞速率增加，如果沒有超過最優帶寬，則RTT不會變化，此時的RTT是物理鏈路延遲。隨著投遞速率繼續增加，這時中間路由節點可能出現需要緩存數據包的情況，這會導致RTT變大。如果投遞速率繼續增加，超過路由緩存能力，則可能出現丟包。

圖中下半部分的過程可以描述為：隨著數據包投遞速率增加，如果沒有超過最優帶寬，則發送方確認接收端收到的數據速率增加。隨著投遞速率繼續增加，因為數據包緩存在中間路由，這些包並不能及時得到ACK，因此發送方得到的ACK速率，即發送發確認接收方收到數據的速率會維持不變。如果投遞速率繼續增加，超過路由緩存能力，則可能出現丟包。

1）應答了多少數據，記為delivered；
2）應答1）中的delivered這么多數據所用的時間，記為interval_us。
將上述二者相除，就能得到帶寬：bw = delivered/interval_us；該計算方法不關注數據包ack及順序，是純粹的標量。

我們可以根據圖示很容易算出從Delivered為7時的數據包被確認到X被確認為止，一共有12-7=5個數據包被確認，即這段時間網路上清空了5個數據包。我們便很容易算出帶寬值了。

當10s內沒有發現最小RTTProp時，就要進入ProbeRTT狀態。在ProbeRTT狀態，僅發4MSS/RTT(接近停止發送)，從而排空鏈路上的數據包，測量真實的RTTProp。這里帶來的一個問題是，在一個RTT時間內以4MSS速率發送可能會造成抖動，特別是長RTT場景。具體的參考willko文章《GBN手札-BBR實時大數據傳輸之痛》。

Ⅷ 淺談TCP（2）：流量控制與擁塞控制

上文 淺談TCP（1）：狀態機與重傳機制 介紹了TCP的狀態機與重傳機制。本文介紹 流量控制 （Flow Control，簡稱流控）與 擁塞控制 （Congestion Control）。TCP依此保障網路的 QOS （Quality of Service）。

根據前文對TCP超時重傳機制的介紹，我們知道Timeout的設置對於重傳非常重要：

而且，這個超時時間在不同的網路環境下不同，必須動態設置。為此，TCP引入了 RTT （Round Trip Time，環回時間）：一個數據包從發出去到回來的時間。這樣，發送端就大約知道正常傳輸需要多少時間，據此計算 RTO （Retransmission TimeOut，超時重傳時間）。 聽起來似乎很簡單：在發送方發包時記下t0，收到接收方的Ack時記一個t1，於是RTT = t1 – t0。然而，這只是一個采樣，不能代表網路環境的普遍情況。

RFC793 中定義了一個 經典演算法 ：

經典演算法描述了RTO計算的基本思路，但還有一個重要問題：RTT的采樣取「 第一次 發Seq+收Ack的時間」，還是「 重傳 Seq+收Ack的時間」？

如圖：

問題的本質是： 發送方無法區分收到的Ack對應第一次發的Seq還是重傳的Seq （進入網路就都一樣了）。針對該問題， Karn / Partridge 演算法選擇迴避重傳的問題： 忽略重傳的樣本，RTT的采樣只取未產生重傳的樣本 。

簡單的忽略重傳樣本也有問題：假設當前的RTO很小，突然發生網路抖動，延時劇增導致要重傳所有的包；由於忽略重傳樣本，RTO不會被更新，於是繼續重傳使網路更加擁堵；擁堵導致更多的重傳，惡性循環直至網路癱瘓。Karn / Partridge演算法用了一個取巧的辦法： 只要一發生重傳，就將現有的RTO值翻倍（指數回退策略），待網路恢復後再仿照經典演算法逐漸平滑以降低RTO 。

該演算法已經做到可用，然而網路抖動對性能的影響比較大。

前面兩種演算法均使用加權移動平均演算法做平滑，這種方法的最大問題是：很難發現RTT值上的較大波動，因為被平滑掉了（1 - a比較小，即最新RTT的權重小）。針對該問題， Jacobson / Karels 演算法引入了最新采樣的RTT值和平滑過的SRTT值的差距做因子，即 DevRTT （Deviation RTT，RTT的偏離度），同時考慮SRTT帶來的慣性和DevRTT帶來的波動：

Linux 2.6採用該演算法計算RTO，默認取α = 0.125, β = 0.25, μ = 1, ∂ = 4（玄學調參，你懂的）。

TCP使用 滑動窗口 （Sliding Window）做流量控制與 亂序重排 。亂序重排在TCP的重傳機制中已經介紹，下面介紹流量控制。

TCP頭里有一個欄位叫Window（或Advertised Window）， 用於接收方通知發送方自己還有多少緩沖區可以接收數據 。 發送方根據接收方的處理能力來發送數據，不會導致接收方處理不過來，是謂流量控制 。暫且把Advertised Window當做滑動窗口，更容易理解滑動窗口如何完成流量控制，後面介紹擁塞控制時再說明二者的區別。

觀察TCP協議的發送緩沖區和接收緩沖區：

假設位置序號從左向右增長（常見的讀、寫緩沖區設計），解釋一下：

據此在接收方計算 AdvertisedWindow ，在發送方計算 EffectiveWindow ：

AdvertisedWindow衡量接收方還能接收的數據量，發送方要根據AdvertisedWindow決定接下來發送的數據量上限，即EffectiveWindow（可能為0）。

由於亂序問題的存在，LastByteRcvd可能指向Seq(LastByteSent)，而Seq(LastByteAcked + 1)至Seq(LastByteSent - 1)都還在路上 ，即將到達接收方，最好的情況是不丟包（丟包後會重傳）， 則LastByteRcvd之後、接收緩沖區邊界之前的空間就是發送方下一次發送數據的長度上限 （重傳不屬於下一次發送），因此， AdvertisedWindow = MaxRcvBuffer – (LastByteRcvd - LastByteRead) 。

LastByteRcvd還可能指向Seq(LastByteAcked)（一個新包都沒有收到） ，顯然AdvertisedWindow的公式不變， 而Seq(LastByteAcked + 1)至Seq(LastByteSent)都還在路上 ，未來將到達接收方，進入接收緩沖區，則「還在路上的Seq(LastByteAcked + 1)至Seq(LastByteSent)」不應超過接收緩沖區的剩餘空間AdvertisedWindow（目前等於MaxRcvBuffer），這要求的是上一次發送滿足LastByteSent - LastByteAcked ≤ AdvertisedWindow， 那麼LastByteSent之後、接收緩沖區剩餘空間邊界之前的空間就是發送方窗口內剩餘可發送數據的長度上限 ，因此， EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked) 。

以下是一個發送緩沖區的滑動窗口：

上圖分為4個部分：

其中， #2 + #3 組成了滑動窗口，總大小不超過AdvertisedWindow，二者比例受到接收方的處理速度與網路情況的影響（如果丟包嚴重或處理速度慢於發送速度，則 #2:#3 會越來越大）。

以下是一個AdvertisedWindow的調整過程，EffectiveWindow隨之變化：

上圖，我們可以看到一個處理緩慢的Server（接收端）是怎麼把Client（發送端）的發送窗口size給降成0的。對於接收方來說，此時接收緩沖區確實已經滿了，因此令發送方的發送窗口size降為0以暫時禁止發送是合理的。那麼，等接收方的接收緩沖區再空出來，怎麼通知發送方新的window size呢？

針對這個問題，為TCP設計了ZWP技術（Zero Window Probe，零窗通告）：發送方在窗口變成0後，會發ZWP的包給接收方，讓接收方來Ack他的Window尺寸；ZWP的重傳也遵循指數回退策略，默認重試3次；如果3次後window size還是0，則認為接收方出現異常，發RST重置連接（<font color="red"> 部分文章寫的是重試到window size正常？？？ </font>）。

注意：只要有等待的地方都可能出現DDoS攻擊，Zero Window也不例外。一些攻擊者會在和服務端建好連接發完GET請求後，就把Window設置為0，於是服務端就只能等待進行ZWP；然後攻擊者再大量並發發送ZWP，把伺服器端的資源耗盡。（<font color="red"> 客戶端等待怎麼耗服務端？？？ </font>）

為什麼要進行擁塞控制？假設網路已經出現擁塞，如果不處理擁塞，那麼延時增加，出現更多丟包，觸發發送方重傳數據，加劇擁塞情況，繼續惡性循環直至網路癱瘓。可知，擁塞控制與流量控制的適應場景和目的均不同。

擁塞發生前，可避免流量過快增長拖垮網路；擁塞發生時，唯一的選擇就是降低流量 。主要使用4種演算法完成擁塞控制：

演算法1、2適用於擁塞發生前，演算法3適用於擁塞發生時，演算法4適用於擁塞解決後（相當於擁塞發生前）。

在正式介紹上述演算法之前，先補充下 rwnd （Receiver Window，接收者窗口）與 cwnd （Congestion Window，擁塞窗口）的概念：

介紹流量控制時，我們沒有考慮cwnd，認為發送方的滑動窗口最大即為rwnd。實際上， 需要同時考慮流量控制與擁塞處理，則發送方窗口的大小不超過 min{rwnd, cwnd} 。下述4種擁塞控制演算法只涉及對cwnd的調整，同介紹流量控制時一樣，暫且不考慮rwnd，假定滑動窗口最大為cwnd；但讀者應明確rwnd、cwnd與發送方窗口大小的關系。

慢啟動演算法 （Slow Start）作用在擁塞產生之前： 對於剛剛加入網路的連接，要一點一點的提速，不要妄圖一步到位 。如下：

因此，如果網速很快的話，Ack返回快，RTT短，那麼，這個慢啟動就一點也不慢。下圖說明了這個過程：

前面說過，當cwnd >= ssthresh（通常ssthresh = 65535）時，就會進入 擁塞避免演算法 （Congestion Avoidance）： 緩慢增長，小心翼翼的找到最優值 。如下：

慢啟動演算法主要呈指數增長，粗獷型，速度快（「慢」是相對於一步到位而言的）；而擁塞避免演算法主要呈線性增長，精細型，速度慢，但更容易在不導致擁塞的情況下，找到網路環境的cwnd最優值。

慢啟動與擁塞避免演算法作用在擁塞發生前，採取不同的策略增大cwnd；如果已經發生擁塞，則需要採取策略減小cwnd。那麼，TCP如何判斷當前網路擁塞了呢？很簡單， 如果發送方發現有Seq發送失敗（表現為「丟包」），就認為網路擁塞了 。

丟包後，有兩種重傳方式，對應不同的網路情況，也就對應著兩種擁塞發生時的控制演算法：

可以看到，不管是哪種重傳方式，ssthresh都會變成cwnd的一半，仍然是 指數回退，待擁塞消失後再逐漸增長回到新的最優值 ，總體上在最優值（動態）附近震盪。

回退後，根據不同的網路情況，可以選擇不同的恢復演算法。慢啟動已經介紹過了，下面介紹快速恢復演算法。

如果觸發了快速重傳，即發送方收到至少3次相同的Ack，那麼TCP認為網路情況不那麼糟，也就沒必要提心吊膽的，可以適當大膽的恢復。為此設計 快速恢復演算法 （Fast Recovery），下面介紹TCP Reno中的實現。

回顧一下，進入快速恢復之前，cwnd和sshthresh已被更新：

然後，進入快速恢復演算法：

下面看一個簡單的圖示，感受擁塞控制過程中的cwnd變化：

Ⅸ TCP(IV) 擁塞控制

網路中的路由器因無法處理高速到達的流量而被迫丟棄數據信息的現象稱為擁塞。這里可能是因為路由器緩存較小或者處理不及時，雖然和流量控制時接收方的情況相似，但是這里有本質區別。因為後者是一對一的，幾乎隻影響一條連接；後者則影響多個連接。

當網路中大量的發送方和接收方被要求承擔超負荷的通信任務時，可以採用 降低發送方發送速率 或者 丟棄部分數據 （也可二者結合）來降低擁塞。

通常來說，接收方沒有一個精確的方法去知道中間路由器的狀態。目前基本的方法有：

之前的文章提到，發送方為了適應接收方接受速度，設置了一個發送窗口來控制流量。同樣的，當擁堵發生時，也需要控制發送速率，於是引入了一個窗口變數，來反映網路傳輸能力，稱為 擁塞窗口 （Congestion window），記作 cwnd。很直觀的，我們可以知道，發送端實際可用窗口 W 表示如下,其中 awnd 表示接收方窗口大小：

​ W = min(cwnd, awnd)

也就是說，還沒有收到 ACK 的數據量（也稱在外數據量）不能多於 W 。通常 W 以位元組或包為單位。很明顯， W 的值是在隨時變化的，並且我們希望 W 接近一個最佳窗口大小——帶寬延時積（Bandwidth-Delay Proct, BDP）,BDP 表示某一時刻的在外數據量，但是確定一個連接的 BDP 也是一個難點。

當連接建立之初，還無法獲知可用的連接資源，也無法確定 cwnd 初始值（有例外，就是之前文章里提到的目的度量）。這時候不應該直接大量快速的向網路中發送數據，因為會造成更嚴重的網路擁堵。獲得 cwnd 最佳值的唯一方法就是以越來越快的速度發包，直到有數據包丟失（或網路擁堵）。可以考慮 慢啟動 發送。在討論具體演算法之前，需要先了解 數據包守恆 的概念。

TCP 發送端的擁塞控制行為是由 ACK 的接收來驅動或「控制」的。並且鏈路的傳輸能力是固定的，當發送方接收到一個 ACK 時，就表示鏈路上多了一個「空位」，於是發送方可以再發送一個數據包。數據包守恆就是指鏈路中最大包的數量守恆。

當一個連接剛啟動時，或者檢測到重傳超時導致的丟包時，需要執行慢啟動 ； TCP 長時間處於空閑狀態也可能觸發慢啟動。其目的是探尋到 cwnd 值已經幫助 TCP 建立 ACK 時鍾。

TCP 發送一定數目的報文開始慢啟動，該數目稱為初始窗口（IInitial Window，IW）。為了簡便，我們討論 IW 為一個 SMSS （sender's MSS）的情況。意味著初始 cwnd 大小為 1 SMSS。

假設沒有丟包且每一個數據都有相應的 ACK。那麼第一個 ACK 到達，說明可以再發送一個新的報文段（數據包守恆），每收到一個「好的」 ACK， cwnd = cwnd + min(N, SMSS) ，這里的 N 是指那個「好的」 ACK 所確認的位元組數。所謂「好的」是指 ACK 號使窗口更新了。

因為通常來說 N 的值等於 SMSS，使得 cwnd 在收到一個 ACK 後增大一倍。所以慢啟動實際上是以指數增長，在 K 輪之後，cwnd = 2^K。如下圖：

當接收方開啟延時 ACK，則發送方 cwnd 增長曲線如圖中藍色曲線，雖然起步看起來慢，但仍是指數增長。當然這對於帶寬延時積很大的網路來說，確實有所浪費，應該採用更好的辦法。

當然不可能讓窗口大小無限增長，否則會造成嚴重的網路擁堵直至網路癱瘓。在上述情況下，cwnd 將大幅減小（減至原值一半），也是慢啟動和 擁塞避免 的轉折點，與 慢啟動閾值 （slow start threshold, ssthresh）有關。

當 cwnd 達到 ssthresh 時，可能還有一些傳輸資源未被佔用。但這時候需要謹慎的試探，不能再以較快速度增大 cwnd。採用避免擁塞演算法，每接收到一個新的 ACK，cwnd 會做以下更新：

​ cwnd = cwnd + SMSS * SMSS / cwnd

假設 cwnd = k * SMSS，則可推導如下：

​ cwnd = cwnd + SMSS / k

發包來看像這樣：

通常認為擁塞避免階段 cwnd 呈線性增長，稱為累加增長。

通常 TCP 連接總是會選擇慢啟動和擁塞避免中的一個，依據就是之前提到的慢啟動閾值。當 cwnd < ssthresh，採用慢啟動演算法， cwnd > ssthresh 採用擁塞避免，相等時選擇任意都行。所以關鍵就是 ssthresh 的值，該值並不是固定的，它的主要目的是， 記錄上一次最好的窗口估計值 。

ssthresh 初始值可以任意設定（如 awnd 或更大），這通常會使 TCP 總是以慢啟動開始。當出現重傳，無論是超時重傳還是快速重傳，都會導致 ssthresh 值更新如下：

​ ssthresh = max(在外數據值 / 2, 2 * SMSS)

在外數據值其實就是當前窗口大小。這樣通常會使 ssthresh 變小（但也可能使其變大），然後觸發擁塞避免。

Tahoe 演算法規定當重傳時，都會進入慢啟動，並且丟包時，將 cwnd 設為 1 SMSS。這顯然性能不太好，已被棄用，不用深究。

Reno 演算法是標准 TCP 的基礎，它根據之前提到的「包守恆」實現了快速恢復，較好的利用了帶寬。快速恢復是針對快速重傳的情景實現的，來看一下它在標准 TCP 中的使用：

以下是 Reno 的狀態轉換圖：

Reno 演算法在同一窗口下丟失多個包時，其中一個包快速重傳成功，就會停止 cwnd 膨脹，造成其它丟失的包可能觸發超時重傳，然後 cwnd 降為 1 SMSS，吞吐量大大降低。NewReno 採用了一個「恢復點」，指的是收到的 ACK 號大於已發送包的序列號的最大值，達到這個恢復點，才會退出快速恢復。下圖最右圖中， ACK11 達到了恢復點。

限制傳輸策略對 TCP 做了微小改進，主要是為了解決窗口較小時，出現丟包，但是沒有足夠的包去引發快速重傳/快速恢復機制。為了盡快觸發快速重傳，每接收兩個連續重復 ACK，就發送一個新的包，使網路中的數據量維持一定數量。這是 TCP 推薦策略。

這里對應 TCP/IP 詳解卷一里，書上對於「應用受限」說法不正確。書上說此時「無法發送」，但是查閱 rfc 原文如下：

擁塞窗口校驗（Congestion Window Validation）機制規定，需要發送新數據時，距離上次發送操作超過一個 RTO，如果是：

在長時間發送暫停後，cwnd 低於 ssthresh，再次發送時會進入慢啟動。Linux 默認開啟 CWV。

在之前的超時重傳里，我們提到了 偽超時，再來回顧下(注意下圖是相當簡易的情形，沒有考慮延時 ACK 以及 cwnd 增長，會意即可)：

偽超時可能引起「回退 N 步」的行為，並且可能觸發快速重傳，浪費不少資源。

該演算法利用 TCP 的 TSOPT 選項，在發送生超時後，重傳報文並記錄 TSV，期待一個 ACK，若 ACK 的 TSER 小於重傳報文的 TSV，則認為該 ACK 是對原始報文的確認而不是對重傳報文的確認，即認定該重傳是偽重傳。

前面提到過，發生超時，則 ssthresh 減半，cwnd 降為 1 SMSS。發生偽超時的話，在 RTO 之後到來的 ACK 會使 cwnd 快速變大，但仍會有不必要重傳。

採用 Eifel 演算法，在判定偽超時後，會撤銷對 ssthresh 的修改。在每次超時對 ssthresh 修改之前，會用 pipe_prev 變數來保存當前的 ssthresh，以便撤銷修改。

若出現偽重傳，當 ACK 到達時，假設 ACK 確認的報文段長度為 A：

前面討論了當失序或者超時的時候 TCP 的行為，這些行為都是通過 ACK 的反饋來觸發或者驅動的，換句話說，這些「擁塞」的情況是「猜出來的」。當明確知道發生擁堵了，TCP 會執行 擁塞窗口縮減 （congestion window recing，CWR）。明確知道擁堵的情況主要有兩種：

CWR 處理過程如下：

直到 cwnd 達到新的 ssthresh 值或者由於其他原因（如丟包）打斷 CWR。

到此，我們總結一下 TCP 擁塞控制的幾個重要狀態：

這個問題還是很有趣的，所以拿出來講一下。先說結論，網路設備的緩沖區並不是越大越好，也不是越小越好，而是需要根據鏈路速率和RTT進行計算，得到一個經驗值。

緩沖區過小的問題很明顯，如果緩沖區太小，很容易就被寫滿了，只要不能進行適當的排隊，丟包率會高，導致傳輸效率差。

假設如下場景：

上圖中，我們假設中間的路由設備的buffer極大，理論來說無論來多少數據，都能buffer起來。中間的路由設備，接收速率是1M/s，而發送速率只有10k/s。

到某一時刻，發送方認為某一數據超時丟失（實際上沒有丟失，而是在緩沖區沒來得及處理），於是重發，導致緩存區有冗餘數據。大量的冗餘數據導致利用率變得極低。

而緩沖區為正常大小的時候，多的數據會被丟棄，過一會而緩沖區有新的位置，新的數據會到來，接收方收到數據是失序的，於是發送冗餘 ACK，促進快速重傳，反而使鏈路利用率得到保障。

大多數攻擊是強迫 TCP 發送速率比一般情況更快或更慢。

原理是接收方將原來的確認范圍劃分成很多小塊，把一個 ACK 變成多個 ACK，使得發送方不斷增大 cwnd，使網路變的擁堵。可以通過計算每個 ACK 的確認量（而不是一個包）來判斷是否是正確的 ACK。

接收方對還沒到達的數據進行提前確認，使得 RTT 變得比較小，同樣使得發送方不斷增大 cwnd。可以採用一個可累加的隨機數，動態匹配 ACK。