用于查找网状网络中的受保护路径的方法

摘要

查找网状网络中的主通信路径的方法，它同时是具有完全保证分段节点或节点－链路保护的受保护路径。该方法包括定义所需保护类型并且还根据初始用户要求和网络的拓扑结构信息来选择预期通信路径的每个特定路径段。在确保特定节点路径段N在网络中可由满足初始用户要求的节点备用路径来保护时，选择通信路径的每个特定节点路径段N。如果通信路径的每个特定链路路径段L在网络中可由满足所述初始用户要求的链路备用路径来保护，以及如果段L通到的节点路径段N不能由适当节点备用路径来保护，则选择该特定链路路径段L。

说明书

技术领域

本发明涉及数据网络领域，更具体来说，涉及查找网状通信网络中的受保护路径，以及在具体情况中涉及用于计算具有保证快速重新路由(FRR)保护的MPLS标签交换路径的方法。

背景技术

确定网状通信网络中的受保护路径的问题对于各种类型的网络以及对于这类网络中可应用的各种数据协议是相关的。为了更好地进行说明，将使用多协议标签交换(MPLS)网络的现代示例来提供和分析此问题。

MPLS是一种新兴技术，它改进IP(因特网协议)网络的可缩放性和性能，以及提供先前采用传统IP不可用的新服务。具体来说，MPLS使服务提供商能够策划其网络中的业务，并且提供基于服务质量(QoS)的服务，包括保证容量(带宽，BW)。通过MPLS，源标签交换路由器(LSR)将标签插入从源系统(例如计算机)到达的分组；所有这些标记的分组则沿用到目标LSR的相同标签交换路径(LSP)，目标LSR从分组取出标签，并将其传递给目标系统。

图1示出LSP路径，它在源节点LSR A始发，经过传输节点LSRB，并且在目标节点LSR C结束。因此，由LSR A映射到LSP的所有分组沿用路径A-＞B-＞C。另外还示出，分组在源LSR A处附加有MPLS标签，并且在目标LSR C解除MPLS标签。

主要MPLS特征是称作快速重新路由(FRR)的机制。FRR允许将LSP快速重新路由到网络链路故障或节点故障周围预先配置的备用LSP，其中前一种情况称作FRR链路保护，而后一种情况称作FRR节点保护。当受保护链路或节点出故障时，主LSP的业务切换到分别朝下一跳(NH)LSR或下下一跳(NNH)LSR的备用LSP。备用LSP在NH或NNH与主LSP的原始路径再合并，NH或NNH将业务重定向到主LSP。注意，这个应用假定节点保护备用LSP在NNH与主LSP路径合并，而没有沿LSP路径继续(例如没有在NNNH)。备用LSP可由多个LSP共享。通过FRR，中断业务流可在不到50毫秒的短时间间隔中在出故障节点/链路周围重新路由。

图2示出FRR链路保护。LSP 1(粗线)和LSP 2(细线)通常沿路径A-＞B流动。当LSR A与LSR B之间的链路出故障时，LSR A将LSP1和LSP 2重新路由到通过LSR C流动到LSR B(NH)的备用LSP(虚线)(备用LSP由LSP 1和LSP 2共享，如前面所述，这是可能的)。备用LSP的路径在NH(下一跳)LSR B与LSP 1和LSP 2的原始路径再合并，LSR B将业务又分别重定向回到LSP 1和LSP 2。

图3示出FRR节点保护。设LSP 1(粗线)和LSP 2(细线)通常沿路径A-＞B-＞C流动。当LSR B出故障时，LSR A将LSP 1和LSP 2重新路由到通过LSR D流动到LSR C(NNH)的备用LSP(虚线)。备用LSP的路径在NNH(下下一跳)LSR C与LSP 1和LSP 2的原始路径再合并，LSR C将业务又分别重定向回到LSP 1和LSP 2。

为了使保护有效，主LSP及其备用LSP必须不同地路由(分离)，否则一旦受保护链路或节点出故障，备用LSP将会出故障。使用图2和图3的示例，链路保护备用LSP的路径(例如图2所示的虚线)必须不使用受保护链路(图2中的链路AB)，并且节点保护备用LSP的路径(例如图3的虚线)必须不使用受保护节点(图3中的节点B)，也不使用其链路的任一个。

链路故障的检测可基于那个链路(图2中的链路AB)上所检测的物理通信层(例如SONET/SDH)的告警。节点故障的检测可基于网络或链路通信层(例如分别为OSPF或PPP)的告警。不时地、优选地由于快速检测机制，节点故障可使用出故障节点上游的链路(图3中的链路AB)上的物理通信层告警来检测。在后一种情况下，可向LSP每跳分配链路保护备用LSP或节点保护备用LSP但不是两者都分配，因为不能区分链路故障和节点故障。为了可适用于所有这些故障检测情况，这个应用还将假定可向LSP每跳分配链路保护或节点保护但不是两者都分配。

