OSPF：链路状态路由选择算法

（1）链路状态路由算法基本原理

在距离矢量算法中，距离的度量并没有考虑物理线路带宽的影响，这在网络状态不复杂的情况下影响不大，但若一些线路带宽较低而另一些线路带宽较高，带宽因素就成为影响距离的重要问题。即使将带宽的影响因素添加在距离的度量中，在距离矢量算法中也会存在慢收敛的问题。因此，距离矢量算法被一个全新的算法所代替，这个算法称为链路状态路由算法（Link-State Routing，链路状态路由）。

链路状态路由算法的思路很简单，每一个路由器必须完成这些工作：①发现它的邻居结点，并获得其网络地址；②测量到各邻居结点的延迟或者线路开销；③构造一个分组，分组中包含所有它刚刚知道的消息；④将这个分组发送给所有其他路由器；⑤计算出每一个其他路由器的最短路径。

在链路状态路由算法中，由于网络上的每个路由器都可以获得所有其他路由器的状态，因此，每个路由器最终都可以构造出网络的拓扑结构。这时，路由器可以根据Dijkstra 算法计算出最短路径，并将计算结果填写到路由表中。实际上，链路状态路由算法中完整拓扑结构的获得和链路延迟信息等都是通过数据间的交换使用实验的方法测量得来。下面详细说明上述的每一个步骤及所需的重要数据信息。

1）发现邻居结点

当一个路由器启动后，它的第一个任务就是找出哪些路由器是它的邻居。为了实现这个目标，需要在每一条线路上发送一个特殊的分组（即HELLO 分组）。线路另一端的路由器应该送回一个应答来说明它是谁。

2）测量线路开销

链路状态路由算法要求每一个路由器知道它到各个邻居结点之间的延迟或者一个合理的度量值。解决这个问题最直接的方法是在线路上发送一个特殊的分组，另一端立即回送应答，通过计算往返时间，再除以2，获得一个合理的延迟估计值。如果希望得到更好的结果，可多次执行这样的测试过程，取它们的平均值。

3）创建链路状态分组

路由器收集到需要交换的信息后，下一步的工作就是建立一个包含这些数据的分组。分组的内容首先是发送方的标识，然后是一个序号和年龄，以及一个邻居列表。对于每个邻居，还要给出到每个邻居的延迟。

创建链路状态分组很容易，困难的是确定创建分组的时机。一种可采取的方法是定期创建分组，另一种可采取的方法为有重要事件发生时才创建分组。

4）发布链路状态分组

当发布链路状态分组后，收到此分组的路由器将会据此改变它们的路由信息。不同的路由器有可能使用不同版本的拓扑结构，从而导致了不一致性、不可达等问题。链路状态路由算法最技巧的部分是如何可靠地发布链路状态分组。

最基本的发布链路状态分组的算法即扩散法。为了控制扩散过程，每一个分组都包含一个序列号，序列号随着每一个新的分组而递增。每一个路由器记录下它所看到的所有（源路由器、序列号）对。当一个新的链路状态分组进来时，路由器在已经看到的分组列表中检查这个新进来的分组。如果它是新的，除了它到来的那条线路之外，在其他的线路上全部转发该分组。如果它是一个重复的分组，则将它丢弃。如果一个分组的序列号小于当前所看到过的来自该源路由器的最大序列号，由于路由器已经有了更新的数据，此分组将被当作过时分组而遭到拒绝。

这个算法存在一些问题，例如，当一个路由器崩溃了，它将丢失所有的序列号记录，发布算法会存在错误的重复分组判断问题；如果一个序列号被破坏了，还会导致过时分组误判的问题。解决这些问题的方案是在每个分组的序列号之后加入年龄信息，并且每秒钟将年龄减“1”。当年龄到“0”时，来自该路由器的信息被丢弃。通常情况下，每隔一段时间，比如说10 s，一个新的分组就会到来，因此，只有当路由器停机时，路由器信息才会过时。利用年龄这个数据，能够使算法解决异常情况判断问题。

5）计算新的路由路径

当一个路由器获得了全部的链路状态分组后，它就具备了计算路由的基础数据，具有了完整的网络拓扑。这样，路由器就可以运行Dijkstra 算法，构建出所有可能目标的最短路径，并将结果写入路由表中，继续进行其他操作。

