TCP/IP

TCP 壅塞控制 (Congestion Control)

TCP 流量控制 (Flow Control),是為避免 高速傳送端 癱瘓 低速接收端。
TCP 壅塞控制 (Congestion Control),則是用於避免 高速傳送端 癱瘓 網路
 
本篇主要介紹 TCP 壅塞控制 常見的四種基本演算法:

慢啟動 (Slow Start)、壅塞避免 (Congestion Avoidance)、

快速重送 (Fast Retransmit) 和 快速恢復 (Fast Recovery)

 
以及,為了實現這些算法,
為每個 TCP 連接,新增的兩個狀態變數:

  • 壅塞視窗 (Congestion Window, cwnd)
  • 慢啟動門檻 (Slow Start Threshold, ssthresh)

 
儘管這些演算法,漸漸被認為 不合時宜
仍可視為 前車之鑒,以了解其他解法。
 


 

壅塞偵測 (Congestion Detection)

任何 壅塞控制 演算法,必須解決的問題是:

網絡,沒有獲取「給定連線的可用頻寬」之機制

 
因此 TCP 壅塞控制 (Congestion Control) 必須以某種方式,
得出關於「在任何給定時間內,可以發送多少資料」的結論,
以調整傳送速率至最佳效能,而不癱瘓 網路
 
偵測方式:
 
 

1. 基於遺失 (Loss-based)

網際網路 (Internet),將全球數億的裝置與網路,
以 交換器、路由器…等多種設備,鏈結編織而成。
 
路由器 (Router),使用 佇列 來儲存封包,
拆裝、封裝、決定最佳路徑 並 轉送封包…。
 
然而:

佇列 (緩衝區) 並非無限大,若緩衝區滿溢,之後送來的封包難保不被丟棄。

 
許多傳輸層協定 (含 TCP),具有 重送 (Retransmission) 機制,
丟棄封包,並不會使網路上的封包數量減少,甚至可能增加,造成嚴重的效能耗損。
(現今,不丟棄封包 產生的耗損可能更大…)
 
傳統 TCP 將計就計,將 封包遺失 視為 壅塞 的徵兆,以調整傳輸速率:

判別 當 TCP區段 遺失 時,接收端 採取以下何種 重送機制,以執行對應策略
— — 逾時重送 (Retransmission Timeout)、快速重送 (Fast Retransmission)。

 
這是因為:

在網際網路平穩運行時,TCP 傳輸錯誤的比例很低,
當區段遺失時,TCP 假設遺失是 壅塞 所造成。

 

當 接收端 使用 逾時重送 (Retransmission Timeout):
表示 接收端 在 逾時之前,未收到 3 個 區段送回的 確認 (ACK) 遺失 — — 壅塞嚴重 的徵兆

當 接收端 使用 快速重送 (Fast Retransmit):
表示 接收端 在 逾時之前,已收到 3 個 區段 — — 壅塞輕微 的徵兆

 
 

緩衝區膨脹 (bufferbloat)

1980s 以來,基於遺失 (Loss-based) 一直做為 壅塞控制 演算法 標準,
並沿用至今 (e.g., 慢啟動、壅塞避免、快速重送/恢復)。
 
為使 壅塞控制 正常運作,
必須 及時回饋 封包遺失 的訊息,使 傳送端 能選擇合適的傳輸速率。
 
隨著科技進步,記憶體價格下跌,
處處充滿了 大型緩衝區 的網路設備,
這對 基於遺失 的壅塞控制 演算法 造成巨大的問題。
 
大型的緩衝區,使 封包 不易被丟棄,而是在佇列中緩慢地等待,
TCP 傳送端 並不知道 壅塞的發生,仍持續成長 傳輸速率,
使網路 產生 高延遲、吞吐量下降 的惡性循環,
這就是惡名昭彰的 — — 緩衝區膨脹 (bufferbloat)
highway
 

Bloated buffers lead to network-crippling latency spikes.
— — Bufferbloat.net

 

2. 其他

不幸的,在今日的互聯網背景,
儘管是較好的實作 — — TCP CUBIC,
或其他 基於遺失 (Loss-based) 壅塞控制 (e.g., TCP (new)Reno),
仍造成嚴重的 緩衝區膨脹 (bufferbloat)
 