FRR保护可定义为分段备用方案，因为它基于提供备用LSP以便防止沿主LSP的路径的单段(节点或链路)的故障。因此，为了完全保护LSP，需要多个备用LSP，每个受保护段一个备用LSP。虽然每个受保护段的备用LSP的路径必须与那个段上的主LSP的路径脱离，但是允许它在其它段上与主LSP共享链路或节点，为了共享链路、节点，并且还可与保护主LSP的其它段的备用LSP共享带宽。这种共享可以极大地提高可完全保护LSP的一组备用LSP实际存在的可能性。例如，图2中的备用LSP的路径必须不使用受保护链路AB，但是可使用沿主LSP 1和2的路径的任何其它链路，例如LSP 1和LSP 2通过其中到达LSR A的链路。

MPLS实现中一个重要方面是如何计算满足LSP要求的路径。路径计算可由源LSR或者由路由服务器/网络管理系统来进行。路径查找算法的输入数据包括LSP要求和所谓的业务策划(traffic-engineered)(TE)网络拓扑结构，其中术语“TE”用来指明拓扑结构包括服务质量(QoS)相关信息、如网络段的可用容量。

LSP要求包括源LSR、目标LSR和附加属性，例如LSP带宽(容量)和FRR保护要求；附加要求可以是服务类(CoS)、跳数限制、双向性等。

TE拓扑结构可表示为节点和互连链路的加权有向图，其中各节点和链路与资源(或TE拓扑结构限制)关联。具体来说，将一个LSR的外出端口与另一个LSR的进入端口连接的各链路与权重、又称作量度或成本的可用BW(可选地，按照所需服务类CoS)以及关于可用备用LSP的信息关联。

备用LSP知识可由可以是任何种类的LSR或网络管理系统的路径计算服务器(PCS)保存。然后，源LSR在需要计算FRR保护LSP的路径时向PCS请求备用LSP信息。备选地，源LSR可请求PCS计算FRR保护LSP本身的路径。

路径查找算法的结果是满足LSP要求而没有违反TE拓扑结构限制的最佳可行路径。存在各种优化标准，它们之中最流行的是最短路径，其中希望查找最小总量度可行路径。基于最短路径标准的LSP路径查找通常称作“限制最短路径优先”(CSPF)。CSPF具有两个试探阶段：(1)在第一阶段，删除所有不可行链路(“链路方向”)。对于带宽可用性，这表示不满足LSP的BW要求的任何链路方向必须从TE拓扑结构中排除。(2)在第二阶段，源LSR与目标LSR之间的最短路径使用例如迪杰斯特拉(Dijkstra)算法等标准算法来计算。

图4示出包含采用链路互连的四个LSR(A、B、C、D)的TE拓扑结构，其中各链路方向(箭头)具有预先配置的量度和可用带宽BW。例如，存在具有量度＝5且可用BW＝100、从LSR B到LSR D的链路方向；量度和BW(在括号内)以链路方向附近所示的矩形标签示出。源/目标LSR A和C示为深色框，而传输LSR示为白色框。

假定需要计算从LSR A到LSR C的BW＝200的LSP的路径。

阶段1：删除所有不可行链路，从而产生图5所示的拓扑结构。例如，删除从B到D的链路方向，因为它具有BW＝100＜200。

阶段2：计算最短路径。在这种情况下，从LSR A到LSR C仅剩下两个可能的路径：

(1)路径A-＞C，其中量度等于2。

(2)路径A-＞D-＞C，其中量度为6+3＝9。

注意，经过某个LSR多于一次、由此形成“业务环路”的路径(例如A-＞D-＞A-＞C)被禁止，因而不予考虑。路径A-＞C是最短路径，因此被选取，如图6所示。在这个示例中，最短路径计算非常简单；在一般情况下，使用例如迪杰斯特拉或贝尔曼-福特算法等系统方法。

当要建立的LSP具有FRR保护要求时，路径计算变得更为复杂。这类要求可能需要：(1)链路保护；(2)节点保护(除了路径上应当具有链路保护的最后一个链路方向)；(3)节点-链路保护，其中需要节点或链路保护，以及节点保护(在可用的任何情况下)应当优先于链路保护。

当必须沿LSP路径保证FRR保护时，出现问题。也就是说，必须保护主LSP沿其路径免于任何单段(链路或节点)故障。这种LSP被认为是完全FRR保护主LSP。必须拒绝不满足这个要求的任何路径。

