OSPF路由协议的分析与实现

1、ospf路由协议的分析与实现1 引言1.1 internet上路由协议的使用现状在路由器上使用的路由协议有静态路由协议和动态路由协议之分。静态路由协议不利用网络的信息，只是按照某种固定的规则去选择路由。这样，在网络的拓扑发生变化的时候，它不能及时的调整自己的路由信息，最多只是由操作人员偶尔对网络的状态的变化作出反应。由于它不能对网络的改变作出反应，故一般用于网络规模不大，拓扑结构固定的网络中。其优点是简单，高效，可靠。与之相反，动态路由协议则能根据网络拓扑的变化(比如某个网络端口不能工作)，在一段网络路由信息汇聚的时间后，计算出新的正确的路由，以适应网络流量和拓扑的变化。当然，动态路由协议也有

2、不正常工作的情况，这就需要静态路由作为它的补充，在这里讨论的仅是动态路由协议。在自治系统内的路由器我们称之为内部网关，它们之间通过交换网络拓扑信息，来寻找可达路径。在此过程中所使用的路由协议，被称之为内部网关协议(igp)。常见的igp有：rip，ospf，igrp，elgrp等。在自治系统外的路由器被称之为外部网关，它们只通过交换可达信息，来寻找可达路径。连接两个自治系统的外部网关并不需要了解这两个自治系统的具体的网络拓扑，只需要了解通过它可以到达哪些网络。在此过程中所是使用的路由协议，被称之为外部网关协议(egp)。常见的egp有：egp，bgp，bgp.4等。1.2 课题研究的背景及意义

3、网络是信息的高速公路，它是靠作用于像立交桥一样的路由器将它连接并延伸的。路由器通过查找自己的路由表来获知该将信息往哪一条路上送，由此可知，路由器需要掌握网络的路由情况，而路由器又是通过路由协议来得到这一信息的，因此路由协议对路由器来说是非常重要的。路由协议的好坏会直接影响到路由器的性能。目前应用较多的路由协议有rip和ospf，它们同属于内部网关协议，但rip基于距离矢量算法，而ospf基于链路状态的最短路径优先算法。它们在网络中利用的传输技术也不同。rip是一个非常简单的路由协议，人们对它已经做了很深入的研究，并不断的对它进行改进。从产品的角度来说，应用它的路由器已经很成熟。但是，由于它自身

4、的一些没有办法改变的原因，限制了它的适用范围，使得它只能适用于一些小规模的网络之中。从市场的角度来讲，随着internet的发展，接入internet的路由器也越来越多，路由负载不断增加，网络规模也不断扩大，需要适用于大规模网络的路由协议，以改善网络的性能。ospf是一种链路状态协议。对于链路状态协议来说，它向整个网络通告自己的邻居信息。因此，在这个协议中，各个网络节点不必交换通往目的站点的距离，而只需维护一张网络的“拓扑图”，在网络拓扑结构发生变化的时候可以及时更新这张图。各个路由器根据这张图，分别计算到不同目的地的距离，从而生成各自的路由表。ospf根据接口的吞吐率、拥塞状况、往返时间、可

5、靠性等实际链路的负载能力定出路由的代价，同时选择最短、最优路由并允许保持到达同一目标地址的多条路由，从而平衡网络负荷。ospf支持不同服务类型的不同代价，从而实现不同qos的路由服务。ospf路由器不再交换路由表，而是同步各路由器对网络状态的认识，即链路状态数据库，然后通过dijkstra最短路径算法计算出网络中各目的地址的最优路由。这样ospf路由器间不需要定期地交换大量数据，而只是保持着一种连接，一旦有链路状态发生变化时，才通过组播方式对这一变化做出反应，这样不但减轻了不参与系统的负荷而且达到了对网络拓扑的快速聚汇。而这些正是ospf强大生命力和应用潜力的根本所在。它解决了rip所不能解决

6、的一些问题。但是，由于它的复杂性，完全掌握该技术的团体和个人还是少数。人们对于它的研究也远远不如rip那样深入。因此，有必要对该路由协议进行深入分析与研究。2 ospf动态路由协议中的路由计算2.1 距离矢量算法rip的不足在适用于自治系统内部的路由器上，目前多采用的是rip协议。rip协议之所以被广泛应用，主要是因为它很简单。rip协议是一种距离矢量路由协议。对于距离矢量路由协议来说，它告知邻居整个网络的拓扑。rip通过周期性的将自己的路由表广播出去来实现这一点，这样还可以达到维护路由器之间的相邻关系的作用。但是简单也需要付出一定的代价：1) 对于庞大且复杂的网络来说，rip可能根本无法胜任

7、。虽然在网络的拓扑结构发生变化后，rip会重新计算新的路由，计算到各个网络和路由器的距离值，在这种情况下，如果遇到距离值计算到无穷大等情况，计算就变得非常缓慢。为了加快网络的收敛速度，将16设置为极限值，在进行计数时，只要距离值达到16就认为两点之间不可达。这样就将rip限制在小网络上使用了，因为在大规模网络上两点之间的距离值往往会大于16。2) 周期性的广播路由表将消耗大量的网络带宽。这个问题对于大规模网络，尤其是慢速链路和广域网就更加突出了。3) 在重新计算路由的过程中，路由器处于一种过度阶段，网络上会出现大量的广播报文，并会引起循环，从而造成网络暂时的拥塞。4) rip在对两点之间的距离

