一种更新OSPF路由的方法及OSPF路由器

摘要

本发明公开了一种更新OSPF路由的方法及OSPF路由器，通过在更新OSPF路由时，找到发生变化的外部关联路由、以及该外部关联路由对应的外部LSA，使得在计算OSPF外部路由时，只需对受影响的OSPF外部路由进行计算，而不需要执行OSPF外部路由的全部计算，减少了外部路由计算的工作量，加快了OSPF路由整体收敛速度，减少了OSPF路由更新时的计算量。

说明书

技术领域

本发明涉及开放最短路径优先(OSPF，Open Shortest Path First)路由协 议技术，尤指一种更新OSPF路由的方法及OSPF路由器。

背景技术

OSPF是一种分层次的路由协议，其层次中最大的实体是自治系统(AS， Autonomous System)，即遵循共同路由策略管理下的一部分网络实体。在 AS中，将网络划分为不同的区域。区域是从逻辑上将路由划分为不同的组， 每个组用区域号标识。参见图1，图1为OSPF区域划分的示意图。在OSPF 中，区域0为骨干区。

OSPF路由器根据在AS中的位置，分为以下四种：

区域内路由器(Internal Router)，该路由器的所有接口属于同一个 OSPF区域；

区域边界路由器(ABR，Area Border Router)，该路由器用来连接骨 干区域和非骨干区域；

骨干路由器(Backbone，Router)，该路由器至少有一个接口属于骨 干区域，所有的ABR和区域0中的区域内路由器都是骨干路由器；

自治系统边界路由器(ASBR，Autonomous System Border Router)， 该路由器用来与其他AS交换路由信息的路由器称为ASBR。

在AS内，每个区域都维持一张唯一的拓扑结构图，各域根据自己的拓 扑图各自计算路由，同时ABR把各个区域的内部路由总结后在域间扩散， ASBR将到其他AS域的外部路由通过ABR在区域间扩散。

OSPF中对链路状态信息的描述都是封装在链路状态通告(LSA，Link State Advertisement)发布出去，OSPF中的路由器主要根据以下几种类型的 LSA进行路由计算：

路由器LSA

通常称为第一类LSA，该LSA描述了路由器物理接口所连接的链路或接 口，指明了链路的状态，代价等。每个OSPF区域内的路由器均会生成第一 类LSA，在生成的区域内泛洪。

网络LSA

通常称为第二类LSA，由广播网的指定路由器(DR，Designated Router) 产生，描述本广播网段所有路由器的链路状态，在其始发的区域内传播，网 络LSA携带两个关键信息，一是生成该网络LSA的广播网的IP网段，用 于在区域内通告本广播网直接可达的IP前缀；另外一个是本广播网所连接的 所有节点，用Attached Router字段表示，用于描述网络拓扑。

网络汇总LSA

通常称为第三类LSA，由ABR产生，描述区域内某个IP网段的路由， 并通告给其他区域，用于在区域间通告可达IP前缀。

ASBR汇总LSA

通常称为第四类LSA，由ABR产生，描述到ASBR的路由，并通告给 相关区域，用于描述到达ASBR节点的网络拓扑。

AS外部LSA

通常称为第五类LSA，由ASBR产生，描述到AS外部的路由，通告到 所有的区域，用于通告从其他协议引入到OSPF中的可达IP前缀。

非纯末梢区域(NSSA，Not-So-Stubby Area)外部LSA

通常称为第七类LSA，由NSSA区域内的ASBR产生，描述到AS外部 的路由，仅在NSSA区域内传播。用于在NSSA区域内通告从其他协议引入 到OSPF中的可达IP前缀。

OSPF网络中的每台路由器都会根据实际的链路状态情况生成相应的 LSA在网络中进行扩散，每台路由器根据接收到的LSA形成自己的链路状态 数据库(LSDB，Link State Date Base)。

OSPF路由器会进行两类路由的计算，包括OSPF内部路由和OSPF外部 路由。OSPF内部路由是指在OSPF路由域根据OSPF协议计算出来的路由； OSPF外部路由是指根据由其他路由协议引入而计算得到的路由。