於是,各種不同的 壅塞偵測 方法孕育而生,
基於延遲 (Delay-based) 的 TCP Vegas、FAST TCP、LEDBAT…,
基於壅塞 (Congestion-based) 的 瓶頸頻寬與往返時間 (Bottleneck Bandwidth and RTT, BBR) 演算法。
(有些人認為仍是 基於延遲 or 基於頻寬延遲乘積 BDP)
 
儘管如此,不同版本之間可能產生許多問題,
如: 許多人認為 BBR 封包遺失,會餓死 CUBIC…,
要統一版本更是困難重重。

基於遺失 的壅塞控制,漸漸被視為 不合時宜
但是否會被完全取代,仍是未知數。

 


 

最大傳輸單元 vs. 最大區段長度
(MTU vs. MSS)

 
在介紹 壅塞控制 演算法 前,得先認識 最大區段長度 (MSS)
TCP 傻瓜視窗症候群 (Silly Window Syndrome, SWS) 一文:

最大區段長度 (Maximum Segment Size, MSS),雙方會在連線建立時決定,
且這條連線運作期間街不會改變,若其中一方未定義,則使用預設值: 536 bytes
 
可別被他的名字唬了,它定義的是所能接收資料』的最大長度,而非區段!
(即不包含 TCP 表頭 + 選項)

 
而在 最大傳輸單元 (Maximum Transmission Unit, MTU) 中,介紹了 MTU 與 MSS 的關係:

不同的 資料鏈結/實體 層,擁有不同的 MTU 大小,
最常見的 為 乙太網路 (Ethernet)1500 個位元組。
 
TCP 透過 路徑 MTU 探索 (Path MTU Discovery)、其他演算法 或 經驗法則,
調整 最大區段長度 (Maximum Segment Size, MSS)。

 
最簡單的算法:

MSS = MTU - 20 octet (TCP 固定表頭) - 20 octet (IP 固定表頭)

以 乙太網路 MTU 1500 為例,
常見的 MSS 有 1460、1400、1380…。
 
 

資料的限制傳送量

可惜的是,很多人對 MSS 的認識也就到此為止 😂,
事實上,它不止用於「預防 IP 分段」,
更做為 壅塞控制 計算「資料的限制傳送量」的重要單位
 
 

以 MSS 為 1460 為例:

若 「資料的限制傳送量」為 1460 * 3 = 4380 (位元組),
代表 傳送端 在接收到 ACK 前,一次至多傳輸 3 個區段。
 
這是待會會用到的術語:

SMSS 表 傳送端 MSS (SENDER MAXIMUM SEGMENT SIZE),

RMSS 表 接收端 MSS (RECEIVER MAXIMUM SEGMENT SIZE),

飛行大小 (FLIGHT SIZE),網路中 的 未完成資料量,可想成資料在飛行中 🤔?

而 全尺寸區段 (FULL-SIZED SEGMENT) 即資料為 SMSS 大小的區段。

 
未完成資料 (outstanding data) 意指:

已發送,但尚未被 確認 (ACK) 的區段。

 


 

壅塞視窗 (Congestion Window, cwnd)

上節提到的「資料的限制傳送量」,
即鼎鼎大名的 — — 壅塞視窗 (Congestion Window, cwnd):

在接收到 確認 (ACK) 區段前,傳送端 能夠傳輸的最大資料總量。

 
如上所述,cwnd 「概念上」時常以 MSS 做為自然單位。
(許多 TCP 實作,則以 位元組 (byte) 為實際單位)
 
傳送端 MSS (SENDER MSS, SMSS) 的值,
可能受到 MTU、Path MTU Discovery、接收端 (RMSS) 或 其他因素影響,
本篇將比照 規範 [RFC 5681],以此為主要單位。
 
流量控制 的 接收視窗 (rwnd) 是:

接收未完成資料量的 接收端限制

 
壅塞視窗 (cwnd) 是:

在收到確認 (ACK) 之前,可以發送到網絡中的資料量的 傳送端限制

 
這是 學習「傳統」壅塞控制 演算法 (Congestion Control Algorithms) 的重點,其主要原理只是:

TCP 在不同狀態下,cwnd 如何增加、減少 或 限制。

 

發送視窗 (Send Window)

流量控制 提到:

