封包該往哪走：路由、轉送與 BGP 的去中心化導航

路由器到底怎麼「知道」該把封包往哪丟？

入門篇裡，我們說封包每經過一台路由器(router)就「讀一次目的地址、查路由表、決定下一站」，輕描淡寫地帶過了「逐跳轉送(hop-by-hop forwarding)」。但這句話藏了一個巨大的問號：全世界有數十億個位址、數十萬條獨立網路，一台路由器的路由表(routing table)裡到底裝著什麼？它又是怎麼在零點零幾毫秒內，從一張可能有上百萬條規則的表裡，決定一個封包的命運的？

更弔詭的是：沒有任何一台路由器「看得到整個網際網路」。每台路由器只認識自己的鄰居，卻能讓一個從台灣出發的封包，準確地在十幾跳之內找到地球另一端的某台伺服器。沒有總指揮、沒有全局地圖，這套去中心化的「集體導航」是怎麼浮現出來的？這一篇，我們就鑽進路由器的腦袋裡。

轉送與路由：兩件常被混為一談的事

要談清楚，得先把兩個動作切開——它們在時間尺度上差了好幾個數量級。

轉送(forwarding) 是「資料平面(data plane)」的事：封包真的到了，路由器看一眼目的位址，從轉送表(forwarding table)查出該從哪個出介面(output port)送出去，然後送出。這件事必須在奈秒到微秒等級完成，通常由專用硬體(ASIC)執行，因為每秒可能有數十億個封包經過。

路由(routing) 是「控制平面(control plane)」的事：路由器們事先透過路由協定彼此交換資訊，協力算出「要去某個目的地，下一跳該交給誰」，把結果寫進路由表。這件事在秒到分鐘等級進行，由路由器的 CPU 跑軟體完成。

打個比方：路由像是平時繪製與更新地圖，轉送則是司機開到路口時瞄一眼地圖立刻轉彎。地圖偶爾更新就好，但每個路口的轉彎決定必須瞬間做出。

位址不是一個個記的：CIDR 與最長前綴匹配

如果路由器要為「每一個 IP 位址」存一條規則，路由表會爆炸到無法處理。真正的做法是以「網段」為單位聚合。

IPv4 位址有 32 位元，習慣寫成像 140.115.103.70 這樣的四段十進位。一個「網段」用「位址 / 前綴長度」表示，例如 140.115.0.0/16，意思是「前 16 位元固定，後 16 位元任意」——這一條規則就涵蓋了 $2^{16} = 65536$ 個位址。這種無類別的位址聚合方式叫 CIDR（Classless Inter-Domain Routing，無類別域間路由）。

於是路由表變成一串「前綴 → 下一跳」的對應：

目的前綴            下一跳(next hop)      出介面
140.115.0.0/16      203.74.205.1         eth0
140.115.103.0/24    10.0.0.2             eth1
0.0.0.0/0           203.74.205.254       eth0   ← 預設路由(default route)

問題來了：140.115.103.70 同時符合 /16 和 /24 兩條前綴，到底聽誰的？規則是 最長前綴匹配(longest prefix match, LPM)——匹配位元數最多的那條優先。所以 /24（更精確、更具體）勝過 /16，封包走 eth1。而最後那條 0.0.0.0/0 前綴長度為 0，匹配任何位址但最弱，是「以上都不符時的兜底」。

最長前綴匹配是整個網際網路轉送的核心演算法。它讓路由可以「先寫粗略大方向、再用更具體規則覆蓋例外」，正是位址能聚合、路由表不致爆炸的關鍵。

動手算一下：判斷兩個位址是否同網段

判斷某位址屬不屬於某網段，要把位址和前綴都換成二進位，比較前綴長度那麼多個位元。我們用程式把這個過程攤開：

def ip_to_int(ip):
    """把點分十進位 IPv4 轉成 32 位元整數"""
    parts = [int(x) for x in ip.split('.')]
    return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]

