ospf工作原理

1、随着 Internet技术在全球范围内的飞速开展，IP网络作为一种最有前景的网络技术，受到了人们的普遍关注。 而作为 IP网络生存、运作、组织的核心一一 IP路由技术提供了解决IP网 络动态可变性、实时性、QoS等关键技术的一种可能。在众多的路由技术中，OSPF协议已成为目前 Internet广域网和 Intranet 企业网采用最多、应用最广泛的路由技术之一。本文在 分析 OSPF动态路由协议根本工作原理的根底上,提出了 Dijkstra算法和 OSPF路由表计算 的实现方法。目前应用较多的路由 协议有 RIP和 OSPF,它们同属于内部网关协议，但RIP基于距离矢量算法，而 OSPF基于链

2、路状态的最短路径优先算法。它们在网络中利用的传输技术也不同。RIP是利用 UDP 的 520 号端口进行传输，实现中利用套接口编程，而OSPF那么直接在IP上进行传输，它的协议号为89.在 RIP当中，所有的路由都由跳数来描述，到达目的地的路由最大不超过 16跳，且只保存唯一的一条路由，这就限制了RIP 的效劳半径，即其只适用于小型的简单网络。同时，运行 RIP的路由器需要定期地一般 30s将自己的路由表广 播到网络当中，到达对网络拓扑的聚合，这样不但聚合的速度慢而且极容易引起播送风暴、 累加到无穷、路由环致命等问题。为此，OSPF应运而生。OSPF是基于链路状态的路由协议，它克服了 RIP的

3、许多缺陷：第一，OSPF不再采用跳数的概念，而是根据接口的吞吐率、拥塞状况、往返时间、可 靠性等实际链路的负载能力定出路由的代价，同时选择最短、最优路由并允许保持到达同一目标地址的多条路由，从而平衡网络负荷；第二，OSPF支持不同效劳类型的不同代价，从而实现不同QoS的路由效劳；第三，OSPF路由器不再 交换路由表,而是同步各路由器对网络状态的认识，即链路状 态数据库，然后通过 Dijkstra最短路径算法计算出网络中各目的地址的最优路由。这样 OSPF路由器间不需要定期地交换大量数据,而只是保持着一种连接，一旦有链路状态发生变化时， 才通过组播方式对这一变化做出反响，这样不但减轻了不参与系统

4、的负荷而且到达了对网络拓扑的快速聚会。而这些正是 OSPF强大生命力和应用潜力的根本所在。一、OSPF 工作原理分析OSPF是一种分层次的路由协议，其层次中最大的实体是AS 自治系统，即遵循共同路由策略管理下的一局部网络实体。在每个AS中，将网络划分为不同的区域。每个区域都有自己特定的标识号。对于主干backbone区域，负责在区域之间分发链路状态信息。这 种分层次的网络结构是根据OSPF的实际提出来的。当网络中自治系统非常大时，网络拓扑数据库的内容就更多，所以如果不分层次的话，一方面容易造成数据库溢出，另一方面当网络中某一链路状态发生变化时，会引起整个网络中每个节点都重新计算一遍自己的路由表

5、， 既浪费资源与时间，又会影响路由协议的性能如聚合速度、稳定性、灵活性等。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表， 而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。OSPF由两个互相关联的主要局部组成：呼叫协议和可靠泛洪机制。呼叫协议检测邻居并维护邻接关系，可靠泛洪算法可以确保统一域中的所有的OSPF路由器始终具有一致的链路状态数据库，而该数据库

6、构成了对域的网络拓扑和链路状态的映射。链路状态数据库中每个条目称为 LSA (链路状态通告)，共有 5种不同类型的 LSA ,路由器间交换信息时就 是交换这些LSA.每个路由器都维护一个用于跟踪网络链路状态的数据库，然后各路由器的 路由选择就是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。 与此同时，OSPF动态监视网络状态，一旦发生变化那么迅速扩散到达对网络拓扑的快速聚合， 从而确定出新的网络路由表。二、Dijkstra 算法Dijkstra算法是路由表计算的依据，通过 Dijkst

7、ra算法可以得到有关网络节点的最短路 径树，然后由最短路径优先树得到路由表。I.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移至

8、E.(4)建立一个与 P相连并从 V开始的所有链路构成的侯选路径集合。这些路径的长度是 P的长度加上与 P 相连的长度。将这些新的链路插入有序表O中，并放置在其长度所对应的等级上。继续执行步骤2.2.Dijkstra算法举例：下面我们以路由器 A为例，来说明最短路径树的建立过程：(1)路由器 A找到了路由器 B、C,将它们列入候选列表B: 1 ; C: 2.(2)从候选列表中找出最小代价项 B,将 B 参加最短路径树并从候选列表中删除。接 着从 B开始寻找，找到了 D,将其放入候选列表C : 2; D: 2.OSPF的设计实现要涉及到指定路由器、泛洪机制、路由表计算等一系列问题。本文仅就备份指

9、定路由器的选举、协议包的接收、发送、Dijkstra算法与路由表的计算进行讨论。(3) 从列表中找出 C,再由 C又找到了 D.但此时 D 的代价为4,所以不再参加候选列 表。最后将D参加到最短路径树。此时候选列表为空，完成了最短路径树的计算。三、OSPF 路由表的计算与实现有关路由表的计算是 OSPF的核心内容，它是动态生成路由器内核路由表的根底。在路由表条目中，应包括有目标地址、目标地址类型、链路的代价、链路的存活时间、链路的类 型以及下一跳等内容。关于整个计算的过程，主要由以下五个步骤来完成：(1)保存当前路由表，当前存在的路由表为无效的，必须从头开始重新建立路由表；(2)域内路由的计算

10、，通过 Dijkstra算法建立最短路径树，从而计算域内路由；(3)域间路由的计算，通过检查Summary-LSA 来 计 算 域 间 路由，假设该路由器连到多 个域，那么只检查主干域的 Summary-LSA ;(4)查看 Summary-LSA :在连到一个或多个传输域的域边界路由器中，通过检查该域 内的Summary-LSA来检查是否有比第(2)(3)步更好的路径；(5)AS外部路由的计算，通过查看 AS-External-LSA来计算目的地在 AS 外的路由。通过以上步骤，OSPF 生成了路由表。但这里的路由表还不同于路由器中实现路由转发 功能时用到的内核路由表，它只是OSPF本身的内部路由表。因此，完成上述工作后，往往还要通过路由增强功能与内核路由表交互，从而实现多种路由协议的学习。OPSF 作为一种重要的内部网关协协议的普遍应用，极大地增强了网络的可