如果预期的保证FRR是链路保护，则没有提供有链路保护的链路方向的简单删除(阶段1)可起作用。例如，如果图4中仅从A到C的链路方向具有链路保护(即，从A到C存在防止链路方向A-＞C的故障的备用LSP)，则删除处理(pruned)的拓扑结构将如图6所示。在这种情况下，对于所需LSP仅存在一个可行路径：A-＞C。

问题在于，当网络用户要求保证FRR节点保护或保证FRR节点-链路保护时，阶段1的简单删除规则有时没有帮助。这种情况会发生，因为受关注LSP路径在路径查找过程的阶段1期间不是已知的。例如，在图7的拓扑结构中，如果LSP路径为A-＞B-＞C，则存在防止节点B的故障的备用(虚线)LSP。但是，如果LSP路径为A-＞B-＞E，则不存在防止节点B的故障的备用LSP；因此，则链路方向A-＞B在LSP路径为A-＞B-＞C是可行的，但在LSP路径为A-＞B-＞E时不可行。由于LSP路径在阶段1是未知的，所以在阶段1删除链路方向A-＞B将是错误的动作，因为受关注LSP路径可能在阶段2选择成使用路径A-＞B-＞C。

分段备用方案的两步方法由Simon Balon等人用于“采用有效带宽共享的可缩放和分散快速重新路由方案(A Scalable andDecentralized Fast-Rerouting Scheme with Efficient Bandwidth Sharing”(2005年12月13日)：它首先使用可用算法之一、如前面所述的二阶段CSPF来计算主LSP路径。对于得到的候选路径，该算法则尝试分配备用LSP。这种方法的缺点在于，它即使当存在这种备用LSP时也无法确保完全FRR保护主LSP。如该论文所述，“当主路径已知时，我们计算防止沿这个路径的任何可能的节点故障所需的备用LSP的集合。如果备用路径在节点故障假设下无法找到，则我们假定只有链路故障将会发生，并且计算新的备用路径。如果再次出故障，则拒绝请求。”

分段备用方案的另一个两步方法由Ranjith等人“用于多跳网络中的可靠实时通信的分布式主分段备用方案”(2002)：它认识到通过非分段备用的分段备用方案(作为FRR保护)的优点，但假定已经选择主路径，并且剩余的全部将计算它的最佳备用路径。但是，如果已经选择主路径，则它可穿过链路和节点而没有可用备用LSP，因此保护无法得到保证。如该论文中所述，“分布式算法必须运行两次，即，第一次查找源与目标之间的最小成本主路径，以及第二次查找这个主路径的一组最小总权重分段备用。”

美国专利公布2003/0229807A1描述一种用于网络的分段保护技术，包括两个步骤：计算最佳(最短)活动路径(AP)，将它分为若干活动段(AS)，然后采用称作备用段或BS的绕行路径来保护各AS。实际上，美国公布2003/0229807描述了已知原理“活动路径优先”(APF)的又一种形式。

由Yu Liu和David Tipper在其论文“节点故障的连续可生存路由选择(Successive Survivable Routing for Node Failures)”中描述一种类似方法，其中在路由和保留预先规划备用路径之前给出工作路径。

另一种已知的方法称作K个最短路径(KSP)方法，其中，算法查找K个最短活动路径(AP)，然后以其成本增加顺序对它们逐个测试，直至找到备用路径或者已经对它们全部进行了测试。由于KSP方法基于有限数量的先验选择AP，即使受保护路径存在，它可能没有找到这种路径。

根据以上所述可以看到，查找网状网络中的保证分段保护路径(比如说MPLS网络中的完全FRR保护主LSP)的任务无法使用上述2阶段路径查找算法的任一个有效地解决。

同时，保证FRR保护对服务提供商极为重要。许多因特网应用、如电子业务和电子商务的本质是为客户提供对因特网的全天候不中断访问的能力。构成因特网的光纤链路或路由/交换节点中的失效或故障可中断因特网服务提供商到其客户的重要链路。在以每秒10千兆位或以上的速度转发分组时，不活动的单独一秒表示数百万字节的宝贵的客户数据被丢弃，并且QoS保证以同样方式进行；更不用说其中这类故障可能具有空难性结果的任务关键应用。

发明内容

因此，本发明的目的是提供一种路径选择方法，它能够查找具有完全保证分段节点或节点-链路保护的网状网络中的最佳通信路径。在特定实际情况中，具体目的是查找网状MPLS网络中具有完全保证FRR节点或节点-链路保护的主LSP。

上述目的可通过提供用于选择网状网络中的源节点与目标节点之间的受保护通信路径的方法来实现，其中，路径的特征在于完全节点保护或完全节点-链路保护，使得在由各包含节点路径段N或链路路径段L的路径段所组成的路径中，采用网络中的备用路径来保护所述路径段的每个，以及

其中各节点路径段N包括节点、进入所述节点的链路以及离开所述节点的链路，而各链路路径段L包括离开一个关联节点并且进入另一个关联节点的单个链路，

该方法包括通过以下步骤来选择所述受保护通信路径作为主路径：

定义作为节点保护或节点-链路保护的所需保护类型，以及

根据网络的初始用户要求和拓扑结构信息进一步选择所述通信路径的各特定路径段，其中各特定路径段的所述选择使用下列规则来执行：

a)在确保所述特定节点路径段N在网络中可由满足所述初始用户要求的节点备用路径来保护时，选择通信路径的所述特定节点路径段N，

