一种mesh 网非全度完全非相关双树遍历保护方法

摘要

一种mesh网非全度完全非相关双树遍历保护方法，首先提出了建立“非全度完全非相关”双树所需要的网络拓扑条件，通过选择节点度数最大的节点作为根节点，以时延为代价，采用广度优先生成树算法计算出两棵保护树。当工作路径中的链路或节点(非源节点，目的节点和根节点)发生故障时，对于链路故障可以实施通道保护和链路保护倒换，对于节点故障也可以实施通道保护倒换和相应节点保护倒换两种机制。该机制不仅能够提供较短的保护倒换时间，利用mesh网络可以提供较高资源利用率，而且还能够避免复杂的配置和倒换动作。

说明书

技术领域

本发明属于通信网络领域，尤其涉及一种mesh网络中的双树遍历保护倒换方法。 

背景技术

随着时代的变迁，科技的进步，网络技术和信息技术得到了前所未有的发展，网络的应用越来越普及，已经渗透到社会的各个领域，深刻影响和改变着人们的工作和生活方式。同时，随着用户需求的不断增加，各种新型业务层出不穷，使得传统的网络拓扑结构已经无法实现用户的新需求，于是mesh网络凭借其自身的优势，渐渐得到了人们的重视，并且在骨干网中起到越来越大的作用。由于mesh网络自身所具有的一些新的特征，对生存性又有着更高的要求。因此为了在网络出现故障时能够快速恢复业务传输，使用户的损失降到最小，从而提高网络生存性，进一步提升运营商的服务质量，提高用户的满意度，就需要提出适应于mesh网络故障恢复的有效的保护机制。 

对于mesh网络的故障保护机制，目前的研究方法主要是以已有的光网络中的恢复机制为基础，来实现相应的mesh网络故障保护。然而，这些机制在实现复杂度、主备倒换时间和资源利用率等方面都各自存在着一定的局限性。mesh网络现有的故障保护机制主要基于以下三种方式：重路由、P-圈保护和基于生成树保护。此三种故障恢复机制也都存在着各自的不足：a.重路由的方式尽管在资源利用率和故障链路或者故障节点保护率方面，具有很好的优势，但是却不能保证较短的故障切换时间，所以只有对故障不敏感的业务恢复过程中才会采用重路由的方式。b.P-圈方式可以提供较高的资源利用率和很高的保护率， 但是在跨区切换的时候，会消耗计算时间，切换时间并不能保证非常短。c.基于生成树的方式可以概括为工作路径(工作树)和保护路径(保护树)的建立方式上，传统的生成树算法在网络业务出现前，就配置了网络的工作路径，这样就造成了资源的浪费，从而降低了资源利用率。而且在此保护方式中，一般只有一棵保护树来提供保护路径，就会存在保护路径出现故障或者被占用的时，无法实现100％的保护的问题。 

发明内容

鉴于以上mesh网络故障恢复机制所存在的不足，本发明的主要目的在于提出一种“非全度完全非相关”双树遍历保护方法。该机制利用mesh网络提供较高资源利用率的优点，采用根节点发送保护倒换使能信息执行倒换动作，并且提出的建立保护树的算法时间复杂度为O(n2)，从而保证本发明的操作简单易行。通过建立两棵保护树，覆盖网络中的所有节点，可以很好的提高网络生存性，而且以“非全度非相关”特征为目标，使得所建立的这两个保护树为链路不相交的。正因为这两棵保护树中的链路是非相关的，因此在故障发生时可以保证相应的故障节点/链路的保护通道不会同时失效，也就是说在一条保护路径发生故障的情况下，可以无故障的启动第二条保护路径，因而可以提高网络故障恢复率。在故障恢复过程中，一般来说，局部保护恢复策略所需时间较短，而本发明中根据不同业务的需求，可以采取源节点启动通道保护倒换的全局保护倒换机制，也可以采取故障链路(节点)端点(上游节点)启动局部保护倒换，因而在故障恢复时间方面也具有一定的优越性。 

为了达到上述目的，本发明的一种mesh网非全度完全非相关双树遍历保护方法，具体包括以下步骤： 

1)建立非全度完全非相关保护树，其中，保护树是遍历网络产生的树形结构； “非全度”是指在建立保护树的过程中，与某个节点相连的所有链路不会出现在同一个树中；“完全非相关”指的是所建立的两棵保护树中没有重叠链路； 

