OSPF路由协议仿真系统的研究与开发

摘? 要 本文主要从分析OSPF协议的基本工作原理出发，介绍了OSPF协议操作过程，研究了OSPF协议的核心算法实现。O S P F由I E T F在2 0世纪8 0年代末期开发，O S P F是S P F类路由协议中的开放式版本。最初的O S P F规范体现在RFC 11 3 1中。这个第1版( O S P F版本1 )很快被进行了重大改进的版本所代替，这个新版本体现在RFC 1247文档中。RFC 1247 OSPF称为O S P F版本2是为了明确指出其在稳定性和功能性方面的实质性改进。这个O S P F版本有许多更新文档，每一个更新都是对开放标准的精心改进。接下来的一些规范出现在RFC 1583、2 1 7 8和2 3 2 8中。 OSPF路由协议是一种典型的链路状态（Link-state）的路由协议，一般用于同一个路由域内。在这里，路由域是指一个自治系统（Autonomous System），即AS，它是指一组通过统一的路由政策或路由协议互相交换路由信息的网络。在这个AS中，所有的OSPF路由器都维护一个相同的描述这个AS结构的数据库，该数据库中存放的是路由域中相应链路的状态信息，OSPF路由器正是通过这个数据库计算出其OSPF路由表的。 作为一种链路状态的路由协议，OSPF将链路状态广播数据包LSA（Link State Advertisement）传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不同。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路由器并采用VC++编程的方式对OSPF路由协议进行了仿真： 通过数据库以邻接矩阵存储网络的拓扑结构图，图中的结点即表示WAN中的路由器； 可以随意选择某一个结点作为初始结点，随机变化网络状态（更改，删除结点，改变度量等等），根据OSPF协议的工作原理，显示每个结点的路由表。 关键字：OSPF协议、仿真、路由表 OSPF工作原理 OSPF是一种分层次的路由协议，其层次中最大的实体是AS（自治系统），即遵循共同路由策略管理下的一部分网络实体。在每个AS中，将网络划分为不同的区域。每个区域都有自己特定的标识号。对于主干（backbone）区域，负责在区域之间分发链路状态信息。这种分层次的网络结构是根据OSPF的实际提出来的。当网络中自治系统非常大时，网络拓扑数据库的内容就更多，所以如果不分层次的话，一方面容易造成数据库溢出，另一方面当网络中某一链路状态发生变化时，会引起整个网络中每个节点都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路由协议的性能（如聚合速度、稳定性、灵活性等）。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。 OSPF由两个互相关联的主要部分组成：“呼叫”协议和“可靠泛洪”机制。呼叫协议检测邻居并维护邻接关系，可靠泛洪算法可以确保统一域中的所有的OSPF路由器始终具有一致的链路状态数据库，而该数据库构成了对域的网络拓扑和链路状态的映射。链路状态数据库中每个条目称为LSA（链路状态通告），共有5种不同类型的LSA，路由器间交换信息时就是交换这些LSA。每个路由器都维护一个用于跟踪网络链路状态的数据库，然后各路由器的路由选择就是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。与此同时，OSPF动态监视网络状态，一旦发生变化则迅速扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。 最短路径优先（SPF）路由算法是OSPF的基础。当SPF路由器加点后，它就初始化路由协议数据结构，然后等待下层协议关于接口已可用的通知信息。当路由器确认接口已准备好，就用OSPF Hello协议来获取邻居信息，即具有在共同的网络上接口的路由器。路由器向邻居发送Hello包并接收它们的Hello包。除了帮助学习邻居外，Hello包也有keep-alive的功能。 在多重访问网络（支持多于两个路由器的网络）中，Hello协议选出一个“指派路由器”和一个备份指派路由器。指派路由器负责为整个多重访问网络生成LSA，它可以减少网络通信量和拓扑数据库的大小。 当两个相邻路由器的链接状态数据库同步后，就称为“邻接”。在多重访问网络中，指派路由器决定哪些路由器应该相邻接，拓扑数据库在邻接路由器对间进行同步。邻接控制路由协议分组的分发，只在邻接点间交换。 每个路由器周期性地发送LSA，提供其邻接点的信息或当其状态改变时通知其它路由器。通过对已建立的邻接关系和链接状态进行比较，失效的路由器可以很快被检测出来，网络拓扑相应地更动。从LSA生成的拓扑数据库中，每个路由器计算最短路径树，以自己为根。这个最短路径树就生成了路由表。 作为一种典型的链路状态的路由协议，OSPF还得遵循链路状态路由协议的统一算法。链路状态的算法非常简单，在这里将链路状态算法概括为以下四个步骤： 1、当路由器初始化或当网络结构发生变化（例如增减路由器，链路状态发生变化等）时，路由器会产生链路状态广播数据包LSA（Link-State Advertisement），该数据包里包含路由器上所有相连链路，也即为所有端口的状态信息。 2、所有路由器会通过一种被称为刷新（Flooding）的方法来交换链路状态数据。Flooding是指路由器将其LSA数据包传送给所有与其相邻的OSPF路由器，相邻路由器根据其接收到的链路状态信息更新自己的数据库，并将该链路状态信息转送给与其相邻的路由器，直至稳定的一个过程。 3、 当网络重新稳定下来，也可以说OSPF路由协议收敛下来时，所有的路由器会根据其各自的链路状态信息数据库计算出各自的路由表。该路由表中包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一个路由器（next-hop）。 4、 第4个步骤实际上是指OSPF路由协议的一个特性。当网络状态比较稳定时，网络中传递的链路状态信息是比较少的，或者可以说，当网络稳定时，网络中是比较安静的。这也正是链路状态路由协议区别与距离矢量路由协议的一大特点。