OSPF 是一种链路状态路由协议它之所以能帮助数据包找到去往目的地的最佳路径靠的就是在每一台路由器上独立运行的一个数学算法。这个算法的名字叫SPFShortest Path First也就是经典计算机科学里的Dijkstra 算法。不过一说“算法”很多朋友就觉得头疼。没关系这篇文章会用你能轻易理解的方式一步步把这个过程拆开来讲。我们不会一上来就丢出一堆术语而是先从一个生活里的类比开始再慢慢对应到真实的 OSPF 网络中去。一、一个生活中的场景你用导航软件找最短路线想象你开车去一个陌生城市手机上的导航软件要帮你找出从当前位置到目的地耗时最短的路线。它是怎么算的呢肯定不能把所有可能路线都试一遍太慢了。导航软件的做法大体上是这样的首先它手里有一张精细的城市道路图图上标明了每条路的长度甚至还能知道实时拥堵情况。它会把自己看作起点不断向外扩展“从我这里出发能直接到哪几条路每条路要走多久” 把直接能到的路都标记下来。然后从这些还没处理过的路里挑出“离我最近”的一个路口把它当作“已经找到最佳路线”的点再从这个路口继续往周围看看能不能通过它让去其他路口的距离变得更短。就这样一圈一圈地往外扩直到计算完所有它能到达的路口为止。最终导航软件就能告诉你到任何一个地方的最快路线以及需要多长时间。这正是 Dijkstra 算法的核心思想也是 OSPF 用来算路的“引擎”。只不过在 OSPF 的世界里“城市道路”变成了路由器和连接它们的链路“耗时”变成了 OSPF 的度量值——开销Cost。二、OSPF 的“活地图”是怎么来的在导航软件里地图是事先下好的。在 OSPF 网络里每台路由器也必须要获得一份完全相同的网络地图这份地图叫做链路状态数据库LSDB。这个地图是怎么被画出来的呢靠的是 LSA链路状态通告。你可以这样理解每台路由器都像一个“广播员”它大声告诉全网络“我有几根线分别连着谁每根线的开销是多少。”这些广播信息LSA会被毫无更改地传遍整个网络区域确保每一台路由器都能听到所有其他路由器的“自我介绍”。最后每台路由器把收到的所有 LSA 汇总在一起就在自己脑子里形成了一张包含所有路由器和链路的网络拓扑图。到这里大家手里的地图就一模一样了。接下来每台路由器就要以自己为“我”在这张图上算出到达所有其它网段的最短路径。三、用一个简单的三台路由器网络来跑一遍算法我们先找一个最简单的例子抛开 OSPF 中那些特殊网络类型比如以太网广播只想象有三台路由器用点对点线路连成一个三角形R1 / \ 5/ \10 / \ R2-------R3 4图中数字是链路开销可以暂时理解成“距离”越小越快。现在我们站在R1的角度要算出它到 R2 和 R3 的最短路径。执行 Dijkstra 算法时我们要管理三份“列表”最短距离表dist记录从 R1 出发到各个节点的当前已知最短距离。一开始R1 到自己是 0到其他所有节点是无穷大∞。已确定节点集合visited放那些我们已经找到绝对最短路径的节点以后不再碰它们。候选节点集合剩下的、还没处理完的节点。准备好后我们开始一步一步地计算。步骤 1初始化dist[R1] 0dist[R2] ∞dist[R3] ∞visited {}此时 R1 是起点也是第一个要处理的“当前节点”。步骤 2处理 R1从未处理的节点中找 dist 值最小的一个。目前只有 R1 的 dist0自然选它。把 R1 放进 visited现在它“确定了”。然后从 R1 出发看它所有的邻居到 R2 的直接链路开销是 5。我们发现从 R1 到 R2 的新距离 dist[R1] 5 0 5 5。这比原来记录的 ∞ 小得多所以更新 dist[R2] 5。到 R3 的直接链路开销是 10。同理新距离 0 10 10比 ∞ 小更新 dist[R3] 10。现在各距离值R1:0 (已确定)R2:5R3:10步骤 3处理 R2从未确定的节点R2 和 R3中选 dist 最小的。R2 的 5 比 R3 的 10 小所以这一次选 R2。把 R2 放进 visited它现在也确定了。站在 R2 上看它的邻居R1 已确定不管只关心未确定的到 R3 的直接开销是 4。计算经过 R2 到达 R3 的路径总开销 dist[R2] 4 5 4 9。和 R3 原来的 dist10 比较9 更小所以更新 dist[R3] 9。更新后R1:0 (已确定)R2:5 (已确定)R3:9步骤 4处理 R3只剩下 R3 未确定了选它。把 R3 放进 visited。看 R3 的邻居R1、R2 都已确定没有未确定节点需要更新。结束。最终计算结果R1 到 R2 的最短距离是 5路径是 R1 → R2。R1 到 R3 的最短距离是 9路径是 R1 → R2 → R3而不是开销为 10 的直连链路。这个过程中最关键的一个操作就是每当我们确定一个新节点就用它当作“跳板”看看能不能帮我们把去其他节点的路变得更短。这叫做“松弛”操作就像把一根拉紧的绳子放松一样。四、把这个方法对应到 OSPF 真实行为上面简单三角形网络帮你理解了算法的骨架但实际 OSPF 网络要处理的情况稍微复杂一点。主要有两个地方不同我们稍微解释一下即使不太明白也没关系不影响核心理解1. 广播网络的特殊处理在真实的以太网里可能多台路由器连在同一个交换机上。这时 OSPF 不会画成全互联的蜘蛛网而是引入一个“虚拟节点”来代表这个广播网络叫做伪节点由 DR 扮演。算法上这个伪节点的作用是路由器到伪节点的开销等于真实链路开销。伪节点到各路由器的开销固定为 0。这样处理后最短路径的计算结果依然是正确的。你可以在脑中保留“虚拟节点”这个概念但这不是初学重点。2. 从最短距离到路由表Dijkstra 算法给出的结果是一棵以 R1 为根的最短路径树树上有所有路由器和网络节点。但路由器的路由表需要的是“目的网段” 和 “下一跳/出接口”。OSPF 会根据以下原则生成路由对于树上的叶子节点通常是末节网络直接加入路由表下一跳为沿着路径的第一个下一跳路由器。如果多条路径开销相等OSPF 会执行等价负载均衡ECMP将流量分摊到这几条路径上。五、为什么路由器不每次重新算一次完整的地图你可能会问每次网络里有条链路断了就要把整张大地图重新算一遍那得多累啊尤其是一些大型 ISP 网络有成百上千台路由器。没错所以路由器的操作系统做了优化这个优化叫增量 SPFiSPF。它的大致思路是如果只是某条链路失效那它只会影响到一部分节点的最短路径。路由器会记住上一次计算时生成的最短路径树只把受影响的那部分枝杈砍掉、重新接好而不是把整棵树连根拔起再种。这个优化对大型网络非常重要不过从学习算法的角度我们只需要知道有这回事就好。六、SPF 算法的几个重要特性理解 SPF 算法后你会更容易明白 OSPF 的一些行为无环路因为所有路由器都是基于完全相同的地图计算最短路径树树的特性决定了从一个点到另一个点只有唯一无环的路径所以 OSPF 区域内路由永远不会有环路。快速收敛当网络变化时一旦新的 LSA 泛洪完成路由器各自运行 SPF就可以立刻算出一个新的无环拓扑这比距离向量协议通过传闻更新要快得多。区域划分的意义运行 SPF 是很消耗 CPU 的所以 OSPF 用“区域”把网络切小每台路由器只需要和区域内路由器保持完全相同的数据库并计算 SPF区域外的路由用更简单的方法传递这样就把计算量控制在了可接受范围内。七、总结OSPF 的 SPF 算法说白了就是每个路由器拿到一张全网地图后自己用 Dijkstra 算法算出以自己为中心的最佳路线图。它的步骤可以浓缩成三句话从自己开始把直接连着的邻居距离记下来。选一个当前距离最近的未处理节点把它“转正”并用它来尝试缩短到其他未处理节点的距离。重复第 2 步直到所有节点都处理完。这个算法虽然简单但极其健壮支撑起了全球无数企业网和数据中心的核心路由。希望这篇通俗的讲解能让你再看到“SPF 计算”时脑子里浮现出的是一个一个“确定”、再“松弛”的有趣过程而不是一堆冰冷的公式。