2)当工作路径中的某条链路或节点发生故障时，根据建立的保护树，对于链路故障，由源节点和目的节点、或故障链路的两个端节点分别向保护树的根节点发送故障通知；对于节点故障，由源节点和目的节点、或故障节点的上游节点向根节点发送故障通知； 

3)当所建立的保护树的根节点收到故障通知后，启动保护倒换机制，向发送故障通知的源节点发送保护倒换使能信息，沿着保护树，配置保护倒换信令，建立保护路径。 

优先地，所述的建立“非全度完全非相关”保护树，要求mesh网网络拓扑中节点的平均度数 其中n为mesh网网络拓扑中节点数。 

优先地，所述的建立“非全度完全非相关”保护树，根据网络拓扑结构，选择节点度数最大的两个节点为根节点，应用广度遍历方法，以链路时延最小为约束，建立完全不相交的两个树。 

优先地，所述的保护倒换机制是根据mesh网络拓扑建立“非全度完全非相关”保护树后，如果工作路径中的某条链路或节点发生故障，对于链路故障，由源节点和目的节点、或故障链路的两个端节点向保护树的根节点发送故障通知；对于节点故障，由源节点和目的节点、故障节点的上游节点向保护树的根节点发送故障通知。 

优先地，保护树的根节点收到故障消息后，就启动保护倒换机制；对于链路故障，根节点向源节点和目的节点、或故障链路的端节点发送保护倒换使能信息，提供通道、或链路保护倒换；对于节点故障，根节点向源节点和目的节点、或故障节点的上游节点发送保护到后使能信息，提供通道或节点保护倒换。 

在mesh网络拓扑中建立两棵“非全度完全非相关”保护树可以提供mesh网络的通道保护和链路保护，为链路故障提供100％保护，并且对一些特定的节点故障具有节点保护倒换的能力。 

本发明的具体内容还包括： 

在网络系统初始化的时候，网络系统管理员需要根据mesh网络拓扑的结构建立两棵“非全度完全非相关”的保护树，每个保护树中的节点不是全度遍历的，即保护树中不会出现所有相邻边都属于该生成树的节点，这样做是为了防止出现割集的情况。在建立保护树时，选取度数最大的节点作为根节点，根据时延最小选择遍历链路，实现图的广度遍历，建立保护树。建立两棵保护树时，要使它们的深度尽量的小，这样可以使故障链路端点或者源节点和目的节点发送的故障通知消息回溯到根节点的平均延迟做到最小，同时还要使两个树的深度尽量的接近，这样可以保证根节点收到故障链路端点或者源节点和目的节点发送消息的平均时间差达到最小。通过这几个手段，可以使网络中出现故障后，以最短的时间对故障做出保护。 

所述非全度是指本保护树生成算法对于网络中的节点的度数具有一定的限制。下面给出此限制的具体理论推导： 

设第一条保护路径为T¹，第二条保护路径是T²，即 n为mesh网络拓扑中节点的个数， 为网络节点的平均度数，由以下推导过程： 

T¹和T²的边的个数分别为n-1，由此可以得到两棵树的完全不相交的边的个数总和为2n-2，而网络中所有的边的个数为 根据图论基本理论可以得到， 从而可以推出网络拓扑节点的平均度数 这就是本方案对格状网络节点平均度数的要求。 

所述非相关是保证所建立的两棵保护树没有公共的链路，这主要是按如下方式来做的：选择一个节点度数最大的节点为根节点，以时延最小为目标，采用广度优先生成树算法遍历网络中的节点，当网络中的所有节点都得到遍历时，就建立了第一棵保护树，此时在网络拓扑图中删除此保护树所包含的所有链路，得到新的网络拓扑图，在新的网络拓扑中继续使用生成保护树的方法，建立第二棵保护树。 

所述选择度数最大的两个节点分别作为两棵保护树的根节点，应用图的广度遍历方法，以时延最小为约束建立保护树，确保保护树中任意一个节点到根节点的平均跳数或平均时延最小； 

