用于在数据通信网络中构造绕过不可用组件的修复路径的方法和装置

摘要

公开了一种在数据通信网络中构造绕过不可用组件的修复路径的方法，该数据通信网络具有作为组件的具有网络地址的节点和其间的链路，该方法包括以下步骤：在参与节点处执行从网络中的通知节点接收标识通知节点和通过其可以到达通知节点的组件的通知。该方法还包括以下步骤：从通知中导出网络修复地址，该网络修复地址用在在通知中标识的组件不可用的情况下。该方法还包括以下步骤：构造针对修复地址的修复路径。

说明书

技术领域

本发明一般地涉及数据通信网络。更具体而言，本发明涉及在数据通信网络中构造绕过不可用组件的修复路径。

背景技术

这一部分中描述的方法可以实现，但是不一定是先前已想到或已实现的方法。因此，除非另外指出，否则这一部分中描述的方法不是该申请的权利要求的现有技术，并且也不应当因为被包括在这一部分中而看作是现有技术。

在诸如因特网之类的计算机网络中，数据分组根据各种路由协议之一经由元件的网络从源被发送向目的地，这些元件包括链路(诸如电话线或光线路之类的通信路径)和节点(例如，引导分组沿着连接到其的多条链路中的一条或多条行进的路由器)。

一类路由协议是链路状态协议。链路状态协议依赖于每个节点处的路由算法。网络上的每个节点通过网络向相邻节点通告链路，并提供与每条链路相关联的代价，这一代价可以基于任何适当的度量，例如链路带宽或延迟，并且一般被表达为整数值。链路可以具有不对称代价，即沿一条链路的方向AB的代价可能不同于沿方向BA的代价。基于链路状态分组(LSP)形式的通告信息，每个节点构造链路状态数据库(LSDB)(这是整个网络拓扑的映射)，并根据其基于适当的算法(例如，最短路径优先(SPF)算法)一般地构造到每个可用节点的单条最优路由。结果构造了“生成树”(SPT)，其根在节点处并且示出了包括到每个可用目的地节点的中间节点在内的最优路径。SPF的结果被存储在路由信息库(RIB)中，并且基于这些结果，转发信息库(FIB)或转发表被更新以适当地控制分组的转发。当存在网络改变时，代表改变的LSP通过网络被与改变相邻的每个节点洪泛，每个节点接收LSP并将其发送向每个相邻节点。

因此，当去往目的地节点的数据分组到达一个节点时，该节点识别到该目的地的最优路由，并沿着该路由将分组转发到下一跳(“NEXT_HOP”)。下一节点重复这一步骤，依此类推。

将会注意到，在正常的转发中，无论从其接收到分组的节点是那个，每个节点都判定分组应当被转发到的下一节点。在某些情形中，这可能形成“环路”(loop)。具体而言，这可能发生在数据库(以及相应的转发消息)在路由转变期间临时失去同步时，即，由于网络的改变，新的LSP被传播，这在RIB或FIB中产生了环路。例如，如果节点A经由节点B发送分组到节点Z(包括根据其SPF的最优路由)，则可能出现这样的情形，其中节点B根据其SPF确定到节点Z的最佳路由是经由节点A并发回分组。这可能持续进行，只要环路仍然存在，尽管通常分组将具有最大跳数，在这之后分组将被丢弃。这种环路可以是两个节点之间的间接环路或围绕节点电路的不直接环路。

对于环路问题已经提出的一种解决方案在Kevin Miles等人于2003年1月9日提交的题为“Method and Apparatus for Constructing a Backup Routein a Data Communications Network”的未决专利申请No.10/340,371(“Miles等人”)中有所描述，该申请的全部内容通过引用结合于此以用于所有目的，就好像被在这里完全公开一样，并且将在下面更详细地讨论。根据Miles等人给出的解决方案，在修复节点检测到相邻组件的故障的情况下，修复节点计算包括除了通过穿越故障组件可达的节点以外根据其协议可达的所有节点的集合的第一节点集合。然后，修复节点计算包括从其可在不穿越故障组件的情况下到达目标节点的所有节点的集合在内的第二节点集合。该方法随后确定在第一节点集合和第二节点集合的交集或其一跳的扩展中是否存在任何中间节点，并将去往目标节点的分组以隧道方式发送到隧道端点(end point)，该隧道端点包括第一和第二节点集合的交集中的节点。