8、进行度量时，其标准是路径上所经过的路由器的数目（hop），选择hop数量少的那条路径。这样就没考虑到网络延迟和链路状态等对传输距离的影响。在计数到无穷大的过程中，网络的中间状态极为混乱，大量分组循环发送，链路拥塞，并且广播报文本身也会由于拥塞而丢失。但由于节点广播其距离向量表是一个随机过程，因此这种慢收敛是不可避免的，而且随时有可能发生。虽然现在有很多针对这一问题的补救措施，如水平分割、毒性逆转和触发更新等。但是，这些技术解决一些问题，却又带来了一些新的问题。例如，在许多路由器共享一个公共网络的结构中采用触发更新技术的情况下，一个广播就能改变这些路由器的路由表，引起新一轮的广播。如果第二轮广播

9、改变了路由表，它又会引起更多的广播，这就产生了雪崩。使用广播技术和使用抑制技术防止慢收敛问题，会是距离矢量算法的应用工作效率极低。广播要耗费大量的网络资源，即使不出现广播雪崩现象，所有周期性地进行广播意味着网络流量随着路由器数目的增加而增加。2.2 ospf路由算法的原理2.2.1 spf树spf算法，又叫dijkstra算法，是通过到达网络节点的不同路径与度量得到从计算节点到网络众多节点的最短路径。该算法涉及的数据结构有：计算节点s、最短路径树e、候选链表c。算法描述如下：1) 将计算节点s定义为树根。2) 初始化树结构e，使之只包含源节点s。初始化候选链表c，使其包含一些从s开始的路径。这

10、些路径的度量等于相应链路的度量值，并以递增顺序排列链表c。3) 若链表c为空，或者c中的第一个路径长度为无穷大，则终止算法。4) 寻找链表c中的最短路径p，从c中删除p。设v为p的最终节点，若v已在集合e中，即跳回步骤3，继续向下执行。否则，p为通往v的最短路径，将v加入e中。5) 建立一个与p相连并从v开始的所有链路都成的候选路径集合。这些路径的度量是p的度量加上与p相连的度量。将这些新的链路插入有序链表c中，并放置在其度量所对应的等级上。跳回步骤3，继续向下执行。2.2.2 ospf路由表的计算路由表数据结构路由表是路由器完成转发包任务的依据。路由器在转发包时，通过将目的地址与路由表条目中

11、描述的目的地址进行比较，找到最大匹配项，从而决定路由策略。因此，路由表数据结构包括的内容有：目的地址、目的类型、目的网络掩码、接口标识、域标识、路径类型、路由度量、链路状态标识和下一条等。路由表的计算过程1. 域内路由的计算域内路由计算分为两个阶段，第一阶段，利用spf算法生成到域内各节点的最短路径优先树，但此时的节点只考虑路由器和传输网络。第二阶段，将端网络加到最短路径优先树中，最短路径优先树的建立如前面spf算法的介绍。但在该阶段，计算路由器只考虑其链路状态数据库（link state database，简称lsdb）中的路由器链路状态通告和网络链路状态通告。因为路由器链路状态通告描述了每

12、个路由器与相应域的链接状况，而网络链路状态通告描述了网络中连接的路由器状况，它们二者可以完全地构成对网络拓扑的映射。这里主要考虑如何由最短路径优先树生成ospf域内路由表。根最短路径优先树已经描述了计算路由器到达网络中各节点的最短路径，所以，在生成域内路由表时的关键是解决下一跳的计算。所谓下一跳，是指路由器在“存储-转发”数据包时，对于到达特定目的的数据包应该转交的地址。下一跳的计算可以用图1来说明根父节点目的图1 下一跳的计算图如图1所示，计算时要涉及根、父节点和目的三个参数。根与父节点之间可以有很多节点。有关计算的规则为：1) 如果目的和根之间至少有一个路由器，则下一跳只需直接从父节点继承

13、。2) 否则，目的和根之间没有路由器，分两种情况讨论：（a）父节点就是根。即对点到多点网络需查看目的节点路由器链路状态通告的链路数据域；对直连或点到点不需要下一跳；对虚链路，下一跳要在检查传输域摘要链路状态通告时得到。输出接口就是直连到目的的接口。（b）父节点是网络。需要查看目的节点路由器链路状态通告的链路数据域。输出接口从下一跳的ip地址获取。2. 域间路由的计算域间路由是指本域中路由器到达其他域的路由。域间路由有两种情况，即到达其它域网络的路由和自治系统边界路由器（autonomous system border router，简称asbr）的路由。这两种情况由ospf中摘要链路状态通告描