def in_subnet(ip, network, prefix_len):
    """判斷 ip 是否落在 network/prefix_len 網段內"""
    # 前 prefix_len 個位元為 1、其餘為 0 的遮罩
    mask = (0xFFFFFFFF << (32 - prefix_len)) & 0xFFFFFFFF
    return (ip_to_int(ip) & mask) == (ip_to_int(network) & mask)

print(in_subnet('140.115.103.70', '140.115.103.0', 24))  # True
print(in_subnet('140.115.200.5',  '140.115.103.0', 24))  # False
print(in_subnet('140.115.200.5',  '140.115.0.0',   16))  # True

關鍵在 mask：/24 的遮罩是 255.255.255.0，把位址與遮罩做位元 AND，等於「抹掉後 8 位元、只看前 24 位元」。兩邊抹完後相等，就代表前 24 位元一致，屬同網段。

最長前綴匹配的查表，本質上就是在所有「匹配成功」的前綴裡挑 prefix_len 最大者：

def longest_prefix_match(dest_ip, table):
    """table 為 [(network, prefix_len, next_hop), ...]"""
    best = None
    for network, prefix_len, next_hop in table:
        if in_subnet(dest_ip, network, prefix_len):
            if best is None or prefix_len > best[1]:
                best = (network, prefix_len, next_hop)
    return best

table = [
    ('0.0.0.0',       0,  '203.74.205.254'),
    ('140.115.0.0',   16, '203.74.205.1'),
    ('140.115.103.0', 24, '10.0.0.2'),
]
print(longest_prefix_match('140.115.103.70', table))
# ('140.115.103.0', 24, '10.0.0.2')  ← /24 勝出

真實高速路由器不會這樣線性掃描——它用 trie（字典樹） 或 TCAM（三態內容定址記憶體）硬體在常數時間內完成查找。但邏輯上要找的東西，就是上面這個「匹配中前綴最長者」。

路由表是怎麼長出來的：距離向量 vs 鏈路狀態

轉送表裡的「下一跳」不是人手動填的（除了少數靜態路由），而是路由器們透過路由協定自動算出來的。兩大家族長期主導著這個領域。

距離向量(distance-vector) 的哲學是「只跟鄰居聊，告訴鄰居我到各地的距離」。每台路由器維護一張「到各目的地的最短距離」向量，週期性地把整張向量傳給直接鄰居；收到鄰居的向量後，用 Bellman-Ford 思路更新自己：

$$ D_x(y) = \min_{v \in N(x)} \big\{ c(x, v) + D_v(y) \big\} $$

意思是「我 $x$ 到 $y$ 的最短距離，等於『我到某鄰居 $v$ 的成本 $c(x,v)$』加上『$v$ 自稱到 $y$ 的距離 $D_v(y)$』，取所有鄰居中的最小值」。沒有任何一台路由器知道完整拓樸，但透過反覆交換、迭代收斂，每台都能算出正確的下一跳。RIP 是經典代表。它的著名弱點是「壞消息傳得慢」——某條路斷了，錯誤資訊可能在路由器間繞圈圈，產生暫時的路由迴圈，史稱「count-to-infinity」問題。

鏈路狀態(link-state) 走相反路線：「不報距離，而是把『我跟誰直接相連、成本多少』這份『鏈路狀態』廣播給網路裡的每一個人」。於是每台路由器都收齊全網的鏈路資訊，在本地拼出一張完整地圖，再各自跑一次 Dijkstra 最短路徑演算法，算出到所有目的地的最佳路徑。OSPF 是代表。它收斂快、不易產生迴圈，代價是每台路由器要儲存完整拓樸、運算量較大。

                距離向量(RIP)         鏈路狀態(OSPF)
聊天對象        只跟直接鄰居           廣播給全網
傳的內容        我到各地的「距離」      我跟鄰居的「連線狀態」
全局視野        沒有，只知方向         有，本地重建完整地圖
核心演算法      Bellman-Ford          Dijkstra
收斂速度        慢，可能繞圈           快
擴展性          小型網路              中大型網路

看一個例子：用 Dijkstra 親手算一次最短路徑

鏈路狀態路由器拿到全網地圖後，跑的就是 Dijkstra。假設一張小網路，節點 A、B、C、D，邊的成本如下，我們從 A 算到所有點：