Miles等人描述的解决方案可以参考图1进一步理解，图1示出了该解决方案被应用于的网络图。网络包括节点P(标号10)，节点A、B、C和S(标号12、14、16、18)经由相应链路20、22、24、26附接到节点P。在节点P发生故障的情况下，充当修复节点的节点S计算除了通过故障组件之外的可到达的第一节点集合，这里称为节点S的P空间，P_S(标号28)。节点S还计算从其可以在不穿越节点P的情况下到达目标节点B的节点，这里称为节点B的Q空间，B_Q(标号30)。作为修复节点的节点S随后识别出P_S中的节点E和Q_B中的节点F(标号32、34)经由链路36在彼此的一跳内。节点S随后以隧道方式经由路径38发送分组到节点E，也就是说，节点S封装分组，并附接节点E的地址作为目的地头部。为了使分组穿越链路36，节点S还向经封装分组添加“直接转发”指令以使得节点E在对分组解封装后转发到节点F，无论其到节点B的下一跳是多少。一旦分组到达节点F，则根据定义，其将会经由节点B的Q空间Q_B中的路径40到达节点B。

该方法的扩展在George Swallow等人于2004年10月27日提交的题为“Method and Apparatus for Forwarding Data in a Data CommunicationsNetwork”的未决专利申请No.10/976,076(“Swallow等人”)中有所描述，该申请的全部内容通过引用结合于此以用于所有目的，就好像被在这里完全公开一样。根据该扩展，修复节点还计算到故障节点的其他邻居的Q空间(从而形成扩展Q空间)，并将分组转发到P空间P_S和扩展Q空间的交集中的节点。再一次参考图1，例如，作为修复节点的节点S识别出节点E’(标号42)可经由路径44到达，并且位于C的Q空间Q_C(标号45)中。分组随后经由路径44跨过Q空间Q_C被转发到节点F’(标号46)，节点F’也落在B的Q空间Q_B中，并且从节点F’分组经由路径48被转发到节点B。

Miles等人和Swallow等人的方法可以针对节点和链路故障实现。在链路故障的情况下，提出了各种解决方案来避免修复节点和经由故障链路连接到修复节点的节点的邻居之间的环路，并且这些方案可以实现冲突修复策略，也就是说，在链路26的故障的情况下实现在图1的节点S与节点A、B和C之间。

一种这样的解决方案在Michael Shand等人于2003年1月15日提交的题为“Method and Apparatus for Determining a Data Communication NetworkRepair Strategy”的未决专利申请No.10/346,051(“Shand等人”)中有所描述，该申请的全部内容通过引用结合于此以用于所有目的，就好像被在这里完全公开一样。根据该方法，修复节点沿着修复路径发送探测分组，并且如果返回探测，则环路被识别。又一解决方案在Michael Shand等人于2004年5月18日提交的题为“Method and Apparatus for ForwardingData in a Data Communications Network”的未决专利申请No.10/848,669(“Shand等人II”)中有所描述，该申请的全部内容通过引用结合于此以用于所有目的，就好像被在这里完全公开一样。根据Shand等人II描述的方法，修复分组被标记为被修复的以避免环路。

这些系统提供了在组件故障的情况下的快速网络恢复，P和Q空间的使用意味着在许多情形中，所选的修复路径不是最短可用修复路径。此外，在某些情形中需要诸如有向转发之类的额外的转发机制。在某些情形中需要进一步的额外的封装层，例如在使用扩展Q空间或者诸如多归属前缀(MHP)的情况下。多次封装是不合需要的，例如由于对额外的校验利计算的需求。

这些问题中的许多问题之所以存在是因为当链路或路由器发生故障时，只有故障的邻居首先知道故障已发生。根据上述解决方案，该故障由作为故障邻居的路由器修复。这些修复路由器不得不操纵分组去往其目的地，而不管网络中的大多数其他路由器不知道故障的本质和位置这一事实。

又一已知方法在可以在万维网上的域“watersprings.org”的目录“pub/id”中的文件“draft-tian-ffr-alt-shortest-path-01.txt”处得到的“FastRe-route using Alternative Shortest Paths”中有所描述。根据该文档中描述的方法，修复节点和其下一跳中的每一个计算替换最短路径作为绕过潜在邻居节点故障的修复路径，这是通过以下方式实现的：在发生这种故障的情况下识别分组的终止点，并通过从链路状态数据库中去除故障节点来计算备用最短路径。然而，该方法需要构造明确的路径，该路径例如使用源路由来在分组自身中对路径编码。

