---
# System prepended metadata
title: 【計算機網路筆記】4.2 What’s Inside a Router?
tags: [計算機網路, Web, Linux, 網路, 網路概論, 電腦雜談, 電腦, 網頁]
---
# 【計算機網路筆記】4.2 What’s Inside a Router?
[TOC]
Hello Guys, I'm LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, **8**th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。
---
路由器（Router）就像是網路世界裡面的「圓環」，負責將來自四面八方的網路 資料包（Datagram），快速精準地轉送到正確的出口。
下圖 4.4 為路由器架構。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 341, Figure 4.4)
而至於路由器內部有什麼呢？首先請看其內部的內部四大核心組件：
- 輸入埠（Input Port）：路由器的「入口閘道」，封包抵達的第一站。
- 它會執行實體層（Physical Layer）功能，當作實體連結進入路由器的終端（終端是上圖 4.4 Input Port 最左邊的方塊）。
- 也執行連結層（Link Layer）功能，我們需要該功能以便與輸入連結跟另一端的連結層（Link Layer）交互運作，由 Input Port 與 Output Port 中間的方塊所表示。
- 它除了終止實體連結並處理連結層（Link Layer）協定外，最關鍵的任務是執行查詢（Lookup），決定剛抵達的封包該被送往哪一個輸出埠。（轉送表也在此被詢問）發生在 Input Port 最右邊的方塊中。
- 交換結構（Switching Fabric）：路由器的「內部高速公路」或「圓環」，負責連接輸入與輸出的內部網路。
- 它完全封裝在路由器內部，負責將輸入埠的封包實際連接並傳送至對應的輸出埠。
- 輸出埠（Output Port）：路由器的「出口閘道」，封包離開路由器前的最後一站。
- 它負責儲存從交換結構送來的封包，並執行必要的連結層與實體層功能，最終將封包傳輸到輸出連結上。
- 因此輸出埠會執行與輸入埠相反的資料。
- 繞送處理器（Routing Processor）：路由器的「大腦」，負責統籌與計算的智慧核心。
- 它負責執行控制層（Control Plane）的功能。
- 在傳統網路路由器中，它會執行繞送協定、維護繞送表和附加連結狀態資訊，並計算路由器的轉送表。
- 在軟體定義網路（SDN）路由器中，它則負責與遠端控制器溝通，以便接收由遠端控制器計算的轉送表條目，並將這些條目安裝在路由器的輸入埠中。
一個路由器的輸入埠、輸出埠和交換結構在一起實作了轉送（Forwarding）功能，且幾乎一定是硬體實作。
Why？考慮一道 100 Gbps 的輸入連結跟一個 64 bytes 的 IP 資料包，在另一份資料包來之前，輸入埠只有 5.12 ns 可處理資料包。
假設 N 個埠被結合在一張路線卡上，資料包處理管線必須要以快 N 倍的速度來實作，對於軟體實作而言太快了（即對來軟體來說處理不過來）。
轉送平面硬體可以被實作成採某路由器廠商自己的硬體設計，或使用如 Intel、Boardcom 這些公司的晶片做建構。
## 資料層與控制層的分工
為了解決極高速的流量問題，路由器在架構上做出了明確的切割：
| 比較維度 | 資料層（Data Plane） | 控制層（Control Plane） |
|---|---|---|
| 主要任務 | 轉送（Forwarding）：將封包從輸入埠移至輸出埠。 | 繞送（Routing）：計算路徑、維護轉送表與管理網路狀態。 |
| 運作時間尺度 | 極短（奈秒，Nanosecond 級別）。 | 較長（毫秒 Millisecond 或秒級別）。 |
| 實作方式 | 幾乎完全由硬體（Hardware）實作（如客製化晶片）。 | 由軟體（Software）實作，執行於傳統 CPU 上。 |
| 涵蓋組件 | 輸入埠、交換結構、輸出埠。 | 繞送處理器。 |
## 轉送機制的演進：圓環交流道比喻
為了能更好理解封包在路由器內的流動，可將路由器想像成一個大型的「圓環交流道」：
- 基於目的端的轉送（Destination-Based Forwarding）：像是傳統的交流道。
- 當車子（封包）開到入口收費站（輸入埠）時，司機告訴收費員他的最終目的地（目的 IP 位址）。
- 收費員查表後，告訴司機該從哪個圓環出口（輸出埠）離開。
- 廣義轉送（Generalized Forwarding）：更先進的交流道。
- 收費員不只看目的地，還會看車牌來自哪裡（來源位址）、車子是什麼型號（協定類型），甚至判斷這輛車是否有安全疑慮來決定是否放行（防火牆阻擋）。
- 收費員可以綜合多種條件來決定這輛車該走哪條路。
當車子進入圓環（交換結構）後，可能會遇到其他入口進來的車子，大家最終都要從各自的出口匝道（輸出埠）離開。
如果某個出口塞車，車子就必須在匝道排隊（佇列等待），這就是路由器發生延遲與掉包的地方。
## 4.2.1 Input Port Processing and Destination-Based Forwarding（輸入埠處理與基於目的端的轉送）
該節摘要：該節深入探討封包抵達路由器的第一站：輸入埠（Input Port），並詳細探討它如何執行基於目的地的轉送（Destination-Based Forwarding）。
輸入埠（Input Port）負責接收實體訊號、解除封裝，並透過極速的硬體查表機制，決定每一個資料包（Datagram）應該被送往哪一個輸出通道。
在高速網路中（例如 10 Gbps 甚至 100 Gbps 的連結），資料包的抵達間隔只有短短幾奈秒（Nanosecond）。
如果每一個資料包都要送到中央 CPU 去排隊問路，路由器早就癱瘓了，因此需要將查表決定去向的任務下放到每一個輸入埠，在地、高速地解決問題。
至於其效能的限制主要來自於記憶體的存取速度與查表演算法的效率。
### 術語解析
- 轉送表（Forwarding Table）：路由器的「指路地圖」。
- 由繞送協定（Routing Protocol）計算得出，或由遠端軟體定義網路（SDN）控制器配發，用來將目的地 IP 位址對應到正確的輸出介面。
- 最長址首相符原則（Longest Prefix Matching Rule）：一種查表規則。
- 當一個目的地位址同時符合轉送表中的多個條目時，路由器會選擇匹配位元數最多（最精確）的那一條路徑。
- 影子副本（Shadow Copy）：為避免存取瓶頸，中央的繞送處理器（Routing Processor）會將轉送表複製一份到每一個輸入埠的線卡（Line Card）上，讓輸入埠能獨立作業。
- 三元內容可定址記憶體（Ternary Content Addressable Memory, TCAM）：一種昂貴但極速的特殊硬體記憶體。
- 給定一個 IP 位址，它能在常數時間 $O(1)$ 內直接用硬體比對出結果。
### 輸入埠的三大處理階段
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 344, Figure 4.5)
當一個信號沿著實體線路來到路由器時，輸入埠（Input Port）會依序進行三個主要處理階段：
1. 線路終端（Line Termination）
- 屬於實體層（Physical Layer）的工作。
- 負責接收光訊號或電訊號。
- 將實體訊號還原成位元流（bit stream）。
2. 資料連結處理（Data Link Processing）
- 屬於資料連結層（Data Link Layer）的工作。
- 負責處理連結層協定，例如 Ethernet。
- 進行錯誤檢查。
- 從訊框（frame）中解封裝（Decapsulation）出網路層資料包，也就是 IP datagram。
3. 查詢、轉送與排隊（Lookup, Forwarding, Queuing）
- 屬於輸入埠中非常關鍵的資料層（Data Plane）處理。
- 路由器會檢查 IP 標頭（IP header）中的目的位址。
- 查詢轉送表（forwarding table）決定封包應該送往哪一個輸出埠（Output Port）。
- 如果交換結構（switch fabric）暫時無法處理，封包可能會在輸入埠排隊。
### 分散式查表：避免集中化瓶頸
假設有一條 10 Gbps 的連結上，全是 64-byte 的小資料包，這表示即每 51.2 奈秒（ $64 \text{byte} = 512 \text{bit} \rightarrow \frac{512 \text{bit}}{10 \times 10^9} = 51.2 ns$ ）就會有一個資料包抵達。
如果每個輸入埠都去問中央的繞送處理器（Routing Processor），系統一定會產生嚴重的瓶頸。
因此，現代路由器採用了分散式架構：中央處理器只負責運算與更新，接著透過一條獨立的內部匯流排（例如 PCI bus），將轉送表的影子副本（Shadow Copy）發送到每一個輸入埠。
這樣一來，每個輸入埠都能自己做決定，實現線速（Line-rate）轉送。
:::info
線速轉送是指網路設備（如交換器、路由器、防火牆）在處理網路封包時，其轉送速度能達到實體網路連線的最高頻寬速度，且在處理過程中不會發生封包丟失或顯著延遲。
:::
### 最長址首相符原則（Longest Prefix Matching Rule）
IPv4 位址共有 32 個位元（bit），如果路由器要為每一個可能存在的 IP 位址都建立一筆轉送表紀錄，就需要約 40 億筆紀錄，這在實務上幾乎不可能實現。
因此，路由器不會逐一記錄每個 IP 位址，而是使用「位址範圍」或「址首（Prefix）」來簡化轉送表。
假設某台路由器有四個連結介面，編號為 0 到 3，封包會依照目的端位址被轉送到不同的介面，如下表所示：
| 目的端位址範圍 | 連結介面 |
|---|---|
| 11001000 00010111 00010000 00000000
到
11001000 00010111 00010111 11111111 | 0 |
| 11001000 00010111 00011000 00000000
到
11001000 00010111 00011000 11111111 | 1 |
| 11001000 00010111 00011001 00000000
到
11001000 00010111 00011111 11111111 | 2 |
| Otherwise（預設路由） | 3 |
如果直接用位址範圍表示，表格看起來仍較複雜，因此，路由器可以改用址首來表示這些範圍，整理後，轉送表只需要四筆條目：
| 目的端位址址首 | 連結介面 |
|---|---|
| 11001000 00010111 00010 | 0 |
| 11001000 00010111 00011000 | 1 |
| 11001000 00010111 00011 | 2 |
| Otherwise（預設路由） | 3 |
使用這種形式的轉送表時，路由器會將封包的目的端位址與表中的址首進行比對。若找到相符的址首，就會依照該條規則將封包轉送到對應的連結介面。
---
例如，某封包的目的端位址為：
```text
11001000 00010111 00010110 10100001
```
觀察可發現，這個位址的前 21 個位元：
```text
11001000 00010111 00010
```
與轉送表中的第一筆規則相符，因此路由器會將該封包轉送到連結介面 0。
**如果某個目的端位址無法與前三筆規則中的任何一筆址首相符，路由器就會使用 Otherwise，也就是預設路由，將封包轉送到連結介面 3。**
---
另一個例子，假設封包的目的端位址為：
```text
11001000 00010111 00011000 10101010
```
這個位址會同時符合兩筆規則：
1. 它與第 2 筆規則的前 24 個位元完全相符：
```text
11001000 00010111 00011000
```
2. 它也與第 3 筆規則的前 21 個位元相符：
```text
11001000 00010111 00011
```
此時，路由器會採用**最長址首相符原則**（Longest Prefix Matching Rule）。
因為第 2 筆規則相符的長度是 24 位元，而第 3 筆規則相符的長度只有 21 位元，所以路由器會選擇較精確的第 2 筆規則，將封包轉送到連結介面 1。
簡單來說，路由器不是看哪一筆先符合，而是看哪一筆符合得最精確，此為最長址首相符原則。
### 轉送表查找的基本概念
在路由器已經擁有轉送表（Forwarding Table）的前提下，查找（lookup）動作在概念上其實很簡單：硬體邏輯只需要在轉送表中搜尋，找出與目的端 IP 位址相符的最長址首相符（Longest Prefix Match）。
也就是說，路由器收到封包後，會根據封包的目的端 IP 位址，去轉送表中找出最精確的匹配規則，並決定要把封包送到哪一個輸出介面。
### 為什麼不能用簡單的線性搜尋？
雖然概念很簡單，但在高速網路中，實作上非常困難。
例如，在 10 Gbps 的連結上，如果傳送的是 64-byte 的小型 IP 資料包，那麼封包抵達的速度非常快，路由器必須在奈秒（nanosecond）等級內完成查找。
因此，查找不能只是用一般軟體慢慢搜尋，也不能使用簡單的線性搜尋（Linear Search）逐筆比對大型轉送表。
| 方法 | 問題 |
| ------ | ----------------- |
| 軟體查找 | 速度太慢，無法應付高速封包抵達 |
| 線性搜尋 | 轉送表很大，逐筆比對會造成嚴重延遲 |
| 硬體加速查找 | 較適合高速路由器需求 |
所以在實務上，轉送表查找必須由硬體完成，而且還需要使用比線性搜尋更高效的查找演算法。
### 記憶體存取時間
高速查找不只和演算法有關，也和記憶體速度有關。
因為每次查表都需要存取轉送表，而封包抵達速度極快，所以記憶體存取時間會直接影響路由器能否達到線速轉送（Line-rate Forwarding）。
因此，現代路由器常使用下列記憶體設計：
| 記憶體類型 | 特色 |
| ------------ | ----------------------- |
| On-chip DRAM | 嵌入晶片內部的 DRAM，容量較大 |
| SRAM（Static Random-Access Memory） | 速度比 DRAM 快，常作為 DRAM 的快取 |
| TCAM（Ternary Content Addressable Memories） | 可用於高速查找，特別適合址首匹配 |
### 查表後：封包進入交換結構
當路由器透過查表（Lookup）決定封包應該被送往哪一個輸出埠（Output Port）後，封包就可以被送入交換結構（Switching Fabric）。
在某些路由器設計中，封包不一定能立刻進入交換結構，因為交換結構可能正在被其他輸入埠的封包使用。
此時，封包會被暫時阻塞（Blocked），並先排在輸入埠的佇列（Queue）中，等待之後被排程（Scheduled）進入交換結構。
也就是說，封包的流程可能是（GPT Image 2.0 生成）：
### 輸入埠不只負責查表
雖然查表通常是輸入埠處理中最重要的動作，但輸入埠還需要完成其他工作，主要包含以下三類：
1. 實體層與連結層處理
2. 檢查與更新 IP 標頭欄位（封包的版本號碼、檢查和、生存時間三個欄位必須被檢查，後兩者必須被更新）
3. 更新網路管理計數器
### 匹配加上行動（Match plus Action）網路設備中的通用抽象模型
輸入埠處理可以被看成一種更通用的模型：Match plus Action，匹配加行動。
先前「查 IP 目的地（Match）」然後「送到特定輸出埠（Action）」，其實只是此概念（Match plus Action）的一種特例。
Match-Action 是現代網路設備中非常常見且強大的設計概念，不只存在於路由器，除了路由器以外的網路設備也會這麼做。
如：
- 連結層交換器（Link-layer Switch）：設備會根據資料訊框中的目的端連結層位址進行匹配。
- Match：檢查目的端 MAC 位址。
- Action：將資料訊框送往指定輸出埠。
- 防火牆（Firewall）：
- Match：匹配特定 IP 位址與埠號組合。
- Action：丟棄封包或允許通過。
- NAT（Network Address Translator，網路位址轉譯器）：
- Match：匹配特定傳輸層埠號。
- Action：改寫埠號後再轉送。
## 4.2.2 Switching（交換）
本節摘要：交換結構（Switching Fabric）是路由器的心臟，是最核心的部分，負責將抵達輸入埠的網路封包，實際且快速地搬運到正確的輸出埠。至於交換的方式有很多種，請見該節後續。
下圖 4.6 為三種交換技術：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 347, Figure 4.6)
### 術語解析
- 交換結構（Switching Fabric）：完全封裝在路由器內部的網路，負責連接路由器的各個輸入埠與輸出埠。
- 非阻塞式（Non-blocking）：一種交換結構的特性。
- 如果一個封包要前往的輸出埠目前沒有其他封包正在使用，它就能保證順利到達該輸出埠，不會因為其他輸入埠與輸出埠之間的傳輸而被阻擋。
- 棋盤式交換結構（Crossbar Switch）：一種基於矩陣網格設計的互連網路交換技術，透過動態開關矩陣上的交叉點，允許多個封包同時進行平行傳輸。
### 交換方式 1：透過記憶體進行交換
這是最早期、也最直觀的作法，早期的路由器其實就是一台傳統的電腦，其輸入埠與輸出埠間的交換動作由 CPU（繞送處理器）的直接控制下完成。
- 運作原理：
- 當一個封包抵達輸入埠時，會觸發 CPU 的中斷（Interrupt）來通知繞送處理器。
- 接著封包會被完整複製到處理器的記憶體中。
- 再來 CPU 會從封包標頭提取出目的端位址、查找轉送表，找到對應的輸出埠後，再將封包從記憶體複製到輸出埠的緩衝區。
- 效能限制：因為所有的資料進出都必須經過系統匯流排與記憶體，所以效能受限於記憶體的頻寬。
- 假設記憶體的讀寫頻寬最大為每秒 $B$ 個封包，因為一個封包需要被寫入再讀出（也就是兩次記憶體存取），所以路由器的總轉送吞吐量必定小於 $B/2$。
- 此外，即使有兩個封包要前往不同的輸出埠，它們也無法同時被轉送。
- 現代應用：某些現代路由器仍採用記憶體交換，只不過查表和儲存的動作被下放到了各個輸入線路卡（Line Card）上的處理器與記憶體，例如 Cisco Catalyst 8500 就是這種架構。
### 交換方式 2：透過匯流排（bus）進行交換
為了解決 CPU 介入造成的瓶頸，第二代架構讓輸入埠可以直接透過一條共享的匯流排（Bus）將封包傳給輸出埠。
- 運作原理：
- 輸入埠在封包前面加上一個內部標籤（Internal Label），標示這個封包要送往本地的哪個輸出埠，然後把封包送到共享匯流排上。
- 所有的輸出埠都會收到這個封包，但只有標籤吻合的輸出埠會把封包收下來，並撕掉這個內部標籤。
- 效能限制：這條匯流排就像是一條單線道的橋樑，如果同時有多個封包抵達不同的輸入埠，同一時間只能有一個封包通過匯流排，其他封包必須在輸入埠排隊等待，因此路由器的交換速度受限於這條匯流排的頻寬。
- 現代應用：對於區域網路（LAN）或企業級網路來說，這種速度通常已經足夠，例如 Cisco 6500 系列路由器就是透過一條 32 Gbps 的背板匯流排來交換封包。
### 交換方式 3：透過互連網路（Interconnection Network）交換
為了解決單一匯流排的單線道瓶頸，我們來到最高階的架構：互連網路。這借鑑了多處理器電腦架構中的技術。
- 運作原理：最經典的就是棋盤式交換結構（Crossbar Switch），該結構由 $2N$ 條匯流排組成，將 $N$ 個輸入埠連接到 $N$ 個輸出埠的互連網路。
- 平行處理：如果輸入埠 $A$ 要傳給輸出埠 $Y$，同時輸入埠 $B$ 要傳給輸出埠 $X$，只要它們不搶同一個輸出埠，控制器就可以同時閉合這兩個交叉點，實現非阻塞式（Non-blocking）的平行傳輸。
- 現代極限挑戰：如果兩個輸入埠都要傳給同一個輸出埠怎麼辦？當然還是要有一個先在輸入埠排隊。
- 為了解決更龐大的流量，更高階的路由器（如 Cisco CRS）會採用多級（Multi-stage）的交換結構，甚至將一個封包切成好幾個小區塊（Chunks），平行地噴射（Spray）到多個交換結構中傳輸，到了輸出埠再重組。
### 三種交換方式比較表
| 比較項 | 透過記憶體交換（Memory） | 透過匯流排交換（Bus） | 透過互連網路交換（Interconnection Network） |
| ------ | ------------------ | ------------------------ | ---------------------------------- |
| 傳輸通道 | 系統記憶體與內部匯流排 | 單一共享背板匯流排 | $2N$ 條匯流交換的網格（Crossbar） |
| 平行傳輸能力 | 否（一次只能處理一個） | 否（一次只能通過一個封包） | 是（只要目的地不同即可平行傳輸） |
| 效能瓶頸 | 記憶體頻寬（極限為 $B/2$） | 單一匯流排的頻寬極限 | 交叉點控制複雜度與輸出埠衝突（Output Contention） |
| 複雜度與成本 | 最低（近似一般電腦） | 中等（需要專用匯流排與內部標籤） | 最高（複雜的硬體矩陣與排程演算法） |
| 代表性範例 | 早期路由器、Cisco 8500 | Cisco 6500 (32 Gbps Bus) | Cisco 12000, Cisco CRS |
## 4.2.3 Output Port Processing（輸出埠處理）
下圖 4.7 為輸出埠處理圖。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 349, Figure 4.7)
輸出埠（Output Port）是路由器的出口端，負責將從交換結構送來的封包暫存、排程，並封裝成適合該實體線路的格式，最終發送出去。
為什麼需要它？當內部交換結構（Switching Fabric）搬運封包的速度，大於外部輸出連結（Output Link）的傳輸速度時，封包就會在出口處塞車。
輸出埠提供了一個緩衝與管理的機制，確保這些封包能有秩序地排隊，並根據特定的優先權或公平性原則被傳送出去。
輸出埠必須處理來自各個輸入埠匯聚而來的龐大流量，當緩衝區（Buffer）耗盡時，就會發生網路世界中最不樂見的現象：封包遺失（Packet Loss），因此，這裡的記憶體管理與排程演算法，直接決定了路由器的效能極限。
在此有兩個名詞需要理解：
1. 排程（Scheduling）：在輸出埠中，從多個正在排隊等待的封包裡，挑選出下一個要被傳送的封包的決策過程。
2. 解佇列（De-queuing）：將被排程器選中的封包從記憶體（緩衝區）中取出，準備交給下層協定進行傳送的動作。
根據上圖 Figure 4.7 的架構，可將輸出埠的處理流程視為一條與輸入埠完全相反的生產線。當封包從交換結構抵達輸出埠時，會依序經歷以下三大階段：
### 1. 佇列（緩衝區管理）
封包抵達輸出埠的第一站是記憶體（Memory）。
因為現代路由器的交換結構（例如 Crossbar）通常具有極高的平行傳輸能力，可能會在同一個時間點將多個封包同時送往同一個輸出埠。
如果輸出埠的實體線路（例如 10 Gbps 的光纖）來不及消化這些瞬間湧入的封包，它們就必須先被存放在輸出埠的緩衝區（佇列）中等待，這就是網路延遲中佇列延遲（Queuing Delay）發生的主要地點。
### 2. 封包排程與解佇列（Packet Scheduling and De-queuing）
當實體線路空閒、空出來時，輸出埠必須決定接下來要傳送哪一個封包？這就是排程（Scheduling）與解佇列（De-queuing）的工作。
最簡單的作法是先進先出（FIFO, First-In-First-Out），也就是誰先排隊誰就先出去，但在現代網路中，為了保證視訊或語音通話等服務品質（QoS），輸出埠通常會實作更複雜的排程演算法，例如優先權佇列（Priority Queuing）或是加權公平佇列（Weighted Fair Queuing, WFQ），選定封包後，就會將它從記憶體中取出（解佇列）。
### 3. 資料連結層與實體層處理（Data Link and Physical Layer Processing）
封包被選中後，就準備要離開路由器了，這時輸出埠必須執行下層協定的傳輸功能：
1. 資料連結層處理（Data Link Processing）：將網路層的 IP 資料包（Datagram）封裝成資料連結層的訊框（Frame）（例如 Ethernet 訊框），並填入正確的 MAC 位址與錯誤檢查碼（CRC）。
2. 線路終端與實體層傳輸（Line Termination / Physical Transmission）：將訊框轉換為實體媒介上的光訊號或電訊號，打入傳輸線路中。
### 輸入埠 vs. 輸出埠
| 處理階段 | 輸入埠（Input Port） | 輸出埠（Output Port） |
| ---------- | --------------------- | ---------------------- |
| 第一步（底層到高層） | 線路終端（接收實體訊號） | 佇列與緩衝（接收交換結構的封包） |
| 第二步（協定轉換） | 資料連結處理（解除訊框封裝，檢查 CRC） | 封包排程與解佇列（決定傳送順序） |
| 第三步（高層到底層） | 查詢與轉送（查表並送入交換結構） | 資料連結與實體層傳輸（封裝成訊框並發送訊號） |
## 4.2.4 Where Does Queuing Occur?（佇列在哪裡發生？）
該節摘要：當封包抵達路由器的速度，超過了路由器內部處理或對外傳輸的速度時，封包就必須在路由器（Router）的輸入端或輸出端排隊，形成佇列（Queuing）。
佇列可能發生在輸入埠，也可能發生在輸出埠，但佇列空間是有限的（取決於路由器的記憶體），當緩衝區滿載時，新來的封包就會被丟棄，這形成封包遺失（Packet Loss），排隊會造成延遲（Delay），掉包則會觸發重傳，兩者共同限制了網路的極限吞吐量（Throughput）。
### 術語解析
- 列前端攔阻（Head-of-the-Line blocking, HOL blocking）：發生在輸入埠的一種現象，排在佇列最前方的封包因為目標輸出埠忙碌而卡住，導致排在它後方、原本可以前往空閒輸出埠的封包也跟著被阻擋而無法前進。
- 主動式佇列管理（Active Queue Management, AQM）：一種先進的丟包策略，與其等緩衝區滿了才丟棄封包，不如在緩衝區快滿時提早主動丟棄或標記封包，用來向發送端發出網路即將壅塞的警告訊號。
- 隨機早期偵測（Random Early Detection, RED）：最廣泛被研究與實作的一種 AQM 演算法。
- 緩衝區膨脹（Bufferbloat）：因為路由器配置了過大的緩衝區，雖減少了丟包率，卻導致封包在佇列中一直排隊，造成極大且持續的網路延遲現象。
### 輸入佇列（Input Queuing）與 HOL 攔阻
路由器內部究竟哪裡會塞車，取決於線路速度（Line Speed）與交換結構傳輸率（Switching fabric transfer rate）的相對快慢。
假設有 $N$ 個輸入埠與 $N$ 個輸出埠，每個埠的線路傳輸率皆為 $R_\text{line}$，而交換結構的傳輸率為 $R_\text{switch}$。
---
如果交換結構的處理速度不夠快（相對於輸入線路速度而言），封包佇列（排隊現象）也會發生在輸入埠中，因為封包必須先加入輸入埠佇列，等輪到他們通過交換結構傳送到輸出埠。
如果交換結構的處理速度夠快（例如 $R_\text{switch}$ 比 $R_\text{line}$ 快 $N$ 倍），輸入埠就幾乎不會有排隊現象，但如果 $R_\text{switch}$ 不夠快，如同前面說的，封包就必須在輸入埠（Input Port）乖乖排隊。
在輸入佇列中，最著名的效能殺手就是列前端攔阻（HOL blocking）。在此考慮假設使用棋盤式交換結構，只要封包的目的地不同，它們就能平行穿越交換結構。
但如果輸入佇列 $A$ 和 $B$ 隊伍最前方的封包都要前往「同一個」輸出埠，其中一個封包就必須等待，此時，那個被迫等待的封包，就會擋住它後方原本可以前往其他空閒輸出埠的封包，此即為 HOL blocking。
[Karol 1987] 研究指出，因為 HOL 攔阻，當輸入連結的封包抵達率達到其容量的 $58\%$ 時，輸入佇列的長度就會無限制地增長。
下圖 4.9 為輸入佇列交換結構中的 HOL 攔阻。上方為於時間 t 的輸出埠競爭（大家都搶同一個輸出埠），導致一個深色封包無法被傳輸；下方為淡藍色封包受到 HOL 攔阻。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 351, Figure 4.8)
### 輸出佇列（Output Queuing）與丟棄策略
即使交換結構非常非常快（$R_\text{switch}$ 是 $R_\text{line}$ 的 $N$ 倍），輸出埠（Output Port）還是可能會塞車，Why？
因為在最糟的情況下，$N$ 個輸入埠可能在同一時間收到封包，而且這 $N$ 個封包「全部都要送往同一個輸出埠」。
交換結構瞬間把這 $N$ 個封包全塞給了該輸出埠，但該輸出埠一次只能送出 $1$ 個封包到外部連結（Link）上，剩下的 $N−1$ 個封包就只能在輸出緩衝區排隊，當這種現象持續、記憶體耗盡時，路由器就必須做出決定：
- 去尾（Drop-tail）：最簡單的做法，直接把新來、擠不進去的封包丟掉。
- 主動式佇列管理（AQM）：比較聰明的做法，在緩衝區滿之前主動丟棄或標記封包的標頭，以便向發送端提供壅塞信號，此標記可用在之前學過的 ECN（Explicit Congestion Notification）上，另外該策略已有最常見的 RED 演算法來實作。
下圖 4.9 為輸出埠的佇列。上方為於時間 t 發生的輸出埠競爭；下方為一個封包時間後的情況（排隊等待輸出）。這張圖引出了封包排程（Packet Schedule），會在下一節討論到。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 352, Figure 4.9)
### 緩衝區設計：多少緩衝區才夠？
既然排隊會造成封包遺失，那把路由器的記憶體（緩衝區）加大不就好了嗎？這是一個經典的工程取捨問題。
多年來，網路界的經驗法則認為，緩衝區大小 $B$ 應該等於平均來回時間（Round-Trip Time, RTT）乘以連結容量（Link Capacity, C），即 $B = RTT \times C$。
例如一條 $10 \text{Gbps}$ 的連結、$RTT$ 為 $250 \ \text{ms}$ 毫秒，就需要高達 $2.5 \text{Gbits}$ 的緩衝記憶體。
但近期的理論與實驗表明 [Appenzeller 2004]，當連結上有大量（數量為 $N$）的獨立 TCP 資料流（Flow）同時穿過該連結時，所需的緩衝區其實可以縮減為：$$B=\frac{RTT×C}{\sqrt{N}}$$
需注意的是，緩衝區是一把雙面刃：**較大的緩衝區能吸收突發流量、降低掉包率，但同時也會帶來更長的排隊延遲。**
對於電競玩家或即時視訊來說，增加十倍的緩衝區可能意味著增加十倍的延遲，這種因為緩衝區過大而導致持續性高延遲的現象，就是近年來備受關注的緩衝區膨脹（Bufferbloat）問題。
---
在此課本舉了一個例子說明緩衝區膨脹：假設你在家裡打連線遊戲，家用路由器正透過 TCP 與遠端的遊戲伺服器連線：
- 傳輸時間（Transmission Time）：家用路由器將一個遊戲 TCP 封包打入外部連結（Link）的時間固定為 $20$ 毫秒（ms）。
- 來回時間（$RTT$）：端到端的 $RTT$ 為 $200$ 毫秒（ms），且路徑上其他地方沒有任何佇列延遲。
#### 突發流量與永久塞車的形成
- 時間 $t=0$：遊戲程式突然產生了一波爆發流量，瞬間有 $25$ 個封包抵達了家用路由器的輸出緩衝區（抵達佇列）。
- 時間 $t=0 \sim 200$ 毫秒：路由器開始努力消化這些封包，每 20 毫秒送出一個封包。
- 時間 $t=200$ 毫秒：第一個封包的 ACK 從遊戲伺服器傳回來，此時，路由器恰好正在傳輸佇列中的後續封包。
- 骨牌效應觸發：當遊戲客戶端在 $t=200$ 收到第一個 ACK 時，根據 ACK 時鐘（ACK clocking）機制，它會立刻再產生一個新的封包送進家用路由器。
- 時間 $t=220$ 毫秒：第二個 ACK 回來了，遊戲客戶端又送出了一個新封包進入佇列。
#### 為什麼會變成 Bufferbloat？
- 離開佇列的速度：每 $20$ 毫秒傳送一個封包。
- 進入佇列的速度：每 $20$ 毫秒收到一個 ACK，觸發一個新封包進入佇列。
進與出的速度達到平衡，亦即最初在 $t=0$ 瞬間累積在緩衝區裡的那些封包（課本例子中最後穩定維持在 5 個封包的長度），永遠都不會被排空。
| 網路狀態指標 | 實際情況與影響 |
| ------------------- | ------------------------------------------------------------------------------------------------ |
| 吞吐量（Throughput） | 最佳狀態，水管是滿的，每 20 毫秒都有封包順利抵達目的地。 |
| 佇列延遲（Queuing Delay） | 極度糟糕，佇列長度維持不變，每一個新產生的動作（如玩家開槍、移動）所對應的封包，都必須在路由器裡排隊等待前面 5 個封包傳完，平白無故多出了 $5 × 20 \text{ms} = 100 \text{ms}$ 的固定延遲。 |
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 354, Figure 4.10)
## 4.2.5 Packet Scheduling（封包排程）
該節摘要：封包排程（Packet Scheduling）是路由器決定在輸出佇列中，哪一個等待中的封包可以獲得下一個傳輸機會的決策機制。
在網路壅塞時，不同類型的流量對延遲的容忍度完全不同，例如即時的 Skype 語音通話（VoIP）只要延遲幾十毫秒就會嚴重影響體驗，但背景下載的電子郵件慢個兩秒卻無關痛癢。
排程機制讓我們可以打破先來後到的規則，根據封包的重要性或公平性來分配網路資源。
幾乎所有現代路由器的高階輸出埠都實作了排程演算法，然而越複雜的排程演算法（如 WFQ）需要消耗越多的硬體運算資源，因此在極高速的核心路由器上，演算法的複雜度與線速（Line-rate）的極限永遠是工程設計上必須妥協的難題。
### 術語解析
- 先進先出（First In First Out, FIFO）：最基礎的排程法則，封包依照抵達的順序排隊與離開，就像日常在超市結帳排隊等待一樣。
- 優先權佇列（Priority Queuing）：將封包分為不同優先等級，高優先權的封包永遠比低優先權的封包先傳送。
- 循環分時佇列守則（Round Robin Queuing Discipline）：將封包分類後，排程器像輪盤一樣，依序從每個類別中抽出一個封包來傳送，確保每個類別都有被分到封包來做傳送。
- 不停工的佇列（Work-conserving Queuing）：一種排程器的特性，只要有任何封包在佇列中等待，排程器就不會讓傳輸連結（Link）閒置，如果輪到某個類別但該類別是空的（找不到任何封包），排程器會立刻跳到下一個類別。
- 加權公平佇列（Weighted Fair Queuing, WFQ）：Round Robin 的升級版，除了輪流發送外，還給予每個類別不同的權重，讓不同類別能按比例分配到保證的頻寬。
### 基本款：先進先出（FIFO）
這是最直觀的設計：
- 當封包抵達時，直接排在隊伍最後面。
- 當傳輸連結空閒時，排程器就從隊伍最前方取出一個封包傳送。
丟包策略：當緩衝區滿了，新來的封包無處安放時，必須決定丟棄誰，常見的作法是去尾（Drop-tail），直接把新來的封包丟掉；或是使用之前提過的主動式佇列管理（Active Queue Management, AQM）來提早丟棄封包以發出壅塞信號。
下圖 4.11 為先進先出（FIFO）佇列的抽象表示方法：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 355, Figure 4.11)
下圖 4.12 為 FIFO 佇列的運作圖：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 356, Figure 4.12)
### 特權款：優先權佇列（Priority Queuing）
為了保障重要流量（例如網路管理訊息或 VoIP），路由器會在輸入時將封包分類，送入不同的優先權佇列中。
- 運作機制：只要高優先權佇列裡有封包，就絕對輪不到低優先權佇列裡的封包傳送。
- 若是優先權類別相同的封包中做選擇時，通常以 FIFO 方式進行。
- 非先佔式的優先權佇列（Non-preemptive Priority Queuing）：網路傳輸通常是非先佔式的。
- 也就是說，即使有一個低優先權的封包正在傳輸，突然來了一個高優先權的封包，路由器也不會中斷目前正在傳輸的低優先權封包。
- 高優先權封包必須等這個低優先權封包傳完，才能搶下下一個傳輸權。
下圖 4.13 為優先權佇列的模型：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 356, Figure 4.13)
下圖 4.14 為優先權佇列的運作圖：
1、3、4 封包皆為高優先權類別，其餘 2、5 為低優先權類別。封包 1 優先做傳輸，傳輸完後接著輪到 3（即便 2 比他早，但因為 3 優先權較高），以此類推。
而輪到 2 傳輸時，儘管後來的 4 優先權比他高，但因為 2 在傳輸，所以不能打斷 2 的傳輸（非先佔式的優先權佇列）。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 357, Figure 4.14)
### 公平輪替款：循環分時（Round Robin）與加權公平佇列（WFQ）
優先權佇列有一個致命缺點：如果高優先權封包源源不絕地湧入，低優先權封包就永遠傳不出去。
為了解決這個問題，引入了輪流的概念：
- 循環分時佇列守則（Round Robin Queuing Discipline）：將封包分類後，排程器依序從 Class 1、Class 2、Class 3... 輪流提取封包傳送。
- 它是不停工的佇列（Work-conserving Queuing），即如果輪到 Class 2 卻沒有封包，排程器不會在那邊停下來等，而是會立刻去檢查下一個類別 Class 3。
下圖 4.15 為兩個類別的循環分時佇列的運作圖：可看到當類別 1 的封包 1 傳輸完後，就輪到類別 2 的封包 3，接著這樣循環下去。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 359, Figure 4.15)
- 加權公平佇列（Weighted Fair Queuing, WFQ）：這是現今路由器極為廣泛實作的演算法。
- 它也是循環分時且不停工的，但它多了一個權重（Weight）。
- 假設有 $N$ 個類別，每個類別 $i$ 分配到一個權重 $w_i$，WFQ 會保證類別 $i$ 能夠得到等於 $\frac{w_i}{\sum w_j}$ 的服務比例（分母中的和是來自於對所有佇列中有封包在等待傳輸的類別計算而得）。
- 在最糟的情況下（所有類別都有封包在排隊），類別 $i$ 保證可以獲得的頻寬比例為：$$R \cdot \frac{w_i}{\sum w_j}$$
- （其中 $R$ 是該連結的總傳輸率，$w_j$ 包含所有目前有封包在排隊的類別權重）。
下圖 4.16 為 WFQ 加權公正佇列：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 360, Figure 4.16)
### 排程演算法對照表
| 排程機制 | 分類方式 | 處理邏輯 | 優點 | 缺點／限制 |
| -------- | ------ | ----------------------------- | ----------------------- | ----------------------------- |
| FIFO | 無分類 | 先進先出：按照封包抵達順序依序傳送，不區分封包類型或重要性。 | 實作極度簡單，硬體負擔最小 | 無法區分流量重要性，對即時應用極不友善 |
| Priority | 依優先權分級 | 高優先級有封包，低優先級就只能等。 | 保證了關鍵流量（如語音、控制訊號）的極低延遲 | 低優先級流量可能面臨傳不了封包的風險 |
| WFQ | 依類別分級 | 權重輪詢：按權重比例（$w_i$）給予每個類別傳輸保證。 | 既能保障公平性，又能為特定類別提供最低頻寬保證 | 需要在硬體維護多個佇列與權重計算，實作複雜度最高 |
## 總整理
路由器的核心任務就是當網路的「圓環交流道」，精準且快速地把資料包（Datagram）送往正確的出口。
### 路由器的 4 大組件
1. 輸入埠（Input Port）：入口閘道。負責終止實體連結、處理連結層，並執行查詢（Lookup）以決定封包要去哪個輸出埠。
2. 交換結構（Switching Fabric）：內部高速公路。將封包從輸入埠搬運到輸出埠。
3. 輸出埠（Output Port）：出口閘道。負責將封包存入緩衝區排隊，並封裝回連結層與實體層送出。
4. 繞送處理器（Routing Processor）：大腦。計算與維護轉送表（傳統網路），或與 SDN 控制器溝通並配發轉送表。
### 資料層 vs. 控制層
為應對極高速流量，路由器在架構上採分離設計：
* 資料層（Data Plane）：由硬體實作，負責轉送（Forwarding），運作於奈秒級別。涵蓋輸入、輸出與交換結構。
* 控制層（Control Plane）：由軟體實作，負責繞送（Routing），運作於毫秒/秒級別。涵蓋繞送處理器。
### 4.2.1 Input Port Processing and Destination-Based Forwarding（輸入埠處理與基於目的端的轉送）
輸入埠必須在極短時間（奈秒）內決定封包去向，因此不能依賴中央 CPU，必須在地化高速處理。
* 處理三階段：
1. 線路終端（實體層）。
2. 資料連結處理（連結層）。
3. 查詢、轉送與排隊（網路層/資料層核心）。
* 分散式查表：繞送處理器會將轉送表發送影子副本（Shadow Copy）到各輸入埠，搭配 TCAM 硬體記憶體，能以 $O(1)$ 常數時間完成高速比對。
* 最長址首相符原則（Longest Prefix Match）：當封包的目的地 IP 同時符合轉送表中的多個範圍（址首）時，路由器會選擇「匹配位元數最長、最精確」的那條路徑。
* Match plus Action：這是一種通用網路抽象模型（匹配條件後執行動作），路由器查 IP 轉送是特例，交換器查 MAC、防火牆查 Port 也都是此概念。
## 4.2.2 Switching（交換）
交換結構負責將封包從輸入埠移至輸出埠，有三種主流技術：
| 交換技術 | 運作原理與效能瓶頸 | 特性與極限 |
| :--- | :--- | :--- |
| 記憶體（Memory） | 早期做法，封包經 CPU 複製進出記憶體。 | 效能受限記憶體頻寬，極限吞吐量為 $B/2$（無法平行傳輸）。 |
| 匯流排（Bus） | 輸入埠加標籤後透過單一共享匯流排丟給輸出埠。 | 單線道，一次只能過一個封包。受限匯流排頻寬。 |
| 互連網路（Crossbar） | $2N$ 條網格匯流排，透過開關矩陣控制。 | 非阻塞式（Non-blocking）。只要目的地不同即可平行傳輸，效能最高。 |
---
## 4.2.3 Output Port Processing（輸出埠處理）
處理流程與輸入埠剛好顛倒，是封包離開前的最後一站：
1. 佇列（緩衝）：接收來自交換結構的大量封包，若實體線路來不及送，就先放進記憶體排隊。
2. 排程與解佇列：決定下一個要送哪個封包（見後續排程演算法），並將其取出。
3. 連結與實體層傳輸：封裝成訊框（Frame）並轉為實體訊號打入線路。
## 4.2.4 Where Does Queuing Occur?（佇列與延遲在哪發生？）
當封包抵達速度 > 處理或傳輸速度時，就會發生佇列，而緩衝區滿載就會導致封包遺失（Packet Loss）。
* 輸入佇列：交換結構不夠快時發生。
* 致命傷：列前端攔阻（HOL blocking）：排在隊伍最前面的封包因為目的地塞車卡住，導致後面「本來可以去空閒出口」的封包跟著被擋住。
* 輸出佇列：多個輸入埠同時送封包給同一個輸出埠時發生。
* 丟棄策略：
1. 去尾（Drop-tail）：滿了就直接丟棄新封包。
2. 主動式佇列管理（AQM / RED）：快滿時提早丟棄或標記封包，警告發送端網路已壅塞。
* 緩衝區膨脹（Bufferbloat）：
* 理論緩衝區大小：$$B = \frac{RTT \times C}{\sqrt{N}}$$
* 盲目加大緩衝區雖能減少掉包，卻會讓封包在裡面排隊排太久，導致持續性的極高網路延遲。
## 4.2.5 Packet Scheduling（封包排程）
決定佇列中哪個封包優先傳送的機制，是保障服務品質（Quality of Service, QoS）的關鍵：
| 排程演算法 | 運作邏輯 | 優缺點 |
| :--- | :--- | :--- |
| FIFO（先進先出） | 依抵達順序排隊。 | 實作最簡單；但不分輕重緩急，對即時應用不友善。 |
| Priority（優先權佇列） | 分等級，高優先權永遠先傳輸（非先佔式）。 | 能保障關鍵流量；但低優先權可能永遠輪不到。 |
| Round Robin（循環分時） | 分類別，排程器依序輪流從各類別抽封包傳送。 | 保障公平性，且為不停工（Work-conserving），空類別會直接跳過。 |
| WFQ（加權公平佇列） | 賦予各類別不同權重（$w_i$），按比例分配保證頻寬。 | 結合公平與優先保障，但硬體實作複雜度極高。 |