CS 168 · LECTURE 05 · 2026-09-10 · 路由
路由不是一次最短路调用，而是在信息分散、拓扑变化和策略约束下持续维护下一跳状态。
版本快照：Fall 2026 官方课表与在线教材，核对日期 2026-09-02；官网仍标注 under construction，日期与政策可能变化。
每台路由器只掌握局部信息时，怎样共同形成无环、可达且可更新的转发表？
把网络表示为图 \(G=(V,E)\)，边权可代表时延、管理成本或策略度量。算法输出到每个目的地的下一跳和代价。但模拟器中的目的通常是 host，边在路由器本地体现为 port；图论节点、物理设备、接口和目的前缀是不同对象。
路由表项至少包含 destination、next hop/port、metric 与 freshness。缺少新鲜度，失效路线会永久存在；缺少下一跳，最短距离也无法转发数据包。
控制平面接收邻居通告、运行算法、更新路由信息；数据平面用稳定的 forwarding table 对每个包执行高速查找。前者关注收敛与策略，后者关注每秒包数、队列和线速实现。
二者相互连接但时间尺度不同：一次链路故障触发若干控制消息，随后数百万数据包使用新表项。把复杂计算放进每包路径会让转发成本不可控。
第一，路由器能观察什么：仅邻居距离，还是完整链路图？第二，何时发送：周期、触发、增量还是组合？第三，坏消息怎样传播：删除、毒化、序列号还是超时？这三问决定距离向量与链路状态的主要差异。
任何算法都要声明故障模型。消息可能延迟、乱序、重复，路由器可能重启，链路可能单向失败。只在同步、无丢失的理想轮次中正确并不足以部署。
拓扑稳定后达到正确表项称为收敛。但收敛过程中可能出现环路、黑洞和次优路径。TTL 限制环路包寿命，却不修复控制状态；快速收敛也不等于瞬态无损。
衡量路由协议要同时看状态规模、控制流量、计算复杂度、收敛速度、故障隔离和策略表达力。后续 DV、LS 与 BGP 分别在这些轴上选择不同位置。
对三路由器三角形，写出一条链路失效后控制平面事件序列与数据平面可能出现的两个瞬态结果。
检查：哪个动作属于数据平面？
link-up 事件创建直连候选
link-up 事件创建直连候选；route advertisement 创建经邻居候选；failure 使候选失效并触发重新选择。
检查：判断一个实现分支是否必要，最有力的问题是什么？
为一个三节点图写 before/event/after routing state。
答案必须出现 packet/message、local state/table、触发 event、after state 与 output；只给定义不算完成。
正文是 CourseStack 的中文解释与重新绘制的教学例子；官方页面负责课程原始定义，历史仓库只提供你的实现证据。