TCP 的 發送視窗大小,主要由 接收端 來維護,
接收端 每次回報確認(ACK) 時,皆會告知傳送端 接收視窗 (rwnd) 大小。

 
事實上,這只對了一半 (因無考慮 壅塞控制),
真正的 發送視窗大小 為:

/*
 * "接收端 接收視窗" 與 "壅塞視窗"
 * 兩者之最小值
 */
 
min(RCV.rwnd, cwnd);

 
傳送端 可傳送的資料量 為:
『接收端的接收視窗』與『壅塞視窗』取較小者。
 
若 接收端接收視窗 < 壅塞視窗,表 接收端 接收緩衝區不足;
相反,若接收端接收視窗 > 壅塞視窗,表 網路此時處於壅塞。
 
貼心提醒:

表頭欄位 的 視窗 (Window),

為 接收視窗 (rwnd),而非 發送 或 壅塞視窗。

TCP-Header-Format-window
 
 

初始視窗 (Initial Window, IW)

初始視窗 (Initial Window, IW),是 TCP 建立連線 (三向交握) 後,
傳送端 使用的 壅塞視窗 (cwnd) 大小,其遵循以下準則設置上限 [RFC 3390]:

if (SMSS > 2190 位元組)
    IW = 2 * SMSS; // 不得超過 2 個區段
else if (SMSS > 1095 位元組)
    IW = 3 * SMSS; // 不得超過 3 個區段
else
    IW = 4 * SMSS; // 不得超過 4 個區段

建立連線時的 SYN/ACK 及其 ACK 區段,不得增加 壅塞視窗 (cwnd) 的大小,
且如果其一遺失,在正確傳輸 SYN 區段後,
初始視窗 (IW) 最多只能為 SMSS 組成的一個區段。
 
具有多 MSS 大小的 IW,
路徑 MTU 探索 (Path MTU Discovery),發現 MSS 值過大時,
應減少 壅塞視窗 (cwnd) 大小,避免許多 分段小區段的 突發 (bursts)。
 
傳統 TCP 將 IW 設定為 1,許多 教科書 為利於解釋,也多使用 1 * SMSS,
1999 年 [RFC 2581],將 IW 上限設為 2 * SMSS,
2002 年 [RFC 3390],為 2 ~ 4 個,是目前的標準,
2013 年 [RFC 6928],實驗將 IW 設為 10 SMSS (上限約 14600 位元組),表示為 IW10。
 


 

壅塞控制 演算法
(Congestion Control Algorithms)

 
壅塞控制 演算法 (Congestion Control Algorithms),或稱 壅塞策略,
標準如 (基於遺失):

慢啟動 (Slow Start)、壅塞避免 (Congestion Avoidance)、

快速重送 (Fast Retransmit) 和 快速恢復 (Fast Recovery)

 
Google 人員新推出的 (基於壅塞/BDP):

瓶頸頻寬 與 往返時間 (Bottleneck Bandwidth and RTT, BBR)

 
一些情況下,TCP 傳送端 可比 壅塞控制 演算法 限制的資料傳送量更 保守 (conservative)
然而,TCP 不該比 壅塞控制 演算法 更為 積極 (aggressive)
 
因不同環境、作業系統… 有不同的 TCP 實作、變體 或 版本,
本篇以 [RFC 5681]: TCP Congestion Control 為標準。
 
有趣的是,BBR 不像其他壅塞控制 演算法,
並非使用 壅塞視窗 做為控制輸出流量的主要手段。
 
 

慢啟動 (Slow Start)

TCP 開始傳輸到未知條件的網絡時,
需緩慢地探測網絡,以確定可用容量,
避免因不適當的大量數據並發而使網絡壅塞。
 
TCP 傳送端 使用 慢啟動壅塞避免
控制注入網路的 未完成 資料量。
 
慢啟動 有點像是騎車,
一開始大家都說 RV,慢慢騎、欣賞風景 😇 :

 
過沒多久,發現路況不錯後…
就..變 GP,速度根本不是慢慢提升..而是指數成長 😂 :

 
慢啟動 不如其名,一點都不「慢」,
相反地,其 cwnd 增長速度非常快速,為 指數成長 (exponential growth)
 
連線建立後,cwnd 大小為 初始視窗 (Initial Window, IW),
TCP 進入 慢啟動階段:

