tcp擁塞控制演算法

⑴ 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擁塞控制

  在計算機網路中的鏈路容量（即帶寬）、交換節點（如路由器）中的緩存和處理機等，都是網路的資源。在某段時間內，若對網路中某一資源的需求超過了該資源所能提供的可用部分，網路的性能就要變壞，從而導致吞吐量將隨著輸入負荷增大而降低。這種情況就叫做 擁塞 。通俗來說，就跟交通擁堵性質一樣。

  網路擁塞的原因有很多，如交換節點的 緩存容量太小、輸出鏈路的容量和處理機的速度 。

   擁塞控制就是防止過多的數據注入網路中，這樣可以使網路中的路由器或鏈路不致於過載 。擁塞控制是一個 全局性的過程 。涉及網路中所有的主機、所有的路由器，以及與降低網路傳輸性能有關的所有因素。

  擁塞控制和流量控制的關系密切，但是 流量控制往往是指點對點的通信量控制 ，是個 端對端 的問題。流量控制所要做的就是抑制發送方發送數據的速率，以便使接收端來得及接收。

  TCP進行擁塞控制的演算法有四種，即 慢開始（slow-start）、擁塞避免（congestion-avoidance）、快重傳（fast retransmit）、快恢復（fast recovery） 。

  為了討論問題方便，提出以下假定：

  擁塞控制也叫做 基於窗口 的擁塞控制。為此，發送方維持一個叫作 擁塞窗口cwnd （congestion window）的狀態變數。 擁塞窗口的大小取決於網路的用誰程度，並且動態的變化。發送方讓自己的發送窗口等於擁塞窗口 。

  接收方窗口值rwnd和擁塞窗口值cwnd的區別：

  發送方控制擁塞窗口的原則是：只要網路沒有出現擁塞，擁塞窗口就可以再擴大一些，以便讓更多的分組發送出去，如果網路出現了擁塞，就必須將擁塞窗口減小一些，以減少分組的發送。 判斷網路擁塞的依據就是出現了超時 。

  慢開始演算法的思路：剛開始發送數據時，不一下向網路中注入大量數據，而是先探測一下，即 由小到大逐漸增大發送窗口 ，也就是說， 由小到大逐漸增大擁塞窗口數值 。

  慢開始演算法具體規定：剛開始發送數據時，先把擁塞窗口cwnd根據 發送方的最大報文段SMSS （Sender Maximum Segment Size）數值的大小設置為不超過2-4個SMSS的數值。在 每收到一個對新的報文段的確認後，可以把擁塞窗口增加最多一個SMSS的數值 。用這樣的方法逐步增大發送方的擁塞窗口rwnd，可以使分組注入到網路中的速率更加合理。

  下面舉例說明一下，雖然實際上TCP是用位元組數作為窗口大小的單位，但為了方便描述，下面使用報文段的個數來作為窗口的大小的單位，並且假設所有的報文段大小相等。

  所以， 慢開始演算法每經過一個傳輸輪次（transmission round），擁塞窗口cwnd就加倍 。

  註：在TCP實際運行時，發送方只有收到一個確認就可以將cwnd加1並發送新的分組，並不需要等一個輪次所有的確認都收到後再發送新的分組。

  從上面可以看出，慢開始演算法雖然起始的窗口很小，但是每過一個輪次，窗口大小翻倍，呈指數爆炸增長，所以必須要對其進行一個限制，防止其增長過大引起網路擁塞。這個限制就是 慢開始門限ssthresh 狀態變數。慢開始門限ssthresh的用法如下：

  擁塞避免演算法的思路是讓擁塞窗口cwnd緩慢增大，即每經過一個往返時間RTT就把發送方的擁塞窗口cwnd加1，而不是像慢開始階段那樣加倍增長。因此在擁塞避免階段就有 「加法增大」AI （Additive Increase）的特點。這表明在擁塞避免階段，擁塞窗口cwnd 按線性規律增長 ，比慢開始演算法的擁塞窗口增長速率緩慢得多。

  下面用一個具體的例子來說明擁塞控制的過程，下圖假設TCP發送窗口等於擁塞窗口，慢開始初始門限設置為16個報文段，即ssthresh = 16。

  在擁塞避免階段，擁塞窗口是按照線性規律增大的，這常稱為 加法增大AI 。無論在慢開始階段還是擁塞避免階段，只要出現一次超時（即出現一次網路擁塞），就把慢開始門限值 ssthresh 設置為當前擁塞窗口的一半，這叫做 乘法減小 MD （Multiplication Decrease）。

  當網路頻繁出現擁塞時，ssthresh 值就下降的很快，以大大減少注入網路中的分組數。

   快恢復演算法 ，如果發送方連續接收到3個冗餘ACK，發送方知道現在只是丟失了個別的報文段，此時調整門限值 ssthresh為當前擁塞窗口的一半，同時設置擁塞窗口 cwnd為新的門限值（發生報文段丟失時擁塞窗口的一半），而不是從1開始。

   TCP對這種丟包事件的行為，相比於超時指示的丟包，不那麼劇烈 ，所以對於連續收到3個冗餘ACK，擁塞窗口不會從1開始開始。

