解析OSPF协议工作原理

　　在如今的计算机网络中，当两台非直接连接的计算机需要经过几个网络通信时，通常就需要路由器。路由器提供一种方法来开辟通过一个网状连接的路径。那么路径是怎么建立的呢？路由器提供协议的任务是，为路由器提供他们建立网状网络最佳路径所需要的相互共享的路由信息。在众多的路由技术中，OSPF协议已成为目前Internet广域网和Intranet企业网采用最多、应用最广泛的路由技术之一。
　　OSPF（Open Shortest Path First开放式最短路径优先）是一个内部网关协议（Interior Gateway Protocol，简称IGP），用于在单一自治系统（autonomous system，AS）内决策路由。链路是路由器接口的另一种说法，因此OSPF也称为接口状态路由协议。OSPF是通过路由器之间通告网络接口的状态建立链路状态数据库，生成最短路径树，每个OSPF路由器使用这些最短路径构造路由表。
　　开放式最短路径优先协议主要用于在自主系统中的路由器之间传输路由信息。想比较路由信息协议，两者虽同属内部网关协议，但RIP基于距离矢量算法，而OSPF基于链路状态的最短路径优先算法。它们在网络中利用的传输技术也不同。

　　RIP是利用UDP的520号端口进行传输，实现中利用套接口编程，而OSPF则直接在IP上进行传输，它的协议号为89。在RIP当中，所有的路由都有跳数来进行描述，到达目的地的路由最大不超过16跳，且保留唯一的一条路由，这就限制了RIP的服务半径，即其只适用于小型的简单网络。同时，运行RIP的路由器需要定期地（一般30s）将自己的路由表广播到网络当中，达到对网络拓扑的聚合，这样不但聚合的速度慢而且极容易引起广播风暴、累加到无穷、路由环致命等问题。为此，OSPF应运而生。OSPF是基于链路状态的路由协议，它客服RIP的许多缺陷：
　　第一，OSPF不再采用跳数的概念，而是基于链路根据接口的吞吐率、拥塞状况、往返时间、可靠性等实际链路的负载能力定出路由的代价，同时选择最短、最优路由并允许保持到达同一目标地址的多条路由，从而平衡网络负荷。
　　第二，OSPF支持不同服务类型的不同代价，从而实现不同QoS的路由服务。
　　第三，OSPF路由器不再交换路由表，而是同步各路由器对网络状态的认识，即链路状态数据库，然后通过Dijkstra最短路径算法计算出网络中各目的地址的最优路由。这样OSPF路由器间不需要定期地交换大量数据，而只是保持着一种连接，一旦有链路状态发生变化时，才通过组播方式对这一变化做出反应，这样不但减轻了不参与系统的负荷而且达到了对网络拓扑的快速聚会。而这些正是OSPF强大生命力和应用潜力的根本所在。
　　1、OSPF工作原理分析
　　OSPF是一种分层次的路由协议，其层次中最大的实体是AS（自治系统），即遵循共同路由策略管理下的一部分网络实体。在每个AS中，将网络划分为不同的区域。每个区域都有自己特定的标识号。对于主干（backbone）区域，负责在区域之间分发链路状态信息。这种分层次的网络结构是根据OSPF的实际提出来的。当网络中自治系统非常大时，网络拓扑数据库的内容就更多，所以如果不分层次的话，一方面容易造成数据库溢出，另一方面当网络中某一链路状态发生变化时，会引起整个网络中每个节点都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路由协议的性能（如聚合速度、稳定性、灵活性等）。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。
　　OSPF由两个互相关联的主要部分组成：“呼叫”协议和“可靠泛洪”机制。呼叫协议检测邻居并维护邻接关系，可靠泛洪算法可以确保统一域中的所有的OSPF路由器始终具有一致的链路状态数据库，而该数据库构成了对域的网络拓扑和链路状态的映射。链路状态数据库中每个条目称为LSA（链路状态通告），共有5种不同类型的LSA，路由器间交换信息时就是交换这些LSA。每个路由器都维护一个用于跟踪网络链路状态的数据库，然后各路由器的路由选择就是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。与此同时，OSPF动态监视网络状态，一旦发生变化则迅速扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。
　　OSPF的设计实现要涉及到指定路由器、备份指定路由器的选举、协议包的接收、发送、泛洪机制、路由表计算等一系列问题。
　　2、OSPF的五种分组类型
　　OSPF共有以下五种分组类型：
　　1）问候分组（Hello）用来发现和维持邻接站的可达性。
　　2）数据库描述分株（Database Description）向临站给自己的链路状态数据库中的所有链路状态项目的摘要信息。
　　3）链路状态请求分组（Link State Request）想对方请求发送某些链路状态项目的详细信息。
　　4）链路状态更新分组（Link State Update）用泛洪法对全网更新链路状态。这种分组是最复杂的，也是OSPF协议最核心的部分。路由使用这种分组将其链路状态通知给临站。
　　5）链路状态确认分组（Link State Acknowledge）对链路更新分组的确认。
　　OSPF规定，没两个邻接路由每隔一段时间要交换一次问候分组。这样就能确定哪些邻站是可达的。其他的四种分组都是用来进行链路状态数据库的同步。所以同步就会是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器叫做完全邻接的路由器。不是完全邻接的路由器表明它们虽然在物理上市相邻的，但是在其链路状态数据库并没有达到一致。
　　3、OSPF协议的特点
　　OSPF协议最主要的特征就是使用分布式的链路状态协议（link state protocol），而不是像RIP协议那样的距离向量协议。OSPF协议有3个主要的特点：
　　1）向本自治系统中所有路由器发送消息。这里使用的方法就是洪泛法，这就是路由器通过所有输出端口向所有相邻的路由器发送信息。而每个相邻路由器又再将此信息发往其所有的相邻路由器。这样，最终端整个区域中所有的路由器都得到这个信息的一个副本。
　　2）发送的信息就是与本路由器相邻的所有路由器的链路状态，但是这只是路由器所知道的部分信息。所谓链路状态其实就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”。OSPF将这个“度量”用来表示费用、距离、时延、带宽等等。
　　3）只有当链路状态发生变化时，路由器才向所有路由器用洪泛法发送此信息，而不是向RIP那样，不管网络拓扑有无发生变化，路由器之间都要定期交换路由表信息。
　　4、OSPF协议的局限
　　对于开放式最短路径优先协议来说，其更加适应于大型网络，保证可传输的可靠性和安全性，但是，OSPF协议本省也不可避免的存在一些缺陷：
　　1）相较与其他网络协议来说，开放式最短路径优先协议的工作方式更为复杂，对于网络配置和操作人员的要求更高，需要操作人员对于网络进行前期规划和设计。
　　2）OSPF协议的工作基于最短路径优先运算法则，而该运算法则较为复杂，需要更多的CPU和内存资源，对于路由器性能的要求更高，增加了组网时的开销。
　　5、Dijkstra算法
　　Dijkstra算法是路由表计算的依据，通过Dijkstra算法可以得到有关网络节点的最短路径树，然后由最短路径优先树得到路由表。
　　5.1 Dijkstra算法的描述如下：
　　1）初始化集合E，使之只包含源节点S，并初始化集合R，使之包含所有其它节点。初始化路径列O，使其包含一段从S起始的路径。这些路径的长度值等于相应链路的量度值，并以递增顺序排列列表O。
　　2）若列表O为空，或者O中第1个路径长度为无穷大，则将R中所有剩余节点标注为不可达，并终止算法。
　　3）首先寻找列表O中的最短路径P，从O中删除P。设V为P的最终节点。若V已在集合E中，继续执行步骤2。否则，P为通往V的最短路径。将V从R移至E。
　　4）建立一个与P相连并从V开始的所有链路构成的侯选路径集合。这些路径的长度是P的长度加上与P相连的长度。将这些新的链路插入有序表O中，并放置在其长度所对应的等级上。继续执行步骤2。
　　5.2 Dijkstra算法举例：
　　下面我们以路由器A为例，来说明最短路径树的建立过程：
　　1）路由器A找到了路由器B、C，将它们列入候选列表{B：1；C：2}。
　　2）从候选列表中找出最小代价项B，将B加入最短路径树并从候选列表中删除。接着从B开始寻找，找到了D，将其放入候选列表{C：2；D：2}。
　　3）从列表中找出C，再由C又找到了D。但此时D的代价为4，所以不再加入候选列表。最后将D加入到最短路径树。此时候选列表为空，完成了最短路径树的计算。
　　6、OSPF路由表的计算与实现
　　有关路由表的计算是OSPF的核心内容，它是动态生成路由器内核路由表的基础。在路由表条目中，应包括有目标地址、目标地址类型、链路的代价、链路的存活时间、链路的类型以及下一跳等内容。关于整个计算的过程，主要由以下五个步骤来完成：
　　1）保存当前路由表，当前存在的路由表为无效的，必须从头开始重新建立路由表；
　　2）域内路由的计算，通过Dijkstra算法建立最短路径树，从而计算域内路由；
　　3）域间路由的计算，通过检查Summary-LSA来计算域间路由，若该路由器连到多个域，则只检查主干域的Summary-LSA；
　　4）查看Summary-LSA：在连到一个或多个传输域的域边界路由器中，通过检查该域内的Summary-LSA来检查是否有比第（2）（3）步更好的路径；
　　5）AS外部路由的计算，通过查看AS-External-LSA来计算目的地在AS外的路由。
　　通过以上步骤，OSPF生成了路由表。但这里的路由表还不同于路由器中实现路由转发功能时用到的内核路由表，它只是OSPF本身的内部路由表。因此，完成上述工作后，往往还要通过路由增强功能与内核路由表交互，从而实现多种路由协议的学习。
　　本文学习了开放式最短路径优先协议（OSPF）。OPSF作为一种重要的内部网关协协议的普遍应用，极大地增强了网络的可扩展性和稳定性，同时也反映出了动态路由协议的强大功能。与路由信息协议（RIP）相比，OSPF更适用于在较复杂的大型网络中应用。同样开放式最短路径优先协议也更加符合未来的网络向大型、高速和可靠的方向的发展需求。