三个核心指标
度、直径、对分带宽，共同衡量拓扑优劣
CS152 · 第 25 课
从多核芯片内部到整个数据中心，只要有多个计算节点需要通信，就需要回答同一组问题：用什么拓扑连接它们？数据包怎么找路？如何避免死锁？这一课系统梳理互联网络设计的核心指标与机制。
常见拓扑：总线（bus）、环（ring）、交叉开关（crossbar）、二维网格（mesh）、环网（torus）、超立方体（hypercube）、树/胖树（tree/fat-tree）。三个衡量拓扑优劣的核心指标：
以 n×n 的二维网格为例：幻灯片给出直径约为 2n（严格的最坏情形曼哈顿距离精确值应为 2(n-1)，幻灯片这里给出的是一个近似/取整表述，量级完全正确，只是常数项有细微差异——这不是计算错误，只是原始材料采用了近似说法）。环网（torus）在网格基础上加入首尾相连的"回绕"链路，把直径大致减半到约 n（与"环网直径 ≈ 网格直径的一半"这一关系一致），代价是额外的布线。对分带宽的计算方式是"切断对分线的链路数 × 每条链路带宽"——对 n×n 网格做垂直切分，会切断 n 条链路（环网因为回绕链路也会被切断，实际是 2n 条）。
维序路由（Dimension-Order Routing, DOR，也称 XY 路由）：一种确定性路由算法，数据包先沿一个维度走完全程，再切换到下一个维度——对网格/环网而言，这个规则本身（不需要虚拟通道）就能保证网格拓扑下的无死锁。自适应路由则允许数据包根据网络当前的拥塞状况动态选择路径。死锁避免的另外两种手段：转向限制（禁止某些特定的转向组合，如"西转北"，以打破循环依赖）和虚拟通道。
存储转发（store-and-forward）：整个数据包必须先完整到达当前跳，才能继续转发到下一跳。虫孔路由（wormhole routing）：把数据包切成更小的"片（flit）"，让片在网络中流水线式地传递——头片可以在整个数据包到达当前跳之前就开始向下一跳移动，从而显著降低延迟；代价是如果头片被阻塞，可能会连带阻塞它已经占用的多条链路。
虚拟通道（Virtual Channel, VC）：把多条逻辑通道复用到同一条物理链路上——既可以用来避免死锁（限制数据包转向时能使用哪些虚拟通道），也可以减少队首阻塞（head-of-line blocking）带来的性能损失。
胖树（fat-tree）是一种树形拓扑，链路带宽在靠近树根的层级逐渐变"胖"（并行链路更多），从而能够实现全对分带宽——这正是大型集群/数据中心网络的常见选择，直接呼应第 24 课末尾"服务器→机架顶部交换机→汇聚层交换机"的网络层级示意图。
问题 1："虫孔路由（wormhole routing）"相对"存储转发（store-and-forward）"的关键优势是什么？
问题 2：维序路由（Dimension-Order Routing, DOR/XY 路由）为什么能在网格拓扑上不依赖虚拟通道就保证无死锁？
问题 3：为什么"胖树（fat-tree）"拓扑特别适合大型集群/数据中心网络？
度、直径、对分带宽，共同衡量拓扑优劣
DOR/XY 路由用固定转向规则天然避免死锁
片级流水线降低延迟，代价是可能连带阻塞多条链路
数据中心网络标准拓扑，靠近树根链路更"胖"以保持全对分带宽
sp23/lecture_slides/L25_Interconnects.pdf（UC Berkeley CS152/CS252A, Spring 2023, Sophia Shao）