⑶ tcp如何實現擁塞控制

TCP擁塞控制是傳輸控制協議（英語：Transmission Control Protocol，縮寫TCP）避免網路擁塞的演算法，是互聯網上主要的一個擁塞控制措施。它使用一套基於線增積減模式的多樣化網路擁塞控制方法（包括慢啟動和擁塞窗口等模式）來控制擁塞。在互聯網上應用中有相當多的具體實現演算法。

在TCP中，擁塞窗口（congestion window）是任何時刻內確定能被發送出去的位元組數的控制因素之一，是阻止發送方至接收方之間的鏈路變得擁塞的手段。他是由發送方維護，通過估計鏈路的擁塞程度計算出來的，與由接收方維護的接收窗口大小並不沖突。

1、慢開始演算法：

簡單的說，開始傳輸時，傳輸的數據由小到大遞增到一個值(即發送窗口由小到大(指數增長)逐漸增大到擁塞窗口的數值)。

2、擁塞避免演算法：

數據發送出去，並發到接收方發回來的確認收到，擁塞窗口每次值加1地線性增大。

3、快重傳演算法：

數據傳輸時(數據被分成報文，每個報文都有個序號)，中間的一部分丟失接收方沒收到，接收方連續接到後面的數據，則發回對丟失前的數據的重復確認，這樣發送方就知道有部分數據丟失了，於是從丟失出重傳數據。

4、快恢復演算法：

快恢復是與快重傳配合的演算法，在發生數據丟失時，發送方收到接收方發回的三個重復確認信息時，就把每次傳輸的數據量減為原來的一半，擁塞窗口也修改為這個值,然後又開始擁塞避免的演算法。

⑷ 常見的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（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擁塞控制演算法之NewReno和SACK

改進原因分析
TCP Reno 提出的快速恢復演算法提高了丟失報文後的吞吐量和頑健性，但是：

僅考慮了每次擁塞發生時只丟失一個報文的情形。
實際網路中，一旦發生擁塞，路由器會丟棄大量的報文，即一次擁塞中丟失多個報文的情形很普遍。

下圖是Reno演算法中快速恢復狀態和擁塞避免狀態之間的相互轉換：

所以，網路在一次擁塞中丟棄了多個報文，被TCP Reno錯誤地分析為傳輸中發生了多次擁塞。過度的窗口減小導致了傳輸超時的發生。因此為了提高一次擁塞中丟棄多個報文情形下TCP的性能，必須使TCP終端減少盲目削減發送窗口的行為。

New Reno：基於Reno演算法的改進
NewReno TCP在Reno TCP的基礎上對快速恢復演算法進行修改，只有一個數據包丟失的情況下，其機制和Reno是一樣的；當同時有多個包丟失時就顯示出了它的優勢。

Reno快速恢復演算法中發送方收到一個新的ACK就退出快速恢復狀態，New Reno演算法中只有當所有報文都被應答後才退出快速恢復狀態。

NewReno TCP添加了恢復應答判斷功能，以增強TCP終端通過ACK報文信息分析報文傳輸狀況的能力。
使TCP終端可以把一次擁塞丟失多個報文的情形與多次擁塞的情形區分開來，進而在每一次擁塞發生後擁塞窗口僅減半一次，從而提高了TCP的頑健性和吞吐量。

兩個概念：部分應答（PACK）、恢復應答（RACK）

記TCP發送端恢復階段中接收到的ACK報文（非冗餘ACK）為ACKx，記在接收到ACKx時TCP終端已發出的序列號（SN）最大的報文是PKTy，如果ACKx不是PKTy的應答報文，則稱報文ACKx為部分應答（Partial ACK，簡稱PACK）；若ACKx恰好是PKTy的應答報文則稱報文ACKx為恢復應答（Recovery ACK，簡稱RACK）。

舉例來理解：
如果4、5、6號包丟了，現在只重傳4，只收到了4的ACK，後面的5、6沒有確認，這就是部分應答Partial ACK。如果收到了6的ACK，則是恢復應答Recovery ACK。

TCP發送端接收到恢復應答表明：經過重傳，TCP終端發送的所有報文都已經被接收端正確接收，網路已經從擁塞中恢復。

