A. 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實時大數據傳輸之痛》。
B. 擁塞演算法
基於包丟失檢測的 Reno、NewReno 或者 cubic 為代表,其主要問題有 Buffer bloat 和長肥管道兩種。和這些演算法不同,bbr 演算法會以時間窗口內的最大帶寬 max_bw 和最小 RTT min_rtt,並以此計算發送速率和擁塞窗口
RTProp : round-trip propagation time BtlBW : bottleneck bandwidth,bbr 演算法關於擁塞窗口的核心就是計算 BtlBW 和 RTprop,根據這兩者值計算 BDP
bbr 演算法輸出 pacing_rate 和 cwnd 兩個數據。pacing_rate 決定發包速率,cwnd 為窗口大小
TCP Tahoe 和 Reno
這兩個演算法是根據其第一次加入到4.3BSD的時間回溯命名的,兩個名字對應自其第一次出現時BSD的代號,而代號分別取自太浩湖(Lake Tahoe)和其附近的城市裡諾市
• Tahoe:如果收到三次重復確認——即第四次收到相同確認號的分段確認,並且分段對應包無負載分段和無改變接收窗口——的話,Tahoe演算法則進入快速重傳,將慢啟動閾值改為當前擁塞窗口的一半,將擁塞窗口降為1個MSS,並重新進入慢啟動階段
• Reno:如果收到三次重復確認,Reno演算法則進入快速重傳,只將擁塞窗口減半來跳過慢啟動階段,將慢啟動閾值設為當前新的擁塞窗口值,進入一個稱為「快速恢復」的新設計階段
Fast recovery
是Reno演算法新引入的一個階段,在將丟失的分段重傳後,啟動一個超時定時器,並等待該丟失分段包的分段確認後,再進入擁塞控制階段。如果仍然超時,則回到慢啟動階段
TCP Vegas
至1990年代中期,TCP量度延遲和RTT都是以傳輸緩存中最後一個被傳送的分段包為准。vegas通過度量傳輸緩存中每個傳送分段包來代替只量度一個分段包,通過每次度量的平均值來增加擁塞窗口。該演算法取名自內華達州最大的城市拉斯維加斯。不過由於一些資源公平性原因,該演算法並沒有在彼得森的實驗室之外廣泛部署。一些研究認為該演算法和其他擁塞演算法混合使用,可能會導致性能競爭不及其他演算法。在各種TCP擁塞演算法的比較研究中,Vegas被認為是最平滑的控制演算法,其次為CUBIC
TCP New Reno
TCP New Reno是對TCP Reno中快速恢復階段的重傳進行改善的一種改進演算法,其定義於RFC 6582,覆蓋了原有在RFC 3782和RFC 2582的舊定義。
在Reno的快速恢復中,一旦出現3次重復確認,TCP發送方會重發重復確認對應序列號的分段並設置定時器等待該重發分段包的分段確認包,當該分段確認包收到後,就立即退出快速恢復階段,進入擁塞控制階段,但如果某個導致重復確認的分段包到遇到重復確認期間所發送的分段包存在多個丟失的話,則這些丟失只能等待超時重發,並且導致擁塞窗口多次進入擁塞控制階段而多次下降。而New Reno的快速恢復中,一旦出現3次重復確認,TCP發送方先記下3次重復確認時已發送但未確認的分段的最大序列號,然後重發重復確認對應序列號的分段包。如果只有該重復確認的分段丟失,則接收方接收該重發分段包後,會立即返回最大序列號的分段確認包,從而完成重發;但如果重復確認期間的發送包有多個丟失,接收方在接收該重發分段後,會返回非最大序列號的分段確認包,從而發送方繼續保持重發這些丟失的分段,直到最大序列號的分段確認包的返回,才退出快速恢復階段。
New Reno在低錯誤率時運行效率和「選擇確認」(Selective ACKnowledgement,SACK)相當,在高錯誤率仍優於Reno
TCP Hybla
TCP Hybla旨在消除由於高延遲地面線路或者衛星無線鏈路下導致的RTT過長而對TCP鏈接的影響。它通過對擁塞窗口動態分析來修改,來減少對RTT的性能依賴
TCP BIC 和 CUBIC
TCP BIC(Binary Increase Congestion control)旨在優化高速高延遲網路(即根據RFC 1072所定義的「長肥網路」(long fat network,LFN))的擁塞控制,其擁塞窗口演算法使用二分搜索演算法嘗試找到能長時間保持擁塞窗口最大值的值。Linux內核在2.6.8至2.6.18使用該演算法作為默認TCP擁塞演算法。
CUBIC則是比BIC更溫和和系統化的分支版本,其使用三次函數代替二分演算法作為其擁塞窗口演算法,並且使用函數拐點作為擁塞窗口的設置值。Linux內核在2.6.19後使用該演算法作為默認TCP擁塞演算法
TCP Westwood和Westwood+
TCP Westwood改良自New Reno,不同於以往其他擁塞控制演算法使用丟失來測量,其通過對確認包測量來確定一個「合適的發送速度」,並以此調整擁塞窗口和慢啟動閾值。其改良了慢啟動階段演算法為「敏捷探測(Agile Probing)」,和設計了一種持續探測擁塞窗口的方法來控制進入「敏捷探測」,使鏈接盡可能地使用更多的帶寬。Westwood+使用更長的帶寬估計間隔和優化的濾波器來修正Westwood對ACK壓縮場景對帶寬估計過高的問題。通過以上改良,TCP Westwood系列演算法在有線網路和無線網路的擁塞控制上獲取平衡,尤其研究中針對於無線通信網路上
Compound TCP
復合TCP(Compound TCP)是微軟自己實現的TCP擁塞控制演算法,通過同時維護兩個擁塞窗口,來實現在長肥網路有較好的性能而又不損失公平性。該演算法在Windows Vista和Windows Server 2008開始廣泛部署,並通過補丁的方式回溯支持到Windows XP和Windows Server 2003。在Linux上也有一個舊版本的移植實現
TCP PRR
TCP PRR(TCP Proportional Rate Rection )是旨在恢復期間提高發送數據的准確性。該演算法確保恢復後的擁塞窗口大小盡可能接近慢啟動閾值。在Google進行的測試中,能將平均延遲降低3~10%,恢復的超時減少5%。PRR演算法之後作為Linux內核3.2版本的默認擁塞演算法
TCP BBR
TCP BBR(Bottleneck Bandwidth and Round-trip propagation time)是由Google設計,於2016年發布的擁塞演算法。以往大部分擁塞演算法是基於丟包來作為降低傳輸速率的信號,而BBR則基於模型主動探測。該演算法使用網路最近出站數據分組當時的最大帶寬和往返時間來創建網路的顯式模型。數據包傳輸的每個累積或選擇性確認用於生成記錄在數據包傳輸過程和確認返回期間的時間內所傳送數據量的采樣率。該演算法認為隨著網路介面控制器逐漸進入千兆速度時,與緩沖膨脹相關的延遲相比丟包更應該被認為是識別擁塞的主要決定因素,所以基於延遲模型的擁塞控制演算法(如BBR)會有更高的吞吐量和更低的延遲,可以用BBR來替代其他流行的擁塞演算法,例如CUBIC
QUIC Quick UDP Internet Connections
QUIC旨在提供幾乎等同於TCP連接的可靠性,但延遲大大減少。它主要通過兩個理解HTTP流量的行為來實現這一點:
第一個變化是在連接創建期間大大減少開銷。由於大多數HTTP連接都需要TLS,因此QUIC使協商密鑰和支持的協議成為初始握手過程的一部分。 當客戶端打開連接時,伺服器響應的數據包包括將來的數據包加密所需的數據。
QUIC使用UDP協議作為其基礎,不包括丟失恢復。相反,每個QUIC流是單獨控制的,並且在QUIC級別而不是UDP級別重傳丟失的數據。這意味著如果在一個流中發生錯誤,協議棧仍然可以獨立地繼續為其他流提供服務
QUIC包括許多其他更普通的更改,這些更改也可以優化整體延遲和吞吐量
每個數據包是單獨加密的,因此加密數據時不需要等待部分數據包。 在TCP下通常不可能這樣做,其中加密記錄在位元組流中,並且協議棧不知道該流中的更高層邊界。這些可以由運行在更上層的協議進行協商,但QUIC旨在通過單個握手過程完成這些
QUIC的另一個目標是提高網路切換期間的性能,例如當移動設備的用戶從WiFi熱點切換到移動網路時發生的情況。 當這發生在TCP上時,一個冗長的過程開始了:每個現有連接一個接一個地超時,然後根據需要重新創建。期間存在較高延遲,因為新連接需要等待舊連接超時後才會創建。 為解決此問題,QUIC包含一個連接標識符,該標識符唯一地標識客戶端與伺服器之間的連接,而無論源IP地址是什麼。這樣只需發送一個包含此ID的數據包即可重新創建連接,因為即使用戶的IP地址發生變化,原始連接ID仍然有效
QUIC在應用程序空間中實現,而不是在操作系統內核中實現。當數據在應用程序之間移動時,這通常會由於上下文切換而調用額外的開銷。 但是在QUIC下協議棧旨在由單個應用程序使用,每個應用程序使用QUIC在UDP上託管自己的連接
Chromium的網路堆棧同時打開QUIC和傳統TCP連接,並在QUIC連接失敗時以零延遲回退到TCP連接
C. 常見的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本身攜帶的信息就可以使得發送方有足夠的信息來知道需要重傳哪些包,而不需要重傳哪些包。
D. 淺談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變化:
E. 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開始開始。
F. tcp如何實現擁塞控制
TCP擁塞控制是傳輸控制協議(英語:Transmission Control Protocol,縮寫TCP)避免網路擁塞的演算法,是互聯網上主要的一個擁塞控制措施。它使用一套基於線增積減模式的多樣化網路擁塞控制方法(包括慢啟動和擁塞窗口等模式)來控制擁塞。在互聯網上應用中有相當多的具體實現演算法。
在TCP中,擁塞窗口(congestion window)是任何時刻內確定能被發送出去的位元組數的控制因素之一,是阻止發送方至接收方之間的鏈路變得擁塞的手段。他是由發送方維護,通過估計鏈路的擁塞程度計算出來的,與由接收方維護的接收窗口大小並不沖突。
1、慢開始演算法:
簡單的說,開始傳輸時,傳輸的數據由小到大遞增到一個值(即發送窗口由小到大(指數增長)逐漸增大到擁塞窗口的數值)。
2、擁塞避免演算法:
數據發送出去,並發到接收方發回來的確認收到,擁塞窗口每次值加1地線性增大。
3、快重傳演算法:
數據傳輸時(數據被分成報文,每個報文都有個序號),中間的一部分丟失接收方沒收到,接收方連續接到後面的數據,則發回對丟失前的數據的重復確認,這樣發送方就知道有部分數據丟失了,於是從丟失出重傳數據。
4、快恢復演算法:
快恢復是與快重傳配合的演算法,在發生數據丟失時,發送方收到接收方發回的三個重復確認信息時,就把每次傳輸的數據量減為原來的一半,擁塞窗口也修改為這個值,然後又開始擁塞避免的演算法。