[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN101953124B - 在数据通信网络中构造绕过多条不可用链路的修复路径 - Google Patents

在数据通信网络中构造绕过多条不可用链路的修复路径 Download PDF

Info

Publication number
CN101953124B
CN101953124B CN200980105263.6A CN200980105263A CN101953124B CN 101953124 B CN101953124 B CN 101953124B CN 200980105263 A CN200980105263 A CN 200980105263A CN 101953124 B CN101953124 B CN 101953124B
Authority
CN
China
Prior art keywords
node
link
network node
address
repair path
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN200980105263.6A
Other languages
English (en)
Other versions
CN101953124A (zh
Inventor
斯图尔特·弗雷德里克·布赖恩特
伊恩·迈克尔·查尔斯·尚德
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Cisco Technology Inc
Original Assignee
Cisco Technology Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Cisco Technology Inc filed Critical Cisco Technology Inc
Publication of CN101953124A publication Critical patent/CN101953124A/zh
Application granted granted Critical
Publication of CN101953124B publication Critical patent/CN101953124B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/18—Loop-free operations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/22—Alternate routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/28—Routing or path finding of packets in data switching networks using route fault recovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/50—Routing or path finding of packets in data switching networks using label swapping, e.g. multi-protocol label switch [MPLS]

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

一种数据处理设备被配置用于：发起用于为第一网络节点和第二网络节点之间的第一链路创建修复路径信息的不经由方案；创建不经由修复路径穿过的其他网络节点的列表；在FIB中创建和存储条目，条目标识网络节点的修复地址并且使得(a)想去往所有通常通过第一链路可达的地址的分组被封装到第二节点而不经由第一节点，(b)想去往通常通过第一链路可达的不经由地址的分组被封装到第二节点而不经由第一节点，并且(c)当通常通过第一链路可达的不经由地址在列表中时丢弃想去往该不经由地址的分组；对于所有其他链路重复前述步骤。

Description

在数据通信网络中构造绕过多条不可用链路的修复路径
技术领域
本公开总地涉及数据通信网络。本发明具体而言涉及在数据通信网络中构造绕过多条不可用链路的修复路径(repair path)。
背景技术
本部分中描述的方案可以被实行，但不一定是先前已经想到过或实行过的方案。因此，除非这里另有指明，否则本部分中描述的方案并不是本申请中权利要求的现有技术，并且不因为被包括在本部分中就被承认是现有技术。
在诸如因特网之类的计算机网络中，数据的分组根据各种路由协议之一，经由包括链路(诸如电话或光线路之类的通信路径)和节点(例如，沿着连接到它的多条链路中的一条或多条引导分组的路由器)在内的元件的网络被从源发送到目的地。
一类路由协议是链路状态协议。链路状态协议依赖存在于每个节点处的路由算法。网络上的每个节点在整个网络中通告去往邻居节点的链路，并且提供与每条链路相关联的代价，该代价可以基于诸如链路带宽或延迟之类的任何适当度量并且通常被表达为整数值。基于以链路状态分组(LSP)的形式通告的信息，每个节点构造可用于构造整个网络拓扑的地图的链路状态数据库(LSDB)，并且一般根据该数据库基于诸如最短路径优先(SPF)算法之类的适当算法来构造去往每个可用节点的单个最优路由。结果，构造出了“生成树”(SPT)，其以该节点为根，并且示出了去往每个可用目的地节点的、包括中间节点的最优路径。SPF的结果被存储在路由信息库(RIB)中，并且基于这些结果，转发信息库(FIB)或转发表被更新，以适当地控制分组的转发。当发生网络变化时，表示该变化的LSP被与该变化相邻的每个节点通过网络流播(flood)，接收到LSP的每个节点将其发送到每个相邻节点。
在正常的转发中，每个节点在不考虑它从哪个节点接收到分组的情况下决定应当把该分组转发到的下一节点。在一些情况下，这可能引起“环路”。尤其，这可能发生在数据库(以及相应的转发信息)在路由转变期间临时失同步时，即因为网络中的变化，导致在RIB或FIB中产生环路的新LSP被传播的情况。只要环路仍存在，这就可能一直继续，但通常分组将会具有最大跳数，在此之后它将被丢弃。这种环路可能是两个节点之间的直接环路或者在一系列节点之间的间接环路。
在一些网络中，两条或更多条链路在共享风险链路群组(SRLG)中逻辑上相关联。如果SRLG中的第一链路发生故障，那么在确定绕过第一故障链路的修复路径时，SRLG中的所有其他链路都被认为也发生故障。
IP快速重路由(IPFRR)是因特网工程任务组的一项提案，即开发用于迅速构造绕过故障链路、故障节点或SRLG的可预测故障的修复路径的技术。然而，已知的解决方案没有提供在多条链路不是已知SRLG的成员的情况下针对这些链路在大致相同时间的故障的保护措施。这种情境中的一个特定问题在于针对链路之一的修复可能会尝试穿过另一故障。如果针对该故障的修复正好穿过第一链路，则导致了环回式修复路径，其无法将分组递送到其目的地。为了避免此问题，已知的不经由(not-via)IPFRR方案明确地禁止对已经修复过的分组的修复，以避免这种环路。然而，这种约束只减轻了由环路导致的间接损害，而其本身不会使得分组可被递送到其目的地。
附图说明
在附图中以示例方式而非限制方式示出了本发明，附图中类似的标号指代相似的元件，其中：
图1示出了网络；
图2是构造当数据通信网络中的多条链路同时发生故障时使用的修复路径的过程的流程图；
图3是当数据通信网络中的多条链路同时发生故障时丢弃流量并触发收敛的过程的流程图；
图4示出了具有相互环回的修复路径的网络；
图5是示出用于构造修复路径的方法可在其上实现的计算机系统的框图；
图6是示出根据已知方案的构造修复路径的方法的网络的表示；图7是示出根据本方案的构造修复路径的方法的网络的表示；图8是示出根据本方案的构造修复路径的方法的流程图；图9是根据本方案在LSP中携带的信息的示意性表示；图10是示出在不可用节点的邻居节点处构造的转发表的示图；图11是示出在不可用节点的非邻居节点处构造的转发表的示图；图12是用于实现构造修复路径的方法的节点的生成树图；图13是用于实现构造修复路径的方法的节点的递增改变的生成树图；图14是示出利用递增式SPF构造修复路径的方法的流程图；图15是示出本方案的另外的实现方式的网络的表示；图16是示出为MHP构造修复路径的方法的流程图；图17是示出本方案的另外的实现方式的网络的表示；图18是示出本方案的另外的实现方式的网络的表示。
具体实施方式
本发明描述了用于在数据通信网络中构造绕过不可用组件的修复路径的方法和设备。在以下描述中，出于说明目的，阐述了许多具体细节以帮助透彻理解本发明。然而，对于本领域的技术人员来说很明显的是，没有这些具体细节也能实现本发明。在其他实例中，公知的结构和设备以框图形式示出，以避免不必要地模糊本发明的主题。
1.0综述
前述“背景技术”中确定的需求以及从以下描述中将变得清楚的其他需求和目的在本发明中得以实现，本发明在一个方面中包括一种数据处理设备，其在网络中可作为第一网络节点操作，并且包括：一个或多个处理器；网络接口，该网络接口通信地耦合到所述一个或多个处理器并且被配置为在网络中一个或多个处理器之间传输一个或多个分组流；存储器，该存储器耦合到处理器并且包括用于路由协议的转发信息库(FIB)；逻辑，该逻辑耦合到一个或多个处理器并且包括一个或多个存储的指令序列，所述指令序列在被一个或多个处理器执行时使得一个或多个处理器执行：发起用于为第一网络节点和第二网络节点之间的第一链路创建和存储修复路径信息的不经由方案；创建和存储不经由修复路径穿过的其他网络节点的列表；在FIB中创建和存储条目，该条目标识网络节点的修复地址并且使得(a)想去往所有通常通过第一链路可达的地址的分组被封装到第二节点而不经由第一节点，(b)想去往通常通过第一链路可达的不经由地址的分组被封装到第二节点而不经由第一节点，并且(c)当通常通过第一链路可达的不经由地址在列表中时丢弃想去往该不经由地址的分组；对于第一网络节点的所有其他链路重复前述步骤。
实施例能够在数据通信网络中构造绕过多个不可用链路的一个或多个修复路径。
在一个实施例中，逻辑还包括在被执行时使得一个或多个处理器执行以下步骤的指令：根据FIB中的条目确定一对或多对相互不兼容的链路故障；利用路由协议，将一对或多对作为次级共享风险链路群组来加以通告。
在一个实施例中，逻辑还包括在被执行时使得经由相应的修复路径发送以修复地址为目的地的网络流量的指令。
在一个实施例中，逻辑还包括在被执行时使得执行以下步骤的指令：确定发生了第一链路和第二链路的同时故障；确定针对第一链路的第一修复路径穿过第二链路，并且针对第二链路的第二修复路径穿过第一链路；确定分组丢弃计数大于指定的阈值，针对重收敛正在使用抑制步骤，并且正在使用无环路收敛机制；响应于最终确定步骤，向实现路由协议的逻辑发送“放弃所有希望”通知，用于强制正常重收敛开始。
在一个实施例中，逻辑还包括在被执行时使得执行以下步骤的指令：从第二节点接收具有路径向量的第一不经由地址的边界网关协议(BGP)通告；为到所接收的不经由地址的修复路径确定链路的列表；接收具有路径向量的其他不经由地址的一个或多个其他BGP通告；基于路径向量确定链路的修复路径相互环回；在FIB中为第一不经由地址插入丢弃修复条目。
在一个实施例中，第一网络节点包括充当修复节点的邻居节点，并且逻辑还包括在被执行时使得修复节点执行以下步骤的指令：针对第二网络节点的目的地地址识别一修复地址作为封装修复端点，用于在第二网络节点不可用的情况下对目的地地址的修复。
在一个实施例中，网络包括多归属前缀，并且逻辑还包括在被执行时使得执行以下步骤的指令：确定到多归属前缀的附接点是否能够在没有修复路径的情况下到达，并且如果是则将分组封装到该附接点；并且如果到多归属前缀的附接点仅能经由修复路径到达，则将流量封装到相应的修复地址。
在一个实施例中，路由协议是链路状态路由协议、MPLS路由协议或距离向量路由协议中的任何一种。
在一个实施例中，第一链路是共享风险链路群组。
在一个实施例中，逻辑还包括在被执行时使得在修复地址之一的前一节点处对分组解封装的指令。在一个实施例中，分组包括多播流量。
在其他方面中，本发明包括被配置为实现这里描述的功能的由计算机实现的方法和计算机可读介质。
2.0结构和功能概述
2.1利用不经由来修复多个无关链路故障
在本专利文献中提名的发明人所著的美国专利申请公布No.2006/0187819中描述了一种用于利用“不经由”方案在数据通信网络中构造绕过不可用组件的修复路径的方法和设备。在公布No.2006/0187819的不经由方案中，除了分配给每个节点的标准地址之外，网络中的每个接口还被分配以一额外的修复地址，该修复地址被称为“不经由地址”(notvia address)。寻址到该不经由地址的分组必须被递送到具有该地址的路由器且不经由不经由地址所暗示的组件；例如，不经由被分配以该地址的接口上的邻居路由器。为了修复故障，修复节点封装该分组去往故障的远端的节点接口的不经由地址。修复路径上的节点于是知道它们必须将分组递送到哪个节点，以及必须避免哪个网络组件。
这里的描述假定已了解公布No 2006/0187819。尤其，本文献描述了对公布No.2006/0187819的方案的某些改进，但不重复公布No.2006/0187819中已经知道的信息。特此通过引用并入公布No.2006/0187819的全部内容，用于所有目的，就好像在这里完全记载了一样。
图1是包括节点A、B、D、G、F、X、Y的假想网络的示图。出于图示出清楚示例的目的，在图1中示出了七个节点，但这里的技术可应用在具有任何大小的任何网络中。每个节点包括诸如路由器或交换机之类的计算元件。每个节点包括处理器、交换系统、存储器和这里针对图5进一步描述的其他硬件元件。每个节点还包括所存储的程序控制逻辑，该逻辑的形式为能够实现这里描述的功能的固件、硬件、软件或其组合。
在一个实施例中，节点A、B、D、G、F、X、Y中的每一个包括在图1中针对节点X示出的功能单元。在一个实施例中，节点包括操作系统102，例如来自加州圣何塞的思科系统公司的Cisco IOS Software。操作系统102可以容宿或控制诸如链路状态协议逻辑104之类的应用，并且还可可选地容宿边界控制协议(BGP)逻辑106，其中链路状态协议逻辑104实现链路状态路由协议，边界控制协议逻辑106实现BGP，例如因特网工程任务组(IETF)请求注释(RFC)1771和相关RFC中定义的BGPv4。在一个实施例中，节点还包括多故障链路修复路径逻辑108，其包括能够实现这里针对图2、图3描述的功能以及在这里其他部分中描述的功能的固件、硬件、软件或其组合。在一个实施例中，多故障链路修复路径逻辑108可被集成到链路状态协议逻辑104或操作系统102中。这里描述的某些功能的一些方面可在BGP逻辑106中实现。另外，图1所示的节点X的所有元件都可集成到软件、固件或其组合的单个单元中，图1中示出分开的块只是为了图示出清楚的示例。
图1中的链路在这里是按照与节点的连通性来描述的；例如，链路A-B耦合到节点A和节点B。链路A-B和链路X-Y被保护，并且所有修复是根据公布No.2006/0187819的技术作为不经由修复来执行的。无环路备用(loop free alternate，LFA)或下游路由也是可能的，并且在这里的其他部分中论述。
在图1的情境中，当两条链路同时发生故障时，可能发生三种可能的修复路径场景：
1.针对链路A-B的修复路径不穿过链路X-Y，并且针对链路X-Y的修复路径不穿过链路A-B。这种情况不会导致环回或分组丢失。
2.针对A-B的修复路径穿过X-Y，但是针对X-Y的修复路径不穿过A-B。在传统的不经由修复路径方案中，在操作中，针对发生故障的链路A-B的被修复分组在到达发生故障的链路X-Y时将被丢弃，因为在公布No.2006/0187819的方案中对被修复分组的修复是被禁止的。然而，如果此分组在到达X-Y时被允许被修复，则不会造成损害，除了有可能发生双重封装以外，双重封装将会导致被修复分组超过路由协议的可允许最大传输单位(MTU)。超过MTU的影响在这里后续部分中论述。
3.针对A-B的修复穿过X-Y，并且针对X-Y的修复穿过A-B。在此情况下，无限制的修复将会导致分组在网络中不断环回，同时封装水平越来越高。这种行为是不合需要的并且对于网络是可能有害的。
在一个实施例中，节点中的多故障链路修复路径逻辑108被配置为识别出这些情况中的哪种情况存在，并且以实现环路避免的方式来执行不经由修复。出于图示出清楚示例的目的，图1仅示出了节点A、B、D、G、Y、X和F，但图1的假想网络可包括能够构造出绕过A-B和X-Y的相互链路故障的有效修复路径的许多其他节点和链路。
图2是构造当数据通信网络中的多条链路同时发生故障时使用的修复路径的过程的流程图。
在步骤202中，第一网络节点利用不经由方案，发起对针对第一网络节点和第二网络节点之间的第一链路的修复路径信息的创建和存储。例如，节点A利用公布No.2006/0187819的方案，为链路A-B预先计算不经由修复路径。当节点A在为A-B计算不经由修复路径时(例如用于被寻址到Ba的流量的路径，其被称为“B不经由A”)，节点A知晓此路径穿过的节点的列表。该节点列表可在SPF过程期间被记录，并且与每条转发链路相关联的不经由地址可以被确定。再次参考图1，如果路径是A、F、X、Y、G、B，则不经由地址的列表为：Fa、Xf、Yx、Gy、Bg。
在步骤204中，创建并存储不经由修复路径穿过的节点的列表。步骤204中的存储可包括在SPF过程期间在存储器中的临时存储。
在公布No.2006/0187819中记载的标准不经由操作下，A填充其转发信息库(FIB)，使得当A-B发生故障时所有通常经由A-B可达的地址都被封装到Ba，但去往不经由地址的所有流量都被丢弃。根据一个实施例中，针对通常通过A-B可达的不经由地址的所有流量也被封装到Ba，除非该不经由地址是先前被识别为在去往Ba的路径上的地址之一，例如Yx，在此情况下分组被丢弃。
相应地，如步骤206、208和212中所示，节点在其转发信息库(FIB)中创建和存储条目，这些条目使得想去往所有通常通过第一链路可达的地址的分组被封装到第二节点而不经由第一节点(步骤206)。节点还创建和存储FIB条目，这些条目使得想去往通常通过第一链路可达的不经由地址的分组被封装到第二节点而不经由第一节点(步骤208)。在步骤212，节点还创建和存储FIB条目，这些条目使得当通常通过第一链路可达的不经由地址在步骤204处创建的列表中时，丢弃想去往该不经由地址的分组。前述步骤对于修复节点的所有其他链路重复。
此方案允许了在以上指出的所有三种情况中执行修复，同时防止了在第三种情况中发生环路。在一个实施例中，所有需要的FIB条目都被预先计算，因此该方案不需要任何详细的分组检查。除了修复节点之外的节点只是简单地利用传统的路由协议操作基于FIB条目来转发分组；不需要特殊的修复标记、修复水平指示符、计数器或其他机制。
本方案允许了良性修复共存，但在一些情况下该方案导致多次封装。不会出现重大的性能问题，因为两次封装或两次解封装通常是在不同节点处执行的。唯一的潜在问题是由于分组大小增大而导致超过网络中所允许的最大传输单位(MTU)，其中分组大小增大是由多次封装引起的。
然而，在第三种情况中，虽然潜在的环回流量被丢弃，但是该流量不被修复。如果在重收敛之前应用抑制(hold-down)步骤，以防链路故障只是短暂的小毛病，并且如果无环路收敛机制(例如有序FIB收敛逻辑)进一步延迟收敛，则流量将被丢弃较长的一段时间。在一个实施例中，作为对这里在第2.2节中描述的方案的附加或替换，响应于不经由分组中生存时间值的期满，采取特殊的动作。例如，在到此为止描述的环回场景中，在没有丢弃环回的不经由分组的特殊步骤的情况下，环回的不经由分组在其未被及时递送到目的地节点时将最终导致不经由分组中的生存时间值的期满。在一个实施例中，在这些情况下，采取“放弃所有希望”(AAH)动作(或者在路由协议逻辑内发送消息)，以立即调用正常的重收敛。在这些情形下，加速发出报告故障的LSP是不够的，因为这可能被有序FIB收敛逻辑视为许可的同时故障；而是必须触发AAH消息以引起正常收敛。有序FIB AAH动作可在不经由地址上的分组丢弃计数已被递增时被触发。
此方案在图3中示出。图3是当数据通信网络中的多条链路同时发生故障时丢弃流量并触发收敛的过程的流程图。在步骤304中，节点通过如上文中针对图2所述预先计算修复路径，已确定了针对第一链路的修复路径穿过第二链路，并且针对第二链路的修复路径穿过第一链路。在步骤305中，第一链路和第二链路的同时故障发生。这是上述的第三场景。结果，修复路径不可使用，并且想去往通过这些链路可达的地址的某些流量被丢弃，直到重收敛发生为止。
在一个实施例中，在步骤307中，节点测试在该节点上维护的分组丢弃计数是否已超过指定的阈值。这种测试被执行来迅速地检测出实际流动的流量是否正导致不可接受的分组丢失并因此可能是在相互环回的修复路径上的，并且通过调用AAH方案，一旦可能就引发补救动作。这种替换方案具有这样的益处，即在穿过256跳所需的时间加上“收回”修复以便任何其他节点可以打破将来的环路所需的时间内解决环路。
分组丢弃计数传统上是由节点的操作系统102维护的，并且可通过节点内的API调用或数据库查找来访问。如果已超过阈值，则节点在步骤308中检查是否在使用抑制步骤。步骤308可以在这样一个逻辑中实现，该逻辑不实际执行测试，而只是进行分支，因为该逻辑的作者知道已经实现了抑制逻辑。如果正在使用抑制步骤，那么在步骤310，逻辑测试在节点处是否正在使用无环路收敛过程。如果是，则触发“放弃所有希望”通知，以停止抑制时段并且强制正常重收敛。作为收敛的结果，可以发现使得流量可被转发而不是被丢弃的新网络路径。如果步骤307、308、310的测试中的任何一个结果为否定，处理则在步骤314继续。
或者，逻辑可以等待，直到描述变化的LSP被正常发出为止，例如，当X宣告X-Y的故障时。当已预先计算出X-Y故障与其自己的修复相互不兼容的修复节点接收到此LSP时，则该修复节点可以发出AAH。这种替换方案具有未克服抑制延迟的缺点。然而，该替换方案不需要数据驱动的操作，并且仍具有所需要的放弃有序FIB收敛过程的效果，而该过程的延迟可能是较长的。
2.2.次级共享风险链路群组
为了应对第三场景，在替换实施例中，计算替换的类SRLG修复路径，而不是简单地丢弃违反的分组。在这种替换方案中，相互不兼容的故障被识别并且作为次级SRLG被通告。这种链路随后在为受影响的不经由地址计算修复路径时被一起视为故障(但对于正常地址不是如此)。
再次参考图2，在替换方案中，在步骤214，在执行步骤202、204、206、208之后，节点确定一对或多对相互不兼容的链路故障，排除针对具有两条链路的节点的那些。在步骤216中，这些链路对作为次级共享风险链路群组被通告。这实际上是在确定针对受影响的不经由地址的修复路径时将这些链路对一起从考虑中排除。
图2的一般方案，识别哪些不经由地址应当被丢弃的步骤202至212作为相互不兼容的故障的指标而言是保守的，因为被丢弃的地址中的一些可能永远不会被用于修复。虽然此问题在图1的示例中不会出现，但是步骤214-216的方案可被用于其他场景，并且是保守的，而且只在修复路径相互不兼容时才调用SRLG计算。
例如，当节点A已识别出针对Yx的正常路径会通过A-B，从而Yx分组应当被丢弃时，节点A通过运行以X为根并且去除了X-Y的SPF算法来执行进一步检查，以确定A-B是否确实是在X的针对Yx的修复路径上。A-B可能不在该修复路径上，即使针对Yx的分组将会穿过A-B，因为为Yx计算了完整的汇集树。
在一个实施例中，进一步检查计算看起来是hk阶的，其中h是修复路径的平均跳长度，k是路由器的邻居的平均数目，但是可以引入某些优化。当A在计算一组修复路径时，A为其所有k个邻居计算修复路径。对于每个邻居，A确定被每个修复路径穿过的节点对的列表。节点对的每个列表可能具有一个或多个共同的节点对，因此需要调查的链路故障的实际数目是节点对的列表的并集。节点A随后运行以每个对的第一节点为根的SPF-第一节点是根，因为配对是在表示路径的方向的情况下被排序的-其中去往第二节点的链路被去除。此SPF虽然不是递增式的，但是一旦到达不经由地址就可以被终止。
例如，当运行以X为根、且去除了链路X-Y的SPF时，可以在到达Yx时终止SPF，并且所得到的路径被放入PATHS中；SPF算法的一个基本属性是，一旦某一节点被放入PATHS中，到它的最短路径就已被找到。一旦路径已被找到，该路径就被检查以确定它是否穿过A的任何链路。因为节点对XY可能存在于A的不止一条链路的列表中，从而节点对XY位于不止一条修复路径上，所以必须识别出正确的列表和具有相互环回的修复路径的链路。所识别出的A的链路随后被A作为与链路X配对的次级SRLG通告。因为节点X也将运行相同的算法，所以节点X将识别出XY与AB配对并且将如此通告它。
在一个实施例中，可以执行交叉检查以验证计算的准确性。列表中的对的排序是很重要的。例如，链路XY和链路YX被分开考虑。
当且仅当修复相互不兼容时，链路的对才被作为次级SRLG通告。所有节点随后利用额外的不经由地址Ba|(x-y)来计算绕过两个故障的修复路径，其中不经由地址Ba|(x-y)的含义是B不经由A或链路X-Y。
大多数相互环回的修复路径是由仅具有两条链路的节点或者网络的只是双向连接的部分导致的。在这些情况下，修复很明显是不可能的；两条链路的故障分割了网络。在一个实施例中，这种情况被识别，以阻止对次级SRLG信息的无用通告。在一个实施例中，识别是通过检测到对次级SRLG的需要的节点首先运行去除了两条链路的不经由计算来执行的。如果此过程没有产生路径，则网络将被这种故障所分割，因此不需要通告，也不进行通告。
因此，在这里的方案中，每个节点执行少量的额外计算并随后可能通告某些次级SRLG信息，这随后又使得其他节点基于该信息重新计算其修复路径。一种替换方案是所有节点代表其他节点执行计算。此方案是可能的，因为执行链路状态协议的节点能够访问路由域的相关流播范围内的全部拓扑信息。在此替换方案中，不需要额外的流播或“两阶段”计算。
在替换实施例中，这里的SRLG方案还可用于在多个并发链路故障导致多向环路的网络拓扑中确定修复路径。图4示出了多个并发链路故障导致多向环路的网络拓扑。网络包括具有链路A-B、A-E、B-G、G-F、G-Y、X-Y、X-F、X-C和C-Y的节点A、B、F、G、X、Y和C。为了简化，这里没有列出相反方向上的相应链路。节点A已计算出A-X(404)作为绕过A-B的修复路径。节点B已计算出B-Y(402)作为绕过B-A的修复路径。节点X已计算出X-C-Y(406)作为绕过X-Y的修复路径。节点Y已计算出Y-C-X作为绕过Y-X的修复路径。在此配置中，当A-B和X-Y相互故障时，沿着修复路径和拓扑内部的节点之间的未受影响的路径，出现无限的环路。另外，如到此为止所述将A-B和X-Y放在次级SRLG中是不足以去除该环路的。
在一个实施例中，可以通过运行额外的SPF计算以扩展检查路径的方法来应对由多个相互链路故障导致的多向环路。具体而言，修复节点通过执行以已知在先前确定的修复路径上的每个节点为根的SPF，来额外地确定另一级修复路径。修复节点还在图2的步骤204处创建的、用于在图2的过程的步骤212处安装丢弃FIB条目的节点列表中包括额外修复路径上的所有节点，如果这些修复路径包括修复节点的话。
一般地，为了应对由三(3)条链路的相互故障导致的环路，该方案除了原始的不经由计算以外还执行两级SPF计算。当涉及四(4)条链路时，考察三个级别，依此类推。该过程可以重复使用对任何数目的期望级别的递归考察，同时针对存储器可用性、处理资源以及执行整个预计算的时间进行平衡。另外，当在此过程中考虑极大数目的故障时，以下可能性增大了，即，实际故障将会以阻止有效转发、直到至少一个链路修复实现为止的方式分割网络。
此外，当在N+1条链路已相互故障并且如上所述仅针对N条链路计算了修复路径的情况下出现环路时，路由协议逻辑可以响应于TTL值的期望而实现上述的“放弃所有希望”过程。从而，“放弃所有希望”方案可以充当安全网，并且针对执行很多级SPF计算的代价进行平衡。
结果，通过安装在识别出多向相互环路时将会使得分组被丢弃而不是继续环回的额外丢弃条目，可以将环路保护扩展到三条或更多条链路。
2.3无环路备用和下游路由
以上描述假定了所有修复都是不经由隧道。然而，实施例在可用时可以使用无环路备用(LFA)或下游路由。LFA或下游路由的使用使这里的方案复杂化，因为这种使用导致了正被修复但却不是寻址到不经由地址的分组。
如果发生故障的两条链路都在使用下游路由，那么不可能发生环回，因为不可能有一对节点都是彼此的下游。然而，当使用LFA时可能发生环路。示例是公知的LFA的节点修复问题。
如果一条链路在使用下游路由，而另一条在使用不经由隧道，那么如果能够确定在下游路由的路径上的节点，则该方案将可行。计算下游路由的一些方法不提供此信息。如果关于下游路由的路径上的节点的信息可用，那么使用下游路由的链路对于另一链路的不经由地址将具有丢弃FIB条目。因此，可能环回的分组在尝试越过此链路时将被丢弃。不同于两条故障链路使用不经由修复的情况(其中当不经由分组首次遇见第二故障时环路将被打破)，下游路由的分组将被无条件地修复，并且下游路由的分组仅会在其被路由回第一故障时才会被丢弃。即，下游路由的分组在被丢弃之前将会运行环路的一圈。
另外，利用下游路由，路径可能被计算到故障的远端，但是分组在到达故障的远端之前可能“脱离”到其目的地。在此情况下，分组可能穿过了某些可能发生了故障、但在计算出的路径上没有考虑到的其他链路。例如，如果A-B修复是下游路由并且X-Y修复是不经由修复，则被封装到YX的X-Y修复分组将沿着尝试穿过A-B的路径而行。如果针对“正常”地址的A-B修复路径是下游路由，则不能假定针对被寻址到YX的分组的修复路径可被发送到同一邻居。这是因为下游路由的有效性在由YX表示的拓扑中必须被查明，而在该拓扑中链路X-Y发生了故障。此拓扑与用于正常下游计算的拓扑不同，并且将正常下游路由用于被封装的分组将会导致未检测到的环路。
如果检查此拓扑中的下游路由在计算上是可行的(在一个实施例中，对于穿过A-B的任何不经由地址QP，节点在Q-P发生故障的拓扑中为该不经由地址执行下游计算)，则针对YX的下游修复可被安全地使用。这些分组不能重新访问X-Y，因为按照定义这种分组将会避免该链路。
或者，这种分组可在不经由隧道中被修复。例如，即使针对穿过A-B的流量的正常修复将会使用下游路由，一个实施例也可以要求寻址到不经由地址的这种流量必须使用到BA的隧道，其方式是通过安装这样一条隧道作为针对被寻址到该不经由地址的流量的路由。仅在已利用上述规则确定这种隧道不穿过Q-P的情况下才会为地址QP安装这种隧道。
在前述实施例中的任何一种中，路由协议的类型-长度-值(TLV)元素可用于通告所构造的修复路径或通告要避免的路径。作为附加或替换，通告可以规定节点需要构造绕过指定链路的不经由修复路径。例如，通告将宣告需要构造绕过被提名、利用端点节点标识或以其他方式标识的一条或多条链路的列表的不经由修复路径。作为另一示例，这种通告还将包括一条可能的修复路径，在此情况下接收节点将确定接收节点在该修复路径上并且因此接收节点应当执行对另一修复路径的计算。作为又一示例，这种通告将会触发接收节点在其FIB中输入指定的修复路径，这实际上强制了接收节点以指定的方式更新其路由表。
3.0实现机构-硬件概述
图5是示出该方法可在其上实现的计算机系统140的框图。该方法是利用运行在诸如路由器设备这样的网络元件上的一个或多个计算机程序实现的。从而，在此实施例中，计算机系统140是路由器。
计算机系统140包括用于传输信息的总线142或其他通信机构和与总线142相耦合用于处理信息的处理器144。计算机系统140还包括诸如随机存取存储器(RAM)、闪存或其他动态存储设备之类的主存储器146，其耦合到总线142，用于存储信息和处理器144要执行的指令。主存储器146还可用于存储在处理器144执行指令期间的临时变量或其他中间信息。计算机系统140还包括只读存储器(ROM)148或其他静态存储设备，其耦合到总线142，用于存储静态信息和处理器144的指令。提供了诸如磁盘、闪存或光盘之类的存储设备150，其耦合到总线142，用于存储信息和指令。
通信接口158可以耦合到总线142，以用于将信息和命令选择传输到处理器144。接口158是传统串行接口，例如RS-232或RS-422接口。外部终端152或其他计算机系统连接到计算机系统140，并利用接口158向其提供命令。运行在计算机系统140中的固件或软件提供终端接口或基于字符的命令接口，以便外部命令可被提供给计算机系统。链路520可以将通信接口158耦合到本地网络522。
交换系统156耦合到总线142，并具有输入接口514和到外部网络元件的相应输出接口519。外部网络元件可包括多个另外的路由器或者耦合到一个或多个主机或路由器的本地网络522，或者诸如因特网这样的具有一个或多个服务器的全局网络。交换系统156根据公知的预定协议和惯例将到达输入接口的信息流量交换到输出接口。例如，交换系统156与处理器144合作，可确定到达输入接口的数据分组的目的地，并利用输出接口将其发送到正确的目的地。目的地可包括主机、服务器、其他末端站、或者本地网络或因特网中的其他路由和交换设备。
计算机系统140实现为充当上述转发数据的方法中的参与节点、修复节点或通知节点的路由器。该实现是由计算机系统140响应于处理器144执行包含在主存储器146中的一条或多条指令的一个或多个序列而提供的。这种指令可以被从另一计算机可读介质(如存储设备150)读取到主存储器146中。包含在主存储器146中的指令序列的执行使得处理器144执行这里描述的过程步骤。多处理配置中的一个或多个处理器也可被用来执行包含在主存储器146中的指令序列。在替换实施例中，可以使用硬线电路来代替软件指令或与软件指令相组合以实现该方法。从而，实施例不限于硬件电路和软件的任何特定组合。
这里所用的术语“计算机可读介质”指参与向处理器144提供指令以供执行的任何介质。这种介质可以采取许多形式，包括但不限于：非易失性介质、易失性介质和传输介质。非易失性介质例如包括光盘或磁盘，如存储设备150。易失性介质包括动态存储器，如主存储器146。传输介质包括同轴电缆、铜线和光纤，包括构成总线142的线路。传输介质也可以采取诸如声波或电磁波之类的无线链路的形式，例如在无线电波和红外数据通信期间生成的那些信号。
计算机可读介质的常见形式例如包括软盘、柔性盘、硬盘、磁带或任何其他磁介质，CD-ROM、任何其他光介质，穿孔卡、纸带、任何其他具有孔图案的物理介质，RAM、PROM和EPROM、FLASH-EPROM、任何其他存储器芯片或卡盘，下文中描述的载波，或者计算机可以读取的任何其他介质。
计算机可读介质的各种形式可用于将一条或多条指令的一个或多个序列传送到处理器144以供执行。例如，指令可以首先承载在远程计算机的磁盘上。远程计算机可以将指令加载到其动态存储器中，并利用调制解调器通过电话线发送指令。计算机系统140本地的调制解调器可以接收电话线上的数据，并使用红外发送器来将数据转换为红外信号。耦合到总线142的红外检测器可以接收在红外信号中携带的数据，并且将数据置于总线142上。总线142将数据传送到主存储器146，处理器144从主存储器146取得指令并执行指令。主存储器146接收的指令可以可选地在处理器144执行之前或之后存储到存储设备150上。
接口519还可提供到连接到本地网络的网络链路的双向数据通信耦合。例如，接口519可以是综合业务数字网络(ISDN)卡或调制解调器，以提供到相应类型电话线的数字通信连接。作为另一示例，接口519可以是局域网(LAN)卡，以提供到兼容LAN的数据通信连接。也可以实现无线链路。在任何这种实现方式中，接口519发送和接收电、电磁或光信号，这些信号携带了表示各类信息的数字数据流。
网络链路一般通过一个或多个网络提供到其他数据设备的数据通信。例如，网络链路可以通过本地网络提供到主机计算机或由因特网服务供应商(ISP)526操作的数据设备的连接。ISP 526又通过全球分组数据通信网络(现在通常称为“因特网”528)提供数据通信服务。本地网络和因特网都使用携带数字数据流的电、电磁或光信号。通过各种网络的信号和在网络链路上并通过接口519的信号(这些信号携带去往和来自计算机系统140的数字数据)是传输信息的载波的示例性形式。
计算机系统140可以通过(一个或多个)网络、网络链路和接口519发送消息和接收数据，包括程序代码。在因特网示例中，服务器可以通过因特网、ISP、本地网络和通信接口发送应用程序的请求代码。一个这样下载的应用提供了如这里所述的方法。
接收到的代码可以在接收时被处理器144执行，和/或被存储在存储设备150或其他非易失性存储装置中以供以后执行。以这种方式，计算机系统140可以获得载波形式的应用代码。
4.0扩展和替换
在前述说明书中，已参考本发明的特定实施例描述了本发明。但是，应当清楚，在不脱离本发明更宽广的精神和范围的前提下，可以进行各种修改和改变。因此，说明书和附图都应当被认为是示例性的，而非限制性的。
任何适当的路由协议和机制以及转发范例都可被采用来实现本发明。所阐述的方法步骤可以按任何适当的顺序来执行，并且来自描述的示例和实施例的各方面可被适当地并列或交换。例如，可以利用诸如中间系统-中间系统(IS-IS)或开放最短路径优先(OSPF)之类的链路状态协议或者路由向量协议和任何转发范例(例如MPLS)来实现方法。方法可被应用在具有任何拓扑的任何网络中，结合网络中的任何组件变化，例如链路或节点故障，或者管理员引入或去除网络组件。
再现公布No.2006/0187819的内容
在诸如因特网之类的计算机网络中，数据分组根据各种路由协议之一，经由包括链路(诸如电话或光线路之类的通信路径)和节点(例如，沿着连接到它的多条链路中的一条或多条引导分组的路由器)在内的元件的网络被从源发送到目的地。
一类路由协议是链路状态协议。链路状态协议依赖存在于每个节点处的路由算法。网络上的每个节点在整个网络中通告去往邻居节点的链路，并且提供与每条链路相关联的代价，该代价可以基于诸如链路带宽或延迟之类的任何适当度量并且通常被表达为整数值。链路可具有不对称代价，即沿一条链路的方向AB的代价可能不同于沿方向BA的代价。基于以链路状态分组(LSP)的形式通告的信息，每个节点构造链路状态数据库(LSDB)(这是整个网络拓扑的映射)，并一般根据该数据库基于诸如最短路径优先(SPF)算法之类的适当算法来构造去往每个可用节点的单个最优路由。结果，构造出了“生成树”(SPT)，其以该节点为根，并且示出了去往每个可用目的地节点的、包括中间节点的最优路径。SPF的结果被存储在路由信息库(RIB)中，并且基于这些结果，转发信息库(FIB)或转发表被更新，以适当地控制分组的转发。当发生网络变化时，表示该变化的LSP被与该变化相邻的每个节点通过网络流播，接收到LSP的每个节点将其发送到每个相邻节点。
结果，当去往目的地节点的数据分组到达一个节点时，该节点识别去往该目的地的最优路由，并沿着该路由将分组转发到下一节点(“NEXT_HOP”)。下一节点重复这一步骤，依此类推。
将会注意到，在正常的转发中，每个节点在不考虑它从哪个节点接收到分组的情况下决定应当把该分组转发到的下一节点。在一些情况下，这可能引起“环路”。尤其，这可能发生在数据库(以及相应的转发信息)在路由转变期间临时失同步时，即因为网络中的变化，导致在RIB或FIB中产生环路的新LSP被传播的情况。例如，如果节点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等人给出的解决方案，在修复节点检测到相邻组件的故障的情况下，修复节点计算包括除了通过穿越故障组件可达的节点以外根据其协议可达的所有节点的集合的第一节点集合。然后，修复节点计算包括所有下述节点的集合在内的第二节点集合：从这些节点可在不穿越故障组件的情况下到达目标节点。该方法随后确定在第一节点集合和第二节点集合的交集或其一跳的扩展中是否存在任何中间节点，并将去往目标节点的分组以隧道方式传输到隧道端点，该隧道端点包括第一和第二节点集合的交集中的节点。
Miles等人描述的解决方案可以参考图6进一步理解，图6示出了该解决方案被应用于的示例性网络图。网络包括节点P(标号10)，节点A、B、C和S(标号12、14、16、18)经由相应链路20、22、24、26附接到节点P。在节点P发生故障的情况下，充当修复节点的节点S计算除了通过故障组件之外的可到达的第一节点集合，这里称为节点S的P空间，PS(标号28)。节点S还计算从其可以在不穿越节点P的情况下到达目标节点B的节点，这里称为节点B的Q空间，BQ(标号30)。作为修复节点的节点S随后识别出PS中的节点E和QB中的节点F(标号32、34)经由链路36在彼此的一跳内。节点S随后以隧道方式经由路径38发送分组到节点E，也就是说，节点S封装分组，并附加节点E的地址作为目的地头部。为了使分组穿越链路36，节点S还向经封装分组添加“直接转发”指令以使得节点E在对分组解封装后转发到节点F，无论其到节点B的下一跳为何。一旦分组到达节点F，则根据定义，其将会经由节点B的Q空间QB中的路径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空间PS和扩展Q空间的交集中的节点。再一次参考图6，例如，作为修复节点的节点S识别出节点E’(标号42)可经由路径44到达，并且位于C的Q空间QC(标号45)中。分组随后经由路径44跨过Q空间QC被转发到节点F’(标号46)，节点F’也落在B的Q空间QB中，并且从节点F’分组经由路径48被转发到节点B。
Miles等人和Swallow等人的方案可以针对节点和链路故障实现。在链路故障的情况下，提出了各种解决方案来避免修复节点和经由故障链路连接到修复节点的节点邻居之间的环回，并且这些方案可以实现冲突修复策略，也就是说，在链路26的故障的情况下实现在图6的节点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 Apparatusfor Forwarding Data in a Data Communications Network”的同样未决的专利申请No.10/848,669(“Shand等人II”)中有所描述，这里通过引用并入该申请的全部内容，用于所有目的，就好像在这里完全记载了一样。根据Shand等人II描述的方案，修复分组被标记为被修复的以避免环回。
虽然这种系统提供了在组件故障的情况下的快速网络恢复，但P和Q空间的使用意味着在许多情形中，所选的修复路径不是最短可用修复路径。此外，在某些情形中需要诸如有向转发之类的额外的转发机制。在某些情形中需要进一步的额外的封装层，例如在使用扩展Q空间或者诸如多归属前缀(multi-homed prefix，MHP)的情况下。多次封装是不合需要的，例如由于对额外的校验和计算的需求。
这些问题中的许多问题之所以存在是因为当链路或路由器发生故障时，最初只有故障的邻居知道故障已发生。根据上述解决方案，故障由作为故障邻居的路由器修复。这些修复路由器不得不操纵分组去往其目的地，而不管网络中的大多数其他路由器不知道故障的性质和位置这一事实。
又一已知方案在编写时可以在万维网上的域“watersprings.org”的目录“pub/id”中的文件“draft-tian-ffr-alt-shortest-path-01.txt”处得到的“Fast Re-route using Alternative Shortest Paths”中有所描述。根据该文档中描述的方案，修复节点和其下一跳中的每一个计算替换最短路径作为绕过潜在邻居节点故障的修复路径，这是通过以下方式实现的：在发生这种故障的情况下识别分组的终止点，并通过从链路状态数据库中去除故障节点来计算备用最短路径。然而，该方案需要构造明确的路径，其中利用了例如源路由来将路径编码在分组自身中。
图6是示出根据已知方案的构造修复路径的方法的网络的表示；图7是示出根据本方案的构造修复路径的方法的网络的表示；图8是示出根据本方案的构造修复路径的方法的流程图；图9是根据本方案在LSP中携带的信息的示意性表示；图10是示出在不可用节点的邻居节点处构造的转发表的示图；图11是示出在不可用节点的非邻居节点处构造的转发表的示图；图12是用于实现构造修复路径的方法的节点的生成树图；图13是用于实现构造修复路径的方法的节点的递增改变的生成树图；图14是示出利用递增式SPF构造修复路径的方法的流程图；图15是示出本方案的另外的实现方式的网络的表示；图16是示出为MHP构造修复路径的方法的流程图；图17是示出本方案的另外的实现方式的网络的表示；图18是示出本方案的另外的实现方式的网络的表示。
总地来说参考图7可以理解一种用于构造修复路径的方法，图7示出了本方法所应用的示例性网络图。该网络包括主节点P(标号200)、源节点S以及节点A、B和C(标号202、204、206、208)，节点S、A、B和C各自经由相应链路210、212、214、216连接到节点P。又一节点D(标号218)经由链路220连接到节点B。除了分配给每个节点的标准地址以外，网络中的每个接口还被分配以一个额外的修复地址。在这里称之为“不经由地址”，但应意识到，这一术语是任意的、描述性的并且非限制性的。不经由地址的语义是寻址到不经由地址的分组必须被递送到具有该地址的路由器，而不经由被分配以该地址的接口上的邻居路由器。
例如，从节点P通过相应链路210、212、214、216到节点S、A、B、C的接口可以具有地址和
Figure BPA00001201116700222
类似地，沿相反方向从节点A、B、C和S分别经由链路212、214、216、210到节点P的接口具有地址
为了修复故障，修复节点(例如节点S)封装分组去往在故障远端上的节点接口的不经由地址。于是，修复路径上的节点知道它们必须向哪些节点递送分组，以及它们必须避免哪些网络组件。
参考图7，假定S具有去往某一目的地D的分组，正常情况下其将经由P和B发送，并且S怀疑P已经发生故障，则S封装分组去往
Figure BPA00001201116700224
根据语义，从S到的路径是从S到B的最短路径，该路径不经由P。如果网络包含从S到B且不经过路由器P的路径，则分组将被成功地递送到B。例如，分组可以沿着路径222被转发到节点X(224)，然后沿着路径226被转发到节点D。由于节点X已经为
Figure BPA00001201116700226
计算出修复路径，因此它将正确地转发所封装的分组。当寻址到
Figure BPA00001201116700227
的分组到达B时，B去除封装，并向其最终目的地亦即节点D转发所修复的分组。
这可以参考图8进一步理解，图8是以高级别图示这里应用的方法的流程图。在框300中，节点P利用诸如LSP之类的通知通告其邻居A、B、C、S及其关联的不经由地址
Figure BPA00001201116700228
将会意识到，充当通知节点的所有其他节点也将发出类似的LSP。结果，不仅可以构造适当的转发表，而且在每个节点发生故障或者因其他原因变为不可用节点的情况下，不经由地址还可为每个节点所用，在这种情况下不经由地址可以用作修复地址。因此在框302中，所有参与节点不仅针对每个正常(无故障)地址，还针对每个不经由地址计算其下一跳。结果，每个节点构造了绕过网络中每个其他节点的修复路径，并针对相应的不经由地址进行存储。
在框304中节点P随后发生故障或因其他原因变为不可用的情况下，则在框306中邻居节点以任何适当的方式检测到故障或者被通知以故障。在邻居节点随后接收到本来要发送向作为其下一跳的故障组件的分组的情况下，在框308中邻居节点作为修复节点，识别出修复端点或目标-其必须将该分组以隧道方式传输到该修复端点或目标以到达其后续的目的地。在以上给出的示例中，对于目的地是D的分组而言，修复节点是节点S，并且修复端点是节点B。具体而言，这是由相应的不经由地址标识的。因此，节点S在框310中沿着修复路径将分组以隧道方式传输到
Figure BPA00001201116700232
在框312中，每个下一跳将经封装的分组向不经由地址
Figure BPA00001201116700233
转发，例如图7中的节点X正确地转发分组。由于所有的参与节点都已经利用相同的修复拓扑计算出到不经由地址的路径，因此分组被利用正常的IP转发加以转发，而不需要对转发代码的扩展。在框314中，分组到达修复端点，修复端点对其进行解封装，并向其目的地(在所描述的示例中是目的地D)转发原始分组，这同样是利用正常的IP转发进行的。
因此，只需要一级封装，并且可以修复任何故障(例如即使在网络是高度不对称的时，在这种情况下Miles等人描述的P/Q空间方案理论上可能失败)。此外，实现了绕过故障的最短可用路径，同样地也不需要诸如有向转发之类的额外的转发机制。
如下面更详细地描述的，参考图8描述的方法是极其健壮的，并且可以适用于很宽范围的常见网络配置和需求。例如，该方法可以应用于故障节点或故障链路的修复，并且可以结合用于单个故障点的策略，即一个节点只提供到一邻居节点或网络的一段的连通性的情况。该方案还可以应用于多归属前缀(MHP)、共享风险群组(SRG)、局域网(LAN)以及单播和多播分组的情形。另外，该方案可以利用例如多协议标签交换(MPLS)或距离向量技术实现。另外，该方案可以实现在只有网络的所有节点的子集是被使能根据本方法构造修复路径的参与节点的情形中。
再次参考图7，将会看出为了允许网络上的每个被使能节点构造针对故障的网络组件(链路或节点)的修复拓扑，每个节点必须通告其不经由地址以及存储在其LSP中的其他相关信息。参考图9，图9是示意性地示出包含在由节点P发出的LSP中的信息的示图，将会看出除了通告每个邻居和其关联的度量(例如，与相应链路相关联的代价)以外，还提供了另外的信息。例如，在列400中提供邻居信息和在列402中提供关联度量的情况下，另外在列404中提供了每个邻居的不经由地址。不经由地址与相应邻居相关联以使得针对邻居A的条目实际上指定
Figure BPA00001201116700241
只要语义被接收到LSP的节点所承认，那么不经由地址自身就可以采取标准IP地址的形式，在这里示意性地示为代表
Figure BPA00001201116700242
等等的a.a.a.a。将会看出，由于网络中的每一节点都提供了类似的信息，因此每个节点可以导出针对网络上的每一不经由地址的修复路径。
因此，再次参考结合图7描述的示例(其中在节点P发生故障的情况下节点S将以节点D为目的地的分组封装到
Figure BPA00001201116700243
)，每一节点更一般地计算其将在任何可能的节点故障的情况下使用的路径。因此，每个节点使网络中的每一其他路由器发生故障，一次一个，并计算它自己的到该节点的每个邻居的最佳路由。换句话说，同样参考图7，某一路由器X将依次地把每个路由器看作P，使P发生故障，然后计算它自己的到由P的邻居通告的每个不经由P地址的路由，即，X计算其到和
Figure BPA00001201116700245
(在每种情况下都不经由P)的路由。
因此，参考图10(图10是示出在节点S处导出的转发表的相关部分的示图)，将会看出对于每个地址(列500)，导出了下一跳(列502)，指定了不经由地址(列504)，还实现了相应的修复地址(列506)。例如，在目的地是节点B并且下一跳被计算为节点P的情况下，那么另外，分组将被以隧道方式传输到的修复地址
Figure BPA00001201116700246
被与相应的修复下一跳存储在一起。在这种情况下，这是沿着从节点S到节点X的路径222的第一跳，在以上参考图7描述的示例中指示为沿着从节点S出发的链路230的节点Z(标号228)。在以节点D为目的地的分组的情况下，正常的下一跳是节点P，并且修复地址是
Figure BPA00001201116700251
因此对于被封装到
Figure BPA00001201116700252
的分组而言，修复下一跳再次是节点Z。在节点A作为目的地地址的情况下，下一跳是节点P，并且修复地址是这提供了某个修复下一跳Ω1(未示出)。节点S的转发表中的修复地址总是去往邻居的邻居，即修复隧道的端点。然而，将会看出，在列500中的正常地址是不经由地址(例如
Figure BPA00001201116700254
)的情况下，尽管下一跳被提供为沿着从节点S出发的链路234的节点Y(标号232)，修复地址和修复下一跳也不被提供，如下更详细所述。因此，节点S将利用正常转发将分组转发到不经由地址(当其依赖于另一节点的修复路径时)，但是在进入分组已经以不经由地址为目的地时，将不会鼓励被隧传到不经由地址的修复。
将会意识到，对于去往给定目的地的给定分组而言，在下一跳发生故障的情况下识别正确的修复地址的方法可以例如根据在节点处构造的SPT以任何适当的方式(例如Miles等人描述的方式)来确定。还将会看出，修复地址是根据接收的所有LSP导出的，并且不一定是从这样的节点导出：修复最终绕过该节点得以形成。例如，再次参考图10，在以节点B为目的地的分组的情况下，在下一跳节点P发生故障时，修复地址是这将是从节点B(而非节点P)接收到的。参考图11(图11示出了在节点X处构造的转发表的某些方面)，将会看出，构造了类似的表，其包括目的地地址字段600、下一跳字段602，为了简化，修复地址字段和修复下一跳字段未被示出，但是这些将按照与上述针对节点S相同的方式被填充。在图示的片段中，将会看出，对于目的地地址B和D而言，下一跳是某一节点Ω2(未示出)。在图示拓扑中，目的地地址
Figure BPA00001201116700256
的下一跳正好是Ω2，因为到B和D的最短路径在修复拓扑中不改变。相反地，节点P的故障可能意味着节点X对
Figure BPA00001201116700257
的下一跳也改变。因此，如下更详细地所述的，在某些情形中可以减少在正常拓扑和修复拓扑之间的改变(即，在故障组件被从修复拓扑中切除的情况下)不影响某些节点的情况下的SPF计算开销。
为了减少计算开销，尤其是确保每个节点不必为每个其他可能节点的故障计算整个SPF，存在各种可能性。首先，如果节点可以识别其不处于从另一节点到修复地址的修复路径中，则其不需要计算对于该修复地址的下一跳。将会注意到，以隧道方式被发送向修复地址的分组将只来源于绕过故障组件修复的节点，即，在故障组件的与修复地址相反的另一侧上的节点。因此，这可以通过从修复节点向其针对给定修复地址的修复路径中的每个其他节点发出信号来实现，在这种情况下接收到信号的每个节点将计算它自己的针对该修复地址的下一跳。或者，可以构建某种形式的“被发现”信令路由。例如，在节点S将分组发送向其修复下一跳(例如节点X)的情况下，如果该修复下一跳还未构造修复路径，则其将丢弃分组，然后计算它自己的修复下一跳。如果在更高级协议的控制下，S在没有从最终目的地接收到确认时重发分组，则节点X现在将把分组转发到其修复下一跳，修复下一跳也将丢弃分组但是同时构造它自己的修复下一跳。该过程继续，直到建立了修复路径为止，此时将发送确认。
根据减少SPF计算开销的第二方式，可以实现递增式SPF。这可以参考图12理解，图12示出了在节点X构造的部分SPT。X首先计算基本拓扑(这时所有路由器都是工作着的)，并确定它到所有节点地址的正常路径。例如，其对于节点B和D的下一跳是经由Ω2的，对于节点P和Y的下一跳是经由节点S(这里为了简化而忽略了节点Z)的，并且节点S对于节点A和C的下一跳是经由节点P的。
然后，节点X使路由器P故障，并执行递增式SPF。递增式SPF是本领域技术人员公知的，并且不在这里详细描述，而仅仅参考图13出于说明目的进行总结，图13示出了递增式SPT。具体而言，将会看出，节点P已被从修复拓扑中切除，结果，节点A和C重新附接到节点Y，但是节点B和D不受影响。结果，可以快速计算出与
Figure BPA00001201116700261
相对应的不经由地址。节点X对于
Figure BPA00001201116700262
和
Figure BPA00001201116700263
的下一跳仍然是节点S。然而，当节点S重新计算其SPT时，其将会鼓励节点Y作为其对
Figure BPA00001201116700264
和
Figure BPA00001201116700265
的修复下一跳。节点X对于节点B和D的下一跳不受影响，从而对于目的地B、D和
Figure BPA00001201116700266
而言，下一跳是Ω2。
结果，在先前经由P到达的所有地址被重新附接时，可以终止递增式计算。然后，节点X回复基本拓扑，并重复依次使每个路由器故障并据此导出不经由地址的过程。该算法相比于一组完全的SPF明显廉价。具体而言，尽管路由器仍然必须为N-1个故障计算修复路径，但是计算工作量远小于N-1个SPF。
该方法可以参考图14进一步理解，图14是图示了SPF的计算的流程图。在框900中，节点X构造网络中所有节点的基本拓扑。在框902中，节点X构造相应的SPT。在框904中，节点X使节点P故障，并且在框906中，节点X构造递增式SPT，将节点P从针对
Figure BPA00001201116700271
的修复拓扑中切除。在框908中，任何分离的不经由地址被与必须被重新附接的任何其他地址重新附接在一起，以允许不经由地址的重新附接，并且在框910中，在所有地址都被重新附接时计算终止。然后在框912中，转发表随后被填充以针对不经由P地址的所有下一跳，例如
Figure BPA00001201116700272
等等。在框914中，对于网络中的每个其他参与节点重复这一程序。
将会看出，这里描述的方案可以应用于节点或链路故障两种情况下。以上提供的论述尤其涉及节点故障，其中不经由地址或修复路径的构造是基于节点故障和据此导出的SPT的。然而，将会意识到，以类似的方式本发明也可以涉及链路故障。
例如，在图7的情况下，作为附加或替换，节点S和/或节点P可以基于绕过链路210的故障通告不经由地址。在这种情况下，不经由地址可以再次利用适当的语义进行通告，以使得接收节点识别出地址类型和所需的计算以获得链路修复下一跳。例如，以上参考图12到14所述的递增式SPT方案将基于修复拓扑，其中并不去除节点P(因此不去除节点P和其他节点之间的所有链路)，而是只去除节点S和P之间的链路210，并且计算递增式SPT。
假定链路而不是节点故障对某些目的地只通过故障路由器可达的情形有帮助，则希望进行尝试以修复这些目的地，这是通过假定只发生了链路故障，并利用针对节点故障计算的不经由地址尝试链路修复来实现的。
为了执行链路修复，S封装到
Figure BPA00001201116700273
(即，其指示网络不经由S将分组递送到节点修复地址P)。S的所有邻居都已经计算了在S自身发生故障的情况下到
Figure BPA00001201116700281
的路径。因此，S可以将分组给予到其邻居中的任何一个(当然，除了P)。然而，S应当优选地在最短可用路径上将经封装分组发送向P。该路径是通过在链路SP故障的情况下运行SPF而计算的。
在该链路修复是在存在节点故障的情况下(在这种情况下故障节点的其他邻居可能运行相冲突的修复策略)进行尝试的时，则环回以非常简单的方式得以避免。具体而言，如上参考图10所述，确保了对于不经由地址不提供修复路径。参考图7，如果A是P的邻居，其位于从S到P的链路修复路径上，并且P自身已发生故障，则来自S的所修复分组将到达A，并被封装到
Figure BPA00001201116700282
A将检测到AP链路已发生故障，并且将正常地尝试修复分组。然而，由于对于
Figure BPA00001201116700283
未提供修复路径，因此A将被强制丢弃分组，从而防止了环路的形成。
该方案在例如单个故障点的情形中是有利的。再次参考图7，其中在节点W(标号240)自身可以提供与网络的一个分段的连通性时，节点P只提供到节点W的连通性，另外，如果节点P发生故障，则没有网络节点可以到达节点W。因此，在节点S检测到在其到节点P的接口处的故障时，其可能希望假定只有链路210发生故障，而不是节点P。结果，S将以节点W为目的地的分组封装到
Figure BPA00001201116700284
尽管节点S理论上可以发送分组到其邻居中的任何一个，但是其最优地使用到
Figure BPA00001201116700285
的最短路径。当分组到达P时，P将剥离封装，并将分组发送向W。然而，如果P确实已发生故障，则分组将到达P的邻居(在封装中仍然寻址到
Figure BPA00001201116700286
)，并且由于该邻居没有针对不经由地址的修复路径，因此它将丢弃分组，因而避免了环路，如上所述。
还将会看出，在相等代价多路径路由(ECMP)可用或者下游路径路由可用的拓扑的情况下，则这些可以相应地实现。例如，在下游路径或无环路备用(LFA)存在的情况下，诸如节点S之类的修复节点可以在适当的情形中用其来替代不经由修复机制。类似地，路由器可以使用ECMP修复来替代不经由修复。
可以看出，这里描述的方案可以适用于很宽范围的网络配置和情形。例如，在多归属前缀(MHP)(这是一个可经由网络中的不止一个路由器到达的前缀，因而具有“多个归属”)的情况下，可以实现本方案。图15是示出包括多归属前缀Y的网络的示图。该网络包括根据以上参考图7所述的连通性的节点S、P、B和C。另外，节点S通过路径1004连接到节点Z 1000，节点B通过路径1006连接到节点V 1002。MHP Y(标号1008)附接在节点Z、P和V处。在这种情况下，当节点S发现节点P已发生故障时，其需要将寻址到Y(通常可通过P到达)的MHP分组发送向仍然能够到达Y的备用路由。
参考图16，图16是图示了在转发MHP分组中涉及到的步骤的流程图，在步骤1102中，节点S在节点P故障的情况下以上文参考图7到9所述的方式运行其递增式SPF，直到P的所有邻居和MHP Y(其将是第二近的)的实例被附接。节点S可以以任何适当方式识别何时所有的适当节点被重新附接，例如通过记录基本SPF期间的所有MHP并确保所有都被重新附接到递增式SPF。
在框1104中，节点S将分组封装到被识别为最近备用节点的前缀附接点。在这是在节点Z(S可以在不使用节点P的情况下到达节点Z)处的情况下，仍然需要封装，因为网络中的其他节点将不会知道节点P的故障，并且可能将分组环回S。因此，在框1106中，节点Z解封装分组并将其转发到节点X。将会注意到，节点Z将包括转发指令，这些转发指令确保了针对MHP Y的解封装分组必须被沿着连接链路1010转发到节点Y，以避免在仍存在经由P的较低代价路由的情况下的潜在环回。
在备用路由器是节点V(节点S经由节点P和节点B到达节点V)的情况下，节点S必须首先利用正常的不经由修复机制修复到节点B的分组。因此，节点S将针对节点Y的分组封装到当分组到达节点B时，节点B对其解封装，并且看到以MHP Y为目的地的分组。由于节点B已经确定节点P已发生故障并且将会执行与节点S相同的计算，因此其将会认识到其对于MHP Y而言的最近附接点是节点V，从而遵循与在节点S处执行的计算相同的计算并正常对其进行修复，从而将其封装到V。
在替换方案中，前缀Y可被认为附接到伪节点N，伪节点N进而又连接到节点B、V、Z中的每一个，在这种情况下，相应接口被分配以不经由地址，并且实现上述的修复路径方案。将会认识到，“伪节点”的概念是本领域技术人员公知的，并且提供了用于处理MHP和LAN的有用的拓扑发明，从而这里不需要进行详细描述。
这里描述的方法还适合于用在包含共享风险群组(SRG)的网络中，SRG是被识别为具有同时发生故障(例如由于共同的物理位置)的概率的网络组件的群组。图17是图示了包括共享风险群组的网络的示意性网络图，并且与图7共同的元件用同一标号。另外，该网络包括节点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的所有成员同时发生故障，则不经由地址的范围指示“不经由整个SRG”。换句话说，
Figure BPA00001201116700301
所有路由器计算到将SRG连接到网络的其余部分的接口的每个不经由地址的不经由路由，该计算是通过同时使单个递增式SPF中的SRG的所有成员(P、P’、P”)发生故障而进行的。为了识别SRG，每个节点保持属于相应SRG的网络中的节点的记录。
然后，当与SRG成员相邻的路由器进行修复时，其将分组封装到具有从SRG到目的地的最低代价路由的路由器的不经由地址。例如参考图17，在S接收到以节点H为目的地的分组(正常情况下该分组将经由节点P和C转发)的情况下，在检测到SRG的故障时，节点S将经由适当的连通性(未示出)将分组封装到节点
Figure BPA00001201116700302
类似地，节点S将把针对节点J的分组封装到等等。
还将会注意到，除了创建针对SRG群组的不经由地址以外，也可以针对群组的每个成员形成个别不经由地址。例如，这可以用在首先是有益的时候，例如在群组的成员包括单个故障点的情况下。以与用于链路故障保护相同的方式避免了环回，这是因为对于邻居不经由地址不存储修复路径。
还将会看出，这里描述的方案可以结合参考图18的局域网实现，图18是图示了LAN的网络图。节点S 1300连接到伪节点N(1302)，节点N自身连接到LAN的成员，节点P(1304)、节点P’(1306)和P”(1308)。节点P连接到节点B(1310)。LAN可被视作SRG的特殊情形，从而针对LAN的所有成员(这里称为L)的故障创建不经由地址。然后节点S可以为流量提供修复路径，对于该流量而言其具有避免了L的替换路径。如果L能够测试LAN的成员(在这种情况下其只能针对LAN上已知的故障节点使用不经由地址)，则可以采用更复杂的方案。与SRG计算一样，只需要单个递增式SPF来计算用于群组L的不经由修复路径。
当S发现其丢失了到P的连通性时，其并不确定故障是其自己的到LAN的接口，是LAN自身，是P的LAN接口还是节点P。在不进行进一步诊断的情况下，S必须修复通过P和B发送的流量，以不经由P、N(即，不经由P且不经由N)发送向B，其保守假设是整个LAN和P都已发生故障。P是单个故障点的目的地必须照常利用避免了某一接口的地址发送向P，通过该接口P可从S到达(即，不经由N到P)，对于路由器P’和P”类似。连接到LAN的每个路由器必须照常针对每个邻居通告一不经由地址。另外，LAN上的每个路由器必须通告不经由伪节点(N)的额外地址。另外，连接到LAN的路由器的每个邻居必须通告两个不经由地址，照常的一个不经由该邻居，而另一个不经由该邻居或伪节点，如果这种程度的连通性已经通过使用点对点链路而实现，那么比起其他情况下其将通告的来，正好多一个地址。如上所述，为了明确地诊断故障网络组件，S将来自P的连通性报告和LAN上的其他路由器中的一个或多个(在这种情况下是P’和P”)关联起来。如果其仅仅丢失了到P的连通性，则可以推断出LAN仍然在工作，并且故障发生在P处，或将P连接到LAN的接口处。然后，其将按通常方式修复B而不经由P(并且对于P是单个故障点的目的地而言，P不经由N)。如果S丢失了到LAN上的不止一个路由器的连通性，其可以推断出故障只发生在LAN处，并且可以修复到P、P’和P”而不经由N，这同样是按通常方式进行的。如果S发生故障，则路由器A需要能够修复到LAN上的每一路由器而不经由S，这是利用不经由S地址的集合按通常方式实现的。提供了较低的故障后连通性但是使用较少地址的替换方案是将LAN和其所有的连接路由器看作是单个SRG。从而，不经由LAN的地址P(P1)将要求不经由连接到LAN的任何路由器到达P。在这种情况下，当S检测到P已经发生故障时，S会将经由P和B到达的流量发送向B，而不经由LAN或附接到LAN(即，附接到B1)的任何路由器。任何只能通过P到达的目的地都将被寻址到P，而不经由LAN或附接到LAN的任何路由器(当然除了P)。
该方案同样可结合另外的实现方式使用。例如在多播分组的情况下，多播流量按与单播类似的方式加以修复。然而，多播转发器能够使用多播分组被寻址到的不经由地址作为预期接收器接口的指示，从而正确地运行所需的反向路径转发(RPF)检查。
此外，可以采用这样的技术，例如在某一节点的前一节点处剥离隧道头部，然后该节点将把未经封装的分组转发到期望修复端点。该方案在Michael Shand等人于2003年7月15日提交的题为“Method and Apparatusfor Forwarding a Tunneled Packet in a Data Communications Network”的同样未决的专利申请No.10/620,866(“Shand等III”)中有所描述，这里通过引用并入该申请的全部内容，用于所有目的，就好像在这里完全记载了一样。
还将会看出，这里描述的方法可以结合替换的路由协议或转发范例实现。一种这样的范例是MPLS(多协议标签交换)。MPLS是一种对于本领域技术人员来说公知的协议，并且在文档“Multi Protocol LabelSwitching Architecture”中有所描述，该文档可以在万维网上的域“ietf.org”的目录“rfc”中的文件“rfc3031.txt”处得到。根据MPLS，建立用于源-目的地对的完整路径，并且用于在路径中的相邻路由器之间转发分组以及头部或“标签”所需的值被前插到分组上。标签将分组引导至正确的接口和下一跳。标签在IP或其他头部之前从而允许更小的外出头部。
用于源-目的地对的路径(称为标签交换路径，LSP)可以根据各种不同的方案建立。一种这样的方案是标签分发协议(LDP)，其中路径中的每个路由器将其标签发送到路径上根据其IP路由表确定的下一跳路由器。或者，可以调用资源预留协议(RSVP)，在这种情况下，例如网络管理员可以管理路径，从而提供了严格的源路由。具体而言，LDP将按通常方式分发用于不经由地址的标签。因此，不经由修复机制可以用于提供MPLS网络中的修复路径，这是通过首先推入修复点用来转发分组的标签，然后推入与实现修复所需要的不经由地址相对应的标签而实现的。例如，参考图7，在节点S有以节点D为目的地的分组(节点D正常情况下经由节点P和B到达)的情况下，在节点P已发生故障时，节点S首先推入B针对D的标签，然后推入其到(节点X)的下一跳到达
Figure BPA00001201116700332
所需的标签，即[Bd，NBp]。同样地，不经由地址已被传播并且被认识，因此该方案被简单地实现。将会注意到，节点S需要节点B针对D的标签，BD。这可以按任何适当的方式实现，例如有向LDP会话。为了获得所有适当的标签，节点S可以与节点P的邻居中的每一个(在节点修复的情况下)或所有的出口路由器(在SRG的情况下)执行有向LDP会话。在链路修复的情况下，节点S将已经具有节点P针对D的标签，PD，因为P是邻居节点。当然，可以采用任何适当的用于获得修复点针对目的地节点的标签的方式，例如Swallow等人描述的任何适当的方案。
或者，该方案同样可以利用诸如距离或路径向量之类的路由向量协议实现，其中通告节点向所有其他节点通告其到目的地的完整路由或向量。在这种情况下，节点P实际上通过忽略针对其每个邻居
Figure BPA00001201116700333
Figure BPA00001201116700334
的向量来通告其不经由地址。结果，如果P发生故障，则在任何节点处都没有任何关于在任何情况下如何经由P到达B的信息，因此其实际上具有经由另一节点选择的不经由路由。结果，所有节点将计算不穿过节点P的路由。
还将会看出，所述方法可以跨网络实现，其中所有路由器都能够计算不经由地址并因而充当参与节点，其中只有路由器的一部分被启用或者其中某些路由器被部分启用。在所有路由器都被启用并且具有修复地址能力的情况下，很清楚该方法可以非常简单地按上述方式实现。在某些路由器被启用而其他路由器不被启用的情况下，当计算不经由路径时，未被启用的节点被从基本拓扑中去除。结果，所计算的到不经由地址的任何一条路由都不会尝试穿过未被启用的节点，从而未被启用的节点将不会接收到它们未被配备来进行处理的不经由地址。路由器可能被部分启用，例如以使得它们能够自己导出修复路径，并因而接收分组并正确地转发分组到不经由地址，而不是它们自己充当执行上述的封装和转发步骤的邻居路由器。在这种情况下，部分启用的路由器可以被包括在修复拓扑中，但是它们自身不能鼓励修复。
这里描述的方法被实现的方式(其中软件、固件、硬件或其任意组合并且具有任何适当的代码改变)对于本领域技术人员来说是清楚的，这里不需要进行详细描述。例如，对诸如内部网关协议(IGP)之类的通信协议的扩展可能需要扩展。具体而言，直接连接到受保护的网络组件的每个被启用的路由器将通告针对该组件的不经由地址，通告方式使得受保护组件和不经由地址之间的关联可以由网络中的其他路由器确定，如上所述。此外，被启用的路由器可以通告其用于计算并实现IGP中的不经由路由的能力以及它们支持的封装类型，例如IP in IP、GRE、L2TPv3，所有这些都是本领域技术人员公知的。
被分配为不经由地址的地址可以是例如从网络的私有地址空间取得的任何适当的地址。任何适当的封装都可用于携带不经由修复，例如IP inIP、GRE或L2TPv3。类似地，可以采用任何备用封装方案，只要封装路由器和被封装分组作为修复点寻址到的路由器具有处理所选的封装类型的常见能力即可。
作为上述方案的结果，应用了一种简单的过程，根据该过程，只需要单级封装，并且由于所有节点实际上都计算最短修复路径，因此其提供了针对任何故障的最短修复路径。此外，将会看出，解封装分组可以“返回”，即被转发到其已经经由隧道到达但是仍然利用正常转发加以转发的一个或多个节点，而不向目的地环回，这是因为修复点离目的地更近。

Claims (8)

1.一种由计算机实现的用于构造修复路径的方法，包括：
发起用于为第一网络节点和第二网络节点之间的第一链路创建和存储修复路径信息的不经由方案；
创建和存储形成从所述第一网络节点到所述第二网络节点的不经由第一链路修复路径的不经由第一链路修复路径网络节点的列表，
其中所述不经由第一链路修复路径穿过所述不经由第一链路修复路径网络节点，
其中所述不经由第一链路修复路径不穿过所述第一网络节点和所述第二网络节点之间的第一链路；
在转发信息库FIB中创建和存储条目，所述条目标识所述第一网络节点的修复地址并且使得(a)想去往所有通常通过所述第一链路可达的地址的分组被封装到所述第二网络节点而不经由所述第一网络节点，(b)想去往通常通过所述第一链路可达的不经由地址的分组被封装到所述第二网络节点而不经由所述第一网络节点，并且(c)当通常通过所述第一链路可达的不经由地址在所述列表中时丢弃想去往该不经由地址的分组；
对于所述第一网络节点的所有其他链路重复前述发起、创建和存储列表和创建和存储条目的步骤。
2.如权利要求1所述的方法，还包括：
根据所述FIB中的条目确定一对或多对相互不兼容的链路故障；
利用路由协议，将所述一对或多对作为次级共享风险链路群组来加以通告。
3.如权利要求1所述的方法，还包括：
确定发生了所述第一链路和第二链路的同时故障；
确定针对所述第一链路的第一修复路径穿过所述第二链路，并且针对所述第二链路的第二修复路径穿过所述第一链路；
确定分组丢弃计数大于指定的阈值，针对重收敛正在使用抑制步骤，并且正在使用无环路收敛机制；
响应于确定分组丢弃计数大于指定的阈值，向实现路由协议的逻辑发送“放弃所有希望”通知，用于强制正常重收敛开始。
4.如权利要求1所述的方法，还包括：
为每个邻居节点确定每个修复路径所穿过的节点对的列表；
执行以每个对的第一网络节点为根的最短路径优先SPF计算，其中去除了到第二网络节点的链路；
确定所得到的链路是否包括所述第一链路。
5.一种由计算机实现的用于构造修复路径的设备，包括：
用于发起用于为第一网络节点和第二网络节点之间的第一链路创建和存储修复路径信息的不经由方案的装置；
用于创建和存储形成从所述第一网络节点到所述第二网络节点的不经由第一链路修复路径的不经由第一链路修复路径网络节点的列表的装置，
其中所述不经由第一链路修复路径穿过所述不经由第一链路修复路径网络节点，
其中所述不经由第一链路修复路径不穿过所述第一网络节点和所述第二网络节点之间的第一链路；
用于在转发信息库FIB中创建和存储条目的装置，所述条目标识所述第一网络节点的修复地址并且使得(a)想去往所有通常通过所述第一链路可达的地址的分组被封装到所述第二网络节点而不经由所述第一网络节点，(b)想去往通常通过所述第一链路可达的不经由地址的分组被封装到所述第二网络节点而不经由所述第一网络节点，并且(c)当通常通过所述第一链路可达的不经由地址在所述列表中时丢弃想去往该不经由地址的分组；
用于对于所述第一网络节点的所有其他链路重复前述发起、创建和存储列表和创建和存储条目的装置。
6.如权利要求5所述的设备，还包括，
用于根据所述FIB中的条目确定一对或多对相互不兼容的链路故障的装置；
用于利用路由协议，将所述一对或多对作为次级共享风险链路群组来加以通告的装置。
7.如权利要求5所述的设备，还包括：
用于确定发生了所述第一链路和第二链路的同时故障的装置；
用于确定针对所述第一链路的第一修复路径穿过所述第二链路，并且针对所述第二链路的第二修复路径穿过所述第一链路的装置；
用于确定分组丢弃计数大于指定的阈值，针对重收敛正在使用抑制步骤，并且正在使用无环路收敛机制的装置；
用于响应于确定分组丢弃计数大于指定的阈值，向实现路由协议的逻辑发送“放弃所有希望”通知，用于强制正常重收敛开始的装置。
8.如权利要求5所述的设备，还包括：
用于为每个邻居节点确定每个修复路径所穿过的节点对的列表的装置；
用于执行以每个对的第一网络节点为根的最短路径优先SPF计算的装置，其中去除了到第二网络节点的链路；
用于确定所得到的链路是否包括所述第一链路的装置。
CN200980105263.6A 2008-02-15 2009-02-09 在数据通信网络中构造绕过多条不可用链路的修复路径 Expired - Fee Related CN101953124B (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US12/032,274 2008-02-15
US12/032,274 US7852751B2 (en) 2008-02-15 2008-02-15 Constructing repair paths around multiple non-available links in a data communications network
PCT/US2009/033601 WO2009102673A1 (en) 2008-02-15 2009-02-09 Constructing repair paths around multiple non-available links in a data communications network

Publications (2)

Publication Number Publication Date
CN101953124A CN101953124A (zh) 2011-01-19
CN101953124B true CN101953124B (zh) 2014-06-11

Family

ID=40474801

Family Applications (1)

Application Number Title Priority Date Filing Date
CN200980105263.6A Expired - Fee Related CN101953124B (zh) 2008-02-15 2009-02-09 在数据通信网络中构造绕过多条不可用链路的修复路径

Country Status (4)

Country Link
US (1) US7852751B2 (zh)
EP (1) EP2260620B1 (zh)
CN (1) CN101953124B (zh)
WO (1) WO2009102673A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106797349A (zh) * 2014-08-18 2017-05-31 思科技术公司 用于动态vnf的动态级联聚类

Families Citing this family (40)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2010018755A1 (ja) * 2008-08-11 2010-02-18 株式会社日立製作所 トランスポート制御サーバ、ネットワークシステム及びトランスポート制御方法
WO2010055408A1 (en) * 2008-11-17 2010-05-20 Telefonaktiebolaget L M Ericsson (Publ) A system and method of implementing lightweight not-via ip fast reroutes in a telecommunications network
US8570860B2 (en) * 2008-12-03 2013-10-29 Micron Technology, Inc. Redundant signal transmission
US8629913B2 (en) * 2010-09-30 2014-01-14 Apple Inc. Overflow control techniques for image signal processing
CN102291311B (zh) * 2011-08-30 2017-03-29 中兴通讯股份有限公司 以太网接口保护方法及网络侧设备
US8934335B2 (en) * 2011-08-30 2015-01-13 Verizon Patent And Licensing Inc. System and method for enhancing loop free alternative coverage
US20140330920A1 (en) * 2011-12-09 2014-11-06 Mingchao Shao Discovering forwarding information for local repair
US8792360B2 (en) 2012-04-30 2014-07-29 Fujitsu Limited Duplicate packet suppression
US8953882B2 (en) 2012-05-31 2015-02-10 Apple Inc. Systems and methods for determining noise statistics of image data
US9332239B2 (en) 2012-05-31 2016-05-03 Apple Inc. Systems and methods for RGB image processing
US9031319B2 (en) 2012-05-31 2015-05-12 Apple Inc. Systems and methods for luma sharpening
US11089247B2 (en) 2012-05-31 2021-08-10 Apple Inc. Systems and method for reducing fixed pattern noise in image data
US9142012B2 (en) 2012-05-31 2015-09-22 Apple Inc. Systems and methods for chroma noise reduction
US8917336B2 (en) 2012-05-31 2014-12-23 Apple Inc. Image signal processing involving geometric distortion correction
US8817120B2 (en) 2012-05-31 2014-08-26 Apple Inc. Systems and methods for collecting fixed pattern noise statistics of image data
US9014504B2 (en) 2012-05-31 2015-04-21 Apple Inc. Systems and methods for highlight recovery in an image signal processor
US9743057B2 (en) 2012-05-31 2017-08-22 Apple Inc. Systems and methods for lens shading correction
US9105078B2 (en) 2012-05-31 2015-08-11 Apple Inc. Systems and methods for local tone mapping
US9025867B2 (en) 2012-05-31 2015-05-05 Apple Inc. Systems and methods for YCC image processing
US8872946B2 (en) 2012-05-31 2014-10-28 Apple Inc. Systems and methods for raw image processing
US9077943B2 (en) 2012-05-31 2015-07-07 Apple Inc. Local image statistics collection
US9455903B2 (en) 2012-07-31 2016-09-27 Cisco Technology, Inc. Recording packet routes using bloom filters
US9007892B2 (en) * 2012-10-26 2015-04-14 Futurewei Technologies, Inc. Apparatus and method to find partially disjoint routes for dual fiber-cuts
US9438472B2 (en) * 2013-07-19 2016-09-06 Telefonaktiebolaget Lm Ericsson (Publ) Extended remote LFA fast reroute
US10015073B2 (en) * 2015-02-20 2018-07-03 Cisco Technology, Inc. Automatic optimal route reflector root address assignment to route reflector clients and fast failover in a network environment
US10382301B2 (en) * 2016-11-14 2019-08-13 Alcatel Lucent Efficiently calculating per service impact of ethernet ring status changes
US10348610B2 (en) * 2017-05-25 2019-07-09 Alcatel Lucent Method and apparatus for minimum label bandwidth guaranteed path for segment routing
CN109587057B (zh) * 2018-12-06 2020-12-22 中通天鸿（北京）通信科技股份有限公司 一种信息传输平台的智能路由方法及系统
US10999366B2 (en) * 2019-03-10 2021-05-04 Mellanox Technologies Tlv Ltd. Mirroring dropped packets
CN110247826B (zh) * 2019-07-10 2022-03-25 上海理工大学 一种点对点网络连通性测试方法
CN113810275B (zh) * 2020-06-17 2023-08-04 华为技术有限公司 发送报文的方法及设备
CN112073226A (zh) * 2020-08-26 2020-12-11 内蒙古智诚物联股份有限公司 一种基于5g技术下的ip网络恢复方法及装置
CN112433997B (zh) * 2020-11-20 2023-07-04 上海哔哩哔哩科技有限公司 数据修复方法及装置
US11552882B2 (en) * 2021-03-25 2023-01-10 Mellanox Technologies, Ltd. Efficient propagation of fault routing notifications
CN115468572A (zh) * 2021-06-11 2022-12-13 华为技术有限公司 路径规划方法及相关设备
CN113726646B (zh) * 2021-08-25 2022-10-18 烽火通信科技股份有限公司 一种分段路由的快速保护倒换方法及装置
CN113630472A (zh) * 2021-09-13 2021-11-09 东软集团股份有限公司 避免网络节点间通道浪费的方法、装置、电子设备及介质
CN114844708B (zh) * 2022-05-07 2024-06-18 长三角信息智能创新研究院 基于流量重路由链路泛洪攻击缓解方法、设备及存储介质
CN115277534B (zh) * 2022-09-26 2023-01-06 安徽华云安科技有限公司 链路构建方法、电子设备及计算机可读存储介质
CN116541262B (zh) * 2023-07-07 2024-03-01 腾讯科技（深圳）有限公司 一种数据处理方法、装置、设备以及可读存储介质

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101099086A (zh) * 2005-02-22 2008-01-02 思科技术公司 用于在数据通信网络中构造绕过不可用组件的修复路径的方法和装置

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7322143B2 (en) * 2003-02-14 2008-01-29 Rohrbaugh Firearms Corp. Semiautomatic handgun
US7330440B1 (en) 2003-05-20 2008-02-12 Cisco Technology, Inc. Method and apparatus for constructing a transition route in a data communications network
US7508755B2 (en) * 2003-07-07 2009-03-24 Alcatel-Lucent Usa Inc. Methods and devices for creating an alternate path for a bi-directional LSP
US7428213B2 (en) 2003-11-21 2008-09-23 Cisco Technology, Inc. Method and apparatus for determining network routing information based on shared risk link group information
US7697416B2 (en) 2006-09-08 2010-04-13 Cisco Technolgy, Inc. Constructing a repair path in the event of non-availability of a routing domain
US7583589B2 (en) 2007-03-15 2009-09-01 Cisco Technology, Inc. Computing repair path information
DE102007043052A1 (de) 2007-09-11 2009-03-12 Giesecke & Devrient Gmbh Optisch variables Sicherheitselement

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101099086A (zh) * 2005-02-22 2008-01-02 思科技术公司 用于在数据通信网络中构造绕过不可用组件的修复路径的方法和装置

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
ATLAS A 等.IETF STAND-WORKING-DRAFT, INTERNET　ENGINEERING TASK FORCE, IETF.《Basic Specification for IP Fast-Reroute: Loop-free Alternates *
BRYANT INTERNET DRAFT M SHAND S PREVIDI.IETF STAND-WORKING-DRAFT, INTERNET ENGINEERING TASK FORCE, IETF,.《IP Fast Reroute Using Not-via Addresses *
draft-ietf-rtgwg-ipfrr-notvia-addresses-01.txt》.2007,第6页-第10页. *
draft-ietf-rtgwg-ipfrr-spec-base-06.txt》.2007,全文. *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106797349A (zh) * 2014-08-18 2017-05-31 思科技术公司 用于动态vnf的动态级联聚类
CN106797349B (zh) * 2014-08-18 2021-04-30 思科技术公司 用于动态vnf的动态级联聚类

Also Published As

Publication number Publication date
WO2009102673A1 (en) 2009-08-20
US20090207728A1 (en) 2009-08-20
US7852751B2 (en) 2010-12-14
CN101953124A (zh) 2011-01-19
EP2260620A1 (en) 2010-12-15
EP2260620B1 (en) 2016-02-03

Similar Documents

Publication Publication Date Title
CN101953124B (zh) 在数据通信网络中构造绕过多条不可用链路的修复路径
CN101099086B (zh) 用于在数据通信网络中构造绕过不可用组件的修复路径的方法和装置
US8842522B2 (en) Incremental deployment of MRT based IPFRR
US8134917B2 (en) Automatic protection switching using link-level redundancy supporting multi-protocol label switching
Shand et al. IP fast reroute framework
TWI586131B (zh) 使用標籤分配協定之多重協定標籤交換技術快速重路由（ｌｄｐ－ｆｒｒ）
US9350639B2 (en) Forwarding data in a data communications network
CN1969492B (zh) 动态转发邻接关系
US7042838B1 (en) Method and apparatus for forwarding data in a data communications network
US8665711B2 (en) Fast restoration for provider edge node and access link failures
US7936667B2 (en) Building backup tunnels for fast reroute in communications networks
US7885179B1 (en) Method and apparatus for constructing a repair path around a non-available component in a data communications network
WO2013045083A1 (en) Optimizing endpoint selection of mrt-frr detour paths
CN103891220A (zh) 使用ldp的mpls快速重新路由(ldp-frr)
US7969898B1 (en) Technique for breaking loops in a communications network
CN111885630B (zh) 数据传输方法及通信装置
EP2649758B1 (en) Minimizing the number of not-via addresses
Lin et al. Redirection based recovery for MPLS network systems

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20140611

Termination date: 20220209