本发明涉及通信技术领域， 特别涉及一种路由备份方法及装置。

背景技术

数据通信网络主要是由互联网协议（Internet Protocol, IP )的协议栈承 载， 每个 IP地址都标志着网络中一个主机的确切地址。 在 IP网络中， 路由器 作为基本网络节点， 承担着传递 IP报文的角色， 具体地， 在传递 IP报文的过 程中，路由器要在本地的 IP路由表中查询对应该 IP报文地址的出接口， 然后 再将该 IP报文从这个出接口中发出。

内部网关协议（ Internal Gateway Protocol, IGP )是 IP网络中最常用的 路由协议， 包括开放式最短路径优先（Open Shortest Path First, OSPF ), 中 间系统到中间系统的路由选择协议 ( Intermediate System to Intermediate System Routing Protocol , IS-IS ), 和路由信息协议 ( Routing information Protocol, RIP )等。 当网络拓朴发生变化时， 如链路故障， 各个网络节点 之间要重新进行路由协议的交互来生成新的路 由表， 即路由收敛的过程。

现有一种快速重路由 （Fast Reroute, FRR ) 的方法主要是： 在链路发 生故障之前按一定算法产生备份路由， 并将备份路由的信息提前下发到路 由器的 IP路由表中进行储存， 当故障发生时，路由器直接使用 IP路由表中备 份路由的信息转发 IP报文，保证业务报文转发的不中断。上述在� ��生备份路 由时， 可以通过部分路由计算（ Partial Routes Calculation, PRC ) 的路由组 织方式， 或是通过无环备选路径（Loop-Free Alternates, LFA )等方法进行 确定备份路由。其中对于 PRC方法主要是以网络节点为单元，将各个网络 节 点发布的路由 （一个网络节点可能会发布多条路由）进行组 织， 这样就可 得知达到目的网络节点的路径， 即最短路径优选（Shortest Path First, SPF ) 的计算， 则到达目的路由的备份路由会继承到达目的网 络节点的备份路由； 而 LFA方法中主要是以路由为单位，将直接可达目 的路由且不会产生环路的 路由作为备份路由。

上述现有的 PRC方法和 LFA方法中进行路由备份的确定时，只针对各个 网络节点发布不同路由的情况， 但是实际应用中多个网络节点可能会发布 同一条路由即多源路由， 现有的方案中并没有针对多源路由进行备份的 方 法。

发明内容

本发明一方面提供一种路由备份方法及装置， 实现了多源路由的备份。 本发明一方面提供一种路由备份方法， 包括：

选择发布了与目的节点发布的路由相同的多源 路由的备选节点； 若从源节点分别到所述目的节点和所述备选节 点的路径上没有交集的 节点， 且从所述源节点到所述备选节点的路径上的中 间节点到所述备选节 点的距离， 小于从所述中间节点返回所述源节点再到所述 目的节点的距离， 将所述源节点到备选节点的路由作为所述源节 点到目的节点的备份路由。

本发明一方面提供一种路由备份方法， 包括：

确定对目的节点进行备份的备选节点；

若从源节点到所述备选节点的路径上的中间节 点到所述备选节点的距 离， 小于从所述中间节点返回所述源节点再到所述 目的节点的距离； 将所 述源节点到所述备选节点的路由作为所述源节 点到目的节点的备份路由。

本发明一方面提供一种路由备份装置， 包括：

备选选择单元， 用于选择发布了与目的节点发布的路由相同的 多源路 由的备选节点；

路由备份单元， 用于当从源节点分别到所述目的节点和所述备 选选择 单元选择的备选节点的路径上没有交集的节点 ， 且从所述源节点到所述备 选节点的路径上的所述中间节点到所述备选节 点的距离， 小于从所述中间 节点返回所述源节点再到所述目的节点的距离 ， 将所述源节点到所述备选 节点的路由作为所述源节点到目的节点的备份 路由。

本发明一方面提供一种路由备份装置， 包括：

备选确定单元， 用于确定对目的节点进行备份的备选节点；