TCP 每次接收 並 確認 (ACK) 新資料時,
增加 至多 1 * SMSS 位元組 的 壅塞視窗 (cwnd) 大小。

 
建議做法為,每次接收到 新資料的 確認 (ACK) 區段 時:

cwnd += min(N, SMSS)

 
其中,N 為收到 ACK 時 「之前尚未被確認的資料」之 位元數,
這是為了抵擋一些北爛的接收端,使用 分段確認 (ACK Division)
 
Ex: 明明可以回應 一個區段 ACK: 10,
硬要回應 兩個區段 ACK: 5、ACK: 10,
誘使傳送端增加 壅塞視窗 (cwnd)。
 
 

以 初始視窗 (IW) = 2 為例:


Client 送出 2 個區段,Server 也回應 2 個 ACK (暫不考慮延遲確認),
由於「每次」都增加將近 1,cwnd 為 2 + 1 + 1 = 4。
(收到一個 ACK 便加 1,共收到兩個 ACK)
 
需注意的是,許多應用程式的性能往往受到 往返時間 (RTT) 的限制,
例如: HTTP 為每個請求建立的 TCP 連線,都得經過 慢啟動階段,
不能立即使用鏈接的最大頻寬容量、速度。

其限制了可用頻寬的吞吐量,
這可能對小型傳輸的性能,帶來不利影響,
因此 連線管理 顯得格外重要。

 

慢啟動門檻 (Slow Start Threshold, ssthresh)

慢啟動 不能無止盡的增加 壅塞視窗 (cwnd) 大小,
否則失去了壅塞「控制」的意義。
 
慢啟動門檻 (ssthresh),為 TCP 另一狀態變數,
或稱 慢啟動門閥、門檻值、閾 (ㄩˋ) 值,
不要說 閥 (ㄈㄚˊ) 值 就對了 😂。
 
當 cwnd 到達此門檻,或 觀察到壅塞時,
即停止 指數成長 的 慢啟動,進入 線性成長壅塞避免

當 cwnd < ssthresh,使用 慢啟動 (Slow Start) ;
當 cwnd > ssthresh,使用 壅塞避免 (Congestion Avoidance) ;
當 cwnd = ssthresh,傳送端 擇一使用。 
Photo by O’REILLY
ssthresh 的初始值可為任意大小(例如,一些實作使用接收視窗大小),
但仍應以網路情形減小 壅塞視窗 (cwnd),以回應壅塞。
 
慢啟動 (Slow Start) 用於「資料開始傳輸」時、
「修復由重送定時器檢測到的遺失區段」後,及「啟動 TCP 傳送端 的 ACK 時鐘」。
 
 

壅塞避免 (Congestion Avoidance)

壅塞避免 期間,每個 往返時間 (RTT),
大約增加 1 SMSS 大小 的 壅塞視窗 (cwnd),
且不應超過,儘管某些規範嘗試如此 (e.g., [RFC 3465]),
壅塞避免 持續到 偵測到壅塞為止。

TCP 每次 往返時間 (RTT) 時,
增加 至多 1 * SMSS 位元組 的 壅塞視窗 (cwnd) 大小。

 
建議做法為,每次接收到 新資料的 確認 (ACK) 區段 時:

cwnd += SMSS * SMSS / cwnd

 
[註]
一些傳統的實作會在公式中附加額外常數。
這是不正確的,甚至可能導致性能下降 [RFC 2525]。
 
 

以 初始視窗 (IW) = 2 為例:


 
Client 送出 2 個區段,Server 也回應 2 個 ACK (暫不考慮延遲確認),
由於「每次」都增加將近 1 * 1 / cwnd,
cwnd 為 2 + 0.5 + 0.5 = 3,
相當於 每個 往返時間 (RTT),cwnd 增加 1 SMSS
 
 

區段遺失

當 TCP 傳送端 用 重送計時器 (retransmission timer),
檢測到區段 遺失 且 重送計時器 仍未重送該區段,
慢啟動門檻 (ssthresh) 不應超出:

ssthresh = max(FlightSize / 2, 2*SMSS)

如上所述,飛行大小 (FlightSize) 是網絡中未完成的資料數量,
 
許多實作中誤將 FlightSize 替換為 cwnd,
這可能導致門檻超出 接收緩衝區 (rwnd) 大小。

 
此外,當 重送計時器 逾時,
壅塞視窗 (cwnd) 不許超出 1 個 SMSS 之大小,
此限制稱為 — — 遺失視窗 (Lost Window, LW)
 