b)如果特定链路路径段L在网络中可由满足所述初始用户要求的链路备用路径来保护，则选择通信路径的所述特定链路路径段L，以及

-b1)在节点保护的情况下，如果这个特定链路路径段L通向的节点是主路径的目标(即，是所谓的“最后一跳”)；

-b2)在节点-链路保护要求的情况下，如果这个特定链路路径段L通向的节点路径段N无法按照规则(a)受到保护。

该方法可通过一阶段来执行。但是，当该方法的第一阶段确定具有环路的受保护通信路径(即，路径包括被穿过多于一次的节点)时，则环路可使用发明内容中以及具体实施方式中进一步提到的措施来排除。

优选地，在该方法中，通信路径是标签交换路径(LSP)，网状网络是多协议标签交换(MPLS)网络，以及所述保护是保证快速重新路由(FRR)段保护。

节点保护要求针对沿通信路径的任何单个节点故障的保护-除了接近目标节点的最后一跳之外；由于目标节点无法具有节点保护，所以该跳必须具有链路保护。节点-链路保护要求针对沿通信路径的任何单个节点或链路的故障的保护，但是，节点保护应当优先于(比如说具有可配置优先量度罚值P)链路保护。

可以看到，规则(b2)覆盖保护通信路径的最后一跳(即最后一个链路路径段)以及当要求节点-链路保护时选择通信路径的路径段的方式。

初始用户要求包括至少以下数据：(1)所述源节点(LSR)；(2)所述目标节点(LSR)；(3)服务质量(QoS)要求，包括通信路径(LSP)的所需带宽/容量的至少一个值，它在带宽可为零时包括所谓的“尽力(besteffort)”情况；(4)所需保护(FRR)的所述类型其中之一，保证(完全)节点保护或保证(完全)节点-链路保护。附加(可选)要求可包括例如对于路径所允许的最大量度(长度、成本等)、服务类(CoS)、路径双向性、显式路径限制、无环路限制(即，一个节点不能由受保护通信路径穿过多于一次)等等。

该方法包括使用网络的拓扑结构信息。拓扑结构信息可表示为节点和互连链路的加权有向图，其中各节点和链路与资源和/或拓扑结构限制关联，包括与可用节点备用路径和链路备用路径有关的信息。具体来说，将一个节点(LSR)的外出端口与另一个节点(LSR)的进入端口连接的各链路与权重、又称作量度或成本的可用BW(例如通过线路有效负载速率减去为网络中的现有LSP所保留的带宽来计算)以及链路保护和节点保护的可用备用路径(LSP)关联；附加资源可以是每个服务类(CoS)的可用BW、共享风险链路组(SRLG)等。节点资源的示例是存储LSP的业务参数可用的内部节点存储器。

优选地并且按照背景技术中给出的说明：

用于保护链路路径段的链路备用路径(LSP)与所选通信路径(主LSP)在作为与链路路径段关联的两个节点其中之一的下一跳节点(NH)处合并，而假定用于保护包括进入链路、节点和外出链路的节点路径段的节点备用路径(LSP)与主LSP路径在作为所述外出链路到达的节点的下下一跳节点(NNH)处合并。

为了确保保证段受保护通信路径，在路径查找算法一开始时(参见以下步骤ii)考虑与可用节点备用路径(LSP)和链路备用路径(LSP)有关的拓扑结构信息。

为此，本发明人提出该方法的以下形式：

i.初步删除步骤：删除拓扑结构信息，以便排除来自其中的从带宽观点来看不满足初始用户要求的链路和备用路径(LSP)。在一个一般示例中，这包括对于所需CoS具有不充分带宽的链路以及可能的具有不充分内部资源(例如存储器)的节点。删除处理拓扑结构信息表示为删除处理拓扑结构图。

