一种基于网络交叉度的域内路由保护方法

摘要

本发明公开了一种基于网络交叉度的域内路由保护方法，属于互联网技术领域，通过对节点对交叉度和网络交叉度的计算，计算出节点间的备份路径。本方案解决已有路由保护方法存在的以下两个问题：(1)默认路径和备份路径的交叉度较高，(2)为了计算两条交叉度低的路径，对默认路径加以限制，即默认路径不采用最短路径。本发明可以降低最短路径和备份路径的交叉度，大大提高了网络可用性。本文提出的方法和目前互联网部署的域内路由协议是兼容的，因此容易实际部署。

权利要求

1.一种基于网络交叉度的域内路由保护方法，包括以下步骤：步骤1：网络中所有节点根据开放最短路径优先(OSPF)协议获取域内网络结构，并且将该域内网络结构传递给该网络中心节点，该中心节点将拥有本自治系统的网络拓扑G，并且令其扩展拓扑结构G’＝G；

步骤2：在中心节点上，对于网络拓扑中的任意节点v，构造以节点v为根的最短路径树spt(v)；

步骤3：根据步骤2构造的最短路径树，计算出所有节点对之间的最短路径；

步骤4：根据步骤3得到的节点间的最短路径，根据以下计算每条链路介数的方法计算每条链路的介数；

链路l的介数为网络中所有最短路径经过该链路的次数，以形式化表示为：其中，B(l)表示链路l的介数，P(o,d,G)来表示节点对(o,d)之间的最短路径，k(l,o,d)表示链路l是否经过o和d的最短路径；

步骤5：根据边介数的大小对边进行降序排列，并将排序后的边存储在集合L中；

步骤6：如果集合L不为空并且G’中边的数量不等于|V|-1，则执行步骤7；否则，则执行步骤11；其中|V|表示节点的数量；

步骤7：从L中取出一条边m，将其从G’中删除，并且将m从L中删除；

步骤8：利用深度优先遍历算法判断网络G’是否连通；如果网络G’连通，则执行步骤9；

如果网络G’不连通，则执行步骤10；

步骤9：执行步骤6；

步骤10：将边m插入到G’中，执行步骤6；

步骤11：在网络中心节点上，对于网络拓扑中的任意节点v，根据网络拓扑G’构造以节点v为根的最短路径树spt(v)，这些最短路径就是节点对之间的备份路径。

2.根据权利要求1所述的一种基于网络交叉度的域内路由保护方法，其特征在于：其步骤8所述的利用深度优先遍历算法判断网络G’是否连通方法为：根据深度优先算法遍历网络G’中的节点，将遍历过的节点的访问标识属性标记为已访问，当遍历算法结束后，所有节点的访问标识属性都为已访问，则网络G’为连通图，否则该网络为非连通图。

说明书

一种基于网络交叉度的域内路由保护方法

技术领域

[0001] 本发明属于互联网技术领域，涉及域内路由保护方案，具体涉及一种基于网络交叉度的域内路由保护方法。

背景技术

[0002] 互联网最初部署的应用都是非实时应用，如发送邮件和传输文件等。随着网络的飞速发展，越来越多的实时应用部署在互联网上，如VoIP(Voice over Internet Protocol)、在线游戏、股票交易、在线手术和视频聊天等，这些实时应用需要互联网服务提供商(Internet Service Provider，ISP)提供近似无间断的服务和快速恢复机制。开放最短路径优先(Open Shortest Path First，OSPF)是最常用的互联网域内路由协议，该协议利用最短路径转发报文。当网络出现故障时，OSPF采用被动恢复方案灵活应对故障。OSPF通过设置各类定时器来降低协议开销，然而研究表明该机制的收敛时间通常需要几秒甚至几十秒。随着互联网的飞速发展，互联网在人们的日常生活中扮演了重要的角色，但是网络的慢收敛问题成为制约其发展的一个重要因素。

[0003] 研究证实网络中的单故障(节点、边)频繁发生。当故障发生时，传统路由协议，如OSPF，无法在50ms内完成收敛，很难满足实时应用对网络收敛时间的需求。因此，学术界和工业界普遍采用路由保护方案来应对网络中的故障。路由保护方案的基本思路是：利用一些无环路规则提前计算出备份路径，当网络中发生故障时，利用备份路径转发报文，从而绕过这些故障，尽可能降低由于故障造成的网络中断时间。

