# 【計算機網路筆記】3.6 Principles of Congestion Control

[TOC]

Hello Guys, I'm LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, **8**th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。

## 3.6.1 The Causes and the Costs of Congestion（壅塞的成因跟代價）

回顧：

當進入網路的資料量超過網路（路由器 router、連結 link等）的處理能力，導致路由器緩衝區佇列積壓甚至滿溢，進而引發封包遺失與嚴重延遲的現象，就是網路壅塞。

只要是資源（如頻寬、緩衝區）有限的共享網路環境，當需求大於供給時，都必然會面臨壅塞問題。

### 術語解析

- 吞吐量（Throughput）：單位時間內成功通過網路的實際數據量（如 Mbps 或 Gbps），反映網路的真實工作效率。
- 承擔負載（Offered Load, $\lambda'_{in}$）：傳輸層傳送到網路中的總資料速率，包含原始資料與因為遺失或逾時而重傳的資料，相對地，單純只算原始資料的產生速率則標示為 $\lambda_{in}$。
- 佇列延遲（Queuing Delay）：封包在 router 的緩衝區（Buffer）中等待被傳輸到輸出連結（Link）所花費的時間。
- 多程路徑（Multihop Path）：或稱多躍點路徑，是指在網路通訊中，封包從傳送端前往接收端的過程中，必須經過一個或多個中繼節點（如路由器或其他網路節點）來進行轉發與傳遞的路徑。
- 壅塞崩潰（Congestion Collapse）：當網路負載極高時，大量封包在半途被丟棄，導致網路資源都被用來轉發最終會遺失的封包，整體有效吞吐量趨近於零的災難性現象。
- 註：為下面情境三帶來的代價。

在接下來的例子中，書中用三個情境描述壅塞帶來的代價。

### 情境一：兩個發送端、一台有無限量緩衝區的路由器

設定：主機 A、B 各有一筆連線，該兩筆連線的 Source 與 Destination 間共用同一臺 router，共享一條容量為 R 的輸出連結，且假設 router 的緩衝區無限大。（如下圖 3.43）


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 286, Figure 3.43)

接著主機 A、B 會以 $\lambda_{in}$ byte/sec 的速率送出流量到 router。

結果當 A 與 B 的原始資料發送速率（ $\lambda_{in}$ ）不斷提高，無論 A、B 送得多快，能獲得的吞吐量極限最多就是 $\frac{R}{2}$。

下圖是吞吐量、延遲繪製為主機傳送速率的函數圖：


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 287, Figure 3.44)

當發送速率逼近連結（Link）容量時，佇列延遲（Queuing Delay）會變得無限大，由於緩衝區無限大，封包雖不會被丟棄，但會在路由器裡面排隊排到天荒地老。

### 情境二：兩個發送端、一台有限量緩衝區的路由器

設定：在真實世界的 router buffer 是有限的，當 buffer 滿了，封包就會被丟棄（Dropped），為此，可靠的通訊協定（Protocol）會執行重傳，而網路實際承受的負載定義為 $\lambda'_{in}$。

所以這個設定大致上就是以下兩點：

1. router buffer 有限量，所以當 buffer 滿了會丟包。
2. 假設每筆連線都是可靠的，若丟包會做重傳。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 288, Figure 3.45)

| 情境假設 | 結果與吞吐量表現 | 壅塞的代價 |
| -------- | -------- | -------- |
| 封包不會遺失 | 發送端知道緩衝區有空位才傳，從不遺失封包，吞吐量可達 $\frac{R}{2}$ | 理想情況，無額外代價 |
| 封包確實遺失才重傳 | 當負載提高，部分寶貴的頻寬被用來傳輸重傳的封包，接收端實際收到的有效吞吐量降至 $\frac{R}{3}$ | 發送端必須執行重傳，以補償因緩衝區溢位而遺失的封包，降低有效的傳輸效率。 |
| 過早逾時 | 發送端遇到嚴重佇列延遲，誤以為封包遺失而觸發重傳，接收端最終收到兩份一樣的封包並丟棄其一，吞吐量進一步降至 $\frac{R}{4}$。 | 面對巨大延遲，發送端不必要的重傳會使路由器浪費寶貴的連結頻寬，來轉發無用的封包副本。 |

下圖為上述三種情形的效能圖：


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 289, Figure 3.46)

### 情境三：四個發送端、多個路由器與多程路徑

