CS 168 · LECTURE 07 · 2026-09-17 · 路由
链路状态让每台路由器获得同一张拓扑图，再独立运行 Dijkstra；地址聚合则让这张图最终能映射到规模可控的前缀表。
版本快照：Fall 2026 官方课表与在线教材，核对日期 2026-09-02；官网仍标注 under construction，日期与政策可能变化。
如果每台路由器都知道全图，怎样保证它们知道的是同一个、足够新的图？
每台路由器产生 link-state advertisement，列出邻居与代价，并用序列号/年龄区分新旧。收到更新的 LSA 后写入链路状态数据库，再转发到除来路之外的邻居。重复与旧副本被丢弃。
泛洪的目标不是“消息只走一次”，而是让连通域内所有活路由器最终拥有同一组最新 LSA。ACK、重传、序列号和老化共同对抗丢失、重复与重启。
源点距离设 0，其余为无穷。每轮取尚未确定且 tentative distance 最小的节点，把它永久加入树，并松弛出边。非负边权保证之后绕经未确定节点不可能得到更短路径。
输出不是“整条路径字符串”，而是对每个目的回溯最短路树得到第一跳。相同代价时的 tie-break 必须稳定，否则不同重算可能造成无谓转发表抖动。
IPv4 地址同时承担定位与标识的历史角色。CIDR 前缀 192.0.2.0/24 表示高 24 bit 固定，剩余 8 bit 在该块内变化。提供商可向外通告聚合前缀，使全球表项数与网络块而非主机数接近。
更具体前缀允许多宿主、流量工程与例外路径，却削弱聚合。地址分配与路由可扩展性因此紧密相连。
DV 只交换目的距离，消息小但容易因间接信息形成环；LS 泛洪局部链路事实，状态和计算更多，却能快速在一致拓扑上重算。两者都不是“集中式”：LS 的图由分布式泛洪获得，每台路由器本地运行算法。
自治系统内部可选择 OSPF/IS-IS 等链路状态协议，而跨域 BGP 关注策略与可扩展性，不能简单用全球 Dijkstra 取代。
给五节点图手跑 Dijkstra，并把最终 predecessor tree 转成每个目的的 next hop；再加入一个 /24 与两个 /25 前缀解释聚合与例外。
检查：链路状态协议为什么需要序列号或年龄？
每个 router 接收 LSA、更新 topology database、运行 Dijkstra，再把 next hop 投影到 FIB
每个 router 接收 LSA、更新 topology database、运行 Dijkstra，再把 next hop 投影到 FIB；地址聚合减少表项。
检查：判断一个实现分支是否必要，最有力的问题是什么？
改变一条链路代价，手推 SPF tree 哪些节点的 predecessor 改变。
答案必须出现 packet/message、local state/table、触发 event、after state 与 output；只给定义不算完成。
正文是 CourseStack 的中文解释与重新绘制的教学例子；官方页面负责课程原始定义，历史仓库只提供你的实现证据。