备份确定单元， 用于当从源节点到所述备选节点的路径上的中 间节点 到所述备选节点的距离， 小于从所述中间节点返回所述源节点再到所述 目 的节点的距离； 将所述源节点到所述备选节点的路由作为所述 源节点到目 的节点的备份路由。

根据本发明一方面的方法， 先选择发布了与目的节点的路由相同的多 源路由的备选节点； 若从源节点分别到目的节点和备选节点的路径 上没有 交集的节点， 且从源节点到备选节点的路径上的中间节点到 备选节点的距 离， 小于从中间节点返回源节点再到目的节点的距 离， 则将源节点到备选 节点的路由作为源节点到目的节点的备份路由 以进行路由快速收敛。 本发 明实施例中主要是针对多个网络节点发布同一 条路由的情况， 釆用一种复 杂度较低的方法进行多源路由备份。

附图说明

为了更清楚地说明本发明实施例或现有技术中 的技术方案， 下面将对 实施例或现有技术描述中所需要使用的附图作 简单地介绍， 显而易见地， 下面描述中的附图仅仅是本发明的一些实施例 ， 对于本领域普通技术人员 来讲， 在不付出创造性劳动性的前提下， 还可以根据这些附图获得其他的 附图。

图 1是本发明实施例提供的一种路由备份方法流� �图；

图 2是本发明实施例中按照 S PF算法组织的网络节点的关系结构示意 图；

图 3是按照本发明实施例中进行路由备份时， 各网络节点之间的关系结 构示意图；

图 4是本发明实施例提供的一种路由备份装置的� �构示意图；

图 5是本发明实施例提供的另一种路由备份装置� �结构示意图； 图 6是本发明实施例提供的另一种路由备份装置� �结构示意图。

具体实施方式

下面将结合本发明实施例中的附图， 对本发明实施例中的技术方案进 行清楚、 完整地描述， 显然， 所描述的实施例仅仅是本发明一部分实施例， 而不是全部的实施例。 基于本发明中的实施例， 本领域普通技术人员在没 有作出创造性劳动前提下所获得的所有其他实 施例， 都属于本发明保护的 范围。

本发明实施例提供一种路由备份方法， 可以应用于多个网络节点发布 同一个路由的场景下， 路由备份装置比如网管设备或网络节点等设备 对源 节点到目的节点路径的备份， 其方法流程图如图 1所示， 包括： 步骤 101 , 选择发布了与目的节点发布的路由相同的多源 路由的备选节 点。

可以理解， 每个网络节点都可以发布至少一条自己直接可 达的路由即 本地路由； 且多个网络节点可能会发布同一条路由即多源 路由， 可以发生 在 IGP域边界的网络节点，主要是由于 IGP域外对于 IGP域内是不可见的， 因 此 IGP域边界的多个网络节点可能会将 IGP域外部的路由作为自己的路由进 行发布， 从而产生了多源路由。 其中网络节点在发布路由时， 可以发布用 于唯一标识一条路由的前缀和开销值等信息， 多个网络节点发布同一条路 由是指多个网络节点发布的路由地址相同即路 由的前缀相同， 但是发布的 其它信息比如开销值可以不相同。

路由备份装置在选择备选节点时，可以先通过 SPF方法组织各个网络节 点发布的路由， 然后在组织的各个网络节点中选择备选节点， 具体在根据 SPF方法进行组织时， 路由备份装置一方面可以以 "路由" 为基点， 将所有 发布了同一条路由的网络节点组织在一起， 另一方面以 "网络节点" 为基 点， 将一个网络节点发布的所有路由都组织在一起 ， 这样就可以得到发布 同一条路由的多个网络节点的信息。

具体地， 在对源节点到目的节点的路由进行备份计算时 ， 可以先根据 各个网络节点发布的同一条路由的信息来选择 一个备选节点， 比如可以在 发布了与目的节点发布的路由相同的多源路由 的多个网络节点中， 选择发 布这条多源路由的开销值较小的网络节点作为 备选节点。