[0004] 作为最早应用于互联网的路由保护算法，等价多路径路由(Equal Cost Multiple Paths，ECMP)，其核心思想为如果源节点到目的节点有多条路径具有相同的最小代价，则可以将其作为备份路径。虽然该算法实现简单，部署容易，但是要求备份路径必须具有相同的最小代价，因此ECMP算法对路由可用性的贡献并不是很大。因此学术界提出利用路由偏转算法来提高路由可用性，即首先利用无环路规则计算源节点到目的节点的所有可选下一跳，再利用标签技术实现报文的灵活转发。虽然该算法可以提高路由可用性，但是其实现复杂，开销较大，难以实际部署。多配置路由(Multiple Routing Configurations，MRC)提出为每个节点保存多个配置图，每个配置包括所有的节点和边，通过调整边权值从而使得部分节点和边在该配置中得到保护，最终构造出针对所有可能出现的单故障的配置图。当报文在转发过程中遇到故障时，可以利用事先配置好的路由转发该报文。然而在现实网络中，该算法需要消耗大量的计算资源和存储开销。FCP(Failure Carrying Packet)提出将报文在转发过程中遇到的故障信息存储在该报文的头部，当报文到达某个节点时，该节点首先检测该报文头部的故障信息字段，根据该字段构造新的拓扑，然后利用新的拓扑重新计算最短路径，从而实现报文的无环路转发。该算法最大的好处是消除了路由收敛过程，然而计算复杂度高，对路由协议的改动比较大，不容易实际部署。针对上述路由保护算法计算开销大，并且对路由协议改动较大，不易部署等问题。国际互联网工程任务组(The Internet Engineering Task Force，IETF)提出利用IP快速重路由框架(IP Fast Re-Route，IPFRR)来降低因网络故障造成的报文丢失率，尽量缩短网络中断时间。无环回路备选机制(Loop-free Alternate，LFA)是基于IPFRR框架提出的一种解决算法，该算法实现简单，得到了广大节点厂商的支持。在请求注解RFC5286文档中，IETF发布了IPFRR的基本框架，提出了LFA的实现形式，其中包括单边保护条件(Loop Free Condition，LFC)，单节点保护条件(Node Protection Condition，NPC)和并发故障保护条件(Downstream Condition，DC)。基于Not-Via地址的快速重路由算法使用特殊地址Not-Via显示说明网络中的故障，从而在转发报文的过程中有效避开该故障。当报文在转发过程中遇到故障时，该报文将会被封装成特殊形式的报文，然后转发到合适的中转节点，最后中转节点对该报文解封装，并且按照最短路径转发该报文。然而，该算法需要辅助地址的协助，计算开销和存储开销较大，因此很难得到互联网服务提供商(Internet Service Provider,ISP)的支持。然而，上述方案都没有考虑备份路径和最短路径中边的交叉度。为了降低备份路径和最短路径中边的交叉度，研究人员提出利用红绿树来计算不相交路径，但是该方案的默认路由可能不是最短路径，这些方案限制了最短路径，无法和目前运行的域内路由协议兼容。

发明内容

[0005] 为了方便描述，我们先定义一些标记，这些标记适用于整个发明。网络可以用图G＝(V,E)来表示，其中变量V表示网络中节点的集合，变量E表示网络中的边的集合。对于网络中的边 用w(e)或者w(i,j)来表示该边对应的代价，根据实际网络配置情况，假设网络中边的代价是对称的，即w(i,j)＝w(j,i)。

[0006] 给定一个网络G＝(V,E)，对于该网络中任意的源和目的节点对(o,d)，用P(o,d,G)来表示该节点对之间的最短路径，D(o,d,G)表示该最短路径对应的代价，P(o,d,G')表示该节点对之间的备份路径，D(o,d,G')表示该备份路径对应的代价，其中G'为G的扩展网络拓扑。我们将在后续章节中详细介绍如何在G的基础上计算G'，在G'中计算出的节点对(o,d)之间的最短路径就是该节点对之间的备份路径。

[0007] 下面描述如何表示节点对(o,d)之间的最短路径和备份路径之间的交叉度。K(o,d,e)表示节点o和节点d之间的最短路径和备份路径是否同时经过边e，可以形式化表示为：

[0008]

[0009] 从公式(1)可知，如果边e同时经过(o,d)之间的最短路径和备份路径，则该值为1；否则，该值为0。

[0010] 定义1：节点对交叉度

[0011] 我们将节点o和节点d之间的交叉度定义为二者之间的最短路径和备份路径同时包含的公共边的数量，可以形式化表示为：

[0012]

[0013] 定义2：网络交叉度

[0014] 网络交叉度可以定义为网络中所有源-目的节点对之间的最短路径和备份路径同时包含的边的数量，即：