附图说明

本发明在附图中以示例方式而非以限制方式示出，在附图中相似的标号指代类似的元件，其中：

图1是图示了根据已知方法构造修复路径的方法的网络表示；

图2是图示了根据本方法构造修复路径的方法的网络表示；

图3是图示了根据本方法构造修复路径的方法的流程图；

图4是根据本方法在LSP中承载的信息的示意图；

图5是图示了在对不可用节点的邻居节点处构造的转发表的图；

图6是图示了在对不可用节点的非邻居节点处构造的转发表的图；

图7是实现了构造修复路径的方法的节点的生成树图；

图8是实现了构造修复路径的方法的节点的递增改变的生成树图；

图9是图示了利用递增SPF构造修复路径的方法的流程图；

图10是图示了本方法的又一实现方式的网络表示；

图11是图示了针对MHP构造修复路径的方法的流程图；

图12是图示了本方法的又一实现方式的网络表示；

图13是图示了本方法的又一实现方式的网络表示；以及

图14是图示了可以在其上实现用于构造修复路径的方法的计算机系统的框图。

具体实施方式

描述了一种用于在数据通信网络中构造绕过不可用组件的修复路径的方法和装置。在下面的描述中，出于说明目的，给出了大量特定细节以提供对本发明的完全理解。然而，本领域技术人员应当清楚，没有这些特定细节也可以实施本发明。在其他实例中，公知的结构和设备以框图形式示出以避免不必要地混淆本发明

这里根据下面的大纲描述实施例：

1.0一般概述

2.0结构和功能概述

3.0构造修复路径的方法

4.0实现机制一硬件概述

5.0扩展和替换

1.0一般概述

在本发明中实现了在前述背景技术中给出的需求以及将从下面的描述中变清楚的其他需要和目的，本发明在一个方面中包括一种在数据通信网络中构造绕过不可用组件的修复路径的方法，该数据通信网络具有作为组件的具有网络地址的节点和其间的链路。该方法包括以下步骤：在参与节点处执行从网络中的通知节点接收标识通知节点和通过其可以到达通知节点的组件的通知。该方法还包括以下步骤：从通知中导出网络修复地址，该网络修复地址用在在通知中标识的组件不可用的情况下。该方法还包括以下步骤：构造针对修复地址的修复路径。

在其他方面中，本发明包括被配置为执行前述步骤的计算机装置和计算机可读介质。

2.0结构和功能概述

总地来说参考图2可以理解一种用于构造修复路径的方法，图2示出了本方法所应用的说明性网络图。该网络包括主节点P(标号200)、源节点S以及节点A、B和C(标号202、204、206、208)，节点S、A、B和C各自经由相应链路210、212、214、216连接到节点P。又一节点D(标号218)经由链路220连接到节点B。除了指派给每个节点的标准地址以外，网络中的每个接口还被指派以一个额外的修复地址。在这里用术语称为“notvia地址(不经由地址)”，将会意识到，这一术语是任意的、描述性的并且非限制性的。Notvia地址的语义是去往notvia地址的分组必须被传递到具有该地址的路由器，而不经由该地址被指派给的接口上的相邻路由器。

例如，从节点P通过相应链路210、212、214、216到节点S、A、B、C的接口可以具有地址和。类似地，沿相反方向从节点A、B、C和S分别经由链路212、214、21 6、210到节点P的接口具有地址。

为了修复故障，修复节点(例如节点S)封装分组去往在故障远端上的节点接口的notvia地址。然后，修复路径上的节点知道它们必须向哪些节点传递分组，并且它们必须避免哪些网络组件。

参考图2，假定S具有去往某一目的地D的分组，正常情况下其将经由P和B发送，并且S怀疑P已经发生故障，则S封装分组去往。根据语义，从S到的路径是从S到B的最短路径，该路径不经由P。如果网络包含从S到B且不经过路由器P的路径，则分组将被成功地传递到B。例如，分组可以沿着路径222被转发到节点X(224)，然后沿着路径226被转发到节点D。由于节点X已经为计算出修复路径，因此它将正确地转发所封装的分组。当去往的分组到达B时，B去除封装，并向其最终目的地(节点D)转发已修复的分组。