区域内和区域间的路由都属于OSPF内部路由。在进行区域内路由计算 时，根据自身的LSDB计算出到区域内其他路由器的路由；并为本区域的Stub 及网段路由生成第三类LSA和第四类LSA。在计算区域间路由时，根据收到 的第三类LSA和第四类LSA以及本区域的路由，计算出到其它区域IP前缀 的路由以及到其他区域ASBR的路由。Area 0要为本区域学习到的IP前缀路 由及ASBR路由传播至路由源区域外的其他区域。在计算OSPF外部路由时 根据收到的第五类和第七类LSA以及本区域的路由，计算得到外部路由。在 本文中，如无特殊说明，外部路由均代表OSPF外部路由。

参见图2，图2为现有技术OSPF路由更新示意图。具体情况如下：

在步骤201中，当链路状态信息发生变化时，OSPF路由器会根据实际 变化的情况，触发全部路由计算、区域间三类增量计算、区域间四类增量计 算或者外部增量计算。

当OSPF路由器收到第三类LSA时，触发区域间三类增量计算；收到第 四类LSA时，触发区域间四类增量计算；收到第五/七类LSA，触发外部增 量计算；在收到其他类型的LSA或者自身的链路状态发生变化时，将触发全 部路由计算。

在步骤202中，根据变化后的链路状态执行区域内路由计算，得到区域 内路由，到区域内的ABR以及ASBR路由。

在步骤203中，根据重新计算的区域内路由，执行区域间路由全部计算， 即对应本路由器上每条第三类LSA以及第四类LSA重新计算路由，然后执 行步骤208。

在步骤204中，针对收到的第三类LSA执行区域间三类增量计算。

在步骤205中，根据区域间三类增量的计算结果，判断是否影响了本路 由器到达转发地址(FA，Forwarding Address)的路由，如果是，则执行208； 否则，结束当前更新流程。

其中，FA是OSPF协议设计用来避免在访问AS外部地址时增加多余的 跳数。ASBR在引入外部路由时，将下一跳地址填到LSA的Forwarding Address中。这样，路由器在处理该条LSA，首先判断自身是否有到该 Forwarding Address的路径，如果有，从到达FA的路由继承下一跳，从而在 转发报文时只需要将报文发送给Forwarding Address即可，不必再经过ASBR 的转发；如果没有，则查找到达该ASBR路由，从找到的ASBR路由继承下 一跳。

在步骤206中，对收到的第四类LSA执行区域间四类增量计算。

在步骤207中，根据区域间四类增量的计算结果，判断是否影响了本路 由器到达ASBR的路由，如果是，则执行步骤208；否则，结束当前更新流 程。

在步骤205和207中，判断计算结果是否影响到了到达FA的路由或到 达ASBR的路由，主要是判断在区域间三类和四类增量计算前后到达FA依 赖路由或者到达ASBR的路由是否发生变化。

在步骤208中，对应本路由器上每条外部LSA，重新计算全部外部路由， 结束当前更新流程。

在步骤209中，执行外部路由增量计算，即针对收到的第五类或第七类 LSA执行外部路由计算，结果当前更新流程。

其中，所述的增量计算是相对于全部路由计算而言的，增量计算表示仅 对变化LSA进行路由计算，对未变化的LSA不执行路由计算；而全部路由 计算是指对所有相关的LSA条目进行计算，不论对应的LSA条目是否发生 变化。

通过现有更新OSPF路由流程可知，只要触发了全部计算，以及执行区 域间三类增量计算后影响了到达FA的路由，以及执行区域间四类增量计算 后影响了到达ASBR的路由时，都会触发外部路由的全部计算。由于外部路 由的确定仅与所依赖的FA路由以及ASBR路由相关，因此在上述情况下， 一些外部路由所依赖的FA路由以及ASBR路由并没有发生变化，不一定需 要触发外部路由的全部计算。