import heapq

def dijkstra(graph, source):
    """graph: {node: [(neighbor, cost), ...]}，回傳 source 到各點最短距離"""
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    prev = {node: None for node in graph}
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, cost in graph[u]:
            nd = d + cost
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, prev

network = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 6)],
    'C': [('A', 4), ('B', 2), ('D', 3)],
    'D': [('B', 6), ('C', 3)],
}
dist, prev = dijkstra(network, 'A')
print(dist)   # {'A': 0, 'B': 1, 'C': 3, 'D': 6}

注意 A 到 C 的直連成本是 4，但繞道 A→B→C 只要 $1 + 2 = 3$，更短——Dijkstra 自動找出這條捷徑。A 到 D 則走 A→B→C→D（$1+2+3=6$），勝過 A→B→D（$1+6=7$）。用優先佇列實作的 Dijkstra 時間複雜度為 $O((V + E) \log V)$，對中型網路綽綽有餘。

把 prev 回溯，就能得到「下一跳」——這正是要寫進轉送表的資訊。例如要去 D，從 D 沿 prev 回溯到 A，第一步是 B，所以「目的 D 的下一跳 = B」。

一台路由器管不了全世界：自治系統與 BGP

到這裡你可能想：那全網跑一個大 Dijkstra 不就好了？問題是全網有數十萬個獨立網路、分屬不同公司與國家，彼此不信任、政策各異——讓中華電信的路由器去儲存全球完整拓樸並聽命於 Google 的成本設定，既不現實也不安全。

於是網際網路被切成數萬個自治系統(Autonomous System, AS)，每個 AS 是「單一機構管理、對外採用統一路由政策」的網路集合，有自己的 AS 編號（如中央大學、某 ISP、某雲端業者各是一個 AS）。路由因此分成兩層：

• AS 內部(intra-AS)：用 OSPF、RIP 這類內部閘道協定(IGP)，目標單純——找「技術上最短」的路徑。
• AS 之間(inter-AS)：用 BGP（Border Gateway Protocol，邊界閘道協定），這是黏合整個網際網路的「膠水協定」。

BGP 的關鍵差異在於：它不追求最短路徑，而是執行「政策」。一個 AS 要不要把某條路徑告訴鄰居、願不願意幫鄰居轉送流量，背後是商業合約（誰付錢給誰、對等互連 peering）而非單純的跳數。BGP 屬於「路徑向量(path-vector)」協定——通告路由時會附上「這條路徑會經過哪些 AS」的完整 AS 清單，一來可用來執行政策，二來只要看到自己的 AS 編號已在清單中就拒絕，藉此偵測並避免迴圈。

這也解釋了一些真實世界現象：你的封包從台北到隔壁城市，有時竟繞道日本或美國——因為兩個 ISP 之間沒有直接的對等互連合約，得繞到雙方共同的上游交換點。技術上的近，不等於 BGP 政策上的近。

traceroute：親眼看封包的每一跳

理論講完，有個工具能讓你親眼看到封包走過的每一跳——traceroute（Windows 上是 tracert）。它的原理巧妙地利用了 IP 標頭裡的 TTL（Time To Live，存活時間） 欄位。

每個 IP 封包帶一個 TTL 計數器，每經過一台路由器就減 1；一旦某台路由器把 TTL 減到 0，它會丟棄該封包，並回送一個 ICMP「逾時(Time Exceeded)」訊息給來源——這個機制本來是防止封包在路由迴圈裡永遠繞下去的保險絲。traceroute 反過來利用它：

送出 TTL=1 的探測封包 → 第 1 台路由器減成 0，丟棄並回報 → 得知第 1 跳是誰
送出 TTL=2 的探測封包 → 第 2 台路由器減成 0，丟棄並回報 → 得知第 2 跳是誰
送出 TTL=3 的探測封包 → ……
依此類推，直到封包真正抵達目的地

於是螢幕上會一行行浮現出封包經過的每一台路由器位址與往返時間：