14、述。如果路由器连接到多个区域，则只考虑主干域的摘要链路状态通告。对于每条链路状态通告有下面的原则：1) 若该链路状态通告的度量值或存活时间为最大值，或者它是本路由器发出，则不予考虑。2) 若该链路状态通告描述的目的为一个网络，且它由域边界路由器产生，则增加到目的网络的路由，相应的度量为本路由器到域路由器的度量加路由器到目的网络的度量。若路由器不可达，则不予考虑。3) 若该链路状态通告描述的目的为asbr，且路由表中优先级没有高于域间路由的条目，则增加相应的路由。4) 根据路由表中到达目的路由的优先级决定是否增加替换相应路由。3. 检查传输域摘要链路状态通告选择更优路由。这一步只在连接到一个或多

15、个传输域上的域边界路由器上执行。它的目的有两个：一是查看有没有比前两步中得到的路由更优的路由存在；二是为虚链路计算真正的下一跳。值得注意的是，这一步计算只是跟新主干域的域内路由和域间路由。如图2所示：边界路由器r1、r2与网络n1有共同的联系，网络n1属于主干域，为了保持主干域的连通性，在路由器r1、r3之间建立了虚链路。从图中可以看出，路由器r2到达n1的度量5要比r1的40小，因此在传输域1中的所有路由器将选择r2把包转发给n1。但通过路由表计算过程中的第(一)步计算，r3已经得到了通过r1将包转发给n1的路径，显然与实际情况不符，因此通过第（三）步计算，r3将选择r2作为转发包的途径。n

16、1n1r1r2n2r3405111传输域1虚链路图2 较优路由的选择图4. as外部路由的计算as外部路由主要考虑通往自治系统外部目的的路由，它是由as外部链路状态通告计算得到的。在每一条as外部链路状态通告中，都通告了到达某一特定目的的度量、转发地址、外部路由标签等内容。因此，as外部路由的计算相对内部路由计算来说比较简单。对每一条链路状态通告，只需经过下面的一些判断：1) 若度量值、存活时间和通告路由器中任一个不符合条件，则不予处理。2) 若不存在到通告路由器的路由，则不予处理。3) 若转发路由器为，则表明数据包应转交给通告路由器asbr，按照这一前提增加相应路由。4) 若转

17、发路由器不为0，但其不可达，则不予处理。5) 根据as外部链路状态通告中通告的路由情况，决定度量类型和度量值，并按情况增加或更新相应的路由。通过以上描述的计算过程，ospf根据链路状态数据库中的内容就会生成路由表。这里的路由表仅是ospf自身的路由表，它不同于路由器实现路由转发时用到的内核路由表。因此，在完成上述计算后，往往还要通过路由增强功能与内核路由表进行交互，从而实现多种路由协议的学习。2.3 ospf路由协议的优势针对于rip的不足，我们大都采用ospf协议。ospf是一种链路状态协议。对于链路状态协议来说，它向整个网络告知自己的邻居信息。因此，在这个协议中，各个网络节点不必交换通往目

18、的站点的距离，而只需维护一张网络的“拓扑图”，在网络拓扑结构发生变化的时候及时更新这张拓扑表。各个路由器根据这张图，分别计算到不同目的地的距离，从而生成各自的路由表。它解决了rip所不能解决的一些问题：1) 无hop数的限制，因此不必被限制在小网中使用。2) 每个路由器都掌握了网络的拓扑结构，各自按照网络拓扑结构来进行路由优化算法，形成自己的优化路由。3) 更新报文的发送是在路由发生变化的时候，而不是周期性的发送，故减少了网络上的路由信息的流量，有利于带宽的有效利用。4) 支持多种度量制式，充分考虑网络延迟，链路状态和吞吐量等因素对两点之间传输距离的影响。5) 支持具有相同度量值的多种链路之间

19、的负载分担。3 ospf协议解析3.1 链路状态路由协议作为一种链路状态的路由协议，ospf将链路状态广播数据包lsa（link state advertisement）传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不同。运行距离矢量路由协议的路由器，是将部分或全部的路由表传递给与其相邻的路由器。链路状态路由的原理非常简单，所有节点维护一张完整的网络图，并按该图计算出全部的最佳路由。网络图保存在一个数据库中，其中每个记录都代表网络的一条链路。链路状态算法，或者成为spf算法，其思路可以分为以下4个部分来描述：1) 发现邻居节点2) 构造链路状态分组3) 发布链路状态分组4) 计算新路

20、由3.1.1 发现邻居节点当一个路由器启动以后，它的第一个任务是要知道谁是它的邻居。这是通过发送hello包来实现的。发现该路由器的邻居，获取它们的网络地址，建立相邻关系，并测量到每个相邻路由器的开销或延迟。3.1.2 构造链路状态分组当用于交换的信息收集起来后，构造一个包含所有数据的分组。该分组以发送者的标识符为开头，紧跟着是顺序号和年龄，和一个邻居节点列表，对应于每个邻居节点，都给出了到它们的延迟。图3给出了一个实例子网，其延时标在线路上，相应的6个链路状态分组见图4。图3 子网拓扑结构图图4 该子网的链路状态分组图3.1.3 发布链路状态分组通过flood（泛洪扩散）算法，向所有的其他路