这可以参考图3进一步地理解，图3是以高级别图示了这里应用的方法的流程图。在框300中，节点P利用诸如LSP之类的通知通告其邻居A、B、C、S和其关联的notvia地址。将会意识到，充当通知节点的所有其他节点也将发出类似的LSP。结果，不仅可以构造适当的转发表，并且notvia地址还可用于每个节点(在每个节点发生故障或者变为不可用节点的情况下)，在这种情况下notvia地址可以用作修复地址。因此，在框302中，所有参与节点不仅针对每个正常(无故障)地址，还针对每个notvia地址计算其下一跳。结果，每个节点构造了绕过网络中每个其他节点的修复路径，并针对相应的notvia地址进行存储。

在框304中节点P随后发生故障或者变为不可用的情况下，则在框306中邻居节点以任何适当的方式检测到故障或者被通知以故障。在邻居节点随后接收到本来要发送向作为其下一跳的故障组件的分组的情况下，在框308中邻居节点作为修复节点，识别其必须将该分组以隧道方式发送到的修复末端点或目标以到达其后续的目的地。在以上给出的示例中，对于目的地是D的分组而言，修复节点是节点S，并且修复端点是节点B。具体而言，这是由相应的notvia地址标识的。因此，节点S在框310中沿着修复路径将分组以隧道方式发送向。在框312中，每个下一跳将经封装的分组向notvia地址转发，例如图2中的节点X正确地转发分组。由于所有的参与节点都已经利用相同的修复拓扑计算出到notvia地址的路径，因此分组被利用正常的IP转发加以转发，而不需要对转发代码的扩展。在框314中，分组到达修复端点，修复端点对其进行解封装，并向其目的地(在所描述的示例中是目的地D)转发原始分组，这同样是利用正常的IP转发进行的。

因此，只需要一级封装，并且可以修复任何故障(例如即使在网络是高度不对称的时，在这种情况下Miles等人描述的P/Q空间方法理论上可能失败)。此外，实现了绕过故障的最短可用路径，同样地也不需要诸如导向转发之类的额外的转发机制。

如下面更详细地描述的，参考图3描述的方法是极其健壮的，并且可以适用于很宽范围的公共网络配置和需求。例如，该方法可以应用于故障节点或故障链路的修复，并且可以结合用于单个故障点的策略，这种情况即是一个节点只提供到邻居节点或网络的一段的连通性。该方法还可以应用于多归属前缀(MHP)、共享风险组(SRG)、局域网(LAN)以及单播和多播分组的情形。另外，该方法可以利用例如多协议标签交换(MPLS)或距离向量技术实现。另外，该方法可以实现在只有网络的所有节点的子网是被使能构造根据本方法的修复路径的参与节点的情形中。

3.0构造修复路径的方法

再次参考图2，将会看出为了允许网络上的每个被使能节点构造针对故障的网络组件(链路或节点)的修复拓扑，每个节点必须通告其notvia地址以及存储在其LSP中的其他相关信息。参考图4，图4示意性地示出了包含在由节点P发布的LSP中的信息，将会看出除了通告每个邻居和其关联的度量(例如，与相应链路相关联的代价)以外，还提供了另外的信息。例如，在列400中提供邻居信息和在列402中提供关联度量的情况下，另外在列404中提供了每个邻居的notvia地址。Notvia地址与相应邻居相关联以使得针对邻居A的条目有效地指定。只要语义由接收到LSP的节点识别，则notvia地址自身可以采取标准IP地址的形式，在这里示意性地示为代表等等的a.a.a.a。将会看出，由于网络中的每一节点都提供了类似的信息，因此每个节点可以导出用于网络上的每一notvia地址的修复路径。

因此，再次参考参考图2描述的示例(其中在节点P发生故障的情况下节点S将去往节点D的分组封装并发送向)，每一节点更一般地计算其将在任何可能的节点故障的情况下使用的路径。因此，每个节点使网络中的每一其他路由器发生故障，一次一个，并计算它自己的到该节点的每个邻居的最佳路由。换句话说，同样参考图2，某些路由器X将依次地把每个路由器看作P，使P发生故障，然后计算它自己的到由P的邻居通告的每个notvia P地址的路由，即，X计算其到和(在每种情况下都不经由P)的路由。