所述分别建立两棵保护树，首先以节点度数次最大节点为根节点建立第一棵保护树，当第一棵保护树建立成功后删除该保护树所包含的链路，从而获得一个不包含第一棵保护树中所有链路的新网络拓扑，在新拓扑中选择节点度数最大的节点为根节点，以时延最小为约束建立第二棵保护树； 

所述mesh网络拓扑中所有链路都是双向的，因此，在本发明中所提到的通道保护倒换机制和链路保护倒换机制在启动时，根据链路传输方向的不同，源节点和目的节点的选择也不同，能够应对双向链路的故障。 

当网络中的工作路径发生链路故障时，有三种发送故障消息到保护树根节点的方式。由工作路径的源和目的节点分别沿着不同的保护树路径发送故障消息到相应的根节点；由故障链路的两个端节点分别沿着两棵不同的保护树路径向相应的根节点发送故障消息；当工作路径中的某个节点发生故障，则由故障节点的上游节点沿着保护树的路径发送故障消息到根节点。 

所述工作路径的源和目的节点(分别记作SourceNode，DestNode)分别沿着各自所在的保护树路径进行故障消息的发送，故障消息会逐级发送到保护树 的根节点。 

所述故障链路的两个端节点(分别记作FaultLinkNode_up，FaultLinkNode_down)分别沿着不同的保护树路径发送故障消息，网络中的每个节点都知道自己在保护树结构中的父节点，因此FaultLinkNode_up和FaultLinkNode_down分别向自己的父节点转发故障消息，这样故障消息就可以逐级发送到保护树的根节点，同时由于两棵树不存在共享链路，因此在故障消息发送的过程中，这两个故障消息不会发生冲突，保证了较低的传输时延。 

所述工作路径中的某个节点发生故障(记作FaultNode)，由FaultNode的上游节点(FaultNode_up)向自己所在的保护树结构中的上游节点发送故障消息，这样故障消息会逐级发送到保护树的根节点。 

所述故障消息的传输，在本发明中其传输效率非常高，常用的故障消息传输时采用洪泛传送或者局部洪泛传送，而本算法的故障消息传输目的性非常明确，同时故障通知消息中主要包含故障节点或链路的标识信息，因此可以有效降低网络的负载，减少由此引起的链路拥塞。 

保护树的根节点接收到源节点(SourceNode)和目的节点(DestNode)(故障链路两端点(FaultLinkNode_up，FaultLinkNode_down)/故障节点的上游节点(FaultNode_up))发送的故障消息后，启动通道保护倒换机制(链路保护倒换机制/节点保护倒换机制)，向源节点(故障链路上游节点/故障节点上游节点)发送保护倒换使能信息，由SourceNode(FaultLinkNode_up/FaultNode_up)根据保护倒换使能消息和自己所在的保护树结构，倒换业务到相应的保护路径中。 

所述的保护树的根节点接收到SourceNode和DestNode发送的故障消息后，由此根节点启动通道保护倒换机制。由于在本发明中建立了两棵保护树，因此就会存在两个不同的根节点，那么当源节点和目的节点位于不同的树中时，就 会出现SourceNode和DestNode分别发送的故障消息到达不同保护树的根节点的情况，同时也会存在其中某个节点在两棵保护树中都处于叶子节点位置的情况，那么此节点就会向自己所在的两棵保护树的父节点都发送故障消息。对于以上两种情况，就存在哪个根节点来启动通道保护机制，也就是发送相应的保护倒换使能消息到源节点的问题，在本发明中解决这个问题的原则是由不包含故障链路的保护树的根节点发送保护倒换是能消息到SourceNode，促使其根据使用该保护树中的路径作为保护通道传输业务。 

所述故障链路的上下游节点发送故障通知到达保护树的根节点，由根节点启动链路保护机制。在这里仍然存在故障通知会沿着不同的保护树到达两个不同的根节点，到底由那个根节点实施保护倒换机制，发送相应的保护倒换使能消息到达FaultLinkNode_up的问题，在此采用相同的原则，即由不包含故障链路的保护树的根节点来实施。当FaultLinkNode_up收到根节点的保护倒换使能消息后，就可以根据此根节点所在的保护树中的保护路径实施链路保护倒换机制。 

