OSPF协议原理

DA000010 OSPF协议原理 ISSUE3.0

第3章 OSPF路由计算过程

上图中描述了通过 OSPF 协议计算路由的过程。由四台路由器组成的网络，连线旁边的数字表示从一台路由器到另一台路由器所需要的花费。为简化问题，我们假定两台路由器相互之间发送报文所需花费是相同的。

首先，每台路由器都根据自己周围的网络拓扑结构生成一条 LSA（链路状态广播），并通过相互之间发送协议报文将这条 LSA 发送给网络中其它的所有路由器。这样每台路由器都收到了其它路由器的 LSA，所有的 LSA 放在一起称作 LSDB（链路状态数据库）。显然，4 台路由器的 LSDB 都是相同的。 其次，由于一条 LSA 是对一台路由器周围网络拓扑结构的描述，那么 LSDB 则是对整个网络的拓扑结构的描述。路由器很容易将 LSDB 转换成一张带权的有向图，这张图便是对整个网络拓扑结构的真实反映。显然，4 台路由器得到的是一张完全相同的图。

最后，接下来每台路由器在图中以自己为根节点，使用SPF算法计算出一棵最短路径树，由这棵树得到了到网络中各个节点的路由表。显然，4 台路由器各自得到的路由表是不同的。

这样每台路由器都计算出了到其它路由器的路由。

由上面的分析可知：OSPF协议计算出路由主要有以下三个主要步骤：

? ?

描述本路由器周边的网络拓扑结构，并生成LSA。

将自己生成的LSA在自治系统中传播。并同时收集所有的其他路由器生成的LSA。

根据收集的所有的LSA计算路由。

路由计算用的算法是Dijkstra算法，描述如下：

Step1：把root加入最小树，设root可直达的顶点为候选人。

Step2：若候选人列表空，则最小树生成完成，否则候选人列表中选取花费最小的，加入到最小树中。

Step3：把新加入的顶点所能直达的顶点列为候选人。 Step4：在候选人名单里除去最小树中已出现的，回Step2

工作过程：通过LSDB可得各路由器的连接(link)状态(state)，利用Dijkstra算法，可由“内”向“外”，从区域内到区域间，从AS内到AS外，逐步生成最小树，进而生成路由表。

在计算过程中，以路由器附属的每一个区域为出发点，计算每一个区域的最小树(相当与一个阶段性的最小树)，区域的最小树包括该区域内部路由器和子网，该区域所知道的其它区域的子网节点，该区域所知道的ASBR路由器ASE节点，系统根据所得的区域的最小树，逐区域改进最小树，最后生成全局的

华为技术有限公司 版权所有, 未经许可不得扩散

29 DA000010 OSPF协议原理 ISSUE3.0 第3章 OSPF路由计算过程

最小树，改进路由表，并根据路由表的变化，调用生成和发送连接状态传送报文的函数，向外发送新的连接信息。 下面详细介绍路由表计算过程： (1) 初始化，保存旧的路由表。

(2) 用Dijkstra算法计算Intra_Area的路由(包括ABR)。

(3) 通过检查Summary LSA，计算InterArea 的路由，若Router是区域边

界的ABR，则只检查Backbone的Summary_LSA。

(4) Root是ABR且连着Transit Area，检查是否有更好的路由(指利用虚连

接改进路由)。

(5) 通过AS External LSA，计算AS外部路由。

计算是按根节点所连的区域逐个区域来计算的，对于每一个区域，分别进行计算，且在计算过程中逐步改进路由表。 路由比较规则：

若有两个不同路由到同一个节点，按以下规则选取：

同一级别的路由比较总是选小的花费的路由。对于不同级别的路由，分为含AS外部的路由：

(1) INT 路由(区域内路由与区域间路由) 在AS外路由之前考虑，即不含外部

路由的路由优先于含外部路由的路由。

(2) type1在ypte2之前考虑，小type2比大type2优先。

(3) 若新的AS外部路由仍不可从当前的路由表入口的路由区分大小，选择

基于Intra_AS的到ASBR路由。 (4) 仍不可分，选少花费的。 (5) 视为等价ASE花费路由。

例如：从路由器A有一条到路由器B的1类外部路由rt1，总的花费是100，现在路由器得到一条新的由A到B的新的路由rt2：若rt2 是自治系统内部路由，则系统将rt2加入路由表，同时删去路由表中的rt1。若rt2是2类外部路由，则系统忽略rt2路由。 不含AS外部路由的路由: 优先级由高到低为： (1) 区域内路由 (2) 骨干区域内路由

(3) 区域间路由（指从经过了两个区域的路由但又不是虚连接构成的骨干区

域内路由）

30 华为技术有限公司 版权所有, 未经许可不得扩散

DA000010 OSPF协议原理 ISSUE3.0

第3章 OSPF路由计算过程

比较时，先看两条路由的优先级是否相同，如果相同的话，按一定规则取的花费小的路由。花费相同的两条路由视为等价路由。如果优先级不同的话，取高优先级的路由。

3.8 思考题

思考题??OSPF协议报文有哪些？OSPF协议路由计算的过程是怎样的？26华为机密，未经许可不得扩散文档密级：内部公开 (1) OSPF协议报文有哪些？

(2) OSPF协议路由计算的过程是怎样的？

华为技术有限公司 版权所有, 未经许可不得扩散

31 DA000010 OSPF协议原理 ISSUE3.0 第4章 LSA链路状态通告

第4章 LSA链路状态通告

课程内容第一章OSPF协议基本概念第二章OSPF网络类型第三章OSPF路由计算过程第四章LSA链路状态通告第五章设计规划OSPF网络27华为机密，未经许可不得扩散文档密级：内部公开 这一部分我们重点介绍OSPF各种链路状态通告LSA，也是深刻理解OSPF协议的关键。

32 华为技术有限公司 版权所有, 未经许可不得扩散