在tcp的擁塞控制演算法

A. tcp如何實現擁塞控制

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

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

1、慢開始演算法：

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

2、擁塞避免演算法：

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

3、快重傳演算法：

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

4、快恢復演算法：

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

B. 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開始開始。

C. tcp擁塞控制演算法包括

擁塞控制的演算法有：慢開始、擁塞避免、快重傳、快恢復。
慢開始和擁塞避免發送方維持一個擁塞窗口的狀態變數，其大小取決於網路的擁塞程度，動態地變化，而發送窗口一般取擁塞窗口和對方給出的接收窗口之間的最小值。慢開始演算法的核心是從小到大逐漸增大擁塞窗口的數值。

D. tcp擁塞控制常用演算法

tcp擁塞控制常用演算法方法如下
TCP協議有兩個比較重要的控制演算法，一個是流量控制，另一個就是阻塞控制。TCP協議通過滑動窗口來進行流量控制，它是控制發送方的發送速度從而使接受者來得及接收並處理。而擁塞控制是作用於網路，它是防止過多的包被發送到網路中，避免出現網路負載過大，網路擁塞的情況。擁塞演算法需要掌握其狀態機和四種演算法。擁塞控制狀態機的狀態有五種，分別是Open，Disorder，CWR，Recovery和Loss狀態。四個演算法為慢啟動，擁塞避免，擁塞發生時演算法和快速恢復。和TCP一樣，擁塞控制演算法也有其狀態機。當發送方收到一個Ack時，LinuxTCP通過狀態機(state)來決定其接下來的行為，是應該降低擁塞窗口cwnd大小，或者保持cwnd不變，還是繼續增加cwnd。

E. 常見的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本身攜帶的信息就可以使得發送方有足夠的信息來知道需要重傳哪些包，而不需要重傳哪些包。

F. TCP擁塞控制

以下資料參考：為了防止網路的擁塞現象，TCP提出了一系列的擁塞控制機制。最初由V. Jacobson在1988年的論文中提出的TCP的擁塞控制由「慢啟動(Slow start)」和「擁塞避免(Congestion avoidance)」組成，後來TCP Reno版本中又針對性的加入了「快速重傳(Fast retransmit)」、「快速恢復(Fast Recovery)」演算法，再後來在TCP NewReno中又對「快速恢復」演算法進行了改進，近些年又出現了選擇性應答( selective acknowledgement,SACK)演算法，還有其他方面的大大小小的改進，成為網路研究的一個熱點。TCP的擁塞控制主要原理依賴於一個擁塞窗口(cwnd)來控制，在之前我們還討論過TCP還有一個對端通告的接收窗口(rwnd)用於流量控制。窗口值的大小就代表能夠發送出去的但還沒有收到ACK的最大數據報文段，顯然窗口越大那麼數據發送的速度也就越快，但是也有越可能使得網路出現擁塞，如果窗口值為1，那麼就簡化為一個停等協議，每發送一個數據，都要等到對方的確認才能發送第二個數據包，顯然數據傳輸效率低下。TCP的擁塞控制演算法就是要在這兩者之間權衡，選取最好的cwnd值，從而使得網路吞吐量最大化且不產生擁塞。由於需要考慮擁塞控制和流量控制兩個方面的內容，因此TCP的真正的發送窗口=min(rwnd, cwnd)。但是rwnd是由對端確定的，網路環境對其沒有影響，所以在考慮擁塞的時候我們一般不考慮rwnd的值，我們暫時只討論如何確定cwnd值的大小。關於cwnd的單位，在TCP中是以位元組來做單位的，我們假設TCP每次傳輸都是按照MSS大小來發送數據的，因此你可以認為cwnd按照數據包個數來做單位也可以理解，所以有時我們說cwnd增加1也就是相當於位元組數增加1個MSS大小。慢啟動：最初的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重新設置為13.重新進入慢啟動過程。從整體上來講，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本身攜帶的信息就可以使得發送方有足夠的信息來知道需要重傳哪些包，而不需要重傳哪些包。

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

H. 如何在運行的內核中選擇tcp擁塞控制演算法

先查看本機支持的擁賽控制演算法，命令：
cat /proc/sys/net/ipv4/tcp_allowed_congestion_control
如果支持，再以root帳號運行命令：
echo "vegas" >/proc/sys/net/ipv4/tcp_congestion_control

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

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

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

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

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

防止擁塞的方法

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

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

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

J. 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