例如图 2所示， 通过 SPF方法的组织后， 可以看出， 在节点 A、 B、 C和 D中， 节点 A为根节点， 节点 B发布了三条路由 bl到 b3 , 节点 C发布了三条路 由 cl到 c3 , 节点 D发布了三条路由 dl到 d3 , 而节点 B、 C和 D都发布了同一条 路由 10.0.0.0/24, 即为多源路由。 如果节点 B为目的节点， 则可以选择节点 C 或节点 D作为备选节点。

步骤 102, 若从源节点分别到目的节点和备选节点的路径 上没有交集的 节点， 且从源节点到备选节点的路径上的中间节点到 备选节点的距离， 小 于从中间节点返回源节点再到目的节点的距离 ， 将源节点到备选节点的路 由作为源节点到目的节点的备份路由。

在选择了备选节点后， 需要确定该备选节点是否能作为目的节点的保 护， 需要满足如下的条件： ( 1 )源节点分别到目的节点和备选节点的路径上� �有交集的节点（除 了源节点）：

比如从源节点到目的节点的路径上经过节点 、 b和 c , 则从源节点到备 选节点的路径上就不能经过节点 a、 b和 c , 也就是两个不同的网络节点需要 有不同的下一跳节点， 这样就保证了从源节点到备选节点的路径上的 任一 个网络节点不会绕回到源节点到目的节点的路 径上。

( 2 )从源节点到备选节点的路径上的任一个中间� �点（不包括源节点 和备选节点）到备选节点的距离 S1 , 小于从中间节点返回源节点再到目的 节点的距离 S2 , 其中 S2为从中间节点返回源节点的距离， 与从源节点到目 的节点的距离之和， 即 S S2:

可以理解， 网络节点在发布路由时， 可以发布用于唯一标识一条路由 的前缀和开销值等信息， 其中开销值可以为指示距离， 带宽和延时等等信 息， 以供其它网络节点进行最优路由的计算。 在本实施例中， 路由备份装 置在进行路由备份的过程中， 考虑了各个网络节点发布的开销值， 具体地， 本实施例中从中间节点到备选节点的距离 S 1可以为从中间节点到备选节点 的最短距离， 与备选节点发布多源路由的开销值之和， 其中该多源路由与 目的节点的一个路由相同。

而中间节点返回源节点再到目的节点的距离 S2为从中间节点到源节点 的最短距离， 从源节点到目的节点的最短距离， 及目的节点发布路由的开 销值之和。

当满足上述条件 1和 2时， 即可实现无环备份， 将源节点到备选节点的 理由作为源节点到目的节点的备份路由， 则源节点的路由下一跳的备份即 为源节点到备选节点路由中源节点的下一跳。 在确定备份路由后， 可以根 据该备份路由进行快速收敛， 具体地， 如果源节点到目的节点的路由发生 故障时， 则将从源节点到目的节点的路由切换为从源节 点到备选节点的路 由。

例如图 3所示， 节点 S为源节点， 在节点 S中储存的路由表中包括目的节 点 A上发布的一条路由 10.0.0.10、 下一跳节点 E及节点 S到目的节点 A的距离 30, 其中从节点 S到目的节点 A的距离为从节点 S到节点 A的最短距离 20与节 点 A发布路由 10.0.0.10的开销值 10之和，而从节点 S到节点 A的最短距离可以 为节点 E发布路由的开销值 10与节点 A发布路由的开销值之和 20； 在备选节 点 B上也发布了这条路由 10.0.0.10,则节点 S可以确定节点 B是否能作为节点 A的保护节点， 具体地：

对于从节点 S到节点 B路径上的一个中间节点 N, 本实施例中， 从节点 N 到节点 B的距离 S1为从节点 N到节点 B的最短距离 10与节点 B发布路由 10.0.0.10的开销值 100之和 110 , 而从节点 N返回节点 S再到节点 A的距离 S2 为从节点 N到节点 S的最短距离 20、 从节点 S到节点 A的最短距离 20及节点 A 发送路由 10.0.0.10的开销值 10的和 50,由于 S1大于 S2,则不能实现无环备份， 即从节点 S到节点 B的路径不能作为从节点 S到节点 A的备份路径， 即节点 N 不能作为节点 S的备份路由。