但是应当注意，删除步骤实际上无需预先应用于所述不可行链路，而仅应用于作为主路径的实际候选的不可行链路。例如，如果主路径按照最短路径标准来选择，以及如果存在量度100的可行(即具有充分带宽)路径1，并且存在其可行性尚未确定的量度200的另一个路径2，则路径2的可行性根本不需要检验，因为路径1由于更短而将始终是优选的。

ii.节点内连接步骤：通过对拓扑结构图添加假想的节点内链路将拓扑结构图(优选地为删除处理拓扑结构图)变换成变换图，其中，如果拓扑结构图中存在绕过所述节点路径段的节点备用路径，则将零量度的假想节点内链路加入节点路径段的节点，以便互连所述节点段的进入链路和外出链路。优选地，节点备用路径在NNH与所选通信路径合并(即，从进入端口的另一链路端的节点延伸到外出端口的另一个链路端的节点)。如果(仅)要求节点保护，则这类零量度节点内链路是充分的。

为了选择具有节点-链路保护的完全保护通信路径，变换图应当包括对删除处理拓扑结构图添加非零量度的其它假想节点内链路的附加操作，其中，如果删除处理图中不存在那个路径段的节点备用路径，而存在那个节点路径段的进入链路的链路备用路径，则将非零量度(或罚值P)的假想节点内链路添加到节点段的节点，以便互连所述节点段的进入链路和外出链路。

iii.变换图还可用于通过应用任何路径计算算法来选择具有完全节点或节点-链路保护的所需通信路径。计算算法可以是例如传统迪杰斯特拉算法。但是，如果受保护路径应当是无环路的，则在步骤iii通过应用所谓的限制迪杰斯特拉算法，可避免环路。备选地但不太优选地，迭代路径计算算法可通过从变换图中得到的通信路径删除形成环路的链路来完成。在那时，路径计算算法再应用于这样的修正图。

以上定义的技术提出这样一种通路查找方法：在给定初始用户要求(例如源/目标、带宽和其它QoS要求以及所需保护的类型)的情况下，包括所述备用(LSP)信息的网络拓扑结构信息能够查找具有保证节点或节点-链路保护(FRR保护)的最佳通信路径(LSP)，前提是这种路径实际存在。

优选地，满足初始用户要求而没有违反拓扑结构限制的所选通信路径也是最小总量度可行路径(所谓的最短路径)。但是，其它优选标准可用于查找所需通信路径，例如最长路径可选择用于检验网络中的最大可能延迟。

附图说明

还将参照以下非限制性附图详细地描述本发明，附图包括：

图1(现有技术)示意示出MPLS网络中的LSP路径。

图2(现有技术)示意示出链路段保护(链路FRR)。

图3(现有技术)示意示出节点段保护(节点FRR)。

图4(现有技术)示出网络拓扑结构的示例。

图5(现有技术)示出从图4所示拓扑结构得到的删除处理网络拓扑结构的示例。

图6(现有技术)示出从图5的删除处理网络拓扑结构所挑选的所选通信路径。

图7示出已知的删除方法不适合于获得保证节点段保护。

图8示出用于选择保证节点保护通信路径的网络拓扑结构的所提出变换的示例。

图9示出用于选择保证节点-链路保护通信路径的网络拓扑结构的所提出变换的示例。

图10示出所提出路径查找算法的简化流程图。

图11示出变换网络拓扑结构的新提出步骤的更详细流程图。

图12示出引入节点内假想链路之前的网络拓扑结构图的另一个示例。

图13示出由图12的图所得到的变换网络拓扑结构图的示例，并且说明使用变换拓扑结构图的所提出方法。

图14示出可如何使用图13的变换拓扑结构图来选择所需最短完全节点保护可行通信路径。

图15示出引入节点内假想链路之前的初始网络拓扑结构图的又一种可能性。

图16示出将适当的节点内连接引入图15的图之后的变换网络拓扑结构图。

图17示出如何在网络中使用图16的变换图来选择最短完全节点-链路保护可行通信路径。

图18示出应用限制迪杰斯特拉算法以便得到无环路FRR通信路径。

具体实施方式

图1至图7已经在背景技术中提到。

在以下详细描述中，一般术语“完全/保证节点或节点-链路保护”可与术语“FRR段保护”、“FRR节点保护”或“FRR节点-链路保护”交替使用，它们特别适合于MPLS网络。相同的方面分别适用于一般术语“节点”、“路径”和特殊术语“LSR”、“LSP”。

