karn演算法

1. tcp鍗忚瀹炵幇閲嶅彂鐨勬満鍒

閲嶄紶鏈哄埗鏄痶cp鏈閲嶈佸拰鏈澶嶆潅鐨勯棶棰樹箣涓
TCP姣忓彂閫佷竴涓鎶ユ枃孌碉紝灝卞硅繖涓鎶ユ枃孌佃劇疆涓涓璁℃椂鍣錛屽彧瑕佽℃椂鍣ㄨ劇疆鐨勯噸浼犳椂闂村埌浜嗚繕娌℃湁鏀跺埌紜璁わ紝灝辮侀噸浼犺繖涓鎶ユ枃孌點
tcp閲囩敤鑷閫傚簲綆楁硶錛屽氨鏄璁板綍姣忎竴涓鎶ユ枃孌靛彂鍑虹殑鏃墮棿錛屼互鍙婃敹鍒扮浉搴旂殑紜璁ゆ姤鏂囨電殑鏃墮棿銆傝繖涓や釜鏃墮棿宸灝辨槸鎶ユ枃孌電殑寰榪旀椂寤秗tt錛屾妸鍚勪釜鎶ユ枃孌電殑寰榪旀椂寤舵牱鏈鍔犳潈騫沖潎錛屽氨寰楀嚭鎶ユ枃孌電殑騫沖潎寰榪旀椂寤躲傛瘡嫻嬮噺鍒頒竴涓鏂扮殑rtt鏍鋒湰錛屽氨鎸変笅璇曢噸鏂拌＄畻涓嬈″鉤鍧噐tt錛
騫沖潎rtt=a*(鏃rtt錛+錛1-a錛*錛堟柊rtt鏍鋒湰錛 0銆=a<1; a 鍏稿瀷鍊間負7/8

璁℃椂鍣ㄨ劇疆鐨勮秴鏃墮噸浼犳椂闂磖to搴旂暐澶т簬涓婇潰鐨勫鉤鍧囧線榪旀椂寤秗tt
鍗 rto=b*rtt
tcp鍘熷厛鐨勬爣鍑嗘帹鑽愬惂b鍙2

鐢變簬濡傛灉鍙戝嚭涓涓猼cp鎶ユ枃孌1鍚庨噸浼犳椂闂村埌鍚庡湪閲嶆柊鍙戦佹姤鏂囨2 濡傛灉鏀跺埌紜璁ゆ姤鏂囨礎CK 鎴戜滑灝嗘棤娉曞垽鏂鏄瀵規姤鏂囨1 鐨勭『璁よ繕鏄2鐨勭『璁わ紙鎶ユ枃孌1鍜岄噸浼犳姤鏂囨2鏄瀹屽叏涓鏍風殑錛 鍥犳Karn鎻愬嚭浜嗕竴涓綆楁硶錛氬湪璁＄畻騫沖潎rtt鏃訛紝鍙瑕佹姤鏂囨甸噸浼犱簡錛屽氨涓嶉噰鍙栦竷寰榪旀椂寤舵牱鏈銆傝繖鏍峰緱鍑虹殑騫沖潎rtt鍜岄噸浼犳椂闂村氨杈冨噯紜 浣嗗張鍥犱負榪欐牱灝嗘棤娉曟洿鏂伴噸浼犳椂闂達紝鎵浠ヨ佸筀arn綆楁硶榪涜屼慨姝ｏ細鎶ユ枃孌墊瘡閲嶄紶涓嬈★紝灝卞皢閲嶄紶鏃墮棿澧炲ぇ涓浜
鏂扮殑閲嶄紶鏃墮棿=r*鏃х殑閲嶄紶鏃墮棿 r鐨勫吀鍨嬪間負2

2. 淺談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變化：