假设网络节点数量为 N, 单源路由数为 M, 多源路由数为 P, 可选择成 为备份的网络节点数为 Q, 则按照现有的 LFA算法进行路由备份的复杂度为 (M+P)*Q, 而按照本实施例的方法进行多源路由备份的复 杂度为 P, 其中复 杂度可以指示在进行路由备份的计算的过程中 ， 使用备份公式来确定备份 路由的次数等信息， 可见釆用本发明实施例的方法进行多源路由备 份的复 杂度较低。

可见， 本发明实施例中， 先选择发布了与目的节点发布的路由相同的 多源路由的备选节点； 若从源节点分别到目的节点和备选节点的路径 上没 有交集的节点， 且从源节点到备选节点的路径上的中间节点到 备选节点的 距离， 小于从中间节点返回源节点再到目的节点的距 离， 则将源节点到备 选节点的路由作为源节点到目的节点的备份路 由以进行路由快速收敛。 本 发明实施例中主要是针对多个网络节点发布同 一条路由的情况， 釆用一种 复杂度较低的方法进行多源路由备份。 结果选择备选节点， 然后再确定该备选节点是否符合无环备份的条 件， 如 果是， 则确定备份路由， 可见， 本发明实施例中是将路由组织的算法与无 环备份的确定进行结合。 本发明实施例还提供一种路由备份方法， 主要是对不同网络节点之间 进行保护的一种路由备份方法， 包括：

步骤 201 , 确定对目的节点进行备份的备选节点。

在确定对目的节点进行备份的备选节点时， 可以选择对目的节点具有 相同接口或与目的节点发布了相同路由的节点 作为备选节点。

步骤 202, 若从源节点到备选节点的路径上的中间节点到 备选节点的距 离， 小于从中间节点返回源节点再到目的节点的距 离， 则源节点到备选节 点的路径上的任一个中间节点就不会返回到源 节点到目的节点的路径上， 可以进行无环备份， 就会将源节点到备选节点的路由作为源节点到 目的节 点的备份路由。

如果确定的备选节点与目的节点发布了同一条 路由， 则从源节点到备 选节点的路径上的中间节点到备选节点的距离 可以为： 从中间节点到备选 节点的最短距离， 与备选节点发布路由的开销值之和； 而中间节点返回源 节点再到目的节点的距离可以为： 从中间节点到源节点的最短距离， 从源 节点到目的节点的最短距离， 及目的节点发布路由的开销值之和等。

需要说明的是， 在确定备份路由后， 可以根据该备份路由进行快速收 敛， 具体地， 如果源节点到目的节点的路由发生故障时， 则将从源节点到 目的节点的路由切换为从源节点到备选节点的 路由。

本发明实施例中先确定对目的节点进行备份的 备选节点， 再确定该备 选节点是否符合无环备份的条件， 如果是， 则确定备份路由， 实现了对不 同网络节点的路由进行的无环保护。 本发明实施例还提供一种路由备份装置，结构 示意图如图 4所示， 包括： 备选选择单元 10 , 用于选择发布了与目的节点发布的路由相同的 多源 路由的备选节点；

路由备份单元 11 , 用于当从源节点分别到所述目的节点和所述备 选选 择单元 10选择的备选节点的路径上没有交集的节点， 且从所述源节点到所 述备选节点的路径上的中间节点到所述备选节 点的距离， 小于从所述中间 节点返回所述源节点再到所述目的节点的距离 ， 将所述源节点到所述备选 节点的路由作为所述源节点到目的节点的备份 路由。

其中从源节点到备选节点的路径上的任一个中 间节点到备选节点的距 离可以为： 从中间节点到备选节点的最短距离， 与备选节点发布多源路由 的开销值之和； 而中间节点返回源节点再到目的节点的距离可 以为： 从中 间节点到源节点的最短距离， 从源节点到目的节点的最短距离， 及目的节 点发布路由的开销值之和。 可见， 本发明实施例中， 备选选择单元 10先选择发布了与目的节点发 布的路由相同的多源路由的备选节点； 若从源节点分别到目的节点和备选 节点的路径上没有交集的节点， 且从源节点到备选节点的路径上的中间节 点到备选节点的距离， 小于从中间节点返回源节点再到目的节点的距 离， 则路由备份单元 11将源节点到备选节点的路由作为源节点到目� ��节点的备 份路由。 本发明实施例中主要是针对多个网络节点发布 同一条路由的情况， 釆用一种复杂度较低的方法进行多源路由备份 。