21、由器发送该分组，如何可靠地发布链路状态分组在链路状态路由选择算法中占相当大的比重，链路状态算法的实现的好坏在一定程度上取决于flood算法的优劣。为了控制扩散，每个分组包含一个顺序号。该顺序号在每次发送新分组时加1。路由器记下它所见过的所有信息对（源路由器，顺序号）。当一个新的链路状态分组到达时，先查看一下该分组是否已经接收过。如果是新的，把它再向除了进入的那条路之外的所有线路发布，如果是重复的，则丢弃它。如果一个分组的顺序号比目前为止已到达的最大顺序号还小，则被认为已过时而拒绝。该算法有一些问题。首先，如果顺序号循环使用，就会发生冲突。解决办法是使用32位的顺序号。如果每秒发送一个链路状态分

22、组，就得花137年才能使计数循环回来，所以避免了冲突的可能性。其次，如果一个路由器崩溃了，它将丢失其顺序号。如果它再从0开始，那么后面的分组可能被当做重复分组而被拒绝。第三，如果顺序号传送后发生错误，可能被当成过时分组而遭拒绝。解决这些问题的方法是，在每个分组的顺序号之后再加上年龄字段（age），每秒将年龄递减1。当年龄变成0时，来自于那个路由器的信息就被丢掉。在初始化扩散过程中，年龄字段也一样递减，以保证没有任何分组会丢失并无限长地存活下去。另外，为了防止路由器到路由器之间的线路出问题，所有的链路状态分组都要应答。3.1.4 计算新路由一旦一个路由器积累了整套的链路状态分组，它便可以重组整个

23、子网结构，用dijkstra算法确定到所有可能目的地的最短路径。此算法的结果可以安装在路由选择表中，并且通常通过操作恢复。3.2 链路状态数据库网络的拓扑结构在ospf中用链路状态数据库来描述，它是ospf协议中关键的一部分。在一个自治系统中，所有运行ospf的路由器都需要维护一个相同的链路状态数据库。其实，这个数据库就是一张有关这个自治系统拓扑结构的图，同时它还是一张加权的图。图中的每一条边都与一个权值相关联，权值表示这条边所示的方向传输数据的代价。这个代价值可以是由管理员自己配置的，也可以是从其他的路由协议中获得的。这样一来，所有路由器都了解了整个自治系统的拓扑结构。在此基础上，每个路由器

24、根据这张加权图利用dijkstra的spf算法来计算得到每一个目的地的最短路径，从而生成路由表。正是由于这个原因，使得尽管路由计算是分布式的，但其计算结果与集中式计算出来的结果一样精确。3.2.1 lsa的类型由于ospf协议定义了许多种路由器的类型，因而定义多种lsa通告的类型也是必要的。1) 路由器lsa，每一台路由器都会产生路由器lsa通告。这个最基本的lsa通告列出了路由器所有的链路或接口，并指明了它们的状态和沿每条链路方向出战的代价，以及该链路上所有已知的ospf邻居。这些lsa通告只会在始发它们的区域内部进行泛洪扩散。2) 网络lsa，每一个多路访问网络中的指定路由器将会产生网络l

25、sa通告，一条网络lsa通告可以描绘一个逻辑上的“伪”节点。网络lsa通告列出了所有与之相连的路由器。网络lsa仅仅在产生这条网络lsa的区域内部进行泛洪扩散。3) 网络汇总lsa，是由abr路由器始发的。abr路由器将发送网络汇总lsa到一个区域，用来通告该区域外部的目的地址。实际上，这些网络汇总lsa就是abr路由器告诉在与之相连的区域内的内部路由器它所能到达的目的地址的一种方法。4) asbr汇总lsa，也是由abr路由器始发的。asbr汇总除了所通告的目的地是一台asbr路由器而不是一个网络外，其他的和网络汇总lsa都是一样的。5) 自主系统外部lsa或者称为外部lsa，是始发于asb

26、r路由器的，用来通告到达ospf自主系统外部的目的地或者ospf自主系统外部的缺省路由的lsa。外部lsa通告将在整个自主系统中进行泛洪扩散。6) 组成员lsa，是用在ospf协议的一个增强版本组播ospf协议（mospf协议）中的。mospf协议将数据包从一个单一的源地址转发到多个目的地，或者是一组共享d类组播地址的成员。7) nssa外部lsa，是指在非纯末梢区域（not-so-stubby-area，nssa）内始发于asbr路由器的lsa通告。nssa外部lsa通告几乎和自主系统外部lsa通告是相同的。只是不像自主系统外部lsa通告那样在整个ospf自主系统内进行泛洪扩散，nssa外部

27、lsa通告仅仅在始发这个nssa外部lsa通告的非纯末梢区域内部进行泛洪扩散。8) 外部属性lsa，是被提议作为运行内部bgp协议的另一种选择，以便用来传送bgp协议的信息穿过一个ospf域。这个lsa从来没有在大范围部署过，ios软件也不支持该lsa。9) opaque lsa是由标准的lsa头部后面跟随专用信息组成的一类lsa。这个信息字段可以直接由ospf协议使用，或者由其他应用分发信息到整个ospf域间接使用。opaque lsa类型现在用于对ospf增加可变的扩展特性，例如在mpls网络中应用的流量工程参数。3.2.2 末梢区域一个学习到外部目的地路由信息的asbr路由器，将通过在整