图8示出将节点内连接操作引入(即，将假想节点内链路引入)网络拓扑结构图，以便获得从节点(LSR)A到节点B的链路方向的保证FRR节点保护。在这个方向上，节点A具有到节点B端口1的链路，节点B又具有从端口2到节点C端口1的链路以及从端口3到节点D端口1的另一个链路。在那个附图及其它附图中，节点的端口示为编号圆圈，而链路的量度值以适当链路上的小正方形示出。量度能理解为可反映链路的长度、成本、质量等的加权。拓扑结构图还具有在节点A处开始并且在节点C处终止的节点保护备用段(LSP，由虚直线表示)，它提供针对节点B的故障的保护。在节点内连接步骤中(示为初始图与变换图之间的箭头INC)，在节点B中沿从端口1到端口2的方向分配零量度节点内链路，因为存在针对节点B的故障来保护主LSP路径A到B到C的备用LSP。零量度(“无成本”)假想节点内链路标记为“0”。注意，在节点B中没有分配从端口1到端口3的零量度节点内链路，因为不存在针对节点B的故障来保护主LSP路径A到B到D的备用LSP。因此，在所得变换图上选择所需通信路径时，主保护LSP路径可从A通到B到C，但无法从A通到B到D。

节点保护备用LSP A-＞C(由虚直线表示)在附图中仅示意示出；实际上，它可穿过除了节点B及其链路之外的多个中间LSR(按照所谓的“节点备用规则”)，因为链路在其节点B出故障时也会立即出故障。

图9示出将节点内连接引入网络拓扑结构，以便获得从节点(LSR)A到节点(LSR)B的链路方向的保证FRR节点-链路保护。拓扑结构与图8相似，但是确认从节点A到B的链路方向还具有从A到B的链路保护备用LSP(以虚曲线表示)。在引入节点内连接(INC)的步骤中，在节点B中分配从端口1到端口2(如图8中)的零量度节点内链路，因为存在针对B的故障来保护主LSP路径A到B到C的备用LSP。但是，另外，在节点B中分配从端口1到端口3的标记为“P”(罚量度)的非零量度节点内链路，因为如果选择可能的LSP路径A-＞B-＞D，则仍然存在至少针对从A到B的链路方向的故障来保护那个可能的LSP的备用LSP。因此，当受保护主LSP路径被选择时，它将最可能从A通到B到C，但是备选地以较低可能性(由于罚量度P)从A通到B到D。优选地，网络设计人员将设置P＞0，以便对节点段保护分配优先权。

但是，设置P＝0可用于对FRR链路保护分配与FRR节点保护相同的优先权。

示意示出链路保护备用LSP A-＞B路径(虚曲线)。实际上，它可穿过多个中间LSR，但它必须不使用与受保护链路相同的端口(节点A的端口1和节点B的端口1)，因为它们在从A到B的主链路方向出故障时也会立即出故障(“链路备用规则”)。。

图10示出用于选择网状网络中的完全保护通信路径的所提出方法的一个优选实施例的一般流程图。步骤10指明存在a)反映网络链路和节点的各种限制(物理和业务相关)的给定网络拓扑结构图，以及b)对于要在网络中查找的通信通路的初始用户要求。

步骤12是从给定拓扑结构图删除具有不充分资源(即，不满足用户要求)的链路、节点和备用路径(LSP)的步骤。备选地，这个步骤可与步骤16结合执行。

步骤14是将假想节点内连接引入删除处理图的步骤。引入这些假想节点内链路的方式取决于删除处理图中其节点和链路的备用路径的存在。在图11以及在具体实施方式中更详细地进行说明。步骤14导致变换拓扑结构图的获得。

步骤16包括将任何路径查找算法应用于在步骤14所得到的变换拓扑结构图，以便获得在存在时沿其所有段满足保证节点或节点-链路保护要求的主通信路径。在这个示例中，路径查找算法是最短路径算法。但是，算法可具有用于查找主通信路径的其它标准。

步骤18检查是否找到路径，以及如果是，则步骤20包括将特定已知备用路径分配给所选主路径的段，并且为主路径段以及为特定备用路径保留资源。

图11详细说明所提出方法的步骤14。

子步骤14.1涉及所需路径的源节点，并且包括在源节点中引入从路径的虚拟源端口到连接外出方向的所有端口的零量度假想链路，以便允许选择网络中的任何可能方向上的路径。

子步骤14.2在目标节点中执行相似操作，以便允许从网络中的任何可能方向到达目标。目标节点的虚拟端口通过来自任何进入端口的零量度假想链路来连接。

子步骤14.3和14.5描述在这种图中如何变换删除处理图，它将允许从其中仅选择在网络中具有保证保护的段。

子步骤14.3允许在删除处理图中将零量度假想链路引入具有节点备用路径的节点。这种零量度链路是受保护节点段的进入链路与外出链路之间的节点内“捷径”，表明值得为通信路径选择该节点段。

