OSPF路由协议的分析与实现.docx

《OSPF路由协议的分析与实现.docx》由会员分享，可在线阅读，更多相关《OSPF路由协议的分析与实现.docx（46页珍藏版）》请在第一文库网上搜索。

1、OSPF路由合同的分析与实现1引言1.1 Intemet上路由合同的使用现状在路由器上使用的路由合同有静态路由合同和动态路由合同之分。静态路由合同不运用网络的信息，只是按照某种固定的规则去选择路由O这样，在网络时拓扑发生变化的时候，它不能及时的调节自己的路由信息,最多只是由操作人员偶尔对网络的状态的变化作出反映。由于它不能对网络的变化作出反映,故一般用于网络规模不大，拓扑构造固定时网络中。其长处是简朴,高效，可靠。与之相反，动态路由合同则能根据网络拓扑的变化（例如某个网络端口不能工作）,在一段网络路由信息汇聚的时间后,计算出新的对时时路由,以适应网络流量和拓扑的变化。固然,动态路由合同也有不正

2、常工作的状况,这就需要静态路由作为它的补充,在这里讨论的仅是动态路由合同。在自治系统内的路由器我们称之为内部网关,它们之间通过互换网络拓扑信息，来寻找可达途径。在此过程中所使用的路由合同,被称之为内部网关合同（IGP）O常见0GP有:RROSPFJGRP,EIGRP等。在自治系统外的路由器被称之为外部网关，它们只通过互换可达信息，来寻找可达途径。连接两个自治系统的外部网关并不需要理解这两个自治系统的具体的网络拓扑,只需要理解通过它可以达到哪些网络。在此过程中所是使用的路由合同，被称之为外部网关合同（EGP）o常见的EGP有:EGP,BGP,BGP.4等。1.2 课题研究的背景及意义网络是信息的

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

4、措施变化的因素,限制了它的合用范畴，使得它只能合用于某些小规模的网络之中。从市场的角度来讲，随着Internet的发展，接入Internet的路由器也越来越多,路由负载不断增长,网络规模也不断扩大,需要合用于大规模网络的路由合同，以改善网络的性能。OSPF是一种链路状态合同。对于链路状态合同来说,它向整个网络告示自己的邻居信息。因此，在这个合同中,各个网络节点不必互换通往目的站点时距离，而只需维护一张网络的“拓扑图”，在网络拓扑构造发生变化的时候可以及时更新这张图。各个路由器根据这张图,分别计算到不同目的地的距离,从而生成各自的路由表。OSPF根据接口的吞吐率、拥塞状况、来回时间、可靠性等实际

5、链路的负载能力定出路由时代价，同步选择最短、最优路由并容许保持达到同一目的地址的多条路由,从而平衡网络负荷。OSPF支持不同服务类型的不同代价,从而实现不同Qc)S的路由服务。OSPF路由器不再互换路由表,而是同步各路由器对网络状态的结识，即链路状态数据库，然后通过Dijkstr。最短途径算法计算出网络中各目的地址的最优路由。这样OSPF路由器间不需要定期地互换大量数据,而只是保持着一种连接，一旦有链路状态发生变化时，才通过组播方式对这一变化做出反映，这样不仅减轻了不参与系统的负荷并且达到了对网络拓扑时迅速聚汇。而这些正是OSPF强大生命力和应用潜力的主线所在。它解决了RIP所不能解决的某些问

6、题。但是，由于它的复杂性,完全掌握该技术的团队和个人还是少数。人们对于它的研究也远远不如R1P那样进一步。因此，有必要对该路由合同进行进一步分析与研究。2OSPF动态路由合同中的路由计算2.1 距离矢量算法RIP的局限性在合用于自治系统内部的路由器上,目前多采用的是RIP合同。R1P合同之因此被广泛应用,重要是由于它很简朴。RIP合同是一种距离矢量路由合同。对于距离矢量路由合同来说,它告知邻居整个网络时拓扑。RIP通过周期性时将自己的路由表广播出去来实现这一点，这样还可以达到维护路由器之间的相邻关系的作用。但是简朴也需要付出一定时代价：D对于庞大且复杂的网络来说,RIP也许主线无法胜任。虽然在

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

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

9、表，它又会引起更多的广播,这就产生了雪崩。使用广播技术和使用克制技术避免慢收敛问题,会是距离矢量算法时应用工作效率极低。广播要耗费大量的网络资源，虽然不浮现广播雪崩现象,所有周期性地进行广播意味着网络流量随着路由器数目的增长而增长。2.2 C）SPF路由算法的原理2. 2.1SPF树SPF算法，又叫DijkStrQ算法，是通过达到网络节点的不同途径与度量得到从计算节点到网络众多节点的最短途径。该算法波及时数据构造有：计算节点S、最短途径树E、候选链表C。算法描述如下：D将计算节点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,继续向下执行。3. 2.2OSPF路由表的计算路由表数据构造路由表是路由器完毕转发包任务时根据。路由器在转发包时，通过将目的地址与路由表条目中描述的目的地址进行比