因此,TCP 傳送端 在重送丟棄的區段之後,將使用慢啟動 演算法,
將視窗從 1 SMSS 增加到新的 ssthresh 值,並接續 壅塞避免 階段。
 
另一方面,若 TCP 傳送端 用 重送計時器 (retransmission timer),
檢測到區段 遺失 但 重送計時器 至少 重送一次慢啟動門檻 (ssthresh) 保持不變
 
 

快速重送 (Fast Retransmit)

TCP 錯誤控制 (Error Control) 一文,初次介紹 快速重送 的概念:
 

接收端:

某區段遺失,代表後續接收的區段 順序錯誤
因此,不應使用 延遲確認 (Delayed ACK),
而是立即確認 (immediate ACK)

 
目的是為了讓 傳送端 知道:

  • 接收到的是 亂序 (out of order) 的區段
  • 預期接收的序列號

 
 

傳送端:

當 接收到 3 個 重複的確認 (duplicate ACK)
則立即重送該區段,而非等到重送計時器逾時。

 
傳送端一開始並不清楚 「重複的確認」的原因 (這可能由多種網路問題),
若收到 1 ~ 2 個重複確認,傳送端 會假設 是網路對區段的重新排序複製 所引起,
而收到 3 個 或 更多的 重複確認,則明顯地指示 區段已遺失
於是 TCP 立即重送 「似乎是」遺失的區段,而非等到計時器逾時。
 

範例:


 
原始的 ACK,再加上 3 個重複的 ACK,
合計共有 4 個 相同的 確認號 (acknowledgment number),
區段重送之後,計時器會重新啟動。
 
 

有限傳輸演算法
(Limited Transmit Algorithm)

一個顯而易見的問題:

當 傳送端 壅塞視窗 (cwnd) 大小為 3 * SMSS,

傳送端 也送出了 3 個區段,然而,其中一個區段被網路丟棄 (遺失) 會如何?

 
Ans:

接收端 至多送回 2 個重複確認 (duplicate ACK) 區段,
但是,快速重送 需要 3 個 重複確認 來觸發,
傳送端 只能等待成本高昂的 逾時重送,才能重送該遺失的區段。

 
TCP 研究者發現,當 TCP 壅塞視窗 (cwnd) 較小時,
許多 遺失恢復策略 (loss recovery strategies),
可能因 資料的發送有限、接收視窗的限制 或 視窗內資料的大量遺失…而無法有效運作。
 
有限傳輸演算法 (Limited Transmit Algorithm)
使 傳送端 在接收到連續兩個 重複確認 (duplicate ACK) 時,
只要滿足以下條件,便傳輸新數據 (快速恢復 將再次提及):

1. 接收端 的 接收視窗 (rwnd),允許區段的傳輸。

2. 未完成的資料數量 < = 壅塞視窗 (cwnd) + 2 * SMSS。

 
換句話說,當發送量超過 壅塞視窗 (cwnd) 時,
傳送端 僅能在傳輸 兩個區段,
且在傳輸這些新區段時,不得更改 壅塞視窗 (cwnd)。
 
有限傳輸演算法,能與 SACK 結合,也可獨立使用,
其增加了 快速重送 恢復 單個遺失區段 的機率,而非使用成本高昂的 逾時重送。
 
 

快速恢復 (Fast Recovery)

當 快速重送 送出「似乎是」遺失的區段後,
TCP 進入 快速恢復 演算法階段,
直到收到 非重複確認 (ACK) 區段。
 
不執行 慢啟動 的原因是:

重複的確認區段,除了是區段遺失的跡象,
往往也代表 該區段 已離開網路,
因此,我們得知它已不再消耗網路資源。

 
快速重送/快速恢復 演算法 由以下幾點實現:
 
 

1. 傳送端 接收到 1 ~ 2 個 重複確認 (duplicate ACK) 時:

若 接收端 接收視窗 允許,可以 接續發送 先前未發送過的區段。
 
總 飛行大小 (FilghtSize) 應保持:

FilghtSize < = cwnd + 2 * SMSS