因此，参考图5(图5图示了在节点S处导出的转发表的相关部分)，将会看出对于每个地址(列500)，导出了下一跳(列502)，指定了notvia地址(列504)，还实现了相应的修复地址(列506)。例如，在目的地是节点B并且下一跳被计算为节点P的情况下，则分组将被以隧道方式发送到的修复地址被与相应的修复下一跳存储在一起。在这种情况下，这是沿着从节点S到节点X的路径222的第一跳，在以上参考图2描述的示例中指示为沿着从节点S出发的链路230的节点Z(标号228)。在去往节点D的分组的情况下，正常的下一跳是节点P，并且修复地址是，因此对于被封装并发送向的分组而言，修复下一跳再次是节点Z。在节点A作为目的地地址的情况下，下一跳是节点P，并且修复地址是，这提供了某个修复下一跳Ω₁(未示出)。节点S的转发表中的修复地址总是去往邻居的邻居，即修复隧道的端点。然而，将会看出，在列500中的正常地址是notvia地址(例如)的情况下，尽管下一跳被提供为沿着从节点S出发的链路234的节点Y(标号232)，修复地址和修复下一跳也不被提供，如下更详细地所述。因此，节点S将利用正常转发将分组转发到notvia地址(当其依赖于另一节点的修复路径时)，但是在进入分组已经是去往notvia地址的时，将不会鼓励对notvia地址的隧道进行修复。

将会意识到，对于去往给定目的地的给定分组而言，在下一跳发生故障的情况下识别正确的修复地址的方法可以以任何适当的方式确定，例如根据在节点处构造的SPT并且例如Miles等人描述的。还将会看出，修复地址是根据接收的所有LSP导出的，并且不必从这样的节点导出，修复最终绕过该节点得以形成。例如，再次参考图5，在分组去往节点B的情况下，在下一跳节点P发生故障时，修复地址是，这将从节点B(而非节点P)接收到。参考图6(图6示出了在节点X处构造的转发表的某些方面)，将会看出，构造了类似的表，包括目的地地址字段600、下一跳字段602，为了简化修复地址字段和修复下一跳字段未被示出，但是这些将按照与针对上述节点S相同的方式被填充。在图示的片段中，将会看出，对于目的地地址B和D而言，下一跳是某一节点Ω₂(未示出)。在图示拓扑中，目的地地址的下一跳也正好是Ω₂，因为到B和D的最短路径在修复拓扑中不改变。

相反地，节点P的故障可能意味着节点X对的下一跳也改变。因此，如下更详细地所述的，在某些情形中可以减少在正常拓扑和修复拓扑之间的改变(即，在故障组件被从修复拓扑中切除的情况下)不影响某些节点的情况下的SPF计算开销。

为了减少计算开销，存在各种可能性，具体而言，其确保了每个节点不必为每个其他可能节点的故障计算整个SPF。首先，如果节点可以识别其不处于从另一节点到修复地址的修复路径中，则其不需要计算对于该修复地址的下一跳。将会注意到，以隧道方式被发送向修复地址的分组将只来源于修复绕过故障组件的节点，即，在距离修复地址的故障组件的另一侧上的节点。因此，这可以通过从修复节点向其针对给定修复地址的修复路径中的每个其他节点发出信令来实现，在这种情况下接收到信号的每个节点将计算它自己的针对该修复地址的下一跳。或者，可以构建某种形式的“被发现”(discovered)信令路由。例如，在节点S将分组发送向其修复下一跳(例如节点X)的情况下，如果该修复下一跳还未构造修复路径，则其将丢弃分组，然后计算它自己的修复下一跳。如果在更高级协议的控制下，S在没有从最终目的地接收到确认时重发分组，则节点X现在将把分组转发到其修复下一跳，修复下一跳也将丢弃分组但是同时构造它自己的修复下一跳。该过程继续，直到在将发送确认的时间点处建立了修复路径为止。

根据减少SPF计算开销的第二方式，可以实现递增SPF。这可以参考图7理解，图7示出了在节点X构造的部分SPT。X首先计算基本拓扑(这时所有路由器都是工作着的)，并确定它到所有节点地址的正常路径。例如，其对于节点B和D的下一跳是经由Ω₂的，对于节点P和Y的下一跳是经由节点S(这里为了简化忽略了节点Z)的，并且节点S对于节点A和C的下一跳是经由节点P的。