設定：四台主機互相傳輸，每條連線都會經過多個路由器，並在不同的路由器上與其他連線競爭有限的緩衝區空間，同樣假設每台主機都會用逾時重送機制來做可靠資料傳輸服務，所有主機的 $\lambda_{in}$ 值都相同，所有路由器的連結容量也為 R byte/sec。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 290, Figure 3.47)

在當提供的負載（ $\lambda'_{in}$ ）極大時，某條連線（如 A 傳給 C，需經過路由器 R1 跟 R2）的封包在第一跳（First-hop）的路由器成功轉發，卻在第二跳（Second-hop）的路由器因競爭輸給其他龐大的流量（例如 B 傳給 D）而被丟棄，最終導致吞吐量趨近於 0。

最後獲得的代價：當一個封包在路徑途中被丟棄，所有上游（Upstream）路由器為了轉發這個封包所消耗的傳輸容量，最後全都浪費掉了。

### 小結

1. 壅塞會導致封包在節點中產生極大的排隊延遲（情境一）。
2. 壅塞造成的封包遺失與延遲，會引發重傳，進一步擠壓並浪費網路頻寬（情境二）。
3. 在多程路徑網路中，壅塞丟包會導致上游路由器先前的轉發努力白費，嚴重時會引發網路癱瘓（情境三）。

## 3.6.2 Approaches to Congestion Control（壅塞控制的方法）

解決網路壅塞有兩大主要流派：

- 端到端壅塞控制
- 網路協助壅塞控制

兩者差異在於網路層的路由器是否會主動幫忙回報壅塞狀況。

在設計傳輸層的壅塞控制機制前，需先決定系統架構的責任歸屬：要讓終端主機自己去猜測網路狀況、或是要求中間路由器主動提供壅塞情況？這決定整個網路協定的複雜度與實作方向。

網際網路預設的 IP 協定非常簡單，不保證傳輸也不主動回報壅塞，因此傳統 TCP 只能採用端對端的猜測方式。

而在某些特定的封閉網路或具備特殊硬體支援的網路（如 ATM（Asynchronous Transfer Mode）網路），則可以做到精準的網路協助控制。

### 術語解析

- 端對端壅塞控制（End-to-end Congestion Control）：網路層不提供任何明確的壅塞支援，端點系統（發送端與接收端）只能透過觀察網路行為（如封包遺失或延遲）來推測是否發生壅塞。
- 網路協助壅塞控制（Network-assisted Congestion Control）：網路內部的路由器會提供明確的回饋給發送端或接收端，告知當前網路的壅塞狀態。
- 抑制封包（Choke Packet）：在網路協助壅塞控制中，由壅塞的路由器直接發送給傳送端的一種警告封包，表示當前網路塞車，需要降速。

### 端對端壅塞控制（End-to-End Congestion Control）

在此方法，位於網路層的路由器只管轉發封包，就算塞車塞到快崩潰，也不主動發出任何警告。（意即網路層不會對壅塞提供任何明確協助）

如何察覺壅塞？終端系統必須靠自己觀察，例如 TCP 傳送端如果發生了逾時（Timeout）或收到三次重複的 ACK，就會推斷網路發生了壅塞，並主動降低傳輸視窗的大小。

進階推測法：除了看封包有沒有遺失，有些較新的 TCP 演算法（如 TCP Vegas）會透過測量封包往返延遲（Round-trip delay）的增加，來提前預測壅塞的發生。

### 網路協助壅塞控制（Network-Assisted Congestion Control）

這個方法讓網路層的路由器也成為參與者，當路由器發現自己的緩衝區快滿時，會主動發送訊號通知終端系統。

回饋的精細度：

- 簡單標記：用一個位元（Bit）來指示該連結有壅塞情況（例如早期的 IBM SNA、DECnet 以及 ATM 網路，或是現在的 TCP ECN 機制）。
- 精確指示：路由器直接告訴發送端，目前能支援的最大傳輸速率是多少（例如 ATM ABR（Available Bit Rate，可用位元速率）壅塞控制）。

#### 網路協助控制的兩種回饋路徑

在網路協助壅塞控制中，路由器要把塞車的訊息傳給發送端，有兩種常見的路徑：

1. 直接回饋（Direct Feedback）：路由器直接發送一個抑制封包（Choke Packet）給發送端，最即時，但也要路由器有能力產生並發送新封包給發送端。
2. 間接回饋（Network feedback via receiver）：路由器不直接找發送端，而是在順向傳輸的資料封包標頭上做記號，當做過記號的封包抵達接收端時，接收端會在回傳給發送端的確認封包（ACK）中，順便通報這個壅塞情況，該方式缺點是通知需要花費一個完整的來回時間（round-trip time）。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 293, Figure 3.49)

