tcp控制演算法

⑴ 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擁塞控制中慢啟動演算法的閾值是怎麼確定的

閥值(threshold)，初始時該參數為64KB。當一次超時發生的時候，閥值被設置為當前擁塞窗口的一半，而擁塞窗口被重置為一個最大數據段。然後使用慢啟動演算法來決定網路的處理能力，不過當增長到閥值的時候便停止。從這個點開始，每一此成功的傳輸都會使擁塞窗口線性地增長(即每次突發數據僅增長一個最大數據段)，而不是成倍地增長。實際上，這個演算法是在猜測，將擁塞窗口減小一半可能是可以接受的，然後再從這點開始慢慢地往上增長。

如果不再發生超時的話，則擁塞窗口將繼續線性增長，知道達到接收方准許窗口的大小。在這個點上，它將停止增長，而且，只要不再發生超時並且接收方的窗口大小不改變大小，則擁塞窗口保持不變。順便提一下，如果一個ICMP SOURCE QUENCH分組到來並且被傳遞給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的擁塞控制中,什麼是慢開始、擁塞避免、快重傳和快恢復演算法

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

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

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

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

防止擁塞的方法

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

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

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

⑸ tcp擁塞控制常用演算法

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