在实际的应用中，区域内路由和区域间路由数量较少，而外部路由的规 格较大，在数十万，甚至百万级别。这样，在进行路由更新时，频繁的对外 部路由进行全部计算，严重影响了OSPF路由整体收敛速度。

发明内容

有鉴于此，本发明的主要目的在于提供一种更新OSPF路由的方法及 OSPF路由器，通过本发明提供的方法以及OSPF路由器能够减少OSPF路由 更新时的计算量。

为达到上述目的，本发明的技术方案是这样实现的：

一种更新OSPF路由的方法，该方法包括：

保存OSPF路由的各外部关联路由；并记录各外部关联路由对应的外部 链路状态通告LSA；

在执行完OSPF内部路由计算后，根据所述保存的内容判断计算前后各 外部关联路由是否发生变化，如果均未发生变化，则结束当前更新流程；如 果发生变化，对于发生变化的外部关联路由，根据所述记录找到其对应的外 部LSA，针对找到的外部LSA计算对应的OSPF外部路由。

一种OSPF路由器，该OSPF路由器包括处理单元和执行单元；

所述处理单元，用于保存OSPF路由的各外部关联路由；并记录各外部 关联路由对应的外部链路状态通告LSA；

所述执行单元，用于在执行完OSPF内部路由计算后，根据所述处理单 元的保存判断计算前后各外部关联路由是否发生变化，如果均未发生变化， 则结束当前更新流程；如果发生变化，对于发生变化的外部关联路由，根据 所述处理单元的记录找到其对应的外部LSA，针对找到的外部LSA计算对应 的OSPF外部路由。

本发明所提供的一种更新OSPF路由的方法及OSPF路由器，通过在更 新OSPF路由时，找到发生变化的外部关联路由、以及该外部关联路由对应 的外部LSA，使在计算外部路由时，只需对受影响的外部路由进行计算，而 不需要执行外部路由的全部计算，减少了外部路由计算的工作量，加快了 OSPF路由整体收敛速度，减少了OSPF路由更新时的计算量。

附图说明

图1为OSPF区域划分的示意图；

图2为现有技术OSPF路由更新流程图；

图3为本发明OSPF路由更新示例性流程图；

图4为本发明OSPF路由器的结构图；

图5为本发明实施例OSPF路由更新流程图。

具体实施方式

在本部分的详细描述中，仅通过对实施本发明的发明者所预期的最佳方 式的示例，示出并描述了本发明的较佳实施例。应意识到，可以在不背离本 发明的前提下，就各个显而易见的方面对其进行修改。相应地，附图和说明 书应被视为在本质上是示例性的，而不是限制性的。

为了实现本发明的发明目的，本发明提供了一种更新OSPF路由的方法。 该方法的示例性流程图可参见图3。具体的，在步骤301中，保存OSPF路 由的各外部关联路由；并记录各外部关联路由对应的外部链路状态通告LSA； 在步骤302中，在执行完OSPF内部路由计算后，根据所述保存的内容判断 计算前后各外部关联路由是否发生变化，如果均未发生变化，则结束当前更 新流程；如果发生变化，执行步骤303；在步骤303中，对于发生变化的外 部关联路由，根据所述记录找到其对应的外部LSA，针对找到的外部LSA 计算外部路由。其中，记录各外部关联路由对应的外部LSA就是记录外部关 联路由与外部LSA之间的对应关系。

本发明通过在外部关联路由发生变化时，找到发生变化的外部关联路由、 以及该外部关联路由对应的外部LSA，使得在计算外部路由时，只需对找到 的外部LSA进行外部路由计算，实施外部路由的增量计算。这样，由于不需 要执行外部路由的全部计算，本发明的技术方案减少了外部路由计算的工作 量，加快了OSPF路由整体收敛速度。

这里，所述记录各外部关联路由对应的外部LSA为：记录外部关联路由 对应的外部前缀，以及所述外部前缀对应的外部LSA；相应的，所述对于发 生变化的外部关联路由，根据所述记录找到其对应的外部LSA为：根据所述 记录对于发生变化的外部关联路由找到其对应的外部前缀，并找到该外部前 缀对应的外部LSA。其中，可以通过二叉树、红黑树等构建外部前缀与外部 LSA的对应关系。