参考图 5所示， 在一个具体的实施例中， 路由备份装置除了包括如图 4 所示的结构外， 还可以包括路由收敛单元 12 , 且备选选择单元 10具体可以 包括节点组织单元 110和选择单元 120 , 其中：

路由收敛单元 12, 用于当所述源节点到所述目的节点的路由发生 故障， 根据路由备份单元 11确定的备份路由， 将所述源节点到所述目的节点的路 由切换为从所述源节点到所述备选节点的路由 。

节点组织单元 110 , 用于通过最短路径优选 SPF组织各个网络节点发布 的路由； 通过节点组织单元 110组织后， 可以直观地得到发布同一条路由的 多个网络节点的信息。

选择单元 120 , 用于在所述节点组织单元 110组织的各个网络节点中， 选择发布了与目的节点发布的路由相同的多源 路由的备选节点。

选择单元 120具体可以用于根据所述节点组织单元 110的组织， 在发布 了与目的节点发布的路由相同的多源路由的多 个网络节点中， 选择发布所 述多源路由的开销值较小的节点作为备选节点 。

本实施例中， 通过节点组织单元 110的组织和选择单元 120的选择后得 到备选节点， 并由路由备份单元 11确定备份路由， 且可以由路由收敛单元 12进行路由快速收敛。 本发明实施例还提供一种路由备份装置，结构 示意图如图 6所示， 包括： 备选确定单元 20 , 用于确定对目的节点进行备份的备选节点。

备选确定单元 20在确定对目的节点进行备份的备选节点时， 可以选择 对目的节点具有相同接口或与目的节点发布了 相同路由的节点作为备选节 点。

备份确定单元 21， 用于当从源节点到备选确定单元 20确定的备选节点 的路径上的中间节点到所述备选节点的距离， 小于从所述中间节点返回所 述源节点再到所述目的节点的距离； 将所述源节点到所述备选节点的路由 作为所述源节点到目的节点的备份路由。

如果备选确定单元 20确定的备选节点与目的节点发布了同一条路� ��， 则从源节点到备选节点的路径上的中间节点到 备选节点的距离可以为： 从 中间节点到备选节点的最短距离， 与备选节点发布路由的开销值之和； 而 中间节点返回源节点再到目的节点的距离可以 为： 从中间节点到源节点的 最短距离， 从源节点到目的节点的最短距离， 及目的节点发布路由的开销 值之和等。

且本实施例中的装置还可以包括收敛单元， 用于当所述源节点到所述 目的节点的路由发生故障， 根据备份确定单元 21确定的备份路由， 将所述 源节点到所述目的节点的路由切换为从所述源 节点到所述备选节点的路 由。 点， 再由备份确定单元 21确定该备选节点是否符合无环备份的条件， 如果 是， 则确定备份路由， 从而可以通过收敛单元进行路由快速收敛， 实现了 对不同网络节点的路由进行的无环保护。

本发明实施例提供的各种路由备份装置可以执 行方法实施例中的相应 步骤， 在此不再赘述。

本领域普通技术人员可以理解上述实施例的各 种方法中的全部或部分 步骤是可以通过程序来指令相关的硬件来完成 ， 该程序可以存储于一计算 机可读存储介质中， 存储介质可以包括： 只读存储器（ROM )、 随机存取存 储器（RAM )、 磁盘或光盘等。

以上对本发明实施例所提供的路由备份方法及 装置， 进行了详细介绍， 例的说明只是用于帮助理解本发明的方法及其 核心思想； 同时， 对于本领 域的一般技术人员， 依据本发明的思想， 在具体实施方式及应用范围上均 会有改变之处， 综上所述， 本说明书内容不应理解为对本发明的限制。