路由器要把分组送往目的地，首先得知道网络里有哪些路由器、它们之间如何连接，以及经过每条链路的代价。链路状态路由（Link-State Routing）的做法是：让路由器收集全网拓扑信息，再各自计算到目的地的最短路径。

从邻居到全网拓扑

每台路由器先发现直接相连的邻居，并确定到邻居的链路代价。常见的做法是通过 Hello 消息确认邻居关系。

之后，路由器生成链路状态通告（Link-State Advertisement，LSA），描述自己连接了哪些邻居以及相应的链路代价，并把通告泛洪给网络中的其他路由器。这样，每台路由器都能逐步建立一份全网拓扑数据库。

泛洪需要处理重复和过期信息。LSA 通常带有序列号和生存时间：序列号帮助路由器识别更新版本，生存时间则让旧信息最终失效。拓扑变化时可以发布新通告，此外也会定期刷新信息。

这里的“一致”不是指所有路由器在同一瞬间看到完全相同的内容。拓扑更新需要时间传播；网络稳定并且通告成功扩散后，各路由器的数据库才会收敛到相同的拓扑视图。

用 Dijkstra 计算路径

有了拓扑数据库后，每台路由器都可以把自己作为起点，运行 Dijkstra 等最短路径算法，计算到其他路由器的最低代价路径。

计算出的路径不会原样写进转发表。路由器通常记录的是下一跳（Next Hop）：收到分组后，根据目的地查出应交给哪个相邻路由器。

路由环路从哪里来

当拓扑信息还没收敛时，不同路由器可能依据不同版本的网络图转发。例如，R3 认为去目的地应先交给 R2，而 R2 仍认为应该交给 R3，分组就可能在两者之间来回转发。因此链路状态路由不仅要计算最短路径，也需要可靠地传播并更新拓扑信息。

为了让计算结果可互操作，路由器需要对链路代价采用相同的定义，并使用兼容的路径计算与平局处理规则。遇到多条等价最短路径时，也可以使用一致的选择规则，或明确支持等价多路径转发（ECMP）。

和距离矢量路由的区别

链路状态路由向其他路由器传播本地链路信息，各路由器据此重建拓扑并独立运行最短路径算法。距离矢量路由则主要和邻居交换到各目的地的距离估计，不要求每台路由器都持有完整拓扑图。

两类方法都需要面对更新传播和网络变化带来的收敛问题；它们交换的信息、计算方式和故障行为则各不相同。

关于互联网体系结构与链路基础，可参阅上一篇 CS168 笔记；域间路由与 IP 寻址见路由器与 BGP 笔记。