本节书摘来自异步社区《OSPF网络设计解决方案（第2版）》一书中的第2章，第2.3节，作者 【美】Thomas M. Thomas II, CCIE #9360，更多章节内容可以访问云栖社区“异步社区”公众号查看
2.3 SPF概述
OSPF网络设计解决方案（第2版）
OSPF是一个链路状态路由协议，此类协议在一些技术文档及文献中也被称为基于SPF的协议，或者是分布式数据库协议。本节讨论链路状态算法的发展，以及该算法对OSPF协议产生的影响。
什么是链路状态协议？
OSPF是一个链路状态协议。那什么是链路状态呢？你可以将链路看作是路由器上的一个接口，而链路的状态也就是对该接口的描述。这种描述包括了接口的IP地址和掩码，以及接口所连接网络的类型和状态。OSPF将网络中所有路由器的链路状态信息汇总于链路状态数据库，再对该数据库运行SPF算法。简而言之，链路状态来自于对一条链路的描述：链路要么是up状态，要么是down状态。
最早的链路状态路由协议被开发用于ARPAnet分组交换网络，该协议的出现为所有其他的链路状态协议奠定了基础。另外，ARPAnet的均质网络环境（即同一厂商的分组交换机使用同步串行链路相互连接）简化了原始协议的设计和实施。
2.3.1 运行SPF
ARPAnet曾经使用了一种早期的距离矢量路由协议，该协议后来逐步发展成为当前仍然使用的RIP协议。随着网络规模的不断扩张，RIP协议开始暴露出一些严重的问题。在这种情况下，人们强烈渴求一种新的路由协议能够运行在AS内部，并且拥有适应由大量路由器和网络连接所组成的大型网络的能力。
为此，OSPF版本1应运而生，由IETF的OSPF工作组在1989年10月发表于RFC 1131中。OSPF基于著名的Dijkstra算法，但是该算法并不是一个新开发的算法，也不是为了满足网络通信需求而专门创建的。这一数学算法最初是在1956年为了演示ARMAC计算机所创立的，直到30多年后才被OSPF所采用。
Edsger W. Dijkstra，1930年出生于荷兰鹿特丹市的一个科学世家。1959年，Dijkstra在荷兰阿姆斯特丹大学很快地取得了他的计算机科学博士学位。在他32岁时，Dijkstra便成为了埃因霍温大学的一名全职教授。他所取得的成就影响至今。
Dijkstra对计算机学术界最为杰出的贡献便是他提出的算法，尤其是最短路径优先算法。但是Dijkstra最初发表该算法时并未意识到这一算法的价值，直到许多年后才被人们所赏识。如今，他的算法甚至对确定最为经济的计算机布线方式和航空业都产生了影响。Edsger Dijkstra在其最初发表最短路径算法的论文中，概括了该算法的目标是找到两点之间通过一系列节点的最短路径。但是在路由领域，节点这一术语需要转换为路由器。
接下来的例子将通过一般性的描述来说明最短路径优先算法的运算过程。
假设你需要很快地找到 A、B 两个城市之间的最短路径。在这两个城市之间，还坐落着一些其他城市（这里也可以看作是路由器），且最终去往目的地的路径可能会经过这些城市。
本例中，你想要确定从A市到达B市的最短路径（花费最少开销），该路径需要经过中间城市所提供的道路（也可看作链路）。当然，这些道路（链路）中有的好，有的差。好的可能更快、更宽或很少堵车。为了确定从A市到达B市的最短（也可以说是最快的）路径（或路由），首先，你需要为每一条道路（链路）分配一个数值以反映通过该道路的速度。
由于计算机仅能够从数值上判断优劣，而无法从主观意愿上对路径进行选择，因此你必须手动为每条道路（链路）分配一个数值作为度量，从而帮助协议进行选择。例如，路由器能够获知度量为50的路径要比度量为100的路径更优。
很明显，本例是为了说明 OSPF，因此例子中 OSPF 将会收集关于如何从A市到B市的所有链路信息。然后，SPF算法将计算出最短路径（见图2-5）。找到最小时间花费（最短路径）的步骤如下所示。
1．从最初的城市开始（A市）。到达A市所需要的时间为0（因为你就在这里）。
2．你知道（通过OSPF）从A市出发，有一条去往其他城市的连接可以到达B市。该连接通往X市，且道路开销为100。将这条链路的信息放在数据库中以备将来参考。
链路A——开销100——去往X市——链路up
3．X市告诉你存在两条离开它的路径。OSPF检查这些链路，并学习到下面的内容。
链路B——开销100——去往Y市——链路up
链路C——开销100——去往Z市——链路up
将这两条条目都放进数据库中，然后继续寻找如何去往B市。
4．Y市告诉你它拥有一条新建的高速公路可以到达B市；将这条信息也放进数据库中。
链路D——开销50——去往B市——链路up
此外，你还学习到了Z市也有去往B市的链路。
链路E——开销100——去往B市——链路up
由于存在两条到达B市的链路，因此SPF算法必须计算哪一条才是最短的路径。
5．OSPF准备着手处理其数据库。（难道你没想过为这个数据库取一个名字吗？）因为之前你一直在追踪关于链路的数据，即开销和up/down状态，并且这些数据内容被放置于数据库中，所以我们称该数据库为链路状态数据库[或者链路状态拓扑]。通过回顾数据库，我们可以获知：
路径A——开销100——去往X市——链路up
路径B——开销100——去往Y市——链路up
路径C——开销100——去往Z市——链路up
路径D——开销50——去往B市——链路up
路径E——开销100——去往B市——链路up
OSPF已经发现了两条去往B市的路径，但是究竟应该使用哪一条呢？你并不知道哪一条才是最短的。但是OSPF的SPF算法可以帮助你确定最短的路径。
6．OSPF现在调用 SPF 算法并且构建一张从 A 市到 B 市包含所有链路的地图。这张地图非常形象地将A市作为树根（即底部），且树根拥有去往各个城市（目的地）的枝干（链路）（见图2-6）。你可以把书本转过来，使其看起开更像一棵树。
尽管使用树的模型图已经非常直观了，但是计算机更喜欢使用数学的方式来获取结果：
路径1：链路A（100）+链路B（100）+链路D（50）=开销（250）
路径2：链路A（100）+链路C（100）+链路E（100）=开销（300）
现在，SPF算法通过比较两条路径便可以确定哪一条才是最短的。然后，你便可以按照最终结果驱车从A市去往B市（实际上也就是开始发送数据包）。SPF会选择路径1，因为该路径比路径2的开销要小。
7．最短路径为路径1。
8．现在，将路径1插入到汽车导航（路由表）中，那么它便能够告诉你（此时，你就好像一个数据包）如何使用最短路径应该到达B市。
这个例子帮助我们演示了SPF算法名称的真正涵义。运行SPF的另一个重要方面是它如何进行收敛。假设依然使用上面的例子，当X市和B市之间的链路失效后，最终的结果将完全不一样。因此，你必须理解这种情况发生的原因，以及为何流量（数据包）会被重定向到Z市的链路。这些概念被称为收敛。
回顾链路状态数据库
链路状态路由选择的原则是，网络中所有的路由器都必须维护一份相同的网络拓扑拷贝。利用这份网络拓扑地图，路由器才能通过执行一系列的运算决定出最佳的路由。网络拓扑信息被放置于数据库中，且数据库内的每一条记录都描述了网络中去往特定节点的链路信息。 >记录中包含了这样的信息：接口标识符、链路编号以及和链路状态相关的度量信息。利用这些信息，每一台路由器都能够非常迅速地计算出从自己到所有其他路由器之间的最短路径。
从本质上来看，OSPF的收敛需要经历O（M.logM）次迭代1，其中M为链路的数量。这比距离矢量Bellman-Ford算法要优越得多，因为距离矢量算法的收敛需要经历O（N.M）次迭代，其中N代表节点数。
1．SPF功能
假设当前存在一个网络，如图2-7所示，网络中接口的开销已经给出。为了构建RTA的最短路径树，那么你必须使RTA成为树根，并计算从树根到每一个目的地的最小开销。
图2-7显示了以RTA的视角所观察到的网络拓扑图。在计算开销时，请注意图中所示箭头的方向。例如，当计算RTA到达10.10.10.0的开销时，从RTB接口访问网络192.168.254.0的开销实际上没有意义。RTA可以通过RTB到达网络10.10.10.0，且该路径开销为15（10+5）。另外，RTA还可以选择通过RTC或通过RTB到达网络100.100.100.0，前者的开销为20（10+10），后者的开销也是20（10+5+5）。当存在去往相同目的地的等价路径时，运行在Cisco设备上的OSPF可以持续跟踪最多16个去往相同目的地的下一跳（即16条等价路径）。
在路由器完成最短路径树的构建后，便可以开始着手建立路由表了。路由器到达直连网络的度量（开销）为0，而去往其他非直连网络的开销可以根据树的模型计算得到。
在讨论OSPF协议的起源之前，你应该首先回顾其关键特点。这些特点和各种协议描述有助于你完成快速的回顾并引出后续概念。
OSPF协议还可以使用下面的定义或描述来命名：
链路状态路由协议；
最短路径优先（SPF）协议；
内部网关协议（IGP）；
分布式路由协议。
OSPF还拥有以下操作特性：
使用开放式的协议构架；
能够动态地调整以适应网络拓扑更变；
拥有可调的距离度量；
支持服务类型（TOS）路由；
支持分层结构；
支持负载均衡；
提供安全特性；
支持以下三种连接或网络：
点到点；
多路访问广播网络；
非广播多路访问网络；
通过在图形化的网络拓扑数据库上运行最短路径算法，以确定路由选择；
利用自治系统及区域的概念对网络进行分割，从而优化管理和流量；
使用多播来替代广播；
允许虚拟链路的使用；
支持VLSM和CIDR。
2．完整的和局部的SPF运算
Cisco为了提高SPF算法计算路由的效率，提供了两种不同类型的SPF运算：完整的和局部的SPF运算。其中完整SPF运算的操作方式已经在本章之前的内容中介绍过了。
只有当区域内的网络拓扑发生更变时，才会进行完整的SPF运算。这种更变是由路由器链路状态通告（LSA）（即1类LSA）所触发的，而不是汇总LSA（3类LSA）。汇总LSA会触发局部SPF运算。
在OSPF协议内，局部SPF只和外部及汇总LSA的更变相关。一般来说，如果是通过外部或汇总LSA来反映的网络抖动，那么此时运行的是局部SPF。换句话说，当区域内的拓扑并未发生更变，而是区域外的一些IP前缀出现抖动，那么此时只需调用局部的SPF运算。
但是如果区域内的IP前缀发生更变，那么OSPF需要重新执行完整的SPF运算。
3．验证SPF的运行
如前所述，监控OSPF的泛洪流量非常重要。一旦路由器接收到更新的LSA，SPF便需要进行重新运算。使用show ip ospf process id命令可以查看到OSPF的运行状态。从该命令的输出中，你还可以查看到当前SPF算法已经执行过的次数。除此以外，输出信息还显示了距离下一次链路状态更新的时间。例2-1显示了show ip ospf命令的输出示例，其中高亮部分指明了SPF运算总共执行的次数。
此外，由于局部SPF运算仅受汇总和外部LSA的影响，因此你可以输入debug ip ospf spf inter命令，或debug ip ospf spf external命令来监控局部SPF。你可以指定访问控制列表对输出内容进行过滤，从而只显示匹配特定LSA ID的LSA条目信息。
1译者注：该公式用于表示时间复杂度。