[0015]

[0016] 本发明关注的问题为：给定一个网络拓扑G＝(V,E)，如何计算其对应的扩展网络拓扑G'＝(V,E')，从而使得R(G,G')最小。为了解决上述技术问题，本发明提供了一种基于网络交叉度的域内路由保护方案，包括以下步骤：

[0017] 步骤1：网络中所有节点根据开放最短路径优先(OSPF)协议获取域内网络结构，并且将该域内网络结构传递给该网络中心节点，该中心节点将拥有本自治系统的网络拓扑G，并且令其扩展拓扑结构G’＝G；

[0018] 步骤2：在中心节点上，对于网络拓扑中的任意节点v，构造以节点v为根的最短路径树spt(v)；

[0019] 步骤3：根据步骤2构造的最短路径树，计算出所有节点对之间的最短路径；

[0020] 步骤4：根据步骤3得到的节点间的最短路径，计算每条边的介数。计算边介数的方法如下：边l的介数为网络中所有最短路径经过该边的次数，以形式化表示为：

[0021]

[0022]

[0023] 其中，B(l)表示边l的介数，k(l,o,d)表示链路l是否经过o和d的最短路径；

[0024] 步骤5：根据边介数的大小对边进行降序排列，并将排序后的边存储在集合L中；

[0025] 步骤6：如果集合L不为空并且G’中边的数量不等于|V|-1，则执行步骤7；否则，则执行步骤11；其中|V|表示节点的数量；

[0026] 步骤7：从L中取出一条边m，将其从G’中删除，并且将m从L中删除；

[0027] 步骤8：利用深度优先遍历算法判断网络G’是否连通；如果网络G’连通，则执行步骤9；如果网络G’不连通，则执行步骤10；

[0028] 步骤9：执行步骤6；

[0029] 步骤10：将边m插入到G’中，执行步骤6；

[0030] 步骤11：在中心节点上，对于网络拓扑中的任意节点v，根据网络拓扑G’构造以节点v为根的最短路径树spt(v)，这些最短路径就是节点对之间的备份路径。

[0031] 与现有技术相比，本发明具有如下优点：本发明不仅可以降低最短路径和备份路径的交叉度，并且和目前互联网部署的域内路由协议是兼容的，容易实际部署本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在说明书、权利要求书以及附图中所特别指出的结构来实现和获得。

附图说明

[0032] 图1是本发明的基于网络交叉度的域内路由保护方法流程示意图。

[0033] 图2是本发明实施例网络拓扑结构示意图。

[0034] 图3是本发明实施例计算以节点0为根的最短路径树的示意图。

[0035] 为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明作进一步地详细说明。

[0036] 下面详细说明本实施例的各个步骤。

[0037] 步骤1，网络中所有节点根据开放最短路径优先(OSPF)协议获取域内拓扑结构，并且将该拓扑信息传递给一个中心节点，如图2；

[0038] 步骤2，在中心节点上，对于网络拓扑中的任意节点v，构造以节点v为根的最短路径树spt(v)。由于节点数量过多，只列出以节点0为根的最短路径树spt(0)，如图3；

[0039] 步骤3：根据步骤2构造的树，计算出所有节点对之间的最短路径；由于路径数量过多，只列出节点0到其余节点的最短路径；下面的数字表示节点的最短路径各节点编号，如0 1 2表示节点0到节点2的最短路径为0 1 2；

[0040] 0 1

[0041] 0 1 2

[0042] 0 3

[0043] 0 3 4

[0044] 0 1 2 5

[0045] 0 3 4 7 6

[0046] 0 3 4 7

[0047] 0 3 4 7 8

[0048] 0 3 4 7 6 9

[0049] 0 3 4 7 6 9 10

[0050] 步骤4：根据步骤3得到的节点间的最短路径，计算每条边的介数；例如B(0,3)＝14表示边(0，3)的介数为14；

[0051] B(0,3)＝14

[0052] B(1,2)＝18

[0053] B(1,3)＝24

[0054] B(2,5)＝10

[0055] B(3,4)＝46

[0056] B(4,5)＝8

[0057] B(4,7)＝50

[0058] B(5,8)＝10

[0059] B(6,7)＝38

[0060] B(6,9)＝26

[0061] B(7,8)＝12

[0062] B(8,10)＝10

[0063] B(9,10)＝18

[0064] B(0,1)＝6

[0065] 步骤5：根据边介数的大小对边进行降序排列，并将排序后的边存储在集合L中；

[0066] B(4,7)＝50

[0067] B(3,4)＝46

[0068] B(6,7)＝38

[0069] B(6,9)＝26

[0070] B(1,3)＝24

[0071] B(1,2)＝18

[0072] B(9,10)＝18

[0073] B(0,3)＝14

[0074] B(7,8)＝12

[0075] B(2,5)＝10

[0076] B(5,8)＝10

[0077] B(8,10)＝10

[0078] B(4,5)＝8

[0079] B(0,1)＝6

[0080] 步骤6：此时集合L不为空并且G’中边的数量为14，|V|-1的值为10，G’中边的数量不等于|V|-1，执行步骤7；

[0081] 步骤7：从集合L中取出边(4,7)，将其从G’和L中删除；

[0082] 步骤8：根据深度优先算法判断G’是否连通，G’此时是连通图，执行步骤9；；

[0083] 步骤9：执行步骤6；

[0084] 步骤6：此时集合L不为空并且G’中边的数量为13，|V|-1的值为10，G’中边的数量不等于|V|-1，执行步骤7；

[0085] 步骤7：从集合L中取出边(3,4)，将其从G’和L中删除；

[0086] 步骤8：根据深度优先算法判断G’是否连通，G’此时是连通图，执行步骤9；

[0087] 步骤9：执行步骤6；

[0088] 步骤6：此时集合L不为空并且G’中边的数量为12，|V|-1的值为10，G’中边的数量不等于|V|-1，执行步骤7；

[0089] 步骤7：从集合L中取出边(6,7)，将其从G’和L中删除；

[0090] 步骤8：根据深度优先算法判断G’是否连通，G’此时是连通图，执行步骤9；

[0091] 步骤9：执行步骤6；

[0092] 步骤6：此时集合L不为空并且G’中边的数量为11，|V|-1的值为10，G’中边的数量不等于|V|-1，执行步骤7；

[0093] 步骤7：从集合L中取出边(6,9)，将其从G’和L中删除；

[0094] 步骤8：根据深度优先算法判断G’是否连通，G’此时是非连通图，执行步骤10；

[0095] 步骤10：将边(6,9)插入到G’中，执行步骤6；

[0096] 步骤6：此时集合L不为空并且G’中边的数量为11，|V|-1的值为10，G’中边的数量等于|V|-1，执行步骤7；

[0097] 步骤7：从集合L中取出边(1,3)，将其从G’和L中删除；

[0098] 步骤8：根据深度优先算法判断G’是否连通，G’此时是连通图，执行步骤9；

[0099] 步骤9：执行步骤6；

[0100] 步骤6：此时G’中边的数量为10；|V|-1的值为10，G’中边的数量等于|V|-1，则执行步骤11；

[0101] 步骤11：在中心节点上，对于网络拓扑中的任意节点v，根据网络拓扑G’构造以节点v为根的最短路径树spt(v)，根据构造的最短路径树，计算出所有节点对之间的最短路径；由于路径数量过多，只列出节点0到其余节点的最短路径；下面的数字表示节点的最短路径各节点编号，如012表示节点0到节点2的最短路径为012；

[0102] 0 1

[0103] 0 1 2

[0104] 0 3

[0105] 0 1 2 5 4

[0106] 0 1 2 5

[0107] 0 1 2 5 8 10 9 6

[0108] 0 1 2 5 8 7

[0109] 0 1 2 5 8

[0110] 0 1 2 5 8 10 9

[0111] 0 1 2 5 8 10

[0112] 下面具体说明本发明的工作原理。

[0113] 定理1：给定一个网络拓扑G＝(V,E)，如果删除网络中的任意一条边l∈E，G'＝(V,E')，E'＝E-{l}，则R(G,G')必定减小。

[0114] 证明：当删除网络中的任意一条边l∈E时，新的拓扑中将不再包含该边，因此根据该拓扑G'＝(V,E')计算出的备份路径将不再包含该边。对于网络中的任意源-目的节点对o和d，如果边 则该节点对的交叉度将不会受到影响，当l∈P(o,d,G)时，则该节点对之间的路径交叉度将会至少减少1。因为在网络拓扑G＝(V,E)中，对于任意一条边l∈E，该边一定会出现在最短路径中，因此，上述定理成立。

[0115] 定理2：给定一个网络拓扑G＝(V,E)，如果删除网络中的一组边 G'＝(V,E')，E'＝E-L，则R(G,G')必定减小。

[0116] 证明：由定理1可知，当删除网络中的任意一条边时，R(G,G')必定减少。因此，当删除多条边时，R(G,G')必定减少，上述定理成立。