链路状态路由算法采取事件（链路中断或路由器崩溃等网络异常情况）来驱动链路状态更新，因此，在网络拓扑结构发生变化时，它能够快速收敛，能够适应大规模的网络。但由于该算法本身的复杂性，对链路带宽、路由器的处理及存储能力要求较高。

（2）OSPF 协议

OSPF（Open Shortest Path First，开放最短路径优先）是使用分布式的链路状态算法实现的路由选择协议，是目前使用最广泛的路由协议之一。OSPF 在实现路由选择算法的过程中，采用了多种路由分组来完成数据信息的交换。OSPF 常见的分组有五种：①问候（hello）分组，用来建立和维持邻居关系。②数据库描述（Database Description，DBD）分组，向邻居给出自己的链路状态数据库中的所有链路状态项目的摘要信息。③链路状态请求（Link State Request，LSR）分组，向对方请求发送某些链路状态项目的详细信息（即发送路由更新请求）。④链路状态更新（Link State Update，LSU）分组，用洪泛法对全网更新链路状态。⑤链路状态确认（Link State Acknowledgement，LSA）分组，对链路更新分组的确认。

在OSPF 中，每一个路由器都需要维护三张表，分别为邻居表（存储邻居关系）、数据库（存储所有链路状态信息）和路由表（存储最佳路由条目），来存储算法所用到的关键数据。

OSPF 规定，每两个相邻路由器每隔10 s 要交换一次问候分组，这样就能确切知道哪些邻站是可达的。在正常情况下，网络中传送的绝大多数OSPF 分组都是问候分组。若有40 s 没有收到某个相邻路由器发来的问候分组，则可认为该相邻路由器是不可达的，应立即修改链路状态数据库，并重新计算路由表。

除了问候分组外，其他的四种分组都是用来进行链路状态数据库的同步。所谓同步，就是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器称为“完全邻接的”路由器。不是完全邻接的路由器表明它们虽然在物理上是相邻的，但其链路状态数据库并没有达到一致。

当一个路由器刚开始工作时，它只能通过问候分组得知它有哪些邻居在工作，也能够获得到达邻居所需要的“代价”。如果所有的路由器都将自己的本地链路状态信息对全网进行广播，那么各路由器只要将这些链路状态信息综合起来，就可得出链路状态数据库。但这样做开销太大。为了降低网络通信的开销，OSPF 采取如下的方式：

每一个路由器与相邻路由器交换链路状态摘要信息，摘要信息主要指出有哪些路由器的链路状态信息已经写入了数据库。经过与相邻路由器交换分组后，路由器就用链路状态请求分组，向对方请求发送自己所缺少的某些链路状态项目的详细信息。通过一系列的分组交换，全网同步的链路数据库就建立了。

在网络运行过程中，只要一个路由器的链路状态发生变化，该路由器就要使用链路状态更新分组，用洪泛法向全网更新链路状态。OSPF 使用的是可靠的洪泛法，其要点如图7.9所示。设路由器R 用洪泛法发出链路状态更新分组，图中用一些小的箭头表示更新分组，第一次先发给相邻的三个路由器，这三个路由器将收到的分组在进行转发时将上游路由器排除在外。可靠的洪泛法是在收到更新分组后要发送确认。确认的发送要延迟一些时间，为的是可以少发送几个确认分组。

图7.9　OSPF 使用洪泛法更新链路状态

为了确保链路状态数据库与全网的状态保持一致，OSPF 还规定每隔一段时间（如30 min）要刷新一次数据库中的链路状态。

OSPF 支持四种网络类型：广播多路访问型（如以太网、令牌环网、FDDI 网）、非广播多路访问型（如帧中继网、X.25）、点到点型（如PPP、HDLC）、点到多点型。