NewReno發送端在收到第一個Partial ACK時，並不會立即結束Fast-recovery，而會持續地重送Partial ACK之後的數據包，直到將所有遺失的數據包重送後才結束Fast-recovery。收到一個Partial ACK時，重傳定時器就復位。這使得NewReno的發送端在網路有大量數據包遺失時不需等待Timeout就能更正此錯誤，減少大量數據包遺失對傳輸效果造成的影響。

NewReno大約每一個RTT時間可重傳一個丟失的數據包，如果一個發送窗口有M個數據包丟失，TCP NewReno的快速恢復階段將持續M個RTT。

改進的快速恢復演算法具體步驟：

快速恢復是基於數據包守恆的原則，即同一時刻能在網路中傳輸的數據包是恆定的，只有當舊數據包離開網路後，才能發送新數據包進入網路。一個重復ACK不僅意味著有一個包丟失了，還表示有發送的數據包離開了網路，已經在接收區的緩沖區中，不再佔用網路資源，於是將擁塞窗口加一個數據包大小。

Reno和NewReno演算法仍存在的問題？
雖然NewReno可以解決大量數據包遺失的問題，但是NewReno在每個RTT時間只能一個數據包遺失的錯誤。為了更有效地處理大量數據包遺失的問題，另一個解決方法就是讓傳送端知道哪些已經被接收端收到，但用此方法必須同時修改傳送端和接收端的傳送機制。

缺乏SACK演算法時發送端只能選擇兩種恢復策略：

TCP SACK在TCP Reno基礎上增加了：

當一個窗口內有多個數據包丟失時：

減少了時延，提高了網路吞吐量，使更快地從擁塞狀態恢復。

SACK中加入了一個SACK選項（TCP option field），允許接收端在返回Duplicate ACK時，將已經收到的數據區段（連續收到的數據范圍）返回給發送端，數據區段與數據區段之間的間隔就是接收端沒有收到的數據。發送端就知道哪些數據包已經收到，哪些該重傳，因此SACK的發送端可以在一個RTT時間內重傳多個數據包。

整個TCP選項長度不超過40位元組，實際最多不超過4組邊界值。

通過一個wireshark示例來說明接收端的SACK行為:

上圖中ACK確認序列號為12421，SACK的塊左邊界值為13801，SACK的塊右邊界值為15181。明確了這三個參數的數值，我們基本上就可以計算出被丟棄的數據報的序列號和長度了。通過上圖所示的帶有SACK的數據報文，我們可以知道被丟棄的數據報文的TCP序列號為12422，其數據長度為13801-12421=1380B。

改進的快速恢復演算法：

【參考文獻】：
吳文紅，李向麗.TCP擁塞控制機制定量性能分析.計算機工程與應用.2008,44(18)
孫偉，溫濤，馮自勤，郭權.基於TCP NewReno的穩態吞吐量分析模型.計算機研究與發展.2010
陳琳，雙雪芹.TCP網路擁塞控制演算法比較研究.長江大學學報.2010,3
許豫飛，TCP擁塞控制演算法集齊性能評估.北京郵電大學.2005,3
劉擁民，年曉紅.對SACK擁塞控制演算法的研究.信息技術.2003,9
焦程波，竇睿彧，蘭巨龍.無線網路中選擇性重傳機制性能分析與改進.計算機應用研究.2007.3
James F.Kurose,Keith W.Ross，Computer Networking A Top-Down Approach Sixth Edition.機械工業出版社

原文： https://blog.csdn.net/m0_38068229/article/details/80417503

⑺ 在TCP的擁塞控制中,什麼是慢開始、擁塞避免、快重傳和快恢復演算法

慢開始：在主機剛剛開始發送報文段時可先將擁塞窗口cwnd設置為一個最大報文段MSS的數值。在每收到一個對新的報文段的確認後，將擁塞窗口增加至多一個MSS的數值。

擁塞避免：當擁塞窗口值大於慢開始門限時，停止使用慢開始演算法而改用擁塞避免演算法。

快重傳演算法：發送端只要一連收到三個重復的ACK即可斷定有分組丟失了，就應該立即重傳丟手的報文段而不必繼續等待為該報文段設置的重傳計時器的超時。

接下來執行的不是慢啟動演算法而是擁塞避免演算法。這就是快速恢復演算法。.

防止擁塞的方法

（1）在傳輸層可採用：重傳策略、亂序緩存策略、確認策略、流控制策略和確定超時策略。

（2）在網路層可採用：子網內部的虛電路與數據報策略、分組排隊和服務策略、分組丟棄策略、路由演算法和分組生存管理。

（3）在數據鏈路層可採用：重傳策略、亂序緩存策略、確認策略和流控制策略。

⑻ 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演算法是基於大量的工程洞察力和運營網路中的擁塞控制實驗而開發的。