然后，节点X使路由器P故障，并执行递增SPF。递增SPF是本领域技术人员公知的，并且不在这里详细描述，而仅仅参考图8出于说明目的进行总结，图8示出了递增SPT。具体而言，将会看出，节点P已被从修复拓扑中切除，因此，节点A和C重新附接到节点Y，但是节点B和D不受影响。因此，可以快速计算出与相对应的notvia地址。节点X对于和的下一跳仍然是节点S。然而，当节点S重新计算其SPT时，其将会鼓励节点Y作为其对和的修复下一跳。节点X对于节点B和D的下一跳不受影响，因此对于目的地B、D和而言，下一跳是Ω₂。

因此，在先前经由P到达的所有地址被重新附接时，可以终止递增计算。然后，节点X回复基本拓扑，并重复依次使每个路由器故障并据此导出notvia地址的过程。该算法相比于一组完全的SPF明显廉价。具体而言，尽管路由器仍然必须为N-1故障计算修复路径，但是计算努力远小于N-1SPF。

该方法可以参考图9进一步理解，图9是图示了SPF的计算的流程图。在框900中，节点X构造网络中所有节点的基本拓扑。在框902中，节点X构造相应的SPT。在框904中，节点X使节点P故障，在框906中，节点X构造递增SPT，将节点P从针对的修复拓扑中切除。在框908中，任何分离的notvia地址被与必须被重新附接的任何其他地址重新附接在一起，以允许notvia地址的重新附接，并且在框910中，在所有地址都被重新附接时计算终止。然后在框912中，转发表被填充以对于notvia P地址的所有下一跳，例如等等。在框914中，对于网络中的每一其他参与节点重复这一程序。

将会看出，这里描述的方法可以应用于节点或链路故障两种情况下。以上提供的讨论尤其涉及节点故障，其中notvia地址或修复路径的构造是基于节点故障和据此导出的SPT的。然而，将会意识到，以类似的方式本发明也可以涉及链路故障。

例如，在图2的情况下，节点S和/或节点P可以额外地或可替换地基于链路210的故障通告notvia地址。在这种情况下，notvia地址可以再次利用适当的语义进行通告，以使得接收节点识别出地址类型和所需的计算以获得链路修复下一跳。例如，以上参考图7到9所述的递增SPT方法将基于修复拓扑，其中并不去除节点P(以及由此带来的节点P和其他节点之间的所有链路)，而是只去除节点S和P之间的链路210，并据此计算递增SPT。

假定链路而不是节点故障对某些目的地只通过故障路由器可达的情形有帮助，则希望进行尝试以修复这些目的地，这是通过假定只发生了链路故障，并利用针对节点故障计算的notvia地址尝试链路修复来实现的。为了执行链路修复，S封装并发送向(即，其指示网络不经由S将分组传递到节点修复地址P)。S的所有邻居都已经计算了在S自身发生故障的情况下到的路径。因此，S可以将分组给予到其邻居中的任何一个(当然，除了P)。然而，S应当优选地在最短可用路径上将经封装分组发送向P。该路径是通过在链路SP故障的情况下运行SPF而计算的。

在该链路修复是在存在节点故障的情况下(在这种情况下故障节点的其他邻居可以运行相冲突的修复策略)进行尝试的时，则环路以非常简单的方式得以避免。具体而言，如上参考图5所述，确保了对于notvia地址不提供修复路径。参考图2，如果A是P的邻居，其位于从S到P的链路修复路径上，并且P自身已发生故障，则来自S的经修复分组将到达A，并被封装发送向。A将检测到AP链路已发生故障，并且将正常地尝试修复分组。然而，由于对于未提供修复路径，因此A将被强制丢弃分组，从而防止了环路的形成。

该方法在例如单个故障点的情形中是有利的。再次参考图2，其中在节点W(标号240)自身可以提供与网络的一个分段的连通性时，节点P只提供到节点W的连通性，另外，如果节点P发生故障，则没有网络节点可以到达节点W。因此，在节点S检测到在其到节点P的接口处的故障时，其可能希望假定只有链路210发生故障，而不是节点P。因此，S将去往节点W的分组封装并发送向。尽管节点S理论上可以发送分组到其邻居中的任何一个，但是其最优地使用到的最短路径。当分组到达P时，P将剥离封装，并将分组发送向W。然而，如果P已确实发生故障，则分组将到达P的邻居(在封装中仍然去往)，并且由于该邻居没有用于notvia地址的修复路径，因此它将丢弃分组，因而避免了环路，如上所述。