在多路访问型网络中，可能存在多个路由器，每台路由器和它的所有邻居将成为完全网状的OSPF 邻接关系。这样，如果有5 台路由器，则需要形成10 个邻接关系，同时将产生25 条LSA，导致网络上存在很多LSA 的拷贝信息。为了避免路由器之间建立完全邻接关系而引起的大量开销，OSPF 要求在区域中选举一个DR（Designated Router，指定路由器），每一个路由器都与DR 建立完全相邻关系。而DR 负责收集所有的链路状态信息，并发布给其他路由器。选举DR 的同时，也选举一个BDR，当DR 失效时，BDR 担负起DR 的职责。

1）DR 的主要工作内容

描述这个多路访问型网络和该网络上剩余的其他相关路由器，管理网络的洪泛过程，同时选取一个BDR 作为双备份之用。

2）DR|BDR 的选取原则

以接口状态为触发方式。每个路由器有一个路由器优先级，优先级为“0”，不能选举为DR|BDR。优先级可以通过配置命令进行修改。问候分组中包含了优先级字段，还包括可能成为DR|BDR 的相关接口的IP 地址。

3）选举过程

DR|BDR 的选举过程可描述如下：

①路由器A 在和邻居建立双向通信后，检查邻居问候报文中的Priority、DR 和BDR 字段，列出所有可以参与选举的邻居。

②如果有一台或多台这样的路由器宣告自己为BDR，选择其中拥有最高路由器优先级的成为BDR；如果相同，选择拥有最大路由器标识的成为BDR；如果没有路由器宣告自己为BDR，选择列表中路由器拥有最高优先级的成为BDR；如果相同，再根据路由器标识进行选择。

③如果有一台或多台路由器宣告自己为DR，选择其中拥有最高路由器优先级的成为DR；如果相同，选择拥有最大路由器标识的成为DR；如果没有路由器宣告自己为DR，将新选举出的BDR 设定为DR。

④如果路由器A 成为新近的DR 或BDR 或者不再成为DR 或BDR，重复步骤②和步骤③，选举结束。

4）筛选过程

简单地说，DR 的筛选过程为：

①优先级为“0”的不参与选举。

②优先级高的路由器为DR。

③优先级相同时，以路由器标识大的为DR；路由器标识以回环接口中最大IP 为准。

④若无回环接口，以真实接口最大IP 为准。

⑤默认条件下，优先级为“1”。

（3）OSPF 协议的区域划分

OSPF 还将一个自治系统划分为若干个更小的范围，称为区域。这样，在使用洪泛法交换链路状态信息时就可以将范围局限于每一个区域，从而减少了整个网络的通信量。为了使每一个区域能够与本区域以外的区域进行通信，OSPF 使用层次结构的区域划分。在上层的区域称为主干区域，作用为连通其他下层区域。从其他区域来的信息都由区域边界路由器进行概括。OSPF 路由器的类型如图7.10所示。

相关概念及解释如下：

①主干区域的标识符规定为：0.0.0.0。在主干区域内的路由器（如R3、R4、R5、R6、R7）为主干路由器。

②同时属于两个以上的区域，但其中一个区域必须在骨干区域中的路由器（如R3、R4、R7）为区域边界路由器。它负责连接主干区域和非主干区域。每一个区域至少有一个区域边界路由器。

③负责与本自治系统以外的其他自治系统交换路由信息的路由器，称为自治系统边界路由器。例如，路由器R6。

图7.10　OSPF 路由器类型

OSPF 不使用UDP 而直接使用IP 分组传送，IP 分组首部的协议字段的值为“89”。OSPF构成的数据报相对较小，可以减少路由信息的通信量。OSPF 采用组播方式交换数据包，其组播地址为224.0.0.5（全部OSPF 路由器）和224.0.0.6（指定路由器）。当互联网规模很大时，由于OSPF 不存在“坏消息传播得慢”的问题，OSPF 协议响应网络变化的时间很短，收敛速度快，因此，OSPF 协议要比RIP 协议好很多。目前，大多数路由器厂商都支持OSPF，并开始在一些网络中取代旧的RIP。

【例7.2】在多路访问型网络中，OSPF 协议要选出一个DR。以下关于DR 的描述中，不是DR 作用的是（　）。(www.chuimin.cn)

A.减少网络通信量　B.检测网络故障

C.负责为整个网络生成LSA　D.减少链路状态数据库的大小

