本发明公开了一种基于逐跳方式的单节点故障保护方法，属于互联网技术领域，解决了一种可以100％保护网络中所有单节点故障情形的路由保护方法。该方案包括：节点d计算以自身为根的最短路径树rspt(d)；计算子树的最终桥，然后计算所有节点的备份下一跳。本发明提出了一种有效的单节点故障路由保护方案。该方案与目前互联网部署的域内路由协议是兼容的，因此支持增量部署，容易在实际环境中部署。
1.一种基于逐跳方式的单节点故障保护方法，包括以下步骤：
步骤1：计算以节点d为根节点的反向最短路径树rspt(d)；
步骤2：将网络中所有节点的备份下一跳设置为空，所有节点的访问标识设置为未访问，所有节点的颜色标记为白色；
步骤3：根据深度优先算法遍历以d为根的最短路径树中的未被访问过的节点；如果所遍历节点为未访问过的节点，则执行步骤4；如果所遍历的以节点d为根节点的最短路径树rspt(d)的全部节点均设为访问过的节点，则终止；
步骤4：将每次遍历的节点表示为节点v，设置节点v的访问标识为已访问；
步骤5：将其子树subtree(d,v)中的所有节点标记为红色，subtree(d,v)表示在rspt(d)中以节点v为根的子树的所有节点；
步骤6：访问节点v的未被访问过的孩子节点，根据计算第一类桥的方法判断；如果节点u∈child(d,v)对应的子树只有一个一类桥，则选择该桥作为该子树最终桥，记为(x,y)，其中child(d,v)表示在rspt(d)中节点v的孩子节点；如果节点u∈child(d,v)对应的子树有多个第一类桥，则根据计算最终的桥的方法，计算具有最短重路由路径的一个桥作为该子树最终的桥，记为(x,y)；
在以d为根的反向最短路径树中，对于该树中的任意一个节点v∈V-d，其中V表示网络中路由器的集合，当节点u∈child(d,v)时，如果存在一条链路，使得x∈subtree(d,u)和y∈V-subtree(d,v)-d同时成立，则链路(x,y)是子树subtree(d,u)的第一类桥；如果节点u∈child(d,v)对应的子树有第一类桥，将子树subtree(d,u)中的所有节点标记为红色，根据深度优先算法遍历子树subtree(d,u)中的所有节点，对于该子树中的节点x，检查它的每一个邻居节点y，如果该节点的颜色为白色，则链路(x,y)为子树subtree(d,u)的桥；
由下面公式计算节点u的重路由路径的代价，r(u,d)＝cost(u,x)+cost(x,y)+cost(y,d)，其中，cost(u,x)表示节点u到节点x的最小代价，cost(x,y)表示节点x到节点y的最小代价，cost(y,d)表示节点y到节点d的最小代价，r(u,d)表示节点u到节点d的重路由路径代价；对于找到的所有桥，选择具有最短重路由路径的一个桥作为该子树其最终的桥；
步骤7：如果节点v的孩子节点对应的子树不存在第一类桥，则根据第二类桥的计算方法，计算该子树的第二类桥，作为该子树最终的桥，记为(x,y)；
在以目的地址d为根的反向最短路径树中，对于该树中的任意一个节点v∈V-d，当节点u∈child(d,v)，w∈child(d,v)时，如果存在一条链路(p,q)，使得p∈subtree(d,u)和q∈subtree(d,w)同时成立，则链路(p,q)为子树subtree(d,u)和子树subtree(d,w)的第二类桥；如果节点u∈child(d,v)对应的子树只有第二类桥，根据广度优先算法遍历子树subtree(d,u)中的所有节点，寻找首次出现的一条边(x,y)，其中x是红色，y是绿色，则链路(x,y)即为该子树的最终桥；
步骤8：根据选择的最终的桥为相应节点，计算备份下一跳；其方法如下：
根据选定的最终的桥计算节点u的重路由路径，用(u,m...x,y,...p,q)来表示节点u的重路由路径，则相应节点的备份下一跳为：Backup(u,d)＝m，Backup(x,d)＝y，…，Backup(p,d)＝q，Backup(u,d)表示节点u到节点d的备份下一跳，Backup(x,d)表示节点x到节点d的备份下一跳，Backup(p,d)表示节点p到节点d的备份下一跳；如果节点已经有备份下一跳，则将该节点的访问标识设置为已访问；
步骤9：如果节点v的孩子节点u有备份下一跳，则将该孩子节点对应的子树中的全部节点标记为绿色；
步骤10：检测subtree(d,v)中节点的颜色，如果subtree(d,v)中节点的颜色存在红色，执行步骤6；
步骤11：检测subtree(d,v)中节点的颜色，如果subtree(d,v)中所有节点的颜色全部为绿色，将subtree(d,v)中所有节点的颜色标记为白色，执行步骤3。
2.根据权利要求1所述的一种基于逐跳方式的单节点故障保护方法，其特征在于：还包括以下步骤：
步骤12：当节点u收到报文时，根据故障检测方法检测，如果节点u到达目的地址的默认下一跳没有故障，则将该报文直接转发到其默认下一跳；如果节点u到达目的地址的默认下一跳出现故障，则将该报文直接转发到其备份下一跳。
一种基于逐跳方式的单节点故障保护方法
技术领域
[0001] 本发明属于互联网技术领域，涉及域内路由保护方案，具体涉及一种基于逐跳方式的单节点故障保护方法。
背景技术
[0002] 近些年来，互联网的发展速度已经远远超出了人们的预期，并且互联网支撑的应用范围也在不断扩大。互联网在迅速发展的同时，面临了新的挑战，其中域内路由可用性(Routing Availability)便是其中一个亟待需要解决的问题。相关研究表明，网络中的故障频繁发生，并且不可避免。在故障修复期间，路由协议需要经历一段时间的收敛过程，在路由协议收敛过程中将有大量报文丢失，大大降低了路由可用性。然而，随着一些新型应用的出现，例如VoIP、在线游戏、视频，这些应用对网络时延提出了更加严格的要求。因此，如何提高网络可用性，降低路由协议收敛过程中报文丢失率，是互联网面临的一个重要挑战。为了解决该问题，学术界和工业界提出了路由保护方案，该方案预先计算备份路由，当网络出现故障时，利用事先计算好的备份路径转发受故障影响的报文，从而有效减少报文丢失率。
[0003] IP快速重路由方案以其独特的优势受到学术界和工业界的青睐，该方案利用无环路规则(Loop Free Alternates：LFA)，计算备份下一跳，从而实现路由保护。该方案计算复杂度小，容易部署，因此大部分厂商的路由器支持该方案。然而，研究表明，利用该方案仅仅能保护50％左右的单故障情形。基于IP快速重路由框架，我们在文章提出了一种高效的路由保护方案。该方案算法复杂度低，并且支持动态更新，支持增量部署，然而该方案的故障保护率和IP快速重路由的故障保护率接近。
[0004] 为了进一步提高网络可用性，提出了利用U-turn方案提高故障保护率，该方案可以在其邻居节点中计算LFA下一跳。U-turn虽然明显提高了故障保护率，但是仍然达不到预期目标。基于快速重路由和U-turn存在的缺陷，提出了基于Not-Via地址的快速重路由方案。该方案利用辅助机制Not-Via地址，显式的表明网络中的故障，从而可用有效保护网络中所有单故障情形。虽然该机制可以大大提高网络的可用性，但是该机制的实现比较复杂，开销较大，不容易实际部署。
[0005] 基于上述方案存在的缺陷，提出了将基于IP快速重路由和基于Not-Via地址快速重路由结合的路由保护方案。该方案的基本思想是，当某节点存在IP快速重路由下一跳时，利用IP快速重路由方案，然而当该节点不在上述保护下一跳时，则利用基于Not-Via地址快速重路由计算保护下一跳。相比基于Not-Via地址快速重路由方案，融合方案大大降低了算法的复杂度，然而该方案仍然需要使用Not-Via地址，因此不容易实际部署。综上所述，IP快速重路由方案虽然实现简单，然而故障保护率较低。Not-Via虽然可以100％保护网络中单节点故障情形，然而该方案部署困难。因此，本发明设计一种可以100％保护网络中所有单节点故障情形的路由保护方法。
发明内容
[0006] 本发明所要解决的技术问题是需要提供基于逐跳方式的单节点故障保护方法，该方法100％保护网络中所有出现的单节点故障情形。由于本发明为一种分布式解决方案，所有节点采用的方法是相同的，因此下面假设计算节点为节点d。为了方便描述，我们先定义一些标记，这些标记适用于整个发明。网络拓扑结构可以用图G＝(V,E)来表示，其中V表示网络中路由器的集合，E表示网络中链路的集合。对于网络中的某条链路e＝(x,y)，用w(e)代表该链路的权值，该值可以是跳数、时延、带宽、能耗等，也可以是其中这几个度量的组合。Backup(s,d)表示节点s到节点d的备份下一跳；cost(s,d)表示节点s到节点d的最小代价，rspt(d)表示以节点d为根的反向最短路径树，child(d,v)表示在rspt(d)中节点v的孩子节点，subtree(d,v)表示在rspt(d)中以节点v为根的子树的所有节点。
[0007] 为了解决上述技术问题，本发明提供了一种基于逐跳方式的单节点故障保护方法，包括以下步骤：
[0008] 步骤1：计算以节点d为根节点的反向最短路径树rspt(d)；
[0009] 步骤2：将网络中所有节点的备份下一跳设置为空，所有节点的访问标识设置为未访问，所有节点的颜色标记为白色；
[0010] 步骤3：根据深度优先算法遍历以d为根的最短路径树中的未被访问过的节点；如果所遍历节点为未访问过的节点，则执行步骤4；如果所遍历的以节点d为根节点的最短路径树rspt(d)的全部节点均设为访问过的节点，则终止；
[0011] 步骤4：将每次遍历的节点表示为节点v，设置节点v的访问标识为已访问；
[0012] 步骤5：将其子树subtree(d,v)中的所有节点标记为红色；
[0013] 步骤6：访问节点v的未被访问过的孩子节点，根据计算第一类桥的方法判断；如果节点u∈child(d,v)对应的子树只有一个一类桥，则选择该桥作为该子数最终桥，记为(x,y)；如果节点u∈child(d,v)对应的子树有多个第一类桥，则根据计算最终桥的方法，计算具有最短重路由路径的一个桥作为该子树最终的桥，记为(x,y)；
[0014] 计算第一类桥的方法如下：
[0015] 在以d为根的反向最短路径树中，对于该树中的任意一个节点v∈V-d，当节点u∈child(d,v)时，如果存在一条链路，使得x∈subtree(d,u)和y∈V-subtree(d,v)-d同时成立，则链路(x,y)是子树subtree(d,u)的第一类桥；如果节点u∈child(d,v)对应的子树有第一类桥，将子树subtree(d,u)中的所有节点标记为红色，根据深度优先算法遍历子树subtree(d,u)中的所有节点，对于该子树中的节点x，检查它的每一个邻居节点y，如果该节点的颜色为白色，则链路(x,y)为子树subtree(d,u)的桥；
[0016] 计算最终桥的方法如下：由下面公式计算节点u的重路由路径的代价，r(u,d)＝cost(u,x)+cost(x,y)+cost(y,d)，其中r(u,d)表示节点u到节点d的重路由路径代价；该公式中涉及到的变量都可以很容易的从链路状态路由协议中得到；其中cost(x,y)可以从链路状态数据库中得到，其余变量可以通过rspt(d)得到，因此很容易计算相应的桥对应的重路由路径的代价；对于找到的所有桥，选择具有最短重路由路径的一个桥作为其最终的桥；
[0017] 步骤7：如果节点v的孩子节点对应的子树不存在第一类桥，则根据第二类桥的计算方法，计算该子树的第二类桥，作为该子树最终的桥，记为(x,y)；
[0018] 第二类桥的计算方法如下：
[0019] 在以目的地址d为根的反向最短路径树中，对于该树中的任意一个节点v∈V-d，当节点u∈child(d,v)，w∈child(d,v)时，如果存在一条链路(p,q)，使得p∈subtree(d,u)和q∈subtree(d,w)同时成立，则链路(p,q)为子树subtree(d,u)和子树subtree(d,w)的第二类桥；如果节点u∈child(d,v)对应的子树只有第二类桥，根据广度优先算法遍历子树subtree(d,u)中的所有节点，寻找首次出现的一条边(x,y)，其中x是红色，y是绿色，则链路(x,y)即为该子树的最终桥；
[0020] 步骤8：根据选择的最终的桥为相应节点，计算备份下一跳；其方法如下：
[0021] 根据选定的最终的桥计算节点u的重路由路径，用(u,m...x,y,...p,q)来表示节点u的重路由路径，则相应节点的备份下一跳为：Backup(u,d)＝m，Backup(x,d)＝y，…，Backup(p,d)＝q；如果节点已经有备份下一跳，则将该节点的访问标识设置为已访问；
[0022] 步骤9：如果节点v的孩子节点u有备份下一跳，则将该孩子节点对应的子树中的全部节点标记为绿色；
[0023] 步骤10：检测subtree(d,v)中节点的颜色，如果subtree(d,v)中节点的颜色存在红色，执行步骤6；
[0024] 步骤11：检测subtree(d,v)中节点的颜色，如果subtree(d,v)中所有节点的颜色全部为绿色，将subtree(d,v)中所有节点的颜色标记为白色，执行步骤3；
[0025] 步骤12：当节点u收到报文时，根据故障检测方法检测，如果节点u到达目的地址的默认下一跳没有故障，则将该报文直接转发到其默认下一跳；如果节点u到达目的地址的默认下一跳出现故障，则将该报文直接转发到其备份下一跳；
[0026] 故障检测方法：在实际网络中可以通过双向转发检测机制(BFD，Bidirectional Forwarding Detection)快速检测网络中的节点故障，BFD是一种高速的独立HELLO协议，BFD在两台网络设备上建立会话，用来检测网络设备间的双向转发路径，为上层应用服务；BFD本身并没有邻居发现机制，而是靠被服务的上层应用通知其邻居信息以建立会话；会话建立后会周期性地快速发送BFD报文，如果在检测时间内没有收到BFD报文则认为该双向转发路径发生了故障，通知被服务的上层应用进行相应的处理。
[0027] 与现有技术相比，本发明具有如下优点：
[0028] 本发明提出了一种基于逐跳方式的单节点故障保护方法，该方案能100％保护网路中所有可能的单节点故障情形，可以大大提高网络可用性，从而更好的支持对时延敏感的应用。另外，本发明充分利用了网络中路径的多样性，因此具有更高的可靠性。
[0029] 本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在说明书、权利要求书以及附图中所特别指出的结构来实现和获得。
附图说明
[0030] 图1是本发明的保护方法流程示意图。
[0031] 图2是本发明实施例网络拓扑结构示意图。
[0032] 图3是本发明实施例中计算以节点d为根的反向最短路径树的示意图。
[0033] 图4是本发明实施例中访问节点a时，为节点e计算保护路径示意图。
[0034] 图5是本发明实施例中访问节点a时，为节点c计算保护路径示意图。
[0035] 图6是本发明实施例中访问节点a时，为节点b计算保护路径示意图。
[0036] 为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明作进一步地详细说明。
[0037] 图1是根据本发明方法的流程示意图。
[0038] 下面详细说明本实施例的各个步骤。目的节点为d，具体步骤如下：
[0039] 步骤1：节点d构造以自身为根的反向最短路径树，如图3；
[0040] 步骤2：将网络中所有节点的备份下一跳设置为空，所有节点的颜色标记为白色；
[0041] 步骤3：根据深度优先算法遍历以d为根的最短路径树中的所有节点；
[0042] 步骤4：将访问的节点表示为节点v，此时v＝a；
[0043] 步骤5：将v的子树中所有节点subtree(d,v)＝{b,c,e,f,g,i}标记为红色；
[0044] 步骤6：找出节点v的所有孩子节点的子树的第一类桥，因为只有节点e对应的子树subtree(d,e)存在第一类桥，第一类桥可以表示为{(g,k),(i,l),(i,m)}；
[0045] 步骤7：因为节点v的孩子节点e对应的子树subtree(d,e)存在第一类桥，所以该步骤不执行任何操作；
[0046] 步骤8：当选择(g,k)为子树subtree(d,e)的第一类桥时，节点e的重路由路径的代价为29，当选择(i,l)为子树subtree(d,e)的第一类桥时，节点e的重路由路径的代价为32，当选择(i,m)为子树subtree(d,e)的第一类桥时，节点e的重路由路径的代价为38；因此选择链路(g,k)作为子树subtree(d,e)的最终桥，并且将该子树中所有节点标记为绿色。根据选择的最终桥可知，节点e的重路由路径为(e,g,k,j,d)，因此Backup(g,d)＝k,Backup(e,d)＝g；
[0047] 步骤9：因为目前v的孩子节点e已经有备份下一跳，则将该孩子节点对应的子树全部标记为绿色，如图4所示；
[0048] 步骤10：因为subtree(d,v)中有红色节点，则执行步骤6；
[0049] 步骤6：因为节点v的其余该子节点的子树现在只有二类桥，则执行步骤7；
[0050] 步骤7：选择链路(c,g)作为节点c为根的子树的最终桥；
[0051] 步骤8：根据选择的最终桥可知，节点c的重路由路径为(c,g,k,j,d)，因此Backup(c,d)＝g；
[0052] 步骤9：因为目前v的孩子节点c已经有备份下一跳，则将该孩子节点对应的子树全部标记为绿色，如图5所示；
[0053] 步骤10：因为subtree(d,a)中有红色节点，则执行步骤6；
[0054] 步骤6：因为节点v的其余该子节点的子树现在只有二类桥，则执行步骤7；
[0055] 步骤7：因此只选择一个桥即可，因此选择链路(b,c)作为以b为根的子树的最终桥；
[0056] 步骤8：根据选择的最终桥可知，节点b的重路由路径为(b,c,g,k,j,d)，因此Backup(b,d)＝c；
[0057] 步骤9：因为节点v的孩子节点b已经有备份下一跳，则将该孩子节点对应的子树全部标记为绿色，如图6所示；
[0058] 步骤10：因为subtree(d,a)中没有红色节点，不执行任何操作；
[0059] 步骤11：因为subtree(d,a)中所有节点都为绿色，将v的子树中所有节点subtree(d,v)＝{b,c,e,f,g,i}标记为白色，执行步骤3；
[0060] 步骤3：遍历网络rspt(d)中的下一个未被访问过的节点。
[0061] 下面具体说明本发明的工作原理。
[0062] 定义1：对于任意事件(u,d,f)，其中u表示源地址，d表示目的地址，f表示u到d的最优路径SP(u,d)上的单节点故障。当该事件出现时，如果u到d依然存在别的路径，二者仍然保持连通。即该网络图中不存在割点，当该网络拓扑结构中的任何一个节点出现故障时，都不会影响该网络的连通性，则称该网络具有健壮拓扑结构。
[0063] 原理1：对于一个健壮的网络拓扑结构，假设节点f出现故障，节点f有k个孩子节点，分别用(f1,f2...fk)表示，则必定存在一个孩子节点fx∈child(f)，该孩子节点对应的子树subtree(d,fx)至少有一个第一类桥；当某个孩子节点fy∈child(f)对应的子树没有第一类桥时，则该孩子节点对应的子树subtree(d,fy)至少有一个第二类桥。
[0064] 证明：下面使用反证法来证明该原理。
[0065] 首先证明该原理的前半部分。当节点f出现故障时，假设节点f的所有孩子节点都没有第一类桥。即对于任意节点fx∈child(f)不存在任何链路(p,q)，使得p∈subtree(d,fx)和q∈V-subtree(d,f)-d同时成立。那么对于任意节点p∈subtree(d,fx)，与节点p相连的链路的另一端q仅仅和集合subtree(d,f)中的结点相连，q到d的最优路径必定经过节点f。根据上述描述可知，当节点f出现故障时，节点fx∈child(f)对应的子树中的节点将无法到达目的。这与健壮的网络拓扑结构的前提假设相矛盾。因此该原理的前半部分成立。
[0066] 下面证明该原理的后半部分。当节点f出现故障时，对于节点fy∈child(f)，当该节点对应的子树没有第一类桥时，假设该节点对应的子树也不存在第二类桥。即对于节点fy∈child(f)，不存在任何链路(m,n)，使得m∈subtree(d,fy)和n∈subtree(d,fk)同时成立，其中fy∈child(f)。那么对于任意节点m∈subtree(d,fy)，与节点m相连的链路的另一端n仅仅和集合subtree(d,fy)中的结点相连，n到d的最优路径必定经过节点f。根据上述描述可知，当节点f出现故障时，节点fy∈child(f)对应的子树中的节点将无法到达目的。这与健壮的网络拓扑结构的前提假设相矛盾。因此该原理的后半部分成立。
[0067] 根据上述证明可知，该原理成立。
[0068] 原理2：当网络中的所有节点都部署上述的路由保护算法时，可以保护网络中任意单节点故障。
[0069] 证明：在网路拓扑中，假设节点f出现故障。对于任意的源-目的(s,d)，当源到目的的最优路径经过节点f时，根据原理1可知，子树subtree(d,f)至少存在一个桥，则算法可以保护节点f。由于节点s是节点f的子孙节点，则当节点f断开时，从源节点s发送到目的节点d的报文可以正常到达。
