第十一章：通訊網路
通訊網路是連接計算機系統各個部分的橋樑。本章探討如何設計高效能的網路，並分析其數學性質。
11.1 路由
路由是指將資料封包從來源節點傳遞到目的節點的過程。好的路由演算法應該能找到最短路徑，並避免網路擁塞。
位元修正路由：
在超立方體網路中，每個節點由二進位編號表示。從節點 u 到節點 v 的路徑可以透過不斷修正 u 的位元，使其逐漸與 v 一致來實現。
在超立方體網路中，每個節點由二進位編號表示。從節點 u 到節點 v 的路徑可以透過不斷修正 u 的位元，使其逐漸與 v 一致來實現。
🧪 超立方體路由模擬器
下圖展示了一個 3維超立方體 (8個節點)。選擇來源和目的節點，觀察封包如何移動。
> 系統就緒。請選擇節點後點擊開始。
11.2 路由測度
衡量網路優劣的數學指標：
Diameter
網路直徑
任意兩點間最短路徑的最大值
Degree
分支度
每個節點連接的邊數 (硬體成本)
Bisection Width
對半頻寬
將網路切成兩半所需移除的最少邊數
對於 n-維超立方體：
節點數 = $2^n$
直徑 = $n$ (非常小，效率高)
分支度 = $n$ (隨規模增加，成本較高)
11.3 網路設計
設計網路時需要在成本(分支度)與效率(直徑)之間取得平衡。
- 完全圖： 直徑最小(1)，但分支度最大，硬體成本過高。
- 線性陣列： 分支度低，但直徑最大。
- 超立方體： 兩者之間的良好折衷，適合平行計算。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)