所述的工作路径中的故障节点(非SourceNode、DestNode和两棵保护树的根节点)发送故障消息到达保护树的根节点，由此根节点启动节点保护倒换机制。这里FaultNode会沿着两棵保护树发送故障消息到各自的根节点，在此选择根节点启动保护倒换机制的原则是：选择不包含故障节点与其上游节点之间链路的保护树的根节点来启动保护倒换机制，并发送保护倒换使能消息到FaultNode_up，由FaultNode_up根据此根节点所在的保护树中的保护路径实施节点故障保护倒换机制。 

所述的保护倒换使能消息，主要是通知相应的节点(SourceNode，FaultLinkNode_up，FaultNode_up)根据哪棵树中的保护路径实施保护倒换功能，因此对网络的传输负荷影响很小。 

附图说明

图1为“非全度完全非相关”保护树建立流程图。 

图2为能够详细描述本发明的原理所采用的mesh网络拓扑。 

图3为所建立的第一棵“非全度完全非相关”保护树。 

图4为建立的第二棵“非全度完全非相关”保护树。 

图5为建立“非全度完全非相关”保护树后的网络拓扑。 

图6为本发明中的保护倒换流程图。 

图7为通道保护倒换机制示意图。 

图8为链路保护倒换机制示意图。 

图9为特殊路径1-2-4的链路发生故障后的通道保护倒换示意图。 

图10为工作路径中的节点(非源和目的节点，以及保护树的根节点)发生故障后的保护倒换。 

具体实施方式

为使本发明的目的、技术方案、以及优点更加清楚明白，下面结合附图和具体实施例子对本发明进一步地详细阐述。 

图1为“非全度完全非相关”保护树建立流程图，本发明首先需要建立两棵满足“非全度完全非相关”条件的保护树，建立保护树的算法如下： 

Step 1：选择节点度数次最大的节点为根节点； 

Step 2：选择时延最小链路遍历节点的相邻节点； 

Step 3：被遍历节点的度数是否满度； 

Step 4：如果被遍历节点满度，则不能选择该链路，选择该节点的子节点遍历相邻节点；如果被遍历节点不满度，转Step 2； 

Step 5：网络拓扑中的节点是否都被遍历； 

Step 6：如果节点被全部遍历，第一棵保护树建立成功；否则转Step 2； 

Step 7：删除第一棵保护树所包含的链路，得到新的网络拓扑； 

Step 8：在新的网络拓扑中选择节点度数最大的节点为根节点； 

Step 9：在新的网络拓扑中应用广度遍历方法，选择时延最短链路遍历网络中的节点，建立第二棵保护树； 

Step 10：在两棵保护树中针对任意两个节点分别建立连通路径。 

在建立保护树的过程中选择节点度数次最大的节点作为第一棵树的根节点，选择节点度数最大的节点作为第二棵树的根节点，是因为在第一棵保护树占用了延迟较好链路的前提下，可以保证两棵树的深度尽量的接近。 

图2是为了详细说明本发明的思想所使用的mesh网络拓扑图，其中圆圈表示节点，节点之间的连线表示链路。该mesh网络拓扑，包含8个节点、14条链路，其中节点集合和链路集合分别为： 

NodeSet＝{1，2，3，4，5，6，7，8}； 

LinkSet＝{1-2，2-3，3-4，4-5，5-6，6-1，2-7，7-6，6-8，3，5，7-5，2-4，3-7，3-8}，所有链路都是双向链路，每条链路具有确定的时延，如链路1-2的时延为12ms。 

图3为建立的第一棵“非全度完全非相关”保护树，其中节点2为根节点。具体的建立过程如下：首先选择节点度数次最大的节点为根节点，在图2中，选择节点2为根节点，以时延最小为约束条件，应用广度遍历方法建立第一棵“非全度完全非相关”保护树，在建立保护树时，确保与一个节点相连的所有链路不能同时出现在同一棵保护树中。 

选定节点2为根节点后，根据时延最小约束，以及与一个节点相连的所有链路不能同时出现在同一个保护树中的要求，选择节点1、3、7为节点2的子节点；再选择节点4、8为节点3的子节点，节点6、5为节点7的子节点，实 现树的广度遍历，建立第一棵“非全度完全非相关”保护树，如图3所示，在此树中每个节点到根节点的平均时延约为37ms。 