还将会看出，在相等代价多路径路由(ECMP)可用或者下游路径路由可用的情况下，这些路由可以据此实现。例如，在下游路径或无环路备用(LFA)存在的情况下，诸如节点S之类的修复节点可以在适当的情形中用其来替代notvia修复机制。类似地，路由器可以使用ECMP修复来替代notvia修复。

可以看出，这里描述的方法可以适用于很宽范围的网络配置和情形。例如，在多归属前缀(MHP)  (这是一个可经由网络中的多于一个路由器到达的前缀，因而具有“多个归属”)的情况下，可以实现本方法。图10示出了包括多归属前缀Y的网络。该网络包括根据以上参考图2所述的连通性的节点S、P、B和C。另外，节点S通过路径1004连接到节点Z1000，节点B通过路径1006连接到节点V 1002。MHP Y(标号1008)附接在节点Z、P和V处。在这种情况下，当节点S发现节点P已发生故障时，其需要将去往Y(通常可通过P到达)的MHP分组发送向仍然能够到达Y的备用路由。

参考图11，图11是图示了在转发MHP分组中涉及到的步骤的流程图，在步骤1102中，节点S在节点P故障的情况下以上文参考图7到9所述的方式运行其递增SPF，直到P的所有邻居和MHP Y(其将是第二最近的)的情形被附接。节点S可以以任何适当方式识别何时所有的适当节点被重新附接，例如通过记录基本SPF期间的所有MHP并确保所有都被重新附接到递增SPF。

在框1104中，节点S封装分组并发送向被识别为最近备用节点的前缀附接点。在这是在节点Z(S可以在不使用节点P的情况下到达)处的情况下，仍然需要封装，因为网络中的其他节点将不会知道节点P的故障，并且可能将分组环回S。因此，在框1106中，节点Z解封装分组并将其转发到节点X。将会注意到，节点Z将包括转发指令，该转发指令确保了用于MHP Y的解封装分组必须被沿着连接链路1010转发到节点Y，以避免在存在经由P的较低代价路由的情况下的潜在环路。

在备用路由器是节点V(节点S经由节点P和节点B到达)的情况下，节点S必须首先利用正常的notvia修复机制修复到节点B的分组。因此，节点S将针对节点Y的分组封装并发送向。当分组到达节点B时，节点B对其解封装，并看出分组是去往MHP Y的。由于节点B已经确立节点P已发生故障并且将会执行与节点S相同的计算，因此其将会认识到其对于MHP Y而言的最近附接点是节点V，从而遵循与在节点S处执行的相同计算，并正常对其进行修复，从而对其进行封装并发送向V。

在替换方法中，前缀Y可被认为附接到伪节点N，伪节点N依次又连接到节点B、V、Z中的每一个，在这种情况下，相应接口被指派以notvia地址，并且实现上述的修复路径方法。将会认识到，“伪节点”的概念是本领域技术人员公知的，并且提供了用于处理MHP和LAN的有用的拓扑发明，从而这里不需要进行详细描述。

这里描述的方法还适合于用在包含共享风险群组(SRG)的网络中，SRG是被识别为具有同时发生故障(例如由于公共的物理位置)的概率的网络组件的群组。图12是图示了包括共享风险群组的网络的示意性网络图，并且与图2共同的元件用同一标号。另外，该网络包括节点P’(1200)和P”(1202)，其中P’连接在节点P和A之间，P”连接到节点A的另一侧。节点F(1204)连接到节点P”，并且节点G(1206)连接到节点F。节点D和E(标号1208、1210)分别连接到节点P’和P”。节点J和K(标号1212、1214)分别连接到节点D和E。节点H(标号1216)连接到节点C。

节点P、P’、P”形成了SRG，因此，如果假定SRG的所有成员同时发生故障，则notvia地址的范围指示“不经由整个SRG”。换句话说， $>>>A>>p>‾>>>=>A>\{>>>p>,>>p>\prime >>,>>p>>\prime >\prime >>>>‾>>\}>$>