且 在傳輸這些新區段時,不得更改 壅塞視窗 (cwnd),
其實就是剛提及的 有限傳輸演算法 (Limited Transmit Algorithm)
 
此外,使用 SACK [RFC 2018] 的 傳送端,
不得發送新數據,除非傳入的 重複確認 包含新的SACK信息。
 


 

2. 接收到 3 個 重複確認 (duplicate ACK) 時:

如上方 「區段遺失」所述,慢啟動門檻 (ssthresh) 不應超出:

ssthresh = max(FlightSize / 2, 2 * SMSS)

若有使用 有限傳輸演算法 (Limited Transmit Algorithm)
藉其傳輸的新數據,不得加入此計算中。
 


 

3. 傳送端 重送 尚未被確認的資料 時:

代表至少 3 個區段 (Segment) 已離開網路 且 被接收端緩衝,
TCP 進入 快速恢復 演算法階段,
直到收到 非重複確認 (ACK) 區段。
 
此時,需將 壅塞視窗 設為:

cwnd = ssthresh + 3 * SMSS

這也是 快速恢復慢啟動 最大的差異之處!
 
Yep! 其中 3 * SMSS 的 3
就是指 已離開網路 且被接收端緩衝的 3 個區段。
 


 

4. 若 傳送端 仍持續接收到 重複確認 (3 個以上):

TCP 繼續保持 快速恢復 階段,
且對每個 重複確認 (duplicate ACK),以 1 * SMSS 增加 壅塞視窗 (cwnd) 大小。
 
如此地擴充 壅塞視窗 (cwnd),
是為了反映出 那些已離開網路的額外區段,
已不再消耗網路資源。
 


 

5. 當接收端 接收視窗 允許:

當先前未傳送的資料有效,
並且 接收端 接收視窗 (rwnd),允許 傳送端 目前的 壅塞視窗 (cwnd),
TCP 傳送端 應發送 1 * SMSS 的未傳送資料。
 


 

6. 當「先前未被確認的資料」之 ACK 抵達:

TCP 必須將 壅塞視窗 (cwnd),設為 慢啟動門檻 (ssthresh),
這稱為 (視窗的) — — deflating,即步驟 2 所述:

ssthresh = max (FlightSize / 2, 2 * SMSS)

 
 

作者: 鄭中勝
喜愛音樂,但不知為何總在打程式 ? 期許能重新審視、整理自身所學,幫助有需要的人。

在《TCP 壅塞控制 (Congestion Control)》中有 13 則留言

  1. 請問鄭大哥 小弟一直以來有 PC 系統TCP協定設置 和網卡設置的問題
    坊間有提供一套軟體 叫做 TCPOptimizer 可以手動很簡單的設置優化內容
    那想請問的是 對於一個PC設備不錯 且網路卡支援較完整的情況下
    使用 TCPOptimizer 如何優 協定裡面的設置才是最妥當的呢?
    *維持在封包持續穩定輸出的同時下 又不失太多的loss 及產生過高的ping 客戶端能怎麼樣調整呢0.0..

    1. 沒有所謂『最好的優化方式』喔 😁
      依不同的上網方式 (e.g., 乙太、Wifi)
      以及 頻寬、網速、應用的不同,都有不同作法

      例如,乙太網路的 MTU 為 1500
      為避免 IP Fragmentation,您可能會將 MSS 調整為 1460
      (詳見此篇 https://notfalse.net/23/mtu)

      又例,一般為避免 等待延遲
      會關閉 Nagle 演算法 –> (TCP_NODELAY)
      但我在開發 Cmd Interaction System 則可能用它來避免小封包問題
      (詳見此篇 https://notfalse.net/25/tcp-sws)

  2. 太神啦!!!!!作為一個一年工作經驗的WEB DEVELOPER表示看不太懂但覺得好強的樣子。剛才在網上找j2ee中的APPLICATION,REQUEST和SESSION這幾個SCOPE的分別時不知GOOGLE為何就出了這頁手癢就點進來看…結果看的過癮一邊看一邊GOOGLE,尤其是CONGESTION 演算法那我又GOOGLE到CODEL和一些相關的偽代碼變相自己也學了不少,雖然好像對現在的工作沒什麼用….

  3. 不好意思,剛學網路
    想問一下這邊的TCP是指TCP/IP整個協定組
    還是說
    傳輸層使用的TCP協定?

發表迴響