28、个ospf自主系统中泛洪扩散自主系统外部lsa来通告那些外部的目的路由信息。在大多数的实际案例中，这些外部lsa通告可能会在每台路由器的链路状态数据库中构成较大百分比的lsa数量。如图5所示，并不是每一台路由器都需要了解所有外部目的地的信息。不管外部目的地在哪儿里，在区域2中的路由器都必须发送数据包到asbr路由器，以便到达那台asbr路由器。在这种情况下，区域2可以被配置成为一个末梢区域。图5 可以通过使区域2成为一个末梢区域来节省内存和提高性能末梢区域是一个不允许自主系统外部lsa通告在其内部进行泛洪扩散的区域。在一个末梢区域里，路由器的链路状态数据库的大小被减小了，因此，这些路由器的性能

29、将得到提高，并且内存也得到节省。当然在一个包含有大量自主系统外部lsa通告的ospf域里，这种改进将更加显著。然而，在末梢区域内也有4个限制条件：1) 和所有区域一样，一个末梢区域内部的所有路由器也必须拥有相同的链路状态数据库。为了确保这个条件，所有末梢区域内的路由器都会在它们的hello数据包中设置一个标志就是e-bit位，并将它设置为0。这样，这些末梢区域路由器将不接受其他路由器发送的任何e-bit位为1的hello数据包。结果，没有配置成一个末梢区域路由器的任何路由器之间将无法成功建立邻接关系。2) 虚链路不能在一个末梢区域内进行配置，也不能穿过一个末梢区域。3) 末梢区域内的路由器不能

30、asbr路由器。这个限制条件是很容易直观地理解的，因为asbr路由器会产生自主系统外部lsa通告，而在一个末梢区域内不能存在自主系统外部lsa通告。4) 一个末梢区域可以拥有多台abr路由器，但是因为缺省路由的原因，区域内部路由器将不能确定哪一台路由器才是到达asbr路由器的最优网关。完全末梢区域（totally stubby area）不仅使用缺省路由到达ospf自主系统外部的目的地址，而且使用缺省路由到达这个区域外部的多有目的地址。一个完全末梢区域的abr将不仅阻塞自主系统外部lsa，而且阻塞所有的汇总lsa，除了通告缺省路由的那一条网络汇总lsa。非纯末梢区域（not-so-stubby

31、-area，nssa）允许外部路由通告到ospf协议自主系统内部，而同时保留自主系统其余部分的末梢区域特征。在nssa区域内部的asbr将始发nssa外部lsa用来通告那些外部的目的网络。这些nssa外部lsa将在整个nssa区域内进行泛洪扩散，但是会在abr路由器的地方被阻塞。3.3 区域的划分在ospf协议的环境下，区域（area）是一组逻辑上的ospf协议路由器和链路，它可以有效地把一个ospf域分割成几个子域。在一个域内的路由器将不需要了解它们所在区域外部的拓扑细节。在这种环境下：1) 路由器仅仅需要和它所在区域的其他路由器具有相同的链路状态数据库，而没有必要和整个ospf域内的所有路

32、由器共享相同的链路状态数据库。因此，在这种情况下，链路状态数据库大小的缩减就降低了对路由器内存的消耗。2) 链路状态数据库的减小也就意味着处理较少的lsa，从而降低了对路由器cpu的消耗。3) 由于链路状态数据库只需要在一个区域内进行维护，因此，大量的lsa泛洪扩散也就被限制在一个区域里面了。区域0（或者区域）是为骨干域保留的区域id号。骨干区域（backbone area）的任务是汇总每一个区域的网络拓扑到其他的所有区域。区域0是一个骨干区域，如果配置了一个以上的区域，它就是必须存在的。所有的区域必须与区域0相连；否则，需要虚链路正是由于这个原因，所有的域间通信量都必须通过骨干

33、区域，非骨干区域之间不能直接交换数据包。如图6所示，区域0为骨干区域，区域1和区域6为非骨干区域。图6 ospf区域图3.3.1 路由器的类型所有的ospf路由器都是下面4种路由器类型中的一种：1) 内部路由器（internal router）是指所有接口都属于同一个区域的路由器。2) 区域边界路由器（area border routers，abr）是指连接一个或者多个区域到骨干区域的路由器，并且这些路由器会作为域间通信量的路由网关。因而，abr路由器总是至少有一个接口是属于骨干区域的，而且必须为每一个与之相连的区域维护不同的链路状态数据库。abr路由器将会汇总与它相连的区域

34、的拓扑信息给骨干区域，然后又将这些汇总信息传送给其他的区域。3) 骨干路由器（backbone router）是指至少有一个接口是个骨干区域相连的路由器。4) 自主系统边界路由器（autonomous system boundary router，asbr）可以认为是ospf域外部的通信量进入ospf域的网关路由器，也就是说，asbr路由器是用来把其他路由选择协议学习到路由，通过路由选择重分配的方式注入到ospf域的路由器。3.3.2 虚链路虚链路（virtual link）是指一条通过一个非骨干区域连接到骨干区域的链路。虚链路主要应用于以下几种目的：1) 通过一个非骨干区域连接一个区域到骨干