11、较,找到最大匹配项,从而决定路由方略。因此，路由表数据构造涉及的内容有:目的地址、目的类型、目的网络掩码、接口标记、域标记、途径类型、路由度量、链路状态标记和下一条等。路由表的计算过程1 .域内路由时计算域内路由计算分为两个阶段,第一阶段,运用SPF算法生成到域内各节点的最短途径优先树,但此时的节点只考虑路由器和传播网络。第二阶段,将端网络加到最短途径优先树中,最短途径优先树的建立如前面SPF算法的简介。但在该阶段，计算路由器只考虑其链路状态数据库(1inkStatDataBase,简称1SDB)中的路由器链路状态告示和网络链路状态告示。由于路由器链路状态告示描述了每个路由器与相应域的链接状况

12、，而网络链路状态告示描述了网络中连接的路由器状况,它们两者可以完全地构成对网络拓扑的映射。这里重要考虑如何由最短途径优先树生成C)SPF域内路由表。最短途径优先树已经描述了计算路由器达到网络中各节点的最短途径，因此，在生成域内路由表时的核心是解决下一跳的计算。所谓下一跳,是指路由器在“存储-转发”数据包时，对于达到特定目的的数据包应当转交的地址。下一跳I相J以用图1来阐明根父节1曰初图1下一跳的计算图如图1所示,计算时要波及根、父节点和目的三个参数。根与父节点之间可以有诸多节点。有关计算的规则为：D如果目的和根之间至少有一种路由器,则下一跳只需直接从父节点继承。2）否则,目的和根之间没有路由器

13、，分两种状况讨论：（。）父节点就是根。即对点到多点网络需查看目的节点路由器链路状态告示的链路数据域;对直连或点到点不需要下一跳;对虚链路，下一跳要在检查传播域摘要链路状态告示时得到。输出接口就是直连到目的的接口。（b）父节点是网络。需要查看目的节点路由器链路状态告示的链路数据域。输出接口从下一跳的IP地址获取。2 .域间路由时计算域间路由是指本域中路由器达到其他域的路由。域间路由有两种状况,即达到其他域网络的路由和自治系统边界路由器（AutOnomosSystemBorderRouter,简称ASBR）的路由。这两种状况由C）SPF中摘要链路状态告示描述。如果路由器连接到多种区域，则只考虑主干

14、域的摘要链路状态告示。对于每条链路状态告示有下面的原则：D若该链路状态告示时度量值或存活时间为最大值，或者它是本路由器发出，则不予考虑。2）若该链路状态告示描述时目的为一种网络,且它由域边界路由器产生，则增长到目的网络的路由，相应时度量为本路由器到域路由器的度量加路由器到目的网络的度量。若路由器不可达,则不予考虑。3）若该链路状态告示描述时目的为ASBR,且路由表中优先级没有高于域间路由的条目,则增长相应的路由。4）根据路由表中达到目的路由的优先级决定与否增长替代相应路3 .检查传播域摘要链路状态告示选择更优路由。这一步只在连接到一种或多种传播域上的域边界路由器上执行。它的目的有两个：一是查看

15、有无比前两步中得到的路由更优的路由存在;二是为虚链路计算真正时下一跳。值得注意的是,这一步计算只是跟新主干域的域内路由和域间路由。如图2所示：边界路由器RI、R2与网络N1有共同的联系，网络N1属于主干域，为了保持主干域的连通性,在路由器R1、R3之间建立了虚链路。从图中可以看出,路由器R2达到N1的度量5要比R1的40小，因此在传播域1中的所有路由器将选择R2把包转发给N1。但通过路由表计算过程中的第（一）步计算，R3已经得到了通过RI将包转发给N1的途径,显然与实际状况不符,因此通过第（三）步计算，R3将选择R2作为转发包的途径。AS外部路由重要考虑通往自治系统外部目的的路由,它是由AS外

16、部链路状态告示计算得到的。在每一条AS外部链路状态告示中,都告示了达到某一特定目的的度量、转发地址、外部路由标签等内容。因此,AS外部路由的计算相对内部路由计算来说比较简朴。对每一条链路状态告示,只需通过下面的某些判断：D若度量值、存活时间和告示路由器中任一种不符合条件，则不予解决。2）若不存在到告示路由器的路由，则不予解决。3）若转发路由器为.0,则表白数据包应转交给告示路由器ASBR,按照这一前提增长相应路由。4）若转发路由器不为0,但其不可达,则不予解决。5）根据AS外部链路状态告示中告示的路由状况,决定度量类型和度量值,并按状况增长或更新相应的路由。通过以上描述的计算过程QSPF根据链路状态数据库中的内容就会生成路由表。这里的路由表仅是C）SPF自身的路由表,它不同于路由器实现路由转发时用到的内核路由表。因此,在完毕上述计算后,往往还要通过路由增强功能与内