但是，“仅节点保护”有时在网络中无法实现。如果根据用户要求允许混合节点-链路保护(步骤14.4)，则步骤14.5提供将附加假想链路引入网络节点。这些链路预计是“更昂贵的”(非零量度)，以便对零量度赋予优先权。这些节点内非零量度假想链路在其进入链路具有链路备用路径、但不存在从那个链路到下下一跳(NNH)NNH的节点备用路径时被插入节点。非零节点内链路插入两个端口之间，一个端口与受保护进入链路连接，而另一个端口与通向NNH的外出链路连接。换言之，如果从链路到NNH的节点保护不可用，但链路保护可用且被允许，则这个链路仍然可使用，但具有较低优先权。

图12示出包括按如下方式互连并且相互形成以下备用路径的节点(LSR)A、B、C和Z的示例网络拓扑结构图：

(1)双向链路AB(从A到B的量度1以及从B到A的量度9)、BZ、BC、AC、CZ

(2)节点保护备用LSP(虚线)：A-＞B(标记为N1并且防止C的故障)、A-＞C(N2，B)、B-＞Z(N3，C)、C-＞Z(N4，B)

(3)链路保护备用LSP C-＞Z(标记为虚线L1并且防止从C到Z的链路方向的故障)。

需要查找从A到Z的主LSP路径，所需LSP必须具有保证FRR节点保护(完全节点段保护)。

我们要记住：

a)由于主LSP的最后一跳根本不能是节点保护(因为如果节点Z出故障，则LSP也出故障)，所以在本申请中将始终假定最后一跳应当具有保证链路保护。

b)假定所有链路和备用LSP属于删除处理拓扑结构图(如上所述的初步删除步骤)，即，它们全部具有满足所需LSP带宽的可用带宽；

c)源(目标)LSR包含标记为“S”(“D”)的LSP源(目标)点，它们的每个分别是标记主LSP的起点(结束)的虚拟端口。

d)假定所有备用LSP均服从先前定义的节点备用规则和链路备用规则。

在这个简单示例中可看到，存在4个可能的LSP路径(其中各节点在路径中仅出现一次，以便避免无穷环路)：A-＞B-＞C-＞Z、A-＞B-＞Z、A-＞C-＞B-＞Z、A-＞C-＞Z，其中只有第一个因在所有跳上具有节点保护(在B故障的情况下的N2，在C故障的情况下的N3)以及在最后一跳上具有链路保护(在链路方向C到Z出故障的情况下的L1)而是可行的。

但是，在大网络中，该过程需要相当复杂的计算，因此应当基于系统方法。本发明人提出的路径查找过程包括引入节点内连接(假想链路)的步骤。图13示出如何帮助系统地查找可行LSP路径。

图13示出完成节点内连接步骤之后的删除处理拓扑结构。仅保留以下节点内连接：

(1)从“S”(源)到所有外出链路方向(到标记为O1、O2的输出端口1和2)的零量度的假想链路

(2)从任何进入链路方向(具有链路保护备用LSP)到目标“D”的零量度的假想链路。例如，它是节点Z的输入端口2(I2)到“D”(由于图12的备用LSP L1)。

(3)删除处理图中节点具有保护备用路径时的节点中的零量度的假想链路。这包括节点B的端口3到2(由于备用LSP N2)、节点B的端口2到1(N4)、节点C的端口3到2(N1)、节点C的端口2到1(N3)-参见图12。

图14示出在删除处理拓扑结构上运行标准最短路径算法(如迪杰斯特拉算法)之后的所选主LSP路径。所选路径是粗线A-＞B-＞C-＞Z，量度1+1+4＝6，当B或C出故障时具有节点保护，而当最后一跳C到Z出故障时具有链路保护。在这个简单示例中可看到，从A到Z不存在其它可行路径。例如，从节点Z的端口1到“D”不存在节点内假想链路，因此不能允许LSP经由链路方向B到Z通过。

图15示出包含按如下方式互连的节点(LSR)A、B、C和Z的示例网络拓扑结构：(1)如图12中的双向链路，(2)节点保护备用LSP：C-＞Z(标记为N1并且防止B的故障)、A-＞C(N2，B)、B-＞Z(N3，C)，(3)链路保护备用LSP C-＞Z(标记为L1并且防止从C到Z的链路方向的故障)、A-＞B(L2)、B-＞Z(L3)。需要查找从A到Z的主LSP路径，其中这个主LSP必须具有保证FRR链路-节点保护。在这个简单示例中可看到，存在如图12中的4个可能的LSP路径(A-＞B-＞C-＞Z；A-＞B-＞Z；A-＞C-＞B-＞Z；A-＞C-＞Z)，其中只有两个是可行的：(1)A-＞B-＞C-＞Z，由于在所有跳上具有节点或链路保护(B故障的情况下的N2，C故障的情况下的N3，C到Z故障的情况下的L1)，(2)A-＞B-＞Z，由于在所有跳上具有节点或链路保护(A到B故障的情况下的L2，B到Z故障的情况下的L3)。

