上文淺談TCP（1）：狀態(tài)機(jī)與重傳機(jī)制介紹了TCP的狀態(tài)機(jī)與重傳機(jī)制。本文介紹流量控制（Flow Control，簡稱流控）與擁塞控制（Congestion Control）。TCP依此保障網(wǎng)絡(luò)的QOS（Quality of Service）。
本文大部分內(nèi)容基于TCP 的那些事兒（下）修改而來，部分觀點(diǎn)與原文不同，重要地方增加了解釋。
TCP的流量控制
RTT算法
根據(jù)前文對TCP超時重傳機(jī)制的介紹，我們知道Timeout的設(shè)置對于重傳非常重要：
- 設(shè)長了，重發(fā)就慢，丟了老半天才重發(fā)，沒有效率，性能差。
- 設(shè)短了，會導(dǎo)致可能并沒有丟就重發(fā)。于是重發(fā)的就快，會增加網(wǎng)絡(luò)擁塞，導(dǎo)致更多的超時，更多的超時導(dǎo)致更多的重發(fā)。
而且，這個超時時間在不同的網(wǎng)絡(luò)環(huán)境下不同，必須動態(tài)設(shè)置。為此，TCP引入了RTT（Round Trip Time，環(huán)回時間）：一個數(shù)據(jù)包從發(fā)出去到回來的時間。這樣，發(fā)送端就大約知道正常傳輸需要多少時間，據(jù)此計算RTO（Retransmission TimeOut，超時重傳時間）。 聽起來似乎很簡單：在發(fā)送方發(fā)包時記下t0，收到接收方的Ack時記一個t1，于是RTT = t1 – t0。然而，這只是一個采樣，不能代表網(wǎng)絡(luò)環(huán)境的普遍情況。
經(jīng)典算法
RFC793 中定義了一個經(jīng)典算法：
首先，采樣RTT，記下最近幾次的RTT值。
-
然后，使用
加權(quán)移動平均算法（Weighted Moving Average Method）做平滑，計算SRTT（Smoothed RTT）：SRTT = ( α * SRTT ) + ((1- α) * RTT) (通常取0.8≤α≤0.9，α越大收斂速度越快) 最后，計算RTO：
RTO = min [ UBOUND, max [ LBOUND, (β * SRTT) ] ] (通常取1.3≤β≤2.0)
Karn / Partridge 算法
經(jīng)典算法描述了RTO計算的基本思路，但還有一個重要問題：RTT的采樣取“第一次發(fā)Seq+收Ack的時間”，還是“重傳Seq+收Ack的時間”？
如圖：
- 情況（a）中，RTT的采樣取“第一次發(fā)Seq+收Ack的時間”。假設(shè)第一次發(fā)的Seq徹底丟包了，則采樣到的時間多算了“從第一次發(fā)到重傳的間隔”。
- 情況（b）中，RTT的采樣取“重傳Seq+收Ack的時間”。假設(shè)是Ack傳輸?shù)穆瑢?dǎo)致恰好剛重傳就收到了接收方之前發(fā)出的Ack，則采樣到的時間少算了“從第一次發(fā)到重傳的間隔”。
問題的本質(zhì)是：發(fā)送方無法區(qū)分收到的Ack對應(yīng)第一次發(fā)的Seq還是重傳的Seq（進(jìn)入網(wǎng)絡(luò)就都一樣了）。針對該問題，Karn / Partridge算法選擇回避重傳的問題：忽略重傳的樣本，RTT的采樣只取未產(chǎn)生重傳的樣本。
簡單的忽略重傳樣本也有問題：假設(shè)當(dāng)前的RTO很小，突然發(fā)生網(wǎng)絡(luò)抖動，延時劇增導(dǎo)致要重傳所有的包；由于忽略重傳樣本，RTO不會被更新，于是繼續(xù)重傳使網(wǎng)絡(luò)更加擁堵；擁堵導(dǎo)致更多的重傳，惡性循環(huán)直至網(wǎng)絡(luò)癱瘓。Karn / Partridge算法用了一個取巧的辦法：只要一發(fā)生重傳，就將現(xiàn)有的RTO值翻倍（指數(shù)回退策略），待網(wǎng)絡(luò)恢復(fù)后再仿照經(jīng)典算法逐漸平滑以降低RTO。
該算法已經(jīng)做到可用，然而網(wǎng)絡(luò)抖動對性能的影響比較大。
Jacobson / Karels 算法
前面兩種算法均使用加權(quán)移動平均算法做平滑，這種方法的最大問題是：很難發(fā)現(xiàn)RTT值上的較大波動，因?yàn)楸黄交袅耍? - a比較小，即最新RTT的權(quán)重?。?。針對該問題，Jacobson / Karels算法引入了最新采樣的RTT值和平滑過的SRTT值的差距做因子，即DevRTT（Deviation RTT，RTT的偏離度），同時考慮SRTT帶來的慣性和DevRTT帶來的波動：
SRTT = SRTT + α(RTT – SRTT) —— 計算SRTT
DevRTT = (1-β)*DevRTT + β*(|RTT-SRTT|) —— 計算SRTT和最新RTT的差距（加權(quán)移動平均）
RTO= μ * SRTT + ? *DevRTT —— 同時考慮SRTT（慣性）與DevRTT（波動）
Linux 2.6采用該算法計算RTO，默認(rèn)取α = 0.125, β = 0.25, μ = 1, ? = 4（玄學(xué)調(diào)參，你懂的）。
TCP滑動窗口
TCP使用滑動窗口（Sliding Window）做流量控制與亂序重排。亂序重排在TCP的重傳機(jī)制中已經(jīng)介紹，下面介紹流量控制。
TCP頭里有一個字段叫Window（或Advertised Window），用于接收方通知發(fā)送方自己還有多少緩沖區(qū)可以接收數(shù)據(jù)。發(fā)送方根據(jù)接收方的處理能力來發(fā)送數(shù)據(jù)，不會導(dǎo)致接收方處理不過來，是謂流量控制。暫且把Advertised Window當(dāng)做滑動窗口，更容易理解滑動窗口如何完成流量控制，后面介紹擁塞控制時再說明二者的區(qū)別。
觀察TCP協(xié)議的發(fā)送緩沖區(qū)和接收緩沖區(qū)：
假設(shè)位置序號從左向右增長（常見的讀、寫緩沖區(qū)設(shè)計），解釋一下：
- 發(fā)送方：LastByteAcked指向收到的連續(xù)最大Ack的位置；LastByteSent指向已發(fā)送的最后一個字節(jié)的位置；LastByteWritten指向上層應(yīng)用已寫完的最后一個字節(jié)的位置。
- 接收方：LastByteRead指向上層應(yīng)用已讀完的最后一個字節(jié)的位置；NextByteExpected指向收到的連續(xù)最大Seq的位置；LastByteRcvd指向已收到的最后一個字節(jié)的位置?？梢钥吹?strong>NextByteExpected與LastByteRcvd中間有些Seq還沒有到達(dá)，對應(yīng)空白區(qū)。
據(jù)此在接收方計算AdvertisedWindow，在發(fā)送方計算EffectiveWindow：
- 接收方在Ack中記錄自己的
AdvertisedWindow = MaxRcvBuffer – (LastByteRcvd - LastByteRead)，隨Ack回復(fù)到發(fā)送方。 - 發(fā)送方根據(jù)Ack中的AdvertisedWindow值，需保證
LastByteSent - LastByteAcked ≤ AdvertisedWindow，則窗口內(nèi)剩余可發(fā)送的數(shù)據(jù)大小EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)，以保證接收方可以處理。
AdvertisedWindow與EffectiveWindow
AdvertisedWindow衡量接收方還能接收的數(shù)據(jù)量，發(fā)送方要根據(jù)AdvertisedWindow決定接下來發(fā)送的數(shù)據(jù)量上限，即EffectiveWindow（可能為0）。
AdvertisedWindow的計算
由于亂序問題的存在，LastByteRcvd可能指向Seq(LastByteSent)，而Seq(LastByteAcked + 1)至Seq(LastByteSent - 1)都還在路上，即將到達(dá)接收方，最好的情況是不丟包（丟包后會重傳），則LastByteRcvd之后、接收緩沖區(qū)邊界之前的空間就是發(fā)送方下一次發(fā)送數(shù)據(jù)的長度上限（重傳不屬于下一次發(fā)送），因此，AdvertisedWindow = MaxRcvBuffer – (LastByteRcvd - LastByteRead)。
EffectiveWindow的計算
LastByteRcvd還可能指向Seq(LastByteAcked)（一個新包都沒有收到），顯然AdvertisedWindow的公式不變，而Seq(LastByteAcked + 1)至Seq(LastByteSent)都還在路上，未來將到達(dá)接收方，進(jìn)入接收緩沖區(qū)，則“還在路上的Seq(LastByteAcked + 1)至Seq(LastByteSent)”不應(yīng)超過接收緩沖區(qū)的剩余空間AdvertisedWindow（目前等于MaxRcvBuffer），這要求的是上一次發(fā)送滿足LastByteSent - LastByteAcked ≤ AdvertisedWindow，那么LastByteSent之后、接收緩沖區(qū)剩余空間邊界之前的空間就是發(fā)送方窗口內(nèi)剩余可發(fā)送數(shù)據(jù)的長度上限，因此，EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)。
當(dāng)然，EffectiveWindow最小取0。
示例1
以下是一個發(fā)送緩沖區(qū)的滑動窗口：
上圖分為4個部分：
-
#1是已發(fā)送已確認(rèn)的數(shù)據(jù)，即LastByteAcked之前的區(qū)域。 -
#2是已發(fā)送未確認(rèn)的數(shù)據(jù)，即LastByteAcked與LastByteSent之間的區(qū)域，大小不超過AdvertisedWindow。 -
#3是窗口內(nèi)未發(fā)送的數(shù)據(jù)，即LastByteSent與窗口右界之間的區(qū)域，大小等于EffectiveWindow（可能為0）。 -
#4是窗口外未發(fā)送的數(shù)據(jù)，即窗口右界與LastByteWritten之間的區(qū)域。
其中，#2 + #3組成了滑動窗口，總大小不超過AdvertisedWindow，二者比例受到接收方的處理速度與網(wǎng)絡(luò)情況的影響（如果丟包嚴(yán)重或處理速度慢于發(fā)送速度，則#2:#3會越來越大）。
示例2
以下是一個AdvertisedWindow的調(diào)整過程，EffectiveWindow隨之變化：
Zero Window
理解有問題，不要求掌握。
上圖，我們可以看到一個處理緩慢的Server（接收端）是怎么把Client（發(fā)送端）的發(fā)送窗口size給降成0的。對于接收方來說，此時接收緩沖區(qū)確實(shí)已經(jīng)滿了，因此令發(fā)送方的發(fā)送窗口size降為0以暫時禁止發(fā)送是合理的。那么，等接收方的接收緩沖區(qū)再空出來，怎么通知發(fā)送方新的window size呢？
針對這個問題，為TCP設(shè)計了ZWP技術(shù)（Zero Window Probe，零窗通告）：發(fā)送方在窗口變成0后，會發(fā)ZWP的包給接收方，讓接收方來Ack他的Window尺寸；ZWP的重傳也遵循指數(shù)回退策略，默認(rèn)重試3次；如果3次后window size還是0，則認(rèn)為接收方出現(xiàn)異常，發(fā)RST重置連接（<font color="red">部分文章寫的是重試到window size正常？？？</font>）。
注意：只要有等待的地方都可能出現(xiàn)DDoS攻擊，Zero Window也不例外。一些攻擊者會在和服務(wù)端建好連接發(fā)完GET請求后，就把Window設(shè)置為0，于是服務(wù)端就只能等待進(jìn)行ZWP；然后攻擊者再大量并發(fā)發(fā)送ZWP，把服務(wù)器端的資源耗盡。（<font color="red">客戶端等待怎么耗服務(wù)端？？？</font>）
TCP的擁塞控制
通信中的擁塞指：
到達(dá)通信子網(wǎng)中某一部分的分組數(shù)量過多，使得該部分網(wǎng)絡(luò)來不及處理，以致引起這部分乃至整個網(wǎng)絡(luò)性能下降的現(xiàn)象，嚴(yán)重時甚至?xí)?dǎo)致網(wǎng)絡(luò)通信業(yè)務(wù)陷入停頓即出現(xiàn)死鎖。
為什么要進(jìn)行擁塞控制？假設(shè)網(wǎng)絡(luò)已經(jīng)出現(xiàn)擁塞，如果不處理擁塞，那么延時增加，出現(xiàn)更多丟包，觸發(fā)發(fā)送方重傳數(shù)據(jù)，加劇擁塞情況，繼續(xù)惡性循環(huán)直至網(wǎng)絡(luò)癱瘓?？芍?，擁塞控制與流量控制的適應(yīng)場景和目的均不同。
擁塞發(fā)生前，可避免流量過快增長拖垮網(wǎng)絡(luò)；擁塞發(fā)生時，唯一的選擇就是降低流量。主要使用4種算法完成擁塞控制：
- 慢啟動
- 擁塞避免
- 擁塞發(fā)生
- 快速恢復(fù)
算法1、2適用于擁塞發(fā)生前，算法3適用于擁塞發(fā)生時，算法4適用于擁塞解決后（相當(dāng)于擁塞發(fā)生前）。
rwnd與cwnd
在正式介紹上述算法之前，先補(bǔ)充下rwnd（Receiver Window，接收者窗口）與cwnd（Congestion Window，擁塞窗口）的概念：
- rwnd是用于流量控制的窗口大小，即上述流量控制中的AdvertisedWindow，主要取決于接收方的處理速度，由接收方通知發(fā)送方被動調(diào)整（詳細(xì)邏輯見上）。
- cwnd是用于擁塞處理的窗口大小，取決于網(wǎng)絡(luò)狀況，由發(fā)送方探查網(wǎng)絡(luò)主動調(diào)整。
介紹流量控制時，我們沒有考慮cwnd，認(rèn)為發(fā)送方的滑動窗口最大即為rwnd。實(shí)際上，需要同時考慮流量控制與擁塞處理，則發(fā)送方窗口的大小不超過min{rwnd, cwnd}。下述4種擁塞控制算法只涉及對cwnd的調(diào)整，同介紹流量控制時一樣，暫且不考慮rwnd，假定滑動窗口最大為cwnd；但讀者應(yīng)明確rwnd、cwnd與發(fā)送方窗口大小的關(guān)系。
4種擁塞控制算法
慢啟動算法
慢啟動算法（Slow Start）作用在擁塞產(chǎn)生之前：對于剛剛加入網(wǎng)絡(luò)的連接，要一點(diǎn)一點(diǎn)的提速，不要妄圖一步到位。如下：
- 連接剛建好，初始化cwnd = 1（當(dāng)然，通常不會初始化為1，太小），表明可以傳一個MSS大小的數(shù)據(jù)。
- 每收到一個ACK，cwnd++，線性增長。
- 每經(jīng)過一個RTT，cwnd = cwnd * 2，指數(shù)增長（主要增長來源）。
- 還有一個ssthresh（slow start threshold），當(dāng)cwnd >= ssthresh時，就會進(jìn)入擁塞避免算法（見后）。
因此，如果網(wǎng)速很快的話，Ack返回快，RTT短，那么，這個慢啟動就一點(diǎn)也不慢。下圖說明了這個過程：
擁塞避免算法
前面說過，當(dāng)cwnd >= ssthresh（通常ssthresh = 65535）時，就會進(jìn)入擁塞避免算法（Congestion Avoidance）：緩慢增長，小心翼翼的找到最優(yōu)值。如下：
- 每收到一個Ack，cwnd = cwnd + 1/cwnd，顯然，cwnd > 1時無增長。
- 每經(jīng)過一個RTT，cwnd++，線性增長（主要增長來源）。
慢啟動算法主要呈指數(shù)增長，粗獷型，速度快（“慢”是相對于一步到位而言的）；而擁塞避免算法主要呈線性增長，精細(xì)型，速度慢，但更容易在不導(dǎo)致?lián)砣那闆r下，找到網(wǎng)絡(luò)環(huán)境的cwnd最優(yōu)值。
擁塞發(fā)生時的算法
慢啟動與擁塞避免算法作用在擁塞發(fā)生前，采取不同的策略增大cwnd；如果已經(jīng)發(fā)生擁塞，則需要采取策略減小cwnd。那么，TCP如何判斷當(dāng)前網(wǎng)絡(luò)擁塞了呢？很簡單，如果發(fā)送方發(fā)現(xiàn)有Seq發(fā)送失敗（表現(xiàn)為“丟包”），就認(rèn)為網(wǎng)絡(luò)擁塞了。
丟包后，有兩種重傳方式，對應(yīng)不同的網(wǎng)絡(luò)情況，也就對應(yīng)著兩種擁塞發(fā)生時的控制算法：
- 超時重傳。TCP認(rèn)為這種情況太糟糕，調(diào)整力度比較大：
- ssthresh = cwnd /2
- cwnd = 1，重新進(jìn)入慢啟動過程（網(wǎng)絡(luò)糟糕，要慢慢調(diào)整）
- 快速重傳。TCP認(rèn)為這種情況通常比RTO超時好一些，主流實(shí)現(xiàn)TCP Reno的調(diào)整力度更柔和（TCP Tahoe的實(shí)現(xiàn)和RTO超時一樣暴躁）：
- ssthresh = cwnd /2
- cwnd = cwnd /2，進(jìn)入快速恢復(fù)算法（網(wǎng)絡(luò)沒那么糟，可以快速調(diào)整，見下）
可以看到，不管是哪種重傳方式，ssthresh都會變成cwnd的一半，仍然是指數(shù)回退，待擁塞消失后再逐漸增長回到新的最優(yōu)值，總體上在最優(yōu)值（動態(tài)）附近震蕩。
回退后，根據(jù)不同的網(wǎng)絡(luò)情況，可以選擇不同的恢復(fù)算法。慢啟動已經(jīng)介紹過了，下面介紹快速恢復(fù)算法。
快速恢復(fù)算法
如果觸發(fā)了快速重傳，即發(fā)送方收到至少3次相同的Ack，那么TCP認(rèn)為網(wǎng)絡(luò)情況不那么糟，也就沒必要提心吊膽的，可以適當(dāng)大膽的恢復(fù)。為此設(shè)計快速恢復(fù)算法（Fast Recovery），下面介紹TCP Reno中的實(shí)現(xiàn)。
回顧一下，進(jìn)入快速恢復(fù)之前，cwnd和sshthresh已被更新：
- ssthresh = cwnd /2
- cwnd = cwnd /2
然后，進(jìn)入快速恢復(fù)算法：
- cwnd = ssthresh + 3 * MSS （嘗試一步到位）
- 重傳重復(fù)Ack對應(yīng)的Seq
- 如果再收到該重復(fù)Ack，則cwnd++，線性增長（緩慢調(diào)整）
- 如果收到了新Ack，則cwnd = ssthresh ，然后就進(jìn)入了擁塞避免的算法了（<font color="red">為什么收到新Ack要降低sshthresh？？？</font>）
可暫時忽略的內(nèi)容：
這種實(shí)現(xiàn)也有問題：依賴于3個重復(fù)Ack?；貞浬衔挠懻摰摹爸貍饕粋€還是重傳所有的問題”，3個重復(fù)Ack并不代表只丟了一個數(shù)據(jù)包，很有可能是丟了好多包。顯然快速恢復(fù)算法選擇“重傳一個”，而剩下的那些包只能等到RTO超時。于是，超時一個窗口就減半一下，多個超時會超成TCP的傳輸速度指數(shù)級下降；同時，超時重傳不會觸發(fā)快速恢復(fù)算法，慢啟動很容易加劇超時的情況，進(jìn)入惡性循環(huán)。
示例
下面看一個簡單的圖示，感受擁塞控制過程中的cwnd變化：
參考：
本文鏈接：淺談TCP（2）：流量控制與擁塞控制
作者：猴子007
出處：https://monkeysayhi.github.io
本文基于 知識共享署名-相同方式共享 4.0 國際許可協(xié)議發(fā)布，歡迎轉(zhuǎn)載，演繹或用于商業(yè)目的，但是必須保留本文的署名及鏈接。