其中，所述的外部关联路由在不同的情况下，包含不同的内容。

具体的，在触发全部计算的情况下，所述外部关联路由包括到达各ASBR 路由和各FA依赖路由。OSPF内部路由计算为区域内和区域间路由计算，此 时所述根据保存的内容判断计算前后各外部关联路由是否发生变化为：根据 所述保存的内容判断计算前后到达各ASBR路由以及各FA依赖路由是否发 生变化，如果均没有发生变化，结束当前更新流程；否则，对于发生变化的 ASBR路由以及FA依赖路由，根据所述记录找到其对应的外部LSA，针对 找到的LSA计算外部路由。

在触发区域间三类增量计算的情况下，所述外部关联路由包括各FA依赖路 由。OSPF内部路由计算为区域间三类增量计算，此时所述根据保存的内容判断 计算前后各外部关联路由是否发生变化为：根据所述保存的内容判断计算前后 到达各FA依赖路由是否发生变化，如果均没有发生变化，结束当前更新流程； 否则，对于发生变化的FA依赖路由，根据所述记录找到其对应的外部LSA，针 对找到的LSA计算外部路由。

在触发区域间四类增量计算的情况下，所述外部关联路由包括到达各ASBR 路由。OSPF内部路由计算为区域间四类增量计算，此时所述根据保存的内容判 断计算前后各外部关联路由是否发生变化为：根据所述保存的内容判断计算前 后到达各ASBR路由是否发生变化，如果均没有发生变化，结束当前更新流程； 否则，对于发生变化的ASBR路由，根据所述记录找到其对应的LSA，针对找 到的LSA计算外部路由。

本发明还提供了一种OSPF路由器，该OSPF路由器包括处理单元和执 行单元。可参见图4。需要说明的是，为了更加清楚、简要的描述本发明的 实现方式，在图4中省略了OSPF路由器的原有功能模块、仅示出了与本发 明相关的功能模块。

具体的，所述处理单元，用于保存OSPF路由的各外部关联路由；并记 录各外部关联路由对应的外部LSA；所述执行单元，用于在执行完OSPF内 部路由计算后，根据所述处理单元的保存判断计算前后各外部关联路由是否 发生变化，如果均未发生变化，则结束当前更新流程；如果发生变化，对于 发生变化的外部关联路由，根据所述处理单元的记录找到其对应的外部LSA， 针对找到的外部LSA计算对应的OSPF外部路由。

其中，所述处理单元，用于在记录各外部关联路由对应的外部LSA时， 记录外部关联路由对应的外部前缀，以及所述外部前缀对应的外部LSA；相 应的，所述执行单元，用于对于发生变化的外部关联路由，根据所述记录找 到其对应的外部LSA时，根据所述处理单元的记录对于发生变化的外部关联 路由找到其对应的外部前缀，并找到该外部前缀对应的外部LSA。

所述处理单元保存的外部关联路由包括到达各ASBR路由和各FA依赖 路由；所述执行单元，用于在执行完区域内和区域间路由计算后，根据保存 的内容判断计算前后各外部关联路由是否发生变化时，根据所述保存的内容 判断计算前后到达各ASBR路由以及各FA依赖路由是否发生变化，如果均 没有发生变化，结束当前更新流程；否则，对于发生变化的ASBR路由以及 FA依赖路由，根据所述记录找到其对应的外部LSA，针对找到的LSA计算 外部路由。

所述处理单元保存的外部关联路由包括各FA依赖路由；所述执行单元， 用于在执行完区域间三类增量计算后，所述根据保存的内容判断计算前后各 外部关联路由是否发生变化时，根据所述保存的内容判断计算前后到达各FA 依赖路由是否发生变化，如果均没有发生变化，结束当前更新流程；否则， 对于发生变化的FA依赖路由，根据所述记录找到其对应的外部LSA，针对 找到的LSA计算外部路由。

