路由与路由问题
Routing一个通信网络有 N 个输入端和 N 个输出端（N 取 2 的幂），中间是一堆小交换机。谁去谁家由一个置换 π 规定：输入 i 的包要送到输出 π(i)。路由就是解决这个 π 的一组路径。最朴素的网络是完全二叉树网：树中任意两点路径唯一，输入 1 到输出 3 的路线清晰唯一。
但树网有个致命伤：根交换机是瓶颈——任何跨子树的通信都要过它。最坏置换 π(i) ::= N−1−i 下，每个包都得路过根：根的拥塞 = N，网络整体报废。这逼出了三个度量：直径（最坏延迟）、开关数（成本）、拥塞（最坏负载）。
二维阵列：花直径换不堵
The 2-D Array阵列把 N 个输入排成一列、N 个输出排成一行，中间 N² 个 2×2 开关。直径涨到 2N（差 1000 输入的树网 22 步 vs 阵列 2000 步），换来定理 11.3.1：拥塞恰好为 2。证明的两半都能"画"出来：上界——每包先右走到自己的列再下走，行 i 的开关最多只见 2 个包；下界——π(0)=0、π(N−1)=N−1 时左下角开关必被 2 个包穿过。
蝶形网：递归数据类型的胜利
The Butterfly蝶形网是递归定义的（第 7 章语法再就业）：F₁ 是 2 输入 2 输出的交叉开关；Fₙ₊₁ 把两份 Fₙ 竖排，新输入 i 与 2ⁿ+i 各连到同一个第 i 个输入开关。开关数 N(logN+1)、直径 logN+2，拥塞约 √N——树与阵列的折中。每个输入到每个输出路径唯一（递归路由），习题 11.8 证明拥塞恰为 √N（N 偶次幂）：第 i 列每个开关恰有 2ⁱ 条入径与 2^(logN−i) 条出径。
三大度量与 trade-off
Routing Measures设计通信网络 = 在三个互相冲突的指标间找平衡。移动滑块看四种经典网络在不同规模 N 下的表现——没有全能冠军，只有 trade-off：
网络设计四强与 Beneš 圣杯
Network Designs2-D 阵列把拥塞压到 2（定理 11.3.1：先横后竖走，每个交换机至多经手 2 个包）——代价是 N² 个开关。Butterfly 网递归生长（Fₙ₊₁ = 两个 Fₙ + 新输入列），路由唯一、直径 log N + 2、拥塞 ≈ √N。Beneš 网则是把两个 butterfly 背靠背缝起来——开关和直径翻倍，换来 拥塞 = 1：任何置换都有"每条边至多一个包"的完美路由。Holy Grail 到手！
证明是归纳 + 一个漂亮的 2-着色：把"包 i 和包 j 不能走同一子网"记成约束图的边——约束图每个顶点至多 2 条边（一条来自输入约束、一条来自输出约束），两条边分属两组 ⇒ 每圈偶长 ⇒ 可 2-着色（引理 11.3.3）。红包走上子网、蓝包走下子网，归纳完成。
拥塞直觉快判
Quick Check终局自测
Final Check六题，覆盖全章。
彩蛋与课后挑战
Easter Eggs & ProblemsPage & Brin 的提醒、Akamai 的实践（原章开头 + 第 6 章）
第 6 章的 Mating Ritual 在 Akamai 的 6.5 万台服务器上真实分流；本章的网络设计则活跃在电话交换机与并行计算机内部。图论不是纸面游戏——Page 和 Brin 靠一张有向图改变了世界（原书开头原话："pay attention to graph theory, and who knows what might happen!"）。
德布鲁因图与 k-路径网络（原书习题 10.5 与 11.5）
第 10 章习题 10.5 的 de Bruijn 图（把每个 k-bit 串当顶点、滑动窗口当边）是"路径即结构"的好玩具；本章习题 11.5 让你填的则是 k-路径网络（5-path / n-path）的参数表——同样是"把路径当包"的构造，但两者各自独立，并无直接承袭关系。
课后挑战（均出自原书习题）
- 11.1 给定一个通信网络：求最大拥塞、构造最坏/最好置换 π。
- 11.2 对 B₃ 中的一个具体置换亲手画约束图（虚线边=第二列冲突，实线边=倒数第二列冲突），再 2-着色完成路由。
- 11.5 / 11.7 设计你自己的 n-path / Reasoner-net，填 diameter / 拥塞 / LMC / CML 对比表——网络设计的毕业考。