图4为建立第二棵“非全度完全非相关”保护树，其中节点5为根节点。其具体的实现过程是：在第一棵“非全度完全非相关”保护树建立成功后，删除第一棵保护树遍历的所有链路，得到一个新的网络拓扑图，在新的拓扑图中选择节点度数最大的节点为根节点。在图2所示mesh网拓扑中选择节点5为第二棵保护树的根节点，以时延最小为约束，考虑与一个节点相连的所有链路不能同时出现在同一个保护树中的条件，建立与第一棵保护树完全非相关的非全度保护树。 

在图2所示网络拓扑中删除第一棵保护树后的网络拓扑中，选择节点5为根节点，节点4、6、3为节点5的子节点，节点2为节点4的子节点，节点1、8为节点6的子节点，节点7为节点3的子节点，建立第二棵“非全度”保护树，且此两棵保护树完全非相关，第二棵保护树中每个节点到根节点的平均时延约为48ms。 

图5为根据保护树建立流程所建立的两棵“非全度完全非相关”保护树后的网络拓扑，粗黑体链路为第一棵保护树中的链路，细黑体链路是第二棵保护树中的链路，节点2和节点5分别是第一棵保护树和第二棵保护树的根节点，从图中可以看出，这两棵保护树的链路完全非相关。 

图6为根据所建立的“非全度完全非相关”保护树所进行的保护倒换流程图。根据mesh网络拓扑建立“非全度完全非相关”保护树后，如果工作路径中的某条链路发生故障，由保护树的根节点启动保护倒换机制，传输保护倒换使能信息到相应的节点，实现通道/链路(节点)保护倒换。保护倒换机制的流程如下： 

Step 1：网络中发生链路故障后，源节点和目的节点(故障链路两端点，故障节点的上游节点)分别沿两棵保护树向根节点发送故障信息； 

Step 2：根节点收到源节点和目的节点(故障链路两端点，故障节点的上游节点)发送的故障消息后，启动通道保护倒换机制(链路保护倒换机制)，发生保护倒换使能信息到源节点(故障链路上游节点，故障节点的上游节点)； 

Step 3：源节点(故障链路上游节点，故障节点的上游节点)接收到保护倒换使能信息； 

Step 4：保效计时器是否失效； 

Step 5：如果保效计时器失效，启动保效计时器，转Step 6；否则转Step 7； 

Step 6：源节点(故障链路上游节点，故障节点上游节点)沿发送保护倒换使能信息的根节点所在保护树建立保护路径，完成保护倒换动作；

Step 7：不启动保护倒换动作。 

当mesh网络中发生链路故障后，由源节点和目的节点分别沿两棵保护树向根节点发送故障通知，根节点接收到源节点和目的节点发送的故障通知后启动通道保护倒换机制；由故障链路的两个端点分别沿两棵保护树向根节点发送故障消息，根节点接收到故障链路两个端点发送的故障消息后启动链路保护倒换机制；由故障节点的上游节点向根节点发送故障消息，根节点接收到故障消息后，启动节点保护倒换机制，向故障消息的源节点(故障节点的上游节点)发送保护倒换使能消息。 

图7为通道保护倒换机制，该情形下的故障通知由SourceNode和DestNode分别发送到保护树的根节点，其中粗体链路构成的路径为工作路径，细体链路构成的路径为保护路径，带箭头细线指示的为信令方向，叉表示链路发生故障。在图7中，根据图2所示网络拓扑，在建立了“非全度完全非相关”的两棵保护树的网络拓扑后，建立工作路径1-2-3-4，当工作链路3-4发生故障后，源节点1和目的节点4分别在两棵保护树上向根节点发送故障通知，第一棵保护树的根 节点2只收到源节点1发送的故障通知，第二棵保护树的根节点5收到源节点1和目的节点4发送的故障通知，由节点5启动通道保护倒换机制，沿第二棵保护树建立从节点1到节点4的保护通道1-6-5-4，向源节点发送保护倒换使能信息，源节点1启动信息保效计时器，在计时器失效之前，源节点忽略接收到的保护倒换使能信息。 

从故障成功检测到业务恢复所经历的时间历程为： 