35、区域。2) 通过一个非骨干区域连接一个分段的骨干区域两边的部分区域。在配置虚链路的时候，有几条相关的规则，说明如下：1) 虚链路必须配置在两台abr路由器之间；2) 配置了虚链路所经过的区域必须拥有全部的路由选择信息，这样的区域又被称为传送区域；3) 传送区域不能是一个末梢区域。虚链路可以看成是两台abr路由器之间的一个无编码的链路，并且它是属于骨干区域的。这些abr路由器之间虽然没有物理的数据链路相连，但是它们可以看做是通过它们之间的虚链路逻辑上虚拟连接的邻居。在每一个abr路由器的路由表中，当发现有到达邻居的abr路由器的路由时，虚链路将转换到完全可操作的点到点接口状态。这条虚链路的代价就

36、是到达它的邻居路由器的路由代价。当接口状态变为点到点状态时。一个邻接关系将通过这条虚链路建立成功。3.4 链路状态数据库的形成与维护在ospf协议中链路状态数据库的形成与维护是通过三种协议（hello协议，交换协议和扩散协议）来完成的。3.4.1 hello协议运行ospf协议的路由器向全网告知自己的邻居信息，当邻居状态发生变化的时候，它又会向全网通告这个变化。那么，ospf路由器怎么知道自己的邻居是谁，怎样检测到自己的邻居已经发生了变化？这一切都是由hello协议来完成的。除此之外，在前面所提到的指派路由器和备份指派路由器的选择，也是由它来完成的。因此我们从以下的几个方面来描述hello协议

37、：1) 动态发现新邻居hello协议中规定，一个运行ospf协议的路由器从它加入网络起，就需要定期的向网络发送hello分组。邻居通过收到这个hello分组来发现它的存在。而它则通过收到邻居发送的hello分组来发现自己的邻居。2) 确认邻居间的双向连接关系邻居之间要进行进一步的操作，必须先建立双向连接。如果ospf路由器检测到邻居发来的hello报文的邻居列表中包含自己，说明邻居已经收到了自己发送的hello报文，能够在网络上看见自己。此时，邻居间的双相连接关系就建立起来了。3) 维持与邻居间的邻接关系一个ospf路由器通过定期向网络发送hello分组来告知邻居自己的存在，同时它通过收到邻居

38、的hello报文，来确保邻居还活着。如果一个ospf路由器在规定时间内没有收到邻居发送的hello分组，则该路由器可以确认此邻居已经死掉了，从而发现拓扑结构的变化。4) 指派路由器的选举对于广播性网络和nbma（non-broadcastmulti-access）网络，我们在所有与该ospf路由器建立双向连接的邻居之间，通过路由器的优先级，id的比较，来选出指定路由器，其它的所有路由器需要与它交换彼此的链路状态数据库，从而建立邻接关系。hello分组的发送可以以组播的形式发给网络上的所有ospf路由器，或者以单播的形式发给自己的邻居。对于选择了指定路由器的网络，在指定路由器和非指定路由器之间；

39、对于其它的网络，在建立了双向连接的路由器之间，都需要建立邻接关系，这就需要随时保持链路状态数据库的一致。这个一致是通过交换协议和扩散协议来完成的。3.4.2 交换协议交换协议仅用于链路状态数据库的初始同步，它规定了刚建立双相连接而又需要建立邻接关系的路由器之间的链路状态数据库怎样进行初始的交换。在这个交换的过程中，路由器双方是非对称的，一个扮演“主”的角色，另一个扮演“从”的角色。因此，这个过程的第一步就是“主”“从”角色的协商。之后，进行的操作就是“主”“从”之间相互告诉对方自己的链路状态数据库中的内容。在第二步中，“主”路由器主动发起交换过程，告知“从”路由器自己的链路状态数据库中有什么内

40、容，“从”路由器收到后，进行应答，并在应答分组中带上自己的链路状态数据库的内容，此时。双方传送的是“数据库描述分组”，这些分组只标志了各个不同的lsa，而不是对每条lsa的具体内容进行述说，在此过程中双方都会将对方的数据库中的内容以自己的数据库中的内容进行比较，若发现自己的数据库中没有该项纪录，则将它放入一个请求链表中，以便稍后向邻居索要该纪录。自然，交换过程的第三步就是向对方发自己的请求链表，并在收到对方的请求后，将对方请求的lsa发给它。在此过程完成后，双方链路状态数据库的内容都达到了一致，这两个路由器之间的连接关系就建立起来了。3.4.3 扩散协议交换协议仅仅保证了在初始时刻，邻接路由器

41、间链路状态数据库的一致，然而，当网络的拓扑结构发生了变化的时候，一个路由器检测到了这样的变化，它就会修改自己的链路状态数据库的内容，为了保持链路状态数据库的一致往，它还必须将这个变化传出去，此时，交换协议就没有办法工作了，这就需要用其他的协议来完成。这个功能就是由扩散协议完成的。在扩散协议当中通过发送和接收链路状态更新分组来实现。1链路状态更新分组的发送当一个路由器检测到它的一各邻居的状态发生了变化的时候，会立即更新自己的链路状态数据库中的相应记录，并将更新后的lsa装在链路状态更新分组中发给与自己相连的其他节点。在一个链路状态更新分组中可能包含有多个lsa，它的传送距离只有一条(hop)。为