$ traceroute www.example.com
 1  192.168.1.1        1.2 ms
 2  203.74.205.254     8.5 ms
 3  211.22.33.1       12.1 ms
 4  * * *                       ← 有些路由器設定不回應
 5  72.14.x.x         45.3 ms
 ...

你可以親眼觀察到延遲在哪一跳突然跳高（往往是跨海光纖那一段），或某些路由器以 * * * 沉默（設定不回 ICMP）。這是把前面所有抽象理論「具現化」最直接的方式，強烈建議你打開終端機親手跑一次。

重點回顧

• 轉送(forwarding)是資料平面、奈秒級的硬體動作；路由(routing)是控制平面、秒級的協定協商。前者照表查、後者建表。兩者常被混為一談，但時間尺度差了好幾個數量級。
• 最長前綴匹配(LPM)是網際網路轉送的核心演算法：CIDR 把位址聚合成網段，查表時匹配位元最多的前綴勝出，讓路由表能「粗略大方向 + 具體例外覆蓋」而不爆炸。
• 距離向量（只跟鄰居報距離，Bellman-Ford）與鏈路狀態（廣播連線狀態、本地跑 Dijkstra） 是兩大路由協定家族，分別對應 RIP 與 OSPF，各有收斂速度與擴展性的取捨。
• 網際網路用自治系統(AS)分層治理：AS 內用 IGP 求最短路徑，AS 間用 BGP 執行商業政策——技術上的近不等於政策上的近。
• traceroute 利用 TTL 逐跳遞減的機制，把封包的每一跳具現化，是驗證所有理論最直接的工具。

深入探討（研究所視角）

把上面的拼圖再往上抽象一層，會看到一個深刻的張力：網際網路的路由是一個「沒有全局最佳解保證」的分散式系統。

域內路由（OSPF/Dijkstra）尚能逼近全局最短路徑，因為單一 AS 內資訊完整、目標一致。但域間的 BGP 完全是另一回事。BGP 是賽局而非最佳化——每個 AS 依本地政策獨立決策，整體不保證收斂，甚至可能根本不存在穩定狀態。理論上著名的 BGP 收斂與穩定性問題指出：當各 AS 的路由偏好設定彼此衝突時，系統可能陷入永久震盪（路由不斷翻來覆去）。學界用「Stable Paths Problem」這個圖論模型刻畫此現象，並證明判定某組政策是否能收斂在一般情況下是困難的。這跟你在演算法課學的「Dijkstra 一定找到最短路」形成強烈對比——一旦引入自利的多方政策，連「會不會停下來」都不再有保證。

第二個值得深思的點是路由的安全性。原始 BGP 建立在「彼此信任」的假設上：一個 AS 宣稱「我能到達某個前綴」，鄰居就相信。這留下巨大漏洞——前綴劫持(prefix hijacking)：惡意或設定錯誤的 AS 宣告一個它根本不擁有的前綴，且若它宣告的前綴更具體（前綴更長），依最長前綴匹配，全球流量就會被導向錯誤目的地。歷史上多次大規模斷網事件（例如某國 ISP 誤宣告 YouTube 的前綴，把全球流量黑洞化）正源於此。應對之道是 RPKI（Resource Public Key Infrastructure） 與 BGPsec，用密碼學憑證驗證「某 AS 是否真有權宣告某前綴」，把信任從「口說無憑」升級為「可驗證」。這也呼應了入門篇統計多工的精神：早期網際網路為了簡單、可運作、可擴展，在許多地方刻意省略了嚴格驗證與全局最佳化；今天我們補課的安全與穩定性機制，幾乎都是在為當年那些「先動起來再說」的工程取捨還債。

最後，把這條線索接回你後續的課程：轉送平面的 trie/TCAM 查找通往硬體與資料結構（IP lookup 是字串前綴查找的經典應用，與壓縮 trie、雜湊優化密切相關）；域內最短路徑通往圖論與最佳化；域間政策路由通往演算法賽局論(algorithmic game theory)與分散式系統的共識問題；RPKI/BGPsec 則通往網路安全與密碼學。一個「封包該往哪走」的樸素問題，竟同時是這幾個領域交會的十字路口——這正是計算機網路最迷人之處。