链路3-4发生故障后，由网络选定的故障诊断机制来判断出故障的发生，并对此故障进行定位，由于链路3-4出现故障，3就把由1发来的数据包和消息数据返回到1，这时，节点1和4便知道了链路3-4发生了故障，然后就开始沿着各自所在的保护树向根节点2和5发送故障通知，根节点先收到节点4发来的故障通知，然后才收到节点1发来的故障通知。这时只有节点5收到了1和4发来的两个故障通知时，才启动保护倒换机制，节点1于是沿着以5为根节点建立的保护树向节点4发送数据包。设从故障发生到节点1得知故障发生所用的时间为T_1-kn；从节点1发送故障消息到根节点2和5的时间分别为T_1-2和T_1-5，从节点4发送故障通知到根节点2和5的时间为T_4-2和T_4-5，则根节点2收到所有故障通知的时间为T_2-f＝max{T_1-2，T_4-2}，根节点5收到所有故障通知的时间为T_5-f＝max{T_1-5，T_4-5}，而根节点2和5反馈回1的时间是T_5-1和T_2-1，当节点1收到消息后，就可以按照规则沿着保护树发送数据包了。在图7中，所用的时间为{12+15+(17+27)×3+22}＝181ms。 

图8为链路保护倒换机制。当工作路径1-2-3-4中的链路3-4发生故障后，由故障链路3-4的端点3和4分别沿保护树向根节点发送故障通知，启动链路保护倒换机制。第一棵保护树的根节点2只收到节点3发送的故障通知，第二棵保护树的根节点5收到节点3和节点4发送的故障通知，由第二棵保护树启动 保护倒换机制，将链路3-4上的业务倒换到路径3-5-4上，向节点3发送保护倒换使能信息，完成保护倒换。同时节点2启动信息保效计时器，在计时器失效前，节点3忽略接收到的保护倒换使能信息。 

从故障成功检测到业务恢复所经历的时间历程为： 

链路3-4发生故障后，由网络中特定的故障诊断机制来诊断出故障的发生，并对此故障进行定位，采用链路保护机制。节点3和4分别向根节点2和根节点5发送故障消息，根节点2收到了节点3发来的消息，而根节点5收到了节点3和4发来的消息，这样根节点5启动保护倒换机制，于是节点1沿着以5为根节点建立的保护树向节点4发送数据包。设从节点3发送故障消息到根节点2和5的时间分别为T_3-2和T_3-5，从节点4发送故障消息到根节点2和5的时间为T_4-2和T_4-5，则根节点2收到所有故障消息的时间为T_2-f＝max{T_3-2，T_3-5}，根节点5收到所有故障消息的时间为T_5-f＝max{T_4-2，T_4-5}，而根节点2和5反馈回1的时间是T_2-1和T_5-1，当节点1收到消息后，就可以按照规则沿着保护树发送数据包了。所用的时间为{41+(17+27)×2+22}＝151ms。 

图9为特殊路径中的链路发生故障后的通道保护倒换机制。如果建立工作路径为1-2-4，该工作路径中的链路2-4发生故障，源节点1和4分别在两棵保护树上向根节点2和5发送故障通知，当根节点2接收到源节点1和目的节点4的故障通知后，给源节点1发送保护倒换使能信息，根节点5也接收到源节点1和目的节点4的故障通知，给源节点1发送保护倒换使能信息，当源节点1收到根节点2发送的保护倒换使能信息后，沿第一棵保护树完成保护切换，同时启动信息保效计时器，在计时器失效前，源节点1接收到根节点5发送的保护倒换使能信息后不启动保护倒换动作。 

图10为节点发生故障后的保护倒换机制。在图10中假设建立的工作路径 为1-2-7-6-5-4，在该工作路径中的节点6发生了故障，其上游节点7沿着两棵保护树的路径分别向根节点2和5发送故障消息，根节点2接收到节点7发送的故障消息后，通过检索自己的拓扑结构，发现在节点7与故障节点6之间的链路7-6属于自己的分支，则不发生保护倒换使能消息。而根节点5在收到节点7的故障消息后，通过检索自己的树状结构，发现链路7-6并不在自己的分支中，则向节点7发送保护倒换使能消息，促使节点7将业务沿着以节点5为根节点的保护树中的路径7-3-5-4进行传输。这里强调的是保护倒换使能消息要回朔到发送故障消息的节点，由此节点开始进行业务的绕行，从而达到保护，强调的是一种局部保护的机制。而对于节点故障也可以使用通道保护来达到业务的恢复。