所述处理单元保存的外部关联路由包括到达各ASBR路由；所述执行单 元，用于在执行完区域间四类增量计算后，所述根据保存的内容判断计算前 后各外部关联路由是否发生变化时，根据所述保存的内容判断计算前后到达 各ASBR路由是否发生变化，如果均没有发生变化，结束当前更新流程；否 则，对于发生变化的ASBR路由，根据所述记录找到其对应的LSA，针对找 到的LSA计算外部路由。

为了更加清楚的理解本发明的技术方案，现列举实施例对本发明的技术 方案作进一步详细介绍。具体参见图5。

OSPF路由器在接收到外部LSA时，记录ASBR路由器与外部LSA，以 及在存在FA时，记录FA与外部LSA之间的对应关系；并在进行区域内/ 区域间路由计算时，记录到达ASBR的路由以及到达FA的依赖路由。

由于不同的外部LSA可能会对应相同的外部前缀，因此在记录ASBR与 外部LSA以及FA与外部LSA之间的对应关系，可以记录ASBR或FA与外 部LSA中携带的外部前缀的对应关系，再记录外部前缀与外部LSA之间的 关系。当到达ASBR路由或FA依赖路由变化时，先找到变化的ASBR或FA， 然后通过ASBR或FA关联的外部前缀查找到关联的外部LSA，最终实现部 分LSA计算。其中，为了提高查找效率，可以通过树构建外部前缀与外部 LSA的关联关系，树上的节点指向一个或多个LSA。通过外部前缀在树上查 找到节点上记录的外部LSA，实现快速查找。树的建立是在接收到外部LSA 时，提取LSA中的外部前缀，构建树的节点及与LSA对应关系。

在步骤501中，链路状态信息发生变化时，OSPF路由器会根据实际情 况触发全部路由计算、区域间三类增量计算、区域间四类增量计算或者外部 增量计算，同时保存自身当前到达各ASBR路由以及到达各FA的依赖路由。

OSPF路由器的具体触发情况可见步骤201中的介绍，在此不再详述。 同时，为了简化描述，将自身当前到各ASBR路由简称为ASBR路由，到达 各FA的依赖路由简称为FA依赖路由。

在步骤502～503中，在触发全部计算的情况下，执行区域内路由计算以 及区域间路由全部计算。

在步骤504中，根据当前保存的计算前的ASBR路由和FA依赖路由， 判断计算前后的各FA依赖路由和ASBR路由是否发生变化，如果均未发生 变化，结束当前更新流程；如果是，执行步骤505。

在步骤505中，对于发生变化的FA依赖路由和ASBR路由，根据记录 的ASBR路由和外部LSA的对应关系，以及FA依赖路由和外部LSA的对 应关系，找到其对应的外部LSA，执行步骤512。

在步骤506中，对收到的第三类LSA执行区域间三类增量计算。

在步骤507中，根据保存的计算之间的FA依赖路由，判断计算前后各 FA依赖路由是否发生变化，均未发生变化，结束当前更新流程；如果发生 变化，执行步骤508。

在步骤508中，对于发生变化的FA依赖路由，根据记录的FA依赖路 由和外部LSA之间的对应关系，找到其对应的外部LSA，执行步骤512。

在步骤509中，对收到的第四类LSA执行区域间四类增量计算。

在步骤510中，根据保存的计算之前的ASBR路由，判断计算前后各 ASBR路由是否发生了变化，如果均未发生，结束当前更新流程；如果发生 变化，执行步骤511。

在步骤511中，对于发生变化的ASBR路由，根据记录的ASBR和外部 LSA之间的对应关系，找到其对应的外部LSA，执行步骤512。

在步骤512中，针对找到的外部LSA计算外部路由，实施外部路由的增 量计算。结束当前更新流程。

在步骤513中，执行外部路由增量计算，即针对收到的第五类或第七类 LSA执行外部路由计算，结果当前更新流程。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本 发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在 本发明的保护范围之内。