當前位置:首頁 » 操作系統 » 手機tcp擁塞演算法選擇

手機tcp擁塞演算法選擇

發布時間: 2022-11-27 23:45:43

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

以下資料參考:為了防止網路的擁塞現象,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本身攜帶的信息就可以使得發送方有足夠的信息來知道需要重傳哪些包,而不需要重傳哪些包。

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

擁塞控制:防止過多的數據注入到網路中,這樣可以使網路中的路由器或鏈路不致過載。擁塞控制所要做的都有一個前提:網路能夠承受現有的網路負荷。擁塞控制是一個全局性的過程,涉及到所有的主機、路由器,以及與降低網路傳輸性能有關的所有因素。流量控制:指點對點通信量的控制,是端到端正的問題。流量控制所要做的就是抑制發送端發送數據的速率,以便使接收端來得及接收

㈣ 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在連接建立成功後會向網路中發送大量的數據包,這樣很容易導致網路中路由器緩存空間耗盡,從而發生擁塞。因此新建立的連接不能夠一開始就大量發送數據包,而只能根據網路情況逐步增加每次發送的數據量,以避免上述現象的發生。具體來說,當新建連接時,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擁塞控制演算法

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

㈧ 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。

㈨ tcp如何實現擁塞控制

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

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

1、慢開始演算法:

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

2、擁塞避免演算法:

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

3、快重傳演算法:

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

4、快恢復演算法:

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

熱點內容
linuxi2c驅動 發布:2024-03-29 18:09:56 瀏覽:671
junit源碼下載 發布:2024-03-29 18:00:10 瀏覽:525
本田雅閣壓縮機不工作 發布:2024-03-29 17:59:13 瀏覽:600
溯源碼可以偽造嗎 發布:2024-03-29 17:54:45 瀏覽:56
北京編程傳 發布:2024-03-29 17:54:44 瀏覽:435
編程畫曲線 發布:2024-03-29 17:48:59 瀏覽:59
簡單存儲服務s3 發布:2024-03-29 17:48:46 瀏覽:336
安卓手機的usb功能在哪裡設置 發布:2024-03-29 17:46:27 瀏覽:758
配置文件ini如何寫 發布:2024-03-29 17:31:05 瀏覽:997
如何更改微信密碼修改 發布:2024-03-29 17:24:49 瀏覽:588