## 總整理

當進入網路的資料量大於網路的處理能力時，會導致路由器緩衝區積壓、滿溢，進而引發封包遺失與嚴重延遲，即為網路壅塞。

3.6.1 相關術語：

1. 吞吐量（Throughput）：單位時間內成功通過網路的實際有效數據量。
2. 承擔負載（Offered Load, $\lambda'_{in}$）：傳輸層送到網路的總資料速率（包含原始資料 $\lambda_{in}$ 與重傳資料）。
3. 佇列延遲（Queuing Delay）：封包在路由器緩衝區排隊等待輸出的時間。
4. 壅塞崩潰（Congestion Collapse）：負載過高時，網路資源全耗費在轉發最終會遺失的封包上，導致有效吞吐量趨近於零的災難。

### 壅塞的三大代價

1. 無限大的排隊延遲
- 情境：無限緩衝區的路由器。
- 結果：雖不會丟包，但當發送速率逼近網路頻寬極限（例如兩端平分頻寬 $\frac{R}{2}$）時，封包會在路由器中面臨無限大的佇列延遲。
2. 重傳浪費寶貴頻寬
- 情境：有限緩衝區的路由器，且傳輸協定保證可靠（會重傳遺失封包）。
- 結果：緩衝區滿溢導致丟包，發送端必須重傳，會使寶貴的頻寬被用來傳送重複的資料，若遇到嚴重延遲導致過早逾時（Premature Timeout），會引發不必要的重傳，使吞吐量進一步劣化（降至 $\frac{R}{3}$ 或 $\frac{R}{4}$）。
3. 上游路由器的轉發努力白費
- 情境：多程路徑（Multihop Path）與多發送端競爭。
- 結果：當封包在路徑的後半段（如下游路由器）因競爭而遭到丟棄時，所有上游路由器為該封包付出的傳輸容量與心力全數浪費，嚴重時會引發全網癱瘓。

### 壅塞控制的兩大流派

在設計通訊協定時，必須決定誰來負責發現壅塞，分為兩種主要作法：

#### 端對端壅塞控制（End-to-End Congestion Control）

- 網路層（路由器）完全不幫忙，只管轉發封包，即使塞車也不發出警告。
- 偵測方式：終端系統（發送端）必須自己猜測，例如傳統 TCP 透過觀察是否發生逾時（Timeout）或收到三次重複的 ACK，來推斷發生丟包與壅塞，進而自主降速。
- 進階預測：部分演算法（如 TCP Vegas）會透過觀察往返延遲（RTT）的微小增加，在丟包前提前預測壅塞。

#### 網路協助壅塞控制（Network-Assisted Congestion Control）

- 網路層（路由器）主動參與，當察覺緩衝區快滿時，主動發送訊號通知終端系統降速。
- 回饋精細度：
- 簡單標記：用 1 個位元（Bit）警告有壅塞（如 TCP ECN）。
- 精確指示：直接告知發送端目前可用的最大傳輸速率（如 ATM ABR）。
- 回饋路徑：
- 直接回饋（Direct Feedback）：路由器直接發送抑制封包（Choke Packet）警告發送端（最即時）。
- 間接回饋（Indirect Feedback）：路由器在順向傳輸的資料封包做記號，接收端收到後，再透過回傳的 ACK 順便通知發送端（需耗費 1 個 RTT 的時間）。

### 比較表：壅塞控制兩大流派

| 比較項目 | 端對端壅塞控制 | 網路協助壅塞控制 |
|--------------|-------------------------------|--------------------------------|
| 網路層（路由器）角色 | 1. 被動。<br>2. 只負責轉發封包，不提供任何壅塞狀態資訊。 | 1. 主動。<br>2. 監控自身狀態，並提供明確的壅塞回饋。 |
| 終端系統角色 | 需透過觀察網路行為（如遺失、延遲）自行推測壅塞。 | 接收來自路由器的明確指示或標記來調整速率。 |
| 壅塞通知方式 | 1. 無明確通知。<br>2. 依賴 Timeout 或重複的 ACK。 | 透過抑制封包直接通知，或在封包標頭做記號間接通知。 |
| 系統複雜度與成本 | 1. 較低。<br>2. 路由器實作簡單，網際網路（IP 協定）預設採用。 | 1. 較高。<br>2. 路由器需具備監控與發送通知的能力。 |
| 代表性協定 / 應用 | 傳統 TCP（網際網路） | ATM 網路、具備 ECN（明確壅塞通知）機制的 TCP |