OSPF是如何计算出路由表来的？什么是SPF算法？写下在查阅了各种文档和书籍后开始对OSPF的一些理解，做此纪录用于学习和分享。

OSPF的特性

[Wiki] Wiki百科中这样写到 开放式最短路径优先（英语：Open Shortest Path First，缩写为 OSPF）是广泛使用的一种路由协议，它属于链路状态路由协议，具有路由变化收敛速度快、无路由环路、支持变长子网掩码（VLSM）和汇总、层次区域划分等优点。

不难看出OSPF有很多难以拒绝的优点，收敛速度快，树状的拓扑时期不会出现环路问题，很容易划分区域，方便管理等，也许这就是为什么大多数企业都会选择OSPF的原因(对比RIP不要好用太多太多) 在上一篇文章中，我们讨论了OSPF是如何选举DR，如何建立链接以及如何交换LSA数据库的。如果你还没有看那篇文章，建议先读一读再继续。

今天主要来看OSPF是如何计算出最短路由的。

SPF算法如何计算出优先算短路径？

SPF算法中有一个很重要的点叫Cost(花费),中文翻译过来叫花费，听起来就像去超市买东西花费了很多钱一样，但它有所不同，它更像是你从家门口打车去到某一个地方花了多少钱。 在树状图中Cost的值代表了一个节点到另一个节点所花费的跃点(Cost)，其实就是你经过了几个路由(节点)。 为什么是树状图？

如果对STP生成树协议有所了解的话，我们就会知道树状图能有效避免环路的问题，如图，树状图不会有任何一个”三角形“出现，这样的结构能避免环路的问题。

回到正题，我们要知道一点每一台路由(节点)都会运行SPF算法来计算出最短路径来，就像图中这四个节点一样，R1会计算出如下信息 R1—R2 Cost=1 但它会计算其他的路径吗，不会。因为SPF不计算间接连接的节点所的Cost值。这或许能解释为什么在配置ospf时我们只会配置相邻的网段而不会配置间接连接的网段。我将四个节点所计算出的信息一一列出 R1: R1—R2 Cost=1 R2: R2—R1 Cost=1 R2—R3 Cost=1 R3: R3—R2 Cost=1 R3—R4 Cost=1 R4: R4—R3 Cost=1

此时每个节点会将自己计算的信息打包和相邻的节点进行数据库交互，它们交换数据包，就有了完整的最短路径树，如下：

  • R1的路径表：

    • 到达R2的最短路径：R1->R2，链路成本(Cost)为1
    • 到达R3的最短路径：R1->R2->R3，链路成本为2
    • 到达R4的最短路径：R1->R2->R3->R4，链路成本为3

  • R2的路径表：

    • 到达R1的最短路径：R2->R1，链路成本为1
    • 到达R3的最短路径：R2->R3，链路成本为1
    • 到达R4的最短路径：R2->R3->R4，链路成本为2

  • R3的路径表：

    • 到达R1的最短路径：R3->R2->R1，链路成本为2
    • 到达R2的最短路径：R3->R2，链路成本为1
    • 到达R4的最短路径：R3->R4，链路成本为1

  • R4的路径表：

    • 到达R1的最短路径：R4->R3->R2->R1，链路成本为3
    • 到达R2的最短路径：R4->R3->R2，链路成本为2
    • 到达R3的最短路径：R4->R3，链路成本为1

最短路径树

完整的最短路径树就是如此生成出来的，有了最短路径树，就像有了一张绝对快速不拖沓的地图。 用这张地图来计算路由表，计算出类似的信息

  • 目标网络：x.x.x.x/x （查找最短路径）
    • 下一跳：y.y.y.y （选择最快的下一跳路由）
    • 出接口：GigabitEthernet0/1

SPF（Shortest Path First，最短路径优先）算法，也称为Dijkstra算法，是OSPF用来计算最短路径的核心算法。总结下来一共四大步骤，下面是SPF算法的工作原理和步骤：

1. 初始步骤

  • 每个OSPF路由器会创建一个链路状态数据库（LSDB），存储关于网络拓扑的所有信息。
  • 路由器通过发送和接收链路状态广告（LSA）来更新其LSDB，确保所有路由器的LSDB保持一致。

2. 计算Cost值

  • Cost（花费）：在OSPF中，Cost表示路由器到达目标网络的开销。Cost的值可以根据链路的带宽、延迟等因素进行设置。默认情况下，OSPF根据链路带宽计算Cost值，带宽越高，Cost越低。
  • 树状图：OSPF使用树状拓扑结构避免环路问题。每个路由器只计算直接相连的链路的Cost值，并根据这些信息逐步构建整个网络的最短路径树。

3. 运行SPF算法

  • 初始节点：从源节点（当前路由器）开始，将其标记为已访问，并初始化其到自身的Cost为0。
  • 扩展节点：从当前节点开始，访问所有直接相连的节点，计算每个节点的累计Cost值，并选择累计Cost值最小的节点作为下一个访问节点。
  • 重复计算：重复上述步骤，直到访问所有节点，生成一棵完整的最短路径树。

4. 生成路由表

  • 每个路由器根据生成的最短路径树，更新其路由表。
  • 路由表包含目标网络、下一跳地址和出接口等信息。

最短路径树中的每个节点都有一个数据库，数据库中包含了目标网络的最短路径和下一跳路由的地址信息，路由器根据最短路径树去更新自己的路由表，实现高效率，高速度，优质的通信。

参考wiki百科；Jan Ho大佬的总结 [https://en.wikipedia.org/wiki/Open_Shortest_Path_First] [https://www.jannet.hk/open-shortest-path-first-ospf-zh-hant]