以下路径查找过程将说明如何系统地查找这两个可行路径并选择最短路径。

图16示出完成节点内连接步骤之后的删除处理拓扑结构。仅保留以下节点内连接：(1)从“S”到所有外出链路方向的零量度的链路方向，(始终对于源节点进行)；(2)从具有链路保护备用LSP的任何进入链路方向到“D”(目标节点)的零量度的链路方向。这包括Z的端口2到“D”(由于备用LSP L1)以及Z的端口1到“D”(L3)；(3)从具有节点保护备用LSP的任何进入链路方向到转到备用LSP的NNH的外出链路方向的零量度的链路方向。这包括节点B的端口3到2(由于备用LSP N2)、节点B的端口2到1(N1)、节点C的端口2到1(N3)；(4)从具有链路保护备用LSP的任何进入链路方向到任何不匹配外出链路方向的预定义非零量度罚值P(这个示例中使用P＝99)的链路方向。这包括节点B的端口3到1(由于备用LSP L2)。

图17示出在删除处理拓扑结构上运行标准最短路径算法、如迪杰斯特拉算法之后的所选主LSP路径。在这个简单示例中可以只看到，能找到两个可行路径：(1)A-＞B-＞C-＞Z，量度为1+1+4＝6；(2)A-＞B-＞Z，量度为1+99+1＝101。路径A-＞B-＞C-＞Z是“较短的”，因此被选取。这个路径具有针对B或C的故障的节点保护以及针对最后一跳C到Z的故障的链路保护。注意，虽然路径A-＞B-＞Z在链路量度(1+1＝2)中较短，但是在节点B的99的节点内量度罚值极大增加它的总量度，并且它最终未被选取。因此，节点内罚值为可用时(A-＞B-＞C-＞Z是完全节点保护)的节点保护被赋予优先于链路保护(A-＞B-＞Z是完全链路保护)的预定义优先权。

图18帮助说明确定所示网络中的无环路FRR保证路径的示例。

设所示网络实际上表示其变换图。

我们将限制迪杰斯特拉算法应用于变换图。例如由Timothy Y.Chow、Fabian Chudak和Anthony Ffrench在其论文“使用预交叉连接轨迹的快速光层网状保护(Fast Optical Layer Mesh Protection usingPre-Cross-Connected Trails)”第7节中描述了限制迪杰斯特拉算法。

限制迪杰斯特拉与具有源节点(A)的有向图配合工作，其中链路的每个具有非负权重。

限制迪杰斯特拉在图中寻找从源节点A到特定节点的最短可容许路径。路径在无环路时是可容许的。如传统迪杰斯特拉算法中那样，在限制算法的各步骤，将特定节点指定为活动节点，并且把从源节点A到那个特定节点的部分路径之一指定为活动部分路径。部分路径一次由一个节点在当前活动节点处扩展。与传统迪杰斯特拉算法相似，限制迪杰斯特拉以树形数据结构来保存部分路径，使得它可在需要时快速查找最短部分路径。

限制迪杰斯特拉的主要方法如下所述：我们从当前活动节点“向前探测”。假定C是活动节点，以及ABC是活动部分路径。我们考虑从节点C外出的各链路。如果链路转到已经包含在活动部分路径中的节点，则它被禁止。我们忽略已禁止链路，并且继续考虑其它外出链路。

我们在所示变换图中查找从A到D的最短无环路FRR保证路径。

注意，我们忽略无环路限制，从A到D的最短路径可确定为：A→B→C→B→D。但是，如果无环路限制有效，则这个路径不是可容许的，因为它两次包含B，即形成环路。

A最初是活动节点。如果我们(借助于限制迪杰斯特拉)向前探测，则存在一个可能的路径-A→B→C。那个路径成为当前活动部分路径，以及节点C成为当前活动节点。

然后，我们进行探测以便从C前进。我们不能经由链路CB移动到B，因为B当已经包含在活动部分路径A→B→C时被禁止。向前探测到E是顺利的，以及我们对数据库添加新的当前部分路径A→B→C→E；当前活动节点这时是节点E。所述部分路径A→B→C→E实际上成为新的活动部分路径，因为没有其它可容许路径可用。

从当前活动节点E，我们向前探测到F。以这种方式继续进行，我们发现，所得最短可容许路径是A→B→C→E→F→G→D。

应当理解，所提出方法的其它形式可被建议用于各种网状网络并且利用所提出限制和标准的变化。每当由以下权利要求书对本发明的一般定义所包含时，这类形式应当被认为是本发明的一部分。