CS 168 · DISCUSSION 10 · GUIDED REASONING WORKBOOK
先把 topology 转成 active tree、path set 或 overlay/underlay 两层 state，再计算容量；不要只看一张漂亮的 Clos 图。
无需离开 CourseStack：先预测，再在表格、时间线或状态空间里完成推导；卡住时逐层打开提示，最后才展开解释与变式。
已阅读 Spring 2026 worksheet 与 official solution；以下是原创等价练习。官方 IDs 用于 coverage，对精确原题请回到页末 PDF。
对应官方 1.1、1.2、1.3、1.4、2.1、2.2、2.3、2.4
Why the official problem exists：同时训练 datacenter design claims、root selection、failure reconvergence 和“不发 update 是否关键”。
七台 switches A–G，A 为最小 ID root；同 cost 时选较小 neighbor。候选 links：AB,AC,BD,CE,CG,DF,EG。
先预测：A 失效后新的 root？
为每个 switch 填 root port；列 active links；A 失效后重算。若 F 漏发 update，判断它是否位于其他节点到 root 的最短证据链。
每节点选择到 root 的最佳 tuple。
树应有 V-1 edges 且连通无环。
遗漏消息只有在它可能改善邻居 belief 时才影响结果。
初始可取 AB,AC,BD,CE,CG,DF；A 下线后 B 成 root，重算 BC,BD,CE,CG,DF。F 若不是任何其他节点最佳路径上的传播者，漏发不改变最终有效树。
message loss 的影响取决于它是否携带支配当前 state 的更优证据。
把 F 的 bridge ID 改为最小并重跑，漏发现在会影响谁？
对应官方 3.1、3.2、3.3、3.4、3.5、3.6
Why the official problem exists：从 minimal paths、bisection、failure 后容量和最坏 hash 依次推导。
每个 leaf 与四台 spine 都有 10Gbps link；servers 只接自己的 leaf。不同 leaf 间每条 minimal path 选择一台 spine，同一 flow 固定 hash。
先预测：ECMP 通常如何避免同一 flow 内重排？
| case | 你要数的对象 | 答案 |
|---|---|---|
| M1→M2 | 同 leaf minimal path | ____ |
| M1→M5 | 可选 spine | ____ paths |
| L1 | rest cut | 4 uplinks × 10Gbps | ____ |
| S1,S3 fail | remaining uplinks | ____ |
| 4 flows worst hash | 共享一条 10Gbps bottleneck | ____ per flow |
path count 是组合乘积。
bisection bandwidth 是跨 cut 容量和。
最坏 hash 要按共享 bottleneck flow 数分。
同 leaf 不经 spine；跨 leaf 有 4 条 minimal paths。L1 的 uplink cut 是 40Gbps；S1/S3 失效后剩 20Gbps。若四条 flow 最坏地落到同一条 10Gbps path，每流约 2.5Gbps，而另外三条 path 可以空闲。路径数量、aggregate cut capacity 与单流吞吐是三个不同量。
topology capacity、routing choice 与 traffic assignment 是三层不同问题。
改用 flowlet switching；它如何在利用多路径与避免 reorder 间取舍？
对应官方 4.1、4.2、4.3
Why the official problem exists：通过每跳 header state 推导路由表规模隔离。
VM1 overlay dst=192.0.2.3，位于 physical server4=4.4.4.4；路径 S1→R1→S4。
先预测：R1 的 FIB 必须知道 VM overlay /32 吗？
| node | action | inner dst | outer dst |
|---|---|---|---|
| S1 | ____ | 192.0.2.3 | ____ |
| R1 | forward | 192.0.2.3 | ____ |
| S4 | ____ | 192.0.2.3 | 4.4.4.4 |
ingress adds outer header。
transit router 查 outer destination。
egress removes outer header。
S1 封装 outer dst=4.4.4.4；R1 仅按 underlay 转发；S4 解封装并交给 VM。无 overlay 时 R1 跟踪每 VM；有 tunnel 时只跟踪 physical endpoints。
封装把地址空间 ownership 与 transit forwarding state 解耦。
VM 迁移到 S5，只需更新哪些 mapping，哪些 transit FIB 可不变？
画一个 2-pod Clos，计算跨 pod path/cut；删两条 spine 后重算；再为一个 VM packet 填每节点 inner/outer destination。