42、了保证这个算法的可靠性，发送方在发出更新报文后，必须等待接收方发来的确认。如果，发送方在规定的时间内没有收到确认，它会以一定的时间间隔重新发送更新分组，直到收到对方的确认为止。2链路状态更新分组的接收当一个路由器收到邻居发来的链路状态更新分组后，它会采取如下的一些措施：1) 在数据库中搜索相应的记录；2) 如果该纪录不存在，就把它加入数据库，并广播该报文；3) 如果该纪录比自己的数据库中的纪录新，则替换数据库中的记录，并广播该报文；4) 如果数据库中的记录新，就把这个更新的记录告诉对方；5) 如果和数据库中的记录一样，则不做任何操作。在这里我们设计到比较相同的lsa的新旧问题，此时，我们是通过

43、比较它们的链路状态序列号（ls sequence number）、ls age和ls checksum来实现的。通过这三个协议的相互协调工作，路由器上的链路状态数据库得以形成，并随时更新，以保证自己的链路状态数据库所描述的网络拓扑是最新的。每当链路状态数据库发生了变化的时候，我们就必须重新生成最短树，然后根据它重新据算出自己的路由表，以完成ospf路由协议的全部功能。4 ospf软件体系概要设计tftptelnetmibsnmp agenttcp/ip软件ospfriproute table抽象网络接口以太网链路级驱动软件ppp级链路级驱动软件hdlc驱动软件局域网接口广域网接口r_ioctl

44、()配置软件diti设备驱动软件console口图7 ospf在整个软件体系中的位置图ospf/rip模块利用tcp/ip软件提供的通信服务，与网络中其他路由器经行通信，通过计算得到一张路由表，tcp/ip软件则通过查找这张路由表来决定一个ip数据转发路径。4.1 ospf路由协议模块划分ospf协议软件的开发，是根据rfc2328的规定来进行的。根据前面的分析，我们可以将ospf模块划分为以下几个部分：1. 通信子块：通过它与路由管理任务打交道，进行协议报文的收发，并完成相应的数据处理。利用路由管理提供的服务，为其它子块提供统一的通信接口，屏蔽掉通信的具体细节。根据ospf协议所描述的功能，

45、我们可以将通信子块作进一步的划分：1) hello协议子块：完成hello协议所描述的功能。a) 接收hello分组，检查其中的内容，以发现新邻居的存在，判断邻居之间应建立的状态关系，以及已建立的状态是否应发生改变，从而向邻居状态机发送相应的时间。检查分组中相应的内容，发送时间给接口有限状态机；b) 根据不同的网络接口类型，以不同的形式周期性的发送hello分组，告知邻居自己的存在；c) 收集邻居路由器的优先级、路由器id等信息，以便在广播型网络和nbma网络上选举指定路由器和备份指定路由器。2) 交换协议子块：完成交换协议所描述的功能。在应建立邻接关系的路由器之间，启动并完成链路状态数据库的

46、初始同步。a) 在邻接关系上接收数据描述分组与邻居交换相关的lsa头部，向邻居状态有限机发送对应时间；b) 向有邻接关系的邻居发送正确的数据描述分组；c) 在邻接关系上发送lsa请求分组；d) 接收lsa请求分组，并以相应的更新分组作为相应；e) 接收更新分组，对lsdb做相应操作，发送相关事件给邻居状态机，并以正确的响应分组对起应答。3) 扩散协议子块：完成扩散协议所描述的功能。a) 接收更新分组，并将接受到的更新分组中lsa放入链路状态数据库中，并在对lsa进行判断后选择响应的方式（比如发送相应报文的方式、是否应该继续扩散等）；b) 在链路状态发生变化的时候及时更新链路状态数据库的内容（包

47、括lsa的刷新、早熟）。产生并发送更新分组，向自己的某些邻居通报这一变化。2. 指定路由器选举子块：在广播网和nbma网络上根据从hello分组中收集到的信息，完成dr和bdr的选举。3. 邻居有限状态机：标明了接口可能的各种状态，接收其它模块发送来的事件，实现各种状态之间的相互转换及相应的操作。4. 接口有限状态机：标明了接口可能的各种状态，接收其他模块发送来的事件，实现各种状态之间的相互转换及相应的操作。5. 链路状态数据库：实现链路状态数据库的生成和维护。在数据库的内容发生变化的时候，调用生成树算法，重新计算最短树，从而生成新的路由表。6. 生成树算法：根据链路状态数据库的内容，按照di

48、jkstra算法，生成一个以自己为根的最短树，并根据这棵树计算出路由表。按照上面的分析，我们可以用图8来表示个子块之间的相互关系。hello协议交换协议模块扩散协议模块邻居状态机接口状态协议链路状态数据库模块生成树算法路由表dr选举表示向状态机发送消息表示调用相应模块图8 ospf协议模块划分图在图8中，并没有标出配置子块与其它各子块的相对位置以及关系，这是因为其它子块的运行是建立在一系列已有的数据结构的基础之上，而这些数据结构的建立以及其值的改变，均是由配置子块来完成的。通讯子模块完成对协议分组的接收和发送工作。通过创建ospf_task子任务执行对协议分组数据的接收。数据报文接收后的处理工

