本发明公开了一种基于增量最短路径优先的域内路由保护方法，属于互联网技术领域，解决了现有DC方法无法在提高故障保护率的同时又不增加网络额外负担的技术问题。该方案包括：节点c计算以自身为根的最短路径树spt(c)；将与其直接相连的链路的代价设置为0；根据增量最短路径优先计算新的最短路径树spt'(c)；根据spt(c)和spt'(c)计算节点c到所有目的的备份下一跳。本发明可以为运行算法的节点计算出符合DC规则的所有备份下一跳，不仅降低了DC方案的实现复杂度，并且与DC具有同样的故障保护率。
一种基于增量最短路径优先的域内路由保护方法
技术领域
[0001] 本发明属于互联网技术领域，涉及域内路由保护方案，具体涉及一种基于增量最短路径优先的域内路由保护方法。
背景技术
[0002] 互联网的飞速发展使其成为全球最主要的通信基础设施。因此，越来越多的应用程序部署在互联网上，人们对互联网的依赖达到了前所未有的程度，生活在以网络为核心的时代。互联网在设计之初主要支持一些非实时应用，例如发送邮件，传送文件等。
[0003] 但是，现在许多实时应用程序部署在互联网上，例如VoIP(Voice over Internet Protocol)，电话会议，视频，远程控制等。因为实时应用对网络时延和丢包率更加敏感，所以这些应用对网络的可靠性提出了更加苛刻的要求。但是目前互联网采用的域内路由协议利用最短路径转发报文，当故障出现时，路由协议需要重新收敛，从而导致报文丢失。现在部署的域内路由协议的慢收敛速度无法满足实时应用对网络可靠性的要求，因此提高域内路由可靠性成为学术界和工业界密切关注的一个重要研究课题。
[0004] 为了缓解域内路由协议慢收敛和实时应用之间的矛盾，许多研究人员开始致力于提高网络可靠性的研究。业界一般采用被动恢复方案和路由保护方案来提高网络的可靠性。被动恢复方案主要通过调整路由协议的默认参数加快路由收敛速度，但是该方案可能导致路由震荡，造成网络不稳定。路由保护方案的基本思路是：给定网络拓扑结构，根据无环路规则预先计算出所有节点到达目的地址的备用下一跳，当网络出现故障时利用这些备用下一跳转发受影响的报文，从而降低网络中断时间，减少报文丢失率，进而大大提高网络可靠性。根据转发报文的方式可以将路由保护方案分为非逐跳转发和逐跳转发。非逐跳转发方式需要利用辅助机制的协助，如Not-Via、隧道和多协议标签交换(MPLS，Multi-Protocol Label Switching)等，这些辅助机制需要消耗大量的存储空间并且增加了转发开销，对协议的改动较大，不容易实际部署。逐跳转发方式和目前互联网域内路由协议的转发方式是相同的，因此受到了学术界的青睐。在基于逐跳转发的路由保护方案中，DC(Downstream Criterion)是一种较为经典并且受到关注的路由保护方案。针对DC算法复杂度较高的问题，本发明设计一种基于增量最短路径优先的域内路由保护方法，该方法不仅具有较高的计算效率，并且和DC具有同样的故障保护率。
发明内容
[0005] 本发明所要解决的技术问题之一是需要提供一种基于增量最短路径优先的域内路由保护方法，该方法可以快速实现DC规则，并且与DC具有相同的故障保护率。由于本发明为一种分布式解决方案，所有节点采用的方法是相同的，因此下面假设计算节点为c。为了方便描述，我们先定义一些标记，这些标记适用于整个发明。我们用图G＝(V,E)表示一个网络拓扑结构，V为该拓扑中节点的集合，E为该拓扑中边的集合。对于 N(v)表示该节点的所有邻居节点，spt(v)为以该节点为根的最短路径树，D(spt(v),x)表示在spt(v)中x的所有子孙节点。对于 w(i,j)为该边对应的代价；对于 cost(c,d)表示这两个节点之间的最小代价，dn(c,v)表示根节点c到节点v的默认下一跳，bn(c,v)表示根节点c到节点v的备份下一跳的集合。
[0006] 为了解决上述技术问题，本发明提供了一种基于增量最短路径优先的域内路由保护方法，包括以下步骤：
[0007] 步骤S101：计算以节点c为根节点的最短路径树spt(c)，包括以下步骤：
[0008] 步骤11，网络中所有路由器根据开放最短路径优先(OSPF)协议获取域内拓扑结构；
[0009] 步骤12，创建一个优先级队列，优先级队列中节点对应的结构体由路由器标识、节点代价、父亲节点和访问标识组成；将网络中所有节点的结构体进行初始化；节点结构体包括，该节点的路由器标识、节点代价、父亲节点和访问标识；将根节点c的节点代价设置为0，将其余节点的节点代价设为无穷大，设置所有节点的父亲节点为空，设置所有节点的访问标记为未访问，路由器ID为Loopback接口(回环接口)地址；将根节点c加入到该队列中；
[0010] 步骤13，检查优先级队列中是否为空；如果不为空，则执行步骤14；如果为空，则执行步骤S102；
[0011] 步骤14，根据节点出队列规则选取一个节点出队列，将出队列的节点存储在变量v中，并且将其访问标识属性设置为已访问，
[0012] 所述节点出队列规则：
[0013] (1)如果节点代价不同时，选择节点代价最小的节点出队列；
[0014] (2)如果多个节点具有相同的节点代价时，选择路由器标识最小的节点出队列；
[0015] 步骤15，如果出队列的节点不是根节点c，计算出根节点c到该节点的默认下一跳；当一个节点出队列后，将该节点的节点代价t(c,v)的数值赋给节点c到该节点的最小代价cost(c,v)即cost(c,v)＝t(c,v)，其中t(c,v)表示节点v的节点代价；
[0016] 通过下面的方法计算根节点c到v的默认下一跳dn(c,v)：
[0017]
[0018] 其中，p(c,v)表示节点v的父亲节点；
[0019] 步骤16，遍历节点v的未被访问过的邻居节点，根据更新邻居节点的节点代价和父亲节点的方法，并且将更新后的节点存储在优先级队列中；
[0020] 所述更新邻居节点的节点代价和父亲节点的方法：
[0021] 将节点v的邻居节点存储在变量u中，如果节点u的访问标识为未访问，并且节点代价满足t(c,u)＞cost(c,v)+w(v,u)，则将其节点代价更新为t(c,u)＝cost(c,v)+w(v,u)，节点u的父亲节点可以表示为p(c,u)＝v；
[0022] 步骤17，如果节点u是节点v的最后一个未被访问的邻居或者节点u的所有邻居都被访问过，则执行步骤13，否则继续遍历其下一个邻居节点，并且执行步骤16；
[0023] 步骤S102：改变与根节点c直连节点的权值，如果x∈N(c)，则将链路(c,x)和链路(x,c)的权值调整为0，即w(c,x)＝w(x,c)＝0，并且将该链路权值变化量存储在变量weight中，N(c)表示根节点c的邻居节点；
[0024] 步骤S103：计算新的最短路径树，包括以下步骤：
[0025] 步骤31，将除去根节点c的所有节点的访问标识设置为未访问，找出节点x的所有子孙节点D(spt(c),x)，如果y∈D(spt(c),x)，则将cost(c,x)＝cost(c,x)-weight，将D(spt(c),x)中所有节点的访问标记设置为已访问，对于 如果该节点未被访问并且与D(spt(c),x)中的节点直接相连，根据t(c,m)＝cost(c,x)+w(x,m)计算该节点的节点代价；如果t(c,m)＜cost(c,m)，则将节点m的节点代价修改为t(c,m)，父亲节点修改为节点x；将节点m加入到优先级队列中；
[0026] 步骤32，检查优先级队列中是否为空，如果不为空，则执行步骤33，如果为空，则执行步骤S104；
[0027] 步骤33，根据节点出队列规则选取一个节点出队列，将出队列的节点存储在变量v中，并且将其访问标识属性设置为已访问；当一个节点出队列后，将该节点的节点代价t(c,v)的数值赋给节点c到该节点的最小代价cost(c,v)即cost(c,v)＝t(c,v)，其中t(c,v)表示节点v的节点代价；
[0028] 所述节点出队列规则：
[0029] (1)如果节点代价不同时，选择节点代价最小的节点出队列；
[0030] (2)如果有多个节点具有相同的节点代价时，选择路由器标识最小的节点出队列；
[0031] 步骤34，遍历节点v的未被访问过的邻居节点，根据更新邻居节点的节点代价和父亲节点方法，并且将更新后的节点存储在优先级队列中；
[0032] 所述更新邻居节点的节点代价和父亲节点方法：
[0033] 将节点v的邻居节点存储在变量u中，如果节点u的访问标识为未访问，并且节点代价满足t(c,u)＞cost(c,v)+w(v,u)，则将其节点代价更新为t(c,u)＝cost(c,v)+w(v,u)，节点u的父亲节点可以表示为p(c,u)＝v；
[0034] 步骤35，如果节点u是节点v的最后一个未被访问的邻居或者节点u的所有邻居都被访问过，则执行步骤32；否则继续遍历其下一个邻居节点，并且执行步骤34；
[0035] 步骤S104：根据spt(c)和spt'(c)计算根节点c到到网络中其他所有节点的备份下一跳，具体方法如下：
[0036] 对于网络中除去根节点c的任意一个节点，将该节点存储在变量u中，如果在spt(c)中，根节点c到节点u的默认下一跳为y；对于链路(c,x)(x≠y)，将其权值调整为0；在新的spt'(c)中，如果节点u为节点x的子孙节点u∈D(spt'(c),x)，则cost(x,u)＜cost(c,u)，则节点x可以作为根节点c到节点u的备份下一跳，即bn(c,u)＝bn(c,u)∪{x}；
[0037] 然后，将链路(c,x)和链路(x,c)的权值调整为变更为0之前的数值，如果与其直接相连的链路的代价没有被调整过，则执行步骤S102，否则方法结束。
[0038] 与现有技术相比，本发明具有如下优点：
[0039] 本发明提出了一种基于增量最短路径优先的域内路由保护方法，该方法可以快速计算出所有节点的符合DC规则的备份下一跳，并且与DC具有相同的故障保护率；另外，本发明充分利用了网络中路径的多样性，因此具有更高的可靠性。
[0040] 本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在说明书、权利要求书以及附图中所特别指出的结构来实现和获得。
附图说明
[0041] 图1是本发明的保护方法流程示意图。
[0042] 图2是本发明实施例网络拓扑结构示意图。
[0043] 图3是本发明实施例计算以节点c为根的最短路径树的过程示意图。
[0044] 图4是本发明实施例当链路(c,a)的权值变为0时对应的最短路径树示意图。
[0045] 图5是本发明实施例当链路(c,b)的权值变为0时对应的最短路径树示意图。
具体实施方式
[0046] 为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明作进一步地详细说明。
[0047] 现在互联网部署的域内路由协议，如IS-IS(Intermediate System-to-Intermediate System，中间系统到中间系统)和OSPF(Open Shortest Path First开放式最短路径优先)，网络中的每个路由器根据自己学习到的网络拓扑结构体计算一棵以自己为根的最短路径树(SPT，Shortest Path Tree)，利用该树构造出路由表。根据上述描述可知，目前域内路由协议采用最短路径转发报文，但是当源节点到目的节点的默认下一跳出现故障时，传输到该节点的报文将会丢失，将会造成网络中断，大大降低了用户体验。为了提升网络可靠性，提高用户体验，国际互联网工程任务组(The Internet Engineering Task Force，IETF)提出利用DC规则(Downstream Criterion)应对网络中的单链路故障。
[0048] DC规则的具体内容如下：对于目的地址d，根节点c可以将报文发送给其邻居节点x，当且仅当满足cost(x,d)＜cost(c,d)。
[0049] 为了实现DC规则，根节点c需要知道cost(c,d)和cost(x,d)的数值。根节点c可以通过spt(c)获得cost(c,d)的值，为了得到cost(x,d)的值，根节点c需要计算一棵以节点x为根的最短路径树。但是，当根节点c有k个邻居节点时，则需要构造k棵最短路径树。因此，该方法的复杂度随着网络节点平均度的增加而增加，因此已有实现方式无法满足大规模网络的需求。
[0050] 图1是根据本发明保护方法的流程示意图。
[0051] 下面详细说明本实施例的各个步骤。
[0052] 假设计算节点为c，该方法开始于步骤S101，在步骤S101中，节点c构造以自身为根的最短路径树，具体步骤如下：
[0053] 步骤11，网络中所有路由器根据开放最短路径优先(OSPF)协议获取域内拓扑结构，如图2；
[0054] 步骤12，创建一个优先级队列Q，将根节点c的节点代价设置为0，将其余节点的节点代价设为无穷大，设置所有节点的父亲节点为空，设置所有节点的访问标记为未访问，路由器ID为Loopback接口(回环接口)地址。首先将根节点c加入到该队列中,Q(c)；
[0055] 步骤13，队列Q不为空，执行步骤14；
[0056] 步骤14，节点c出队列，如图3(1)，变量v的值为c，将节点c的访问属性标记为已访问；
[0057] 步骤15，因为出队列的节点是c，所以该步骤不执行任何操作；
[0058] 步骤16，遍历节点c的未被访问的邻居节点，u＝a，更新其节点代价和父亲节点；更新后节点a的节点代价为t(c,a)＝3，父亲节点为p(c,a)＝c，此时队列中的节点包括{a}；
[0059] 步骤17，因为节点a不是节点c的最后一个未被访问的邻居节点，因此执行步骤16；
[0060] 步骤16，遍历节点c的未被访问的邻居节点，u＝b，更新其节点代价和父亲节点。更新后节点b的节点代价为t(c,b)＝5，父亲节点为p(c,b)＝c，此时队列中的节点包括{a,b}；
[0061] 步骤17，因为节点b是节点c的最后一个未被访问的邻居节点，因此执行步骤13；
[0062] 步骤13，队列Q不为空，执行步骤14；
[0063] 步骤14，节点a出队列，如图3(2)，变量v的值为a，将节点a的访问属性标记为已访问,cost(c,a)＝3；
[0064] 步骤15，节点c到节点a的默认下一跳为a；
[0065] 步骤16，遍历节点a的未被访问的邻居节点，u＝d，更新其节点代价和父亲节点；更新后节点d的节点代价为t(c,d)＝6，父亲节点为p(c,d)＝a，此时队列中的节点包括{b,d}；
[0066] 步骤17，因为节点d不是节点a的最后一个未被访问的邻居节点，因此执行步骤16；
[0067] 步骤16，遍历节点a的未被访问的邻居节点，u＝e，更新其节点代价和父亲节点。更新后节点e的节点代价为t(c,e)＝9，父亲节点为p(c,e)＝a，此时队列中的节点包括{b,d,e}；
[0068] 步骤17，因为节点e是节点a的最后一个未被访问的邻居节点，因此执行步骤13；
[0069] 步骤13，队列Q不为空，执行步骤14；
[0070] 步骤14，节点b出队列，如图3(3)，将节点b的访问属性标记为已访问,cost(c,b)＝5；
[0071] 步骤15，节点c到节点b的默认下一跳为b；
[0072] 步骤16，遍历节点b的未被访问的邻居节点，u＝d，更新其节点代价和父亲节点；因为cost(c,b)+w(b,d)＝7>t(c,d)＝6,所以不对其进行更新；
[0073] 步骤17，因为节点d不是节点b的最后一个未被访问的邻居节点，因此执行步骤16；
[0074] 步骤16，遍历节点b的未被访问的邻居节点，u＝e，更新其节点代价和父亲节点，因为cost(c,b)+w(b,e)＝8>t(c,e)＝9,所以更新后节点e的节点代价为t(c,e)＝8，父亲节点为t(c,e)＝b；此时队列中的节点包括{d,e}；
[0075] 步骤17，因为节点e是节点b的最后一个未被访问的邻居节点，因此执行步骤13；
[0076] 步骤13，队列Q不为空，执行步骤14；
[0077] 步骤14，节点d出队列，如图3(4)，将节点d的访问属性标记为已访问,cost(c,d)＝6；
[0078] 步骤15，节点c到节点d的默认下一跳为a；
[0079] 步骤16，遍历节点d的未被访问的邻居节点；
[0080] 步骤17，因为节点d的所有邻居已经被访问，所以执行步骤13；
[0081] 步骤13，队列Q不为空，执行步骤14；
[0082] 步骤14，节点e出队列，如图3(5)，将节点e的访问属性标记为已访问，cost(c,e)＝8；
[0083] 步骤15，节点c到节点e的默认下一跳为b；
[0084] 步骤16，遍历节点e的未被访问的邻居节点；
[0085] 步骤17，因为节点e的所有邻居已经被访问，所以执行步骤13；
[0086] 步骤13，队列Q为空，执行步骤S102；
[0087] 步骤S102，将链路(c,a)和链路(a,c)的权值调整为0；
[0088] 步骤S103：计算新的最短路径树，包括以下步骤：
[0089] 步骤31，将所有节点的访问标记设置为未访问；节点a的所有子孙节点为{d}，将节点d的最小代价调整为3，将节点d的访问标识设置为未访问；更新节点e的节点代价和父亲节点，更新后节点e的节点代价为t(c,e)＝6，父亲节点为p(c,e)＝a，将节点e加入到队列，此时队列中的节点包括{e}；
[0090] 步骤32，队列Q不为空，执行步骤33；
[0091] 步骤33，节点e出队列，将节点e的访问属性标记为已访问,cost(c,e)＝6；
[0092] 步骤34，遍历节点e的未被访问的邻居节点，u＝b，更新其节点代价和父亲节点。因为cost(c,e)+w(e,b)＝9>cost(c,b)，所以不对其进行更新；
[0093] 步骤35，因为节点b是节点e的最后一个邻居，执行步骤32；
[0094] 步骤32，队列Q为空，执行步骤S104；
[0095] 步骤S104，节点c到节点e的备份下一跳为a，将链路(c,a)和(a,c)的权值调整为变更之前的数值；
[0096] 步骤S102，将链路(c,b)和链路(b,c)的权值调整为0；
[0097] 步骤S103：计算新的最短路径树，包括以下步骤：
[0098] 步骤31，将所有节点的访问标记设置为未访问。节点b的所有子孙节点为{e}，将节点e的节点代价调整为3，将节点e的访问标识设置为未访问；更新节点d的节点代价和父亲节点，更新后节点d的节点代价为3，父亲节点为b，将节点d加入到队列，此时队列中的节点包括{d}；
[0099] 步骤32，队列Q不为空，执行步骤33；
[0100] 步骤33，节点d出队列，将节点d的访问属性标记为已访问；
[0101] 步骤34，遍历节点d的未被访问的邻居节点，u＝a，更新其节点代价和父亲节点。因为cost(c,d)+w(d,a)＝6>cost(c,b)＝3，所以不对其进行更新；
[0102] 步骤35，因为节点a是节点d的最后一个邻居，执行步骤32；
[0103] 步骤32，队列Q为空，执行步骤S104；
[0104] 步骤S104，节点c到节点d的备份下一跳为b，将链路(c,b)和(b,c)的权值调整为变更之前的数值；因为与节点c直接相连的链路的权值都调整过，所以方法运行结束。
[0105] 图2为本发明实施例网格拓扑结构示意图。为根据步骤11，网络中所有路由器根据开放最短路径优先(OSPF)协议获取域内拓扑结构。
[0106] 图3为本发明实施例计算以节点c为根的最短路径树的具体过程示意图。展示本发明实施例计算最短路径树的过程。
[0107] 图4为本发明实施例当链路(c,a)的权值变为0时对应的最短路径树示意图。展示本发明实施例当链路(c,a)的权值变为0时对应的最短路径树。
[0108] 图5为本发明实施例当链路(c,b)的权值变为0时对应的最短路径树示意图。展示当链路(c,b)的权值变为0时对应的最短路径树。
[0109] 下面具体说明本发明的工作原理。
[0110] 原理1：在spt(c)中，节点c到节点u的默认下一跳为y。对于链路(c,x)(x≠y)，将其权值调整为0，在新的spt'(c)中，如果节点u为节点x的子孙节点，即u∈D(spt'(c),x)，则cost(x,d)＜cost(c,d)。
[0111] 证明：因为dn(c,u)＝y,y≠x，所以cost(c,u)＝cost(c,y)+cost(y,u)。因为在spt'(c)，u∈D(spt'(c),x)，所以costnew(c,u)＝cost(c,x)+cost(x,u)，其中costnew(c,u)表示在spt'(c)中，节点c到节点u的最小代价，因为，在spt'(c)中，cost(c,x)＝0，所以costnew(c,u)＝cost(x,u)(1)。因为，在spt(c)中， 在spt'(c)中，v∈D(spt(c),x)，所以costnew(c,u)＞cost(c,u)(2)。根据(1)和(2)可以得到cost(x,u)＜cost(c,u)。
[0112] 原理2：在spt(c)中，节点c到节点u的默认下一跳为y。对于链路(c,x)(x≠y)，将其权值调整为0，在新的spt'(c)中，如果节点u为节点x的子孙节点，即u∈D(spt'(c),x)，则节点x可以作为节点c到节点u的备份下一跳，即bn(c,u)＝bn(c,u)∪{x}。
[0113] 证明：由原理1可知，cost(x,d)＜cost(c,d)，根据DC规则可知节则节点x可以作为节点c到节点u的备份下一跳，因此该定理成立。
[0114] 原理3：本发明可以为节点c计算出所有满足DC条件的备份下一跳。
[0115] 证明：我们用反证法来证明该定理。对于目的地址u，假设存在一个节点x(x∈N(c))满足DC条件cost(x,u)＜cost(c,u)，但是利用上述方法计算出的节点c到节点u的备份下一跳集合不包括节点x。当计算节点x可以作为哪些节点的备份下一跳时，首先将链路(c,x)的权值调整为0，然后根据i-SPF构造新的最短路径树spt'(c)，由于cost(x,d)＜cost(c,d)，则在spt'(c)中节点u必定为节点x的子孙节点，根据原理1和原理2可知节点x可以作为节点c到节点u的备份下一跳，与前提假设矛盾，即该定理成立。