【解析】在OSPF 中，区域是一个网络，由一组临近OSPF 路由器的集合构成。区域中有且只有一个指定路由器（Designated Router，DR），用来与区域中其他的路由器交换链路状态通告（LSA，Link State Advertisements），其他的路由器则只能通过指定路由器来发送自己的链路状态更新包。这样做的好处是减少了路由器之间交换信息造成的网络拥塞。DR 是一个区域中具有最高ID 的路由器。

OSPF 的路由可分为三种类型：区域内部的路由、区域外部的路由和AS 之间的路由。

区域内部的路由主要由路由器通过邻接关系，从DR 处获得本区域完整的网络拓扑，在此基础上用Dijkstra 算法计算整个网络的拓扑图（在路由器中以数据库形式保存）形成路由表来进行区域内部的路由。

区域之间的路由要通过区域边界路由器，它保存有相连两个区域的所有拓扑图，所有在本区域内部不存在的目的地，均要交给区域边界路由器，由它转发包到区域外，通常这个外部区域为“0”区域，再由“0”区域转发到相应的目的地。

AS 之间的路由要通过AS 边界路由器来完成，将数据报转发到外部AS。

引入区域概念和DR 后，能减少数据库的大小。

【答案】B

（4）OSPF 的相关配置

在路由器中进行OSPF 相关配置较简单，关键是对OSPF 协议工作过程的理解及实验现象的正确认识。OSPF 常用的配置命令见表7.8。

表7.8　Cisco 路由器常用OSPF 配置命令

图7.11　OSPF 配置实例

下面以图7.11 的拓扑结构为例，说明OSPF协议中单区域下的OSPF 配置过程及所出现的实验现象。

1）基本配置

配置路由器主机名与拓扑图一致，配置路由器接口IP 地址与PC 机的IP 地址与拓扑图中一致，并且保证直连网络的连通性（具体过程略）。

2）配置OSPF 路由

在routerA、routerB、routerC 三台路由器上分别配置OSPF 路由，命令如下：

routerA:

routerA(config)#router ospf 100

routerA（config-router）#network 172.16.1.0 0.0.0.255 area 0　；通告自己的直连网

routerA(config-router)#network 10.1.1.0 0.0.0.3 area 0

routerA(config-router)#network 10.1.1.4 0.0.0.3 area 0

routerA(config-router)#exit

routerB:

routerB(config)#router ospf 100

routerB（config-router）#network 172.16.2.0 0.0.0.255 area 0　；通告自己的直连网

routerB(config-router)#network 10.1.1.0 0.0.0.3 area 0

routerB(config-router)#network 10.1.1.8 0.0.0.3 area 0

routerB(config-router)#exit

routerC:

routerC(config)#router ospf 100

routerC（config-router）#network 172.16.3.0 0.0.0.255 area 0　；通告自己的直连网

routerC(config-router)#network 10.1.1.4 0.0.0.3 area 0

routerC(config-router)#network 10.1.1.8 0.0.0.3 area 0

routerC(config-router)#exit

3）查看路由表、路由协议及OSPF 邻居

在路由器上用show ip route 命令查看路由表，结果如图7.12所示。

图7.12　使用OSPF 协议后的路由表

说明：使用OSPF 得到的路由表项的标识为“O”。

在路由器上用show ip protocol 命令查看路由协议，结果如图7.13所示。

图7.13　查看OSPF 协议的信息

说明：由图7.13 可以看出OSPF 进程ID、路由器ID、通告的直连网及管理距离等信息。

在路由器上用show ip ospf neighbor 命令查看路由器邻居的基本信息，结果如图7.14所示。

图7.14　查看路由器邻居的基本信息

还可以用show ip ospf interface 命令查看运行OSPF 路由协议接口的详细信息，包括传输延迟、状态及优先级等，如图7.15所示。

图7.15　查看运行OSPF 路由协议接口的详细信息

4）测试连通性

在PC1 上ping 172.16.2.1，测试连通性。其他连通性测试略。

网络中运行OSPF 协议后，还可以修改端口带宽和链路Cost 值来改变路由的OSPF 度量值，从而改变路由器的路径选择；OSPF 协议还支持多区域的路由选择；这些操作的相关配置过程，读者可参阅其他资料，这里不再叙述。