49、作则是由通讯子模块中的接收部分来完成的。邻居状态和接口状态对协议分组的接收和发送的处理有很大的影响，而在接收分组处理中也会引发相应的邻居状态机时间和接口状态机事件，因而造成邻居状态和接口状态的改变。另外，通讯子模块传送和接收的数据内容主要是链路状态声明，必然会引发链路状态数据库维护模块的处理。这样，在通讯子模块中就不可避免的需要调用大量其他子模块提供的函数接口，同时也产生引发其他子模块处理动作的事件。4.2 全局数据结构的描述根据ospf协议规定，我们首先定义ospf协议软件模块所需的基本数据结构。依照协议文本规定，路由器在运行ospf协议软件时需要保存一些适用于整个协议软件的参数，因此我们构

50、建结构ospf用于存放这些参数。路由器所处的不同区域也具有不同的配置参数。路由器所处的不同区域也具有不同的配置参数（如区域id、属于本区域的链路状态声明、本区域的认证方式等），我们在结构ospf下又建立了结构area。在一个区域内，路由器可能有多个接口，因此需要intf接口数据结构。最后，因为ospf协议所做的链路状态信息交换都是与邻居进行的，邻居的信息和邻接关系都必须记录，我们在intf结构下建立了nbr邻居数据结构（因为每个邻居都是相对于某个接口的，而一个接口可能会有几个邻居）。最终，形成了如图9所示的层次关系的数据结构：ospf areaospf areaospf areaospfosp

51、f interfaceospf interfaceospf neighborospf neighbor图9 ospf基本数据结构的示意图在图9中有四种基本的数据结构，ospf全局数据结构定义为：struct ospf；ospf area定义为：structarea；ospf interface定义为：structintf；ospf neighbor定义为struct nbr。5 ospf路由协议的实现5.1 计算最短路径树dijkstra算法在各种网络寻径表刷新的协议中，ietf的0spf是一种功能最强、特性最丰富的开放路由选择协议。ospf被设计成用于自治系统范围内的ip路由选择协议，能够对

52、自治系统中的拓扑变化快速检测，并在检测变化后迅速汇聚到对一个新拓扑的认同。网络中的每个路由影像使用“树”结构，路由器本身作为“根”部。此树称为“最短路径树”，它跟踪自治系统范围内到每个目标的最短路径。每个ospf路由器都维护一个描述自治系统拓扑结构的数据库，根据这个数据库通过构建最短路径树来计算出路由表。构建最短路径树的方法有dijkstra算法、函数空间迭代和策略空间迭代法等。5.1.1 dijkstra算法dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。dijkstra算法是很有

53、代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用open, close表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。dijkstra 算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点（源点）到其余各节点的最短路径时，经典dijkstra 算法将网络中的节点分成三部分：未标记节点、临时标记节点和最短路径节点（永久标记节点）。算法开始时源点初始化为最短路径节点，其余为未标记节点，算法执行过程中，每次从最短路径节点往相邻节点扩展，

54、非最短路径节点的相邻节点修改为临时标记节点，判断权值是否更新后，在所有临时标记节点中提取权值最小的节点，修改为最短路径节点后作为下一次的扩展源，再重复前面的步骤，当所有节点都做过扩展源后算法结束。具体算法描述如下：设在一非负权简单连通无向图g=（v：顶点集，e：边集，w：边权值）中，d为图g 的邻接矩阵，求源点p0 到其余所有节点pi 的最短路径长度。1) 将 v 分为未标记节点子集n、临时最短路径节点子集t 和最短路径节点子集s，每个节点上的路径权值为d(i)。初始化：s=p0，t=，n=v-s，d(0)=0, d(i)=；2) 更新：将新加入s 集合的节点ps 作为扩展源，计算从扩展源到相

55、邻节点的路径值。若该值比节点上的原值小， 则用该值替换原值， 否则保持原值不变， 即d(i)=mind(s)+dsi,d(i)，并将这些相邻节点之中的未标记节点归为临时标记节点，即t= tpi，n=n-pi；3) 选择：在t 中选择具有最小路径值d(s)的节点ps，归入集合s 中，即s=sps，t=t-ps；4) 迭代判断：若 t=算法结束，否则转（2）。该算法总共需要迭代n-1 次，每次迭代都新加一个节点到临时节点集合中，由于第i 次迭代时不在临时节点集合中的节点数为n-i，即第i 次迭代需对n-i 个节点进行处理。5.1.2 dijkstra算法实现代码#include#includeusing namespace std;const int maxnum=1000000; /边权最大值int n; /节点数目int dist501; /到节点1的最短路径值bool state501; /节点被搜索过状态指示int data501501; /邻接矩阵/查找权值最小的节点int findmin()int minnode=0, min=maxnum;for(int i=1; i=n; i+)if (