基于快速洪泛的快速收敛以从网络故障恢复

摘要

路由器检测到网络故障，并且响应该故障，将快速故障通知消息从路由器的接口的某个集合洪泛出。快速故障通知消息包括识别网络故障的信息，并且包括被指派到与检测到的网络故障耦合并且不是路由器的该组接口的一部分的接口的MAC（媒体访问控制）地址作为其源MAC地址。路由器更新路由选择表以反映网络故障。快速故障通知消息的洪泛在完成路由选择表更新以反映网络故障之前被执行。

说明书

对相关申请的交叉引用

本申请要求2011年2月28日提交的美国临时专利申请No. 61/447669、2010年10月25日提交的美国临时专利申请No. 61/406420和2010年9月29日提交的美国临时专利申请No. 61/387511的优先权，这些申请各自通过引用被结合于本文中。

技术领域

本发明的实施例涉及连网领域，并且更具体地说，涉及从网络故障的快速收敛。

背景技术

快速从网络故障恢复的能力是最受追求的网络特性之一。很少有解决方案令人满意地解决此问题。一个此类解决方案是RFC（请求注解）5714中描述的IP快速重新路由(IPFRR)。IPFRR模仿MPLS-FRR（多协议标签交换快速重新路由）的解决方案，不同之处是MPLS-FRR是基于路径的或换而言之是基于源路由选择的。这暗示重新路由判定能够由PLR（本地修复点）路由器独自执行，而无需网络中其它LSR（标签交换路由器）的协作。然而，基于IP的FRR就其本质而言不是基于源路由选择的。因此，其重新路由判定可能得不到网络中其它路由器的重视，这能够导致严重的后果，如业务停止或路由选择环路。

围绕IPFRR概念已提议了几种方法。一种方法是RFC 5286中描述的LFA（无环替代）。LFA方案要求大量的计算，并且具有覆盖问题。另一种方法是2010年10月21日的IETF草案“draft-ietf-rtgwg-ipfrr-notvia-address-06”中描述的非通路(Not-Via)。非通路方案复杂，并且成本高而难以有用。从RFC 5714的以下段落明白围绕IPFRR概念提议的方案中困难的主要原因：第一段，第1部分：“然而，存在一种备选方案，该方案要计算允许故障由检测到故障的路由器在本地修复的备份路由，不急需向其它路由器通知故障。”。叙述“不急需向其它路由器通知故障”违反了域范围的同步是关键的IP网络的性质。

通常，在普通链路状态路由选择操作中，在路由器检测到链路故障或其它网络中断时，路由器将通知洪泛到所有其周围近邻路由器，这些路由器在进行一定处理（例如更新路由选择和/或转发表）后，将信息传播到更远的其它路由器，直至每个路由器得以更新和同步。此洪泛机制是缓慢的，要相当长的时间完成，并且取决于网络结构和大小。

发明内容

描述了一种基于快速洪泛的快速收敛架构。在一个实施例中，用于快速故障通知消息的输送机制是基于桥接的。用于发起基于桥接的基于快速洪泛的快速收敛的路由器检测到网络故障，并且响应该故障，将快速故障通知消息从路由器的一个或多个接口的集合洪泛出。快速故障通知消息包括识别网络故障的信息，并且包括被指派到与检测到的网络故障耦合并且不是路由器的该组接口的一部分的接口的MAC（媒体访问控制）地址作为其源MAC地址。路由器更新路由选择表以反映网络故障。快速故障通知消息的传送在完成路由选择表更新以反映网络故障之前被执行。在一个实施例中，快速故障通知消息向接收路由器指示在它确定是否更新其路由选择表之前，它要在其数据传输层中确定是否将该快速故障通知消息从其接口的一个或多个接口的集合洪泛出。在一个实施例中，用于基于桥接的快速洪泛的发起路由器包括数据传输层和应用层。数据传输层包括快速故障通知(FFN)模块，该模块配置成响应检测到的网络故障，将快速故障通知消息从其接口的一个或多个接口洪泛出。应用层包括路由选择协议模块，该模块配置成响应检测到的网络故障而更新路由选择表。

描述了一种用于接收基于桥接的快速故障通知消息的路由器。响应在接口上接收快速故障通知消息，以及响应确定快速故障通知消息的源MAC地址与接口不相关联，路由器将源MAC地址和接口对添加到路由器的桥MAC表，将快速故障通知消息洪泛到一个或多个其它接口以便传输到一个或多个其它路由器，以及更新路由选择表以反映网络故障。快速故障通知消息的洪泛在完成更新路由选择表以反映网络故障的步骤之前被执行。在一个实施例中，用于基于桥接的快速洪泛的接收路由器包括数据传输层和应用层。应用层包括路由选择协议模块，该模块配置成管理路由选择表。数据传输层包括存储MAC地址和接口的关联的桥MAC表和FFN模块，FFN模块配置成响应接收的快速故障通知消息和响应确定其源MAC地址与其中接收了消息的接口不相关联，将源MAC地址与该接口相关联，将快速故障通知消息洪泛到一个或多个其它接口，以及将快速故障通知消息发送到路由选择协议模块以更新路由选择表，从而反映网络故障。在路由选择协议模块完成路由选择表的其更新前，FFN模块洪泛快速故障通知消息。

在一个实施例中，用于快速故障通知消息的输送机制是经使用生成树协议(STP)的第2层桥接网络。发起基于快速洪泛的快速收敛的路由器检测到网络故障，并且响应该故障，将第2层快速故障通知消息从一个或多个接口洪泛出，并且更新其路由选择表以反映网络故障。快速故障通知消息包括识别网络故障的信息，并且向接收快速故障通知消息的路由器指示，独立于更新其路由选择表以反映网络故障，将快速故障通知消息从STP未阻塞的其接口洪泛出。在一个实施例中，路由器包括数据传输层和应用层。数据传输层包括快速故障通知(FFN)模块，该模块配置成响应检测到的网络故障，将第2层快速故障通知消息从其接口的一个或多个接口洪泛出。应用层包括路由选择协议模块，该模块配置成响应检测到的网络故障而更新路由选择表。

也描述了一种用于接收和响应第2层桥接网络中接收的快速故障通知消息的路由器。路由器接收包括识别网络故障的信息的快速故障通知消息。路由器将快速故障通知消息从STP未阻塞的一个或多个其接口洪泛出，并且更新路由选择表以反映网络故障。在完成路由选择表的更新以反映网络故障前，路由器洪泛快速故障通知消息。在一个实施例中，路由器包括数据传输层和应用层。应用层包括路由选择协议模块，该模块配置成管理路由选择表。数据传输层包括FFN模块，该模块配置成响应接收快速故障通知消息，将该消息从STP未阻塞的一个或多个接口洪泛出，以及将该消息发送到应用层上的路由选择协议模块以更新路由选择表，从而反映网络故障。

在一个实施例中，用于快速故障通知消息的输送机制是基于单播的。路由器检测到网络故障，并且响应该故障，将包括识别网络故障的信息的快速故障通知消息传送到与路由器在相同域中的每个其它路由器，并且更新路由选择表以反映网络故障。独立于更新路由选择表以反映网络故障，快速故障通知消息被传送到那些路由器。在一个实施例中，路由器包括数据传输层和应用层。应用层包括路由选择协议模块，该模块配置成更新路由选择表。数据传输层包括FFN模块，该模块配置成响应检测到的网络故障，将快速故障通知消息传送到与路由器在相同域中的每个其它路由器。

还描述了一种用于接收和响应基于单播的快速故障通知消息。在一个实施例中，路由器接收包括识别网络故障的信息的快速故障通知消息，绕过用于快速故障通知消息的邻接检查；以及更新路由选择表以反映网络故障。在一个实施例中，路由器包括配置成接收和发送单播快速故障通知消息到路由选择协议模块的接口，路由选择协议模块绕过用于那些快速故障通知消息的邻接检查，并且更新路由选择表以反映快速故障通知消息中的网络故障。

在一个实施例中，用于快速故障通知消息的输送机制是基于多播的。路由器检测到网络故障，并且响应该故障，将快速故障通知消息传送到多播组地址。快速故障通知消息包括识别网络故障的信息，并且还向已加入多播组并且将接收快速故障通知消息的多个路由器的每个路由器指示，独立于该路由器更新其路由选择表，确定是否将快速故障通知消息多播到其接口。路由器也更新路由选择表以反映网络故障。独立于更新路由选择表以反映网络故障，路由器传送快速故障通知消息。在一个实施例中，路由器包括数据传输层和应用层。应用层包括路由选择协议模块，该模块配置成响应检测到的网络故障而更新路由选择表。数据传输层包括FFN模块，该模块配置成响应检测到的网络故障，将快速故障通知消息传送到多播组地址。

还描述了一种用于接收和响应基于多播的快速故障通知消息。在一个实施例中，路由器在接收快速故障通知消息时执行RPF（反向路径转发）检查。路由器加入多播组并且接收寻址到与多播组相关联的地址的快速故障通知消息。响应确定其上接收了快速故障通知消息的接口是与路由器用于到达快速故障通知消息的源路由器的相同接口，路由器将消息多播到至少一个其它接口。路由器更新路由选择表以反映网络故障。在完成路由选择表更新前，路由器多播快速故障通知消息。在一个实施例中，路由器包括数据传输层和应用层。数据传输层包括FFN模块，该模块配置成响应接收快速故障通知消息，以及响应确定其上接收了该消息的接口是与用于到达该消息的源路由器的相同接口，将该消息多播到其接口的其它接口，并且将该消息发送到应用层上的路由选择协议模块以更新路由选择表。

在一个实施例中，在多播快速故障通知消息时，接收基于多播的快速故障通知消息的路由器使用最短路径优先(SPF)树(SPT)。路由器将相同网络中的多个路由器之一选择为SPT的根节点，并且使用当前网络拓扑构建SPT。路由器加入多播组并且接收寻址到与多播组相关联的地址的快速故障通知消息。路由器根据SPT多播快速故障通知消息，并且更新路由选择表以反映快速故障通知消息中指示的网络故障。在完成更新路由选择表之前，路由器根据SPT多播快速故障通知消息。在一个实施例中，路由器包括应用层和数据传输层。数据传输层包括SPT和FFN模块，FFN模块配置成响应接收快速故障通知消息，根据SPT来多播该消息，并且将该消息发送到应用层上的路由选择协议模块以更新路由选择表，从而反映网络故障。

在一个实施例中，接收基于多播的快速故障通知消息的路由器使用双向多播树，双向多播树使用PIM（协议独立多播）协议实现来构建。路由器使用PIM来构建双向树并且加入多播组。路由器接收寻址到与该多播组相关联的地址并且包括识别网络故障的信息的快速故障通知消息，根据双向多播树来多播该消息，以及更新路由选择表以反映网络故障。在完成路由选择表的更新之前，路由器根据双向多播树多播快速故障通知消息。在一个实施例中，路由器包括应用层和数据传输层。数据传输层包括使用PIM所构建的双向多播树和FFN模块，FFN模块配置成响应接收快速故障通知消息，根据双向多播树多播该消息，并且将快速故障通知消息发送到应用层上的路由选择协议模块以更新路由选择表。

附图说明

通过参照下面的描述和用于示出本发明实施例的附图，可最好地理解本发明。在图中：

图1示出根据一个实施例在网络中的路由器中包含的基于快速洪泛的快速收敛(FFFC)架构；

图2示出根据一个实施例的使用快速故障通知应用的示范网络，该应用使用FFFC架构；

图3是根据一个实施例的示出由检测网络故障的路由器为发起域范围的FFFC而执行的示范操作的流程图；

图4是根据一个实施例的示出由接收快速故障通知消息的路由器执行的示范操作的流程图；

图5示出根据一个实施例的使用基于桥接的洪泛来散布快速故障通知的示范网络；

图6是根据一个实施例的示出由检测到网络故障的路由器为使用基于桥接的快速故障通知消息洪泛来发起域范围的FFFC而执行的示范操作的流程图；

图7是根据一个实施例的示出由在使用基于桥接的快速故障通知消息的FFFC架构中接收快速故障通知消息的路由器执行的示范操作的流程图；

图8是根据一个实施例的示出在第2层桥接网络中已检测到网络故障的路由器上为使用基于STP（生成树协议）的洪泛来发起域范围的FFFC而执行的示范操作的流程图；

图9是根据一个实施例的示出由接收第2层快速故障通知消息的路由器执行的示范操作的流程图；

图10示出根据一个实施例的使用基于单播的快速故障通知消息的示范网络；

图11是根据一个实施例的示出由检测到网络故障并使用基于单播的快速故障通知消息洪泛的路由器执行的示范操作的流程图；

图12是根据一个实施例的示出由接收使用基于单播的传输技术传输的快速故障通知消息的路由器执行的示范操作的流程图；

图13示出根据一个实施例的使用选通（gated）多播的快速故障通知消息的示范网络；

图14是根据一个实施例的示出由检测到网络故障的路由器为使用基于选通多播的快速故障通知消息洪泛来发起域范围的FFFC而执行的示范操作的流程图；

图15是根据一个实施例的示出由在选通多播快速故障通知消息中接收快速故障通知消息的路由器执行的示范操作的流程图；

图16示出根据一个实施例的用于基于在路由器执行的SPF（最短路径优先）计算来构建SPT（最短路径树）的示范操作；

图17示出根据一个实施例的由检测到网络故障的路由器使用基于SPF选择根节点SPT，为使用基于多播快速故障通知消息来发起域范围的FFFC而执行的示范操作；

图18是根据一个实施例的示出由在基于SPT选择根节点的FFFC应用中接收多播快速故障通知消息的路由器执行的示范操作的流程图；

图19示出根据一个实施例的由检测到网络故障的路由器使用双向多播树，为使用多播快速故障通知消息来发起域范围的FFFC而执行的示范操作，所述双向多播树使用PIM（协议独立多播）协议来构建；

图20是根据一个实施例的示出由在使用双向多播树的FFFC应用中接收多播快速故障通知消息的路由器执行的示范操作的流程图，所述双向多播树使用PIM协议来构建；以及 

图21示出根据一个实施例的用于快速故障通知消息的示范格式。

具体实施方式

在下面的描述中，陈述了许多特定细节。然而，要理解的是，实践本发明的实施例可无需这些特定细节。在其它情况下，公知的电路、结构和技术未详细显示以免混淆对此描述的理解。通过包括的描述，本领域技术人员将能够在不进行不当实验的情况下实现适当的功能性。

说明书中对“一个实施例”、“一实施例”、“示例实施例”等的引用是指所述实施例可包括具体特征、结构或特性，但每个实施例可不一定包括该具体特征、结构或特性。另外，此类短语不一定指相同实施例。此外，在结合实某个实施例描述某个具体特征、结构或特性时，认为结合无论是否明确描述的其它实施例来实现此类特征、结构或特性是在本领域技术人员的认知之内。

在下面的描述和权利要求中，可使用术语“耦合”和“连接”及其衍生词。应理解，这些术语无意作为彼此的同义词。“耦合”用于指示可相互直接物理或电接触或不直接物理或电接触的两个或更多要素相互协作或交互。“连接”用于指示在相互耦合的两个或更多要素之间通信的建立。

描述了一种基于快速洪泛的快速收敛(FFFC)架构。FFFC架构最小化在出现网络故障（例如，在链路或设备发生故障）时的网络停工时间（downtime）。在本发明的一个实施例中，为实现快速散布事件到网络中所有感兴趣的接收器的目的 ，FFFC架构使用事件框架。事件框架独立于基础输送机制。因此，可使用带有适合用于不同要求的不同属性的不同输送机制。例如，可使用为简单性进行优化的一些输送机制，同时可使用改进可靠性的其它输送机制。

事件框架是应用独立的，因为多个不同应用能够生成事件和/或注册以接收事件。在一个实施例中，基于TLV（类型长度值）的事件框架用于在应用与输送机制之间做出保证。使用事件框架的应用的一个示例是快速故障通知。快速故障通知用于改进网络收敛时间。例如，在网络中发生故障时，与故障相邻的路由器能够检测到它并快速将故障通知散布到整个区域的其它路由器。不同路由器上的路由选择协议（例如，诸如OSPF（开放式最短路径优先）和中间系统到中间系统(IS-IS)等链路状态IGP（内部网关协议）路由选择协议）能够注册和接收此类故障通知，随后对故障快速做出反应以实现快速收敛。快速故障通知中的事件是链路停工事件或节点停工事件。为了网络稳定性的缘故，不洪泛开动（up）事件（例如，链路开动或节点开动）。

图1示出根据一个实施例在网络中的路由器中包含的基于快速洪泛的快速收敛(FFFC)架构。示范FFFC架构是分层结构，其中，在每个路由器上布置各种路由选择功能。如图1所示，FFFC架构包括应用层105和数据传输层107。应用层105包括路由选择协议特定功能性，并且一般是相应路由器的控制平面的一部分。数据传输层107包括用于本文中所述快速洪泛机制的功能性（例如，它负责网络事件到网络中所有感兴趣的接收器的迅速散布），并且一般是相应路由器的数据平面的一部分。具体而言，应用层105包括分别在路由器120A-N上的路由选择协议模块110A-N，并且数据传输层107包括分别在路由器120A-N上的快速洪泛模块115A-N。

路由选择协议模块110A-N被注册以分别接收来自快速洪泛模块115A-N的事件。在一个实施例中，快速洪泛模块允许路由器120将网络故障通知散布到网络中的其它路由器120，这些路由器随后能够转发通知到对应路由选择协议模块110以做进一步处理（例如，更新路由选择协议表和/或转发表）。因此，快速洪泛机制与应用层105分开，并且被转移到数据传输层107上。

虽然以存储和转发方式执行洪泛的用于从网络故障恢复的常规路由选择协议处理是可靠（例如，包括重新传送）和安全（例如，包括邻接检查）的，但它涉及控制平面操作和控制平面到数据平面通信，这减慢了网络范围的收敛。然而，本文中所述FFFC架构使网络故障通知的洪泛和应用层105分开，并且将它转移到数据传输层107上。因此，数据传输层107提供能够以数据业务速度输送路由选择协议消息的域范围的快速洪泛平台，以便整个路由选择域能够实现域范围的快速收敛。在一个实施例中，普通洪泛功能仍被包括在应用层中以便在快速洪泛通知未到达预期路由器的情况下确保最终同步。普通洪泛功能要求在传送故障通知消息前更新路由选择表和转发表。

图2示出根据一个实施例的使用快速故障通知应用的示范网络，该应用使用FFFC架构。该示范网络包括路由器220A-N，并且形成环形拓扑。路由器220A和路由器220B通过链路252耦合。路由器220B和路由器220C通过链路254耦合。路由器220C和路由器220N通过链路256耦合（在路由器220C与路由器220N之间可以有0个或更多路由器）。路由器220N和路由器220A通过链路250耦合。路由器220A-N分别包括IGP模块210A-N和快速故障通知(FNN)模块215A-N。IGP模块210A-N分别是路由器220A-N的应用层的一部分，并且FFN模块215A-N分别是路由器220A-N的数据传输层的一部分。

在图2所示的示例中，路由器220C是目的地为路由器220A的分组的源。在普通操作期间，分组采用从路由器220C通过路由器220B到达目的地路由器220A的路径。如图2所示，网络遇到了网络故障；具体而言，链路252已发生故障。因此，路由器220B不能通过链路252将分组转发到路由器220A。因此，来自路由器220C的分组将不通过路由器220B到达目的地路由器220A。然而，来自路由器220C的分组能够通过路由器220N到达目的地路由器220A。

为了解释的目的，路由器220B检测到链路252的故障。然而，应理解，路由器220A也可检测到故障。故障的检测可在不同实施例中以不同方式执行。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。链路252的故障的检测是事件框架中的事件。因此，通知IGP模块210B链路252的故障的消息被发送到IGP模块210B，IGP模块210B能够更新路由器220B的路由选择表和转发表以反映链路252的故障。

由于路由器220B检测到故障，因此，在一个实施例中，它发起FFFC过程，并且是用于快速故障通知消息洪泛的起点。因此，在检测到故障后某个时间，路由器220B始发指示在链路252上故障的快速故障通知消息。快速故障通知消息用于通知已注意接收该类型的故障的消息的其它路由器。例如，快速故障通知消息指示在链路252上存在故障。另外，快速故障通知消息也向接收路由器指示应执行快速洪泛过程，包括将快速故障通知消息转发到其下一跳而不等待收敛。例如，快速故障通知消息要由那些路由器转发而无需来自其应用层的交互。为了图2的目的，每个路由器220A-N已注册接收快速故障通知消息。

在一个实施例中，快速故障通知消息使用现有IGP PDU（协议数据单元）分组格式。例如，如果IGP是OSPF，则反映断开的邻接（一个少数路由器链路）的OSPF外部LSA（链路状态通告）能够用作快速故障通知消息并且快速洪泛到路由器而无特殊修改。这允许例如路由器220A和220C-N等接收器以其通常方式处理分组。另外，由于分组与普通洪泛中使用的分组并非不同，因此，它保证在普通洪泛比得上本文中所述的快速洪泛时，过渡将是无缝的。另外，使用普通分组意味着在快速与慢速收敛之间将不存在重复工作。换而言之，无论何时更新路由器（已经快速洪泛了快速故障通知消息），洪泛便停止。然而，使用用于快速故障通知消息的现有IGP PDU分组格式意味着消息对于多个协议不能变得始终如一。例如，用于OSPF的现有IGP PDU分组格式与IS-IS的分组格式不同。因此，对于IS-IS，要使用与OSPF不同的格式。另外，由于IS-IS PDU不是基于IP的，因此，在一些情况下，它可要求封装。此外，缺陷之一是普通IGP洪泛机制使用邻接检查以防止来自不受信任方的DoS（服务拒绝）攻击或PDU回复。为使快速故障通知消息被接受，此邻接检查需要被绕过，这为DoS攻击或PDU回复攻击打开了方便之门。然而，可使用域范围的认证以便针对这些类型的攻击进行保护。

在另一实施例中，快速故障通知消息使用常见消息格式而不考虑协议。此格式允许有关故障链路的足够信息，并且在本文中所述事件框架中在接收器路由器上作为本地事件处理。在一个实施例中，统一格式是基于TLV的。在一个实施例中，超时手段用于针对使用常见消息格式的快速故障通知消息由于程序错误（bug）或其它错误状况而被错误地洪泛的情况进行保护。将在本文中后面更详细描述的图21示出独立于IGP协议并且是由数据传输层发出的第2层协议分组的示范消息格式。

在一个实施例中，快速故障通知消息包括向接收路由器指示该消息是用于本文中所述FFFC架构的特定目的地IP地址或MAC地址。

在始发快速故障通知消息后，检测路由器220B洪泛快速故障通知消息。如图2所示，路由器220B通过链路254将快速故障通知消息洪泛到路由器220C。这在概念上示为从FFN模块215B发送到FFN模块215C。可使用执行快速洪泛的任何数量的机制。在一个实施例中，使用的洪泛机制可靠（它甚至在故障发生后到达所有参与方）、无环、简单，并且能够被认证。

在一个实施例中，在路由器220B完成更新其路由选择和转发表以反映链路252（在它被收敛之前）的故障之前，路由器220B生成和传送快速故障通知消息260。因此，独立于更新其路由选择和转发表，路由器220B生成和传送快速故障通知消息。

接收路由器220C接收快速故障通知消息260。通知消息260是在本文中所述事件框架中的事件，并且IGP模块210C已注册以接收用于事件的消息。在一个实施例中，基于快速故障通知消息260具有特定目的地IP地址或MAC地址，将它识别为用于FFFC架构的消息。因此，在接收消息后，它将指示链路252的故障的快速故障通知消息272转发到IGP模块210C，以便IGP模块210C能够对故障做出反应，并且开始收敛处理。在一个实施例中，IGP模块210C通过放弃邻接检查而放宽其消息接受准则。在接收快速故障通知消息272后，IGP模块处理消息，包括在适当时更新路由选择表和转发表以反映链路252的故障。在一个实施例中，更改被预下载到数据平面（例如，在转发表中）以改进收敛时间。

除转发快速故障通知消息272到IGP模块210C外，FFN模块215C洪泛快速故障通知消息的副本。出于示范目的，FFN模块215C通过链路256将快速故障通知消息262洪泛到路由器220N。快速故障通知消息262能够在快速故障通知消息272之前发送或者与其同时发送。因此，根据一个实施例，快速故障通知消息262被洪泛到下一路由器而无需与IGP模块210C的任何交互，这降低了收敛时间。

路由器220N响应接收快速故障通知消息262而执行的处理与路由器220C响应接收快速故障通知消息260而执行的处理类似。快速故障通知消息262是IGP模块210N注册的框架中的事件。因此，FFN模块215N将指示链路252的故障的快速故障通知消息274发送到IGP模块210N。IGP模块210N随后在适当时更新路由选择表和转发表以反映链路252的故障。FFN模块215N通过链路250也将快速故障通知消息264洪泛到路由器220A。快速故障通知消息264能够在快速转发消息274的转发之前转发或者与其同时转发。响应接收快速故障通知消息220A，快速洪泛机制215A将快速故障通知消息276转发到IGP模块210A，以便IGP模块210A能够对链路252的通知和故障做出反应。

在一个实施例中，由于快速故障通知消息260、262和264在数据传输层处理，因此，它们和数据业务以相同的速度传送。通过特定示例，从路由器220C通过链路256发送到路由器220N的快速故障通知消息262与从路由器220C通过链路256发送到路由器220N的数据业务以相同的速度行进。由于快速故障通知消息260、262和264与数据业务以相同速度行进，因此，则下一跳路由器与前一路由器具有用于处理通知消息的相同时间量（假设有相同的计算能力）。例如，假设路由器220C和220N具有相同计算能力，则路由器220N具有用于处理通知消息262的时间量与路由器220C具有用于处理通知消息260的时间量相同。

应理解，路由器220A-N不同时收敛。这是由于快速故障通知消息的传播延迟而引起的。例如，路由器220C将接收指示链路252的故障的快速故障通知消息，之后路由器220N接收类似消息。然而，使用本文中所述FFFC架构，在第一路由器修改后，业务丢失便立即停止。这是因为数据业务与快速故障通知消息经历相同传播延迟，这补偿了在远程路由器收敛的延迟开始。

例如，假设路由器220A-N每个具有50毫秒的收敛时间和通过每一跳20毫秒的传送延迟。通过将丢失分组的数量除以在域中任何两个路由器之间的业务流速率，测量收敛时间。如果所有各个路由器具有相同计算能力和相同收敛时间，则这应等于域范围的网络收敛时间。例如，在出现链路252故障时，路由器220B将快速转发通知消息260（例如，链路状态更新）发送到路由器220C，并且开始其收敛。下面的表1示出收敛时间线。

表1 

节点收敛开始收敛完成220B050 ms220C20 ms70 ms

在时间0，路由器220B在链路252的故障后开始其收敛。另外，路由器220B同时将快速转发通知消息260发送到路由器220C。在前50毫秒期间，丢弃从路由器220B通过链路252到路由器220A的分组（由于链路252的故障）。快速转发通知消息260在20毫秒后到达路由器220C，在该时间点，路由器220C开始其收敛。因此，在路由器220B完成其收敛后，路由器220C开始其收敛。路由器220C也将快速故障通知消息262发送到下一跳路由器（例如，路由器220N）。大致立即在50毫秒和路由器220B已收敛后，路由器220B向路由器220C重新路由目的地为220A的分组。那些分组使用20毫秒到达路由器220C，并且因此将在链路252的故障后70毫秒到达。路由器220C在接收快速转发通知消息260后50秒收敛，这是在链路252的故障后70毫秒。因此，数据业务分组将在路由器220C收敛的大约相同时间到达。此过程在域范围上继续。由于路由器220C和所有其它下游路由器正好在数据分组到达前逐一收敛，因此，数据分组经校正的路径成功到达目的地（路由器220A）。

如果路由器220A-N具有不同收敛时间，则微环回可形成，但分组仍将在一个或多个环路后被送达。例如，假设相同链路故障情形（链路252已发生故障），但路由器220C需要90毫秒收敛，而其它路由器在50毫秒内收敛。路由器220B在链路252的故障后70毫秒将分组重新路由到路由器220C时，路由器220C将尚未完成其更新。因此，它仍可继续使用其旧转发表，并且将目的地为路由器220A的分组发送到路由器220B，路由器220B又将那些分组重新路由回路由器220C。这些分组将到达路由器220C的时间是在故障后的110毫秒，并且路由器220C将已完成更新并且将正确地转发分组。在此示例中，分组被循环一次，然而，应理解，在一些情况下可存在多个环路。由于不同收敛时间线造成分组临时在错误的方向被转发，分组可能被重新排序。分组重新排序对TCP通信有不利影响，因为新序列编号的分组可在更旧序列编号的分组之前到达。

本文中所述FFFC架构允许在受影响路由器收敛后立即重新路由数据业务，而不是所有路由器收敛后才重新路由。另外，在受影响路由器的收敛时，本文中所述FFFC架构保证用于所有受影响业务的正确路由。本文中所述FFFC架构随任何大小和任何拓扑的网络扩展，至少不差于普通IGP洪泛。

图3是根据一个实施例的示出由检测网络故障的路由器为发起域范围的FFFC而执行的示范操作的流程图。在操作310，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作315。

在操作315，路由器生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息要作为在接收路由器上的快速洪泛事件处理。另外，快速故障通知消息也向接收路由器指示应执行快速洪泛过程，包括将快速故障通知消息转发到其下一跳而不等待收敛（不等待更新路由选择和转发表）。例如，快速故障通知消息要由那些路由器转发而无需来自其应用层的交互。在一个实施例中，快速故障通知消息包括专用于FFFC的特定目的地IP地址或MAC地址。因此，快速故障通知消息包括允许接收路由器更新其路由选择和转发表以反映网络故障以及应该独立于更新路由选择和转发表将快速故障通知转发到其下一跳路由器的信息。

如上所述，快速故障通知消息可使用现有IGP PDU分组格式或者可使用常见消息格式而不考虑协议。流程随后转到操作320，并且路由器将快速故障通知消息洪泛到一个或多个路由器。流程随后转到操作325，并且路由器更新其路由选择和转发表以反映网络故障。在路由器更新其路由选择和转发表后，数据分组将被重新路由以避免网络故障。

在一些实施例中，操作325可与操作315和/或320同时开始，然而，应理解，一般在生成和传送快速故障通知消息后才完成更新。也应理解，在生成和传送快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图4是根据一个实施例的示出由接收快速故障通知消息的路由器执行的示范操作的流程图。在操作410，路由器接收包括有关网络故障的信息的快速故障通知消息。快速故障通知消息也指示该消息要在FFFC架构中被处理。例如，快速故障通知消息可包括专用于本文中所述FFFC的特定目的地IP地址或MAC地址。流程随后转到操作415。

在操作415，将快速洪泛消息发送到路由器上的适当路由选择协议模块（例如，路由器上的IGP模块）以做进一步处理。如果路由器包括下一跳路由器，则流程转到操作420，并且快速故障通知消息被洪泛到下一跳路由器。应理解，由于这是快速故障通知消息，因此，在将快速故障通知消息洪泛到其下一跳路由器前，路由器不等待直至它已更新其路由选择和转发表。流程随后转到操作425，并且路由器更新其路由选择和转发表以反映网络故障。在路由器更新其路由选择和转发表后，数据分组将被重新路由以避免网络故障。

在一些实施例中，操作425可与操作420同时开始，然而，应理解，一般在洪泛快速故障通知消息后才完成更新。也应理解，在洪泛快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行将接收的快速故障通知消息洪泛到其下一跳路由器。

基于桥接的快速故障通知消息洪泛

在一个实施例中，用于快速故障通知消息洪泛的输送机制是基于桥接的。用于快速故障通知消息的基于桥接的输送机制不像基于树的输送机制一样遭受由于链路断开而造成的树分区。在路由器发生故障或者多个链路同时发生故障（例如，链路卡故障）时，所有基于树的快速洪泛方案具有的限制是洪泛变成分区的，并且在拓扑的不同部分中的路由器可因此具有拓扑更改的不同感知。因此，可形成路由选择环路和/或黑洞。本文中所述基于桥接的输送机制不遭受变成分区的流动。

图5示出根据一个实施例的使用基于桥接的洪泛来散布快速故障通知的示范网络。网络500包括路由器520A-D，这些路由器全部是包括某个区域中所有节点和链路的桥接网络的一部分。路由器520A-D分别包括桥虚拟接口(BVI) 515A-D和IGP模块510A-D。BVI 515A-D配置成始发和接收本文中所述的快速故障通知，并且分别是路由器520A-D的数据传输层的一部分。BVI 515A-D是某种类型的快速故障通知(FFN)模块。

IGP模块510A-D分别是路由器520A-D的应用层的一部分。路由器520A包括接口Ab 570。路由器520B包括接口Ba 572、Bc 574、Bd 576。路由器520C包括接口Cb 578和Cd 580。路由器520D包括接口Db 582和Dc 584。接口Ab 570和Ba 572通过链路552耦合。接口Bc 574和Cb 578通过链路554耦合。接口Cd 580和Dc 584通过链路556耦合。接口Bd 576和Db 582通过链路550耦合。

如图5所示，路由器形成环形拓扑。因此，在网络中可能出现环回。MAC移动检测是桥接网络中针对环路进行保护的公知方法，然而，控制平面将其判定移到路由器的不同线路卡上的所有接口的时间量（例如，几毫秒）可使网络瘫痪。在本发明的一个实施例中，学习一次的洪泛方案被引入并用于防止网络中的环路。在快速转发通知消息到达桥接口时，桥开始其普通MAC学习过程。一般情况下，这包括桥确定消息的源MAC地址是否与其上接收了消息的接口相关联。MAC地址和接口的关联一般存储在桥MAC表中。如果条目不存在（MAC地址和接口关联是新的），则执行常规MAC学习和洪泛过程（将快速故障通知洪泛到该桥组的所有其它接口）。然而，如果条目存在（MAC地址和接口关联已经知道），则丢弃快速故障通知消息，并且不执行进一步处理。

学习一次的洪泛方案环路防止机制保证每个接口将最多一次接收快速故障通知消息并且将它洪泛到其它接口。因此，具有n个接口的桥将最多洪泛快速故障通知消息n次。

在图5所示示例中，在接口Ab 570与Ba 572之间的链路552已发生故障。为了解释的目的，路由器520B检测到链路552的故障。然而，应理解，路由器520A也可检测到故障。故障的检测可在不同实施例中以不同方式执行。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。链路552的故障的检测是事件框架中的事件。

在检测到故障时，通过BVI接口515B发送指示在链路552上故障的快速故障通知消息以开始快速洪泛过程。具体而言，通过接口Bc 574和576洪泛出快速故障通知消息560。快速故障通知消息560具有指派到接口Ba 572的源MAC地址。为了此示例的目的，将相对于通过接口Bc 574洪泛出快速故障通知消息560来描述洪泛的方向，然而，应理解的是，相对于通过接口Bc 576洪泛出快速故障通知消息560，执行类似的操作。

跨链路554发送快速故障通知消息560，并且在路由器520C的接口Cb 578接收它。假设这是在接口Cb 578上第一次接收具有快速故障通知消息560的源MAC地址的分组，接口和MAC地址关联（例如，接口Cb 578和接口的MAC地址的关联）得以了解（例如，添加到桥MAC表）。快速故障通知消息560也被洪泛到BVI 515C，并且通过接口Cd 580被洪泛出。BVI 515C将通知转发到IGP模块510C以进行处理（例如，更新路由器520C的路由选择表和/或转发表以反映链路552的故障）。

跨链路556发送快速故障通知消息560，并且在路由器520D的接口Dc 584接收它。在如相对于路由器520C所述的类似过程中，假设这是在接口Dc 584上第一次接收具有快速故障通知消息560的源MAC地址的分组，接口和MAC地址关联（例如，接口Dc 584和接口的MAC地址的关联）得以了解（例如，添加到桥MAC表）。快速故障通知消息560也洪泛被到BVI 515D，并且通过接口Dd 582被洪泛出。BVI 515D将通知转发到IGP模块510D以进行处理（例如，更新路由器520D的路由选择表和/或转发表以反映链路552的故障）。

跨链路550发送快速故障通知消息560，并且在路由器520B的接口Bd 576接收它。在如相对于路由器520C和520D所述的类似过程中，假设这是在接口Bd 576上（从外部源）第一次接收具有快速故障通知消息560的源MAC地址的分组，接口和MAC地址关联（例如，接口Bd 576和接口的MAC地址的关联）得以了解（例如，添加到桥MAC表）。快速故障通知消息560也洪泛被到BVI 515B，并且通过接口Bc 574被洪泛出。

跨链路554发送快速故障通知消息560，并且在接口Cb 578上接收它。然而，由于快速故障通知消息560已经在接口Cb 578被接收，因此，快速故障通知消息也将被丢弃，并且环路停止。

图6是根据一个实施例的示出由检测到网络故障的路由器为使用基于桥接的快速故障通知消息洪泛来发起域范围的FFFC而执行的示范操作的流程图。在操作610，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作615。

在操作615，路由器生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息包括与链路故障有关联的路由器上接口的源MAC地址。例如，参照图5，假设链路552已发生故障，路由器520B生成包括接口Ba 572的源MAC地址的快速故障通知消息。快速故障通知消息要作为在接收路由器上的快速洪泛事件处理。例如，快速故障通知消息向每个接收路由器指示它应在其数据传输层中确定是否将快速故障通知消息从一个或多个其接口洪泛出而不等待收敛（不等待更新路由选择和/或转发表），并且在适当时更新路由选择和/或转发表以反映在快速故障通知消息中所示的网络故障。因此，快速故障通知消息向接收路由器指示MAC学习和查找应由数据传输层（例如，入口端口）执行，而无需与应用层（或在其它情况下的控制平面）交互，并且因此以线路速率（line rate）被执行，以及应用层要在适当时独立于洪泛过程而更新路由选择和/或转发表。在一个实施例中，快速故障通知消息包括专用于FFFC以向接收路由器指示它应将消息作为快速故障通知消息处理的特定目的地MAC地址。因此，快速故障通知消息包括允许接收路由器以线路速率洪泛快速故障通知消息以及更新其路由选择和/或转发表以反映网络故障的信息。

流程随后转到操作620，并且路由器将快速故障通知消息洪泛到桥组。桥组包括是相同广播域的一部分的一个或多个网络接口。例如，参照图5，路由器520B将快速故障通知消息560通过接口Bc 574和Bd 576洪泛出。流程随后转到操作625，并且路由器更新其路由选择和转发表以反映网络故障。在路由器更新其路由选择和转发表后，数据分组将被重新路由以避免网络故障。

在一些实施例中，操作625可与操作615和/或620同时和/或在其它之前开始，然而，应理解的是，一般在生成和传送快速故障通知消息后才完成更新。也应理解的是，在生成和传送快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图7是根据一个实施例的示出由在使用基于桥接的快速故障通知消息的FFFC架构中接收快速故障通知消息的路由器执行的示范操作的流程图。在操作710，路由器在接口上接收包括有关网络故障的信息的快速故障通知消息。快速故障通知消息也指示该消息要在FFFC架构中被处理。例如，快速故障通知消息可包括专用于本文中所述FFFC的特定目的地IP地址或MAC地址。流程随后转到操作715。

在操作715，路由器确定快速故障通知消息的源MAC地址是否与其上接收它的接口相关联。例如，路由器访问桥MAC表以确定源MAC地址是否与接口相关联。如果源MAC地址与接口不相关联，则流程转到操作720。如果源MAC地址已经与接口相关联（这一般意味着快速故障通知消息已经在该接口上被接收），则流程转到操作740，并且分组被丢弃。如前面所述，如果已经知道分组，则丢弃分组，这用于防止网络中的环路。另外，在一个实施例中，MAC学习和查找以线路速率在入口接口内被执行，并且其执行无需与路由器的控制平面的交互。因此，本发明的实施例学习一次的洪泛技术用于防止环路，并且比诸如MAC移动检测等其它常用环路防止技术更快（例如，它以线路速率操作）。

在操作720，路由器将快速故障通知消息中包括的源MAC地址与其上接收它的路由器的接口相关联。例如，路由器将源MAC地址和接口对添加到桥MAC表。流程随后转到操作725，并且路由器将快速故障通知消息洪泛到桥组的所有其它接口（如果有）以促使快速故障通知消息被发送到相邻路由器。流程随后转到操作730，并且快速故障通知消息被发送到用于路由选择协议的BVI（例如，路由器上的IGP模块）以做进一步处理。流程随后转到操作735，并且路由器（例如，IGP模块）更新路由选择表和/或转发表以反映故障。

在一个实施例中，为制止桥使用用于非FFFC目的，专用MAC地址可被保留并用作用于快速故障通知消息的目的地MAC地址。在一个实施例中，可配置ACL（访问控制列表），以便桥只接受用于FFFC目的的专用MAC地址。

第2层桥接网络上基于STP的快速故障通知消息洪泛

在一个实施例中，用于快速故障通知消息洪泛的输送机制是在第2层桥接网络上，使用生成树协议(STP)。第2层桥接网络中的洪泛已被很好地定义，并且能够用于输送快速故障通知消息。在每个参与路由器上配置桥组，并且在所有桥上启用STP。STP用于通过创建路由器的生成树来防止桥环路，并且阻止不是树的一部分的那些接口。STP在IEEE 802.ID中定义。此类型的机器称为桥式路由器。在接收IP分组时，桥式路由器路由IP分组。在接收其它类型的分组时，桥式路由器桥接分组。由于桥式路由器路由IP分组，因此，在第2层桥接网络上基于STP的快速故障通知消息洪泛中使用的快速故障通知消息是第2层分组，以避免根据IP转发表转发。

图8是根据一个实施例的示出在第2层桥接网络中已检测到网络故障的路由器（例如，桥式路由器）上为使用基于STP的洪泛来发起域范围的FFFC而执行的示范操作的流程图。在操作810，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作815。

在操作815，路由器（例如，该路由器上的FFN模块）生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息是第2层分组。用于第2层快速故障通知消息的示范格式将参照图21进一步详细描述。快速故障通知消息要作为在接收路由器上的快速洪泛事件来处理。例如，接收快速故障通知消息的路由器要将分组洪泛到STP未阻塞的所有其它接口而不等待收敛。因此，快速故障通知消息向接收路由器指示其数据传输层应将分组洪泛到STP未阻塞的所有其它端口而无需与应用层的交互，并且因此以线路速率执行，以及其应用层要在适当时更新路由选择和/或转发表。因此，快速故障通知消息包括允许接收路由器以线路速率洪泛快速故障通知消息以及更新其路由选择和/或转发表以反映网络故障的信息。

流程随后转到操作820，并且路由器将第2层快速故障通知消息洪泛到桥组的成员。流程随后转到操作825，并且路由器在适当时更新其路由选择和/或转发表以反映故障（例如，IGP模块在适当时更新其路由选择和/或转发表）。在一些实施例中，操作825可与操作815和/或820同时和/或在其它之前开始，然而，应理解的是，一般在生成和传送快速故障通知消息后才完成更新。也应理解的是，在生成和传送快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图9是根据一个实施例的示出由接收第2层快速故障通知消息的路由器执行的示范操作的流程图。在操作910，路由器接收包括有关网络故障的信息的第2层快速故障通知消息。例如，该路由器的FFN模块（在数据传输层上）接收第2层快速故障通知消息。流程随后转到操作915，并且路由器（例如，该路由器的FFN模块）将快速故障通知消息洪泛到STP未阻塞的所有其它接口。流程随后转到操作920，并且快速故障通知消息被发送到路由器上的路由选择协议模块（例如，IGP模块）以做进一步处理。流程随后转到操作925，并且路由选择协议模块更新路由选择和转发表以反映网络故障。在一些实施例中，操作920操作925可与操作915同时或在其之前开始，然而，应理解的是，一般在洪泛快速故障通知消息后才完成更新。也应理解的是，在洪泛快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。

第2层桥接网络上的STP洪泛既简单又快速。然而，STP洪泛占用相当长的时间持续期进行周转（准备好用于下一命中），并且它也遭受树分析问题，这暗示它不能处理同时多个链路故障。

基于单播的快速故障通知消息洪泛

在一个实施例中，用于快速故障通知消息洪泛的输送机制是基于单播的。检测到网络故障的路由器生成快速故障通知消息，并且将副本发送到域中的每个路由器。域中路由器的标识存储在路由器上的路由选择和/或转发表中。这些单播快速故障通知消息以类似于转发常规IP数据业务的方式以数据平面速度被转发到目的地路由器。

图10示出根据一个实施例的使用基于单播的快速故障通知消息的示范网络。网络1000包括路由器1020A-D。路由器1020A和1020B通过链路1052耦合。路由器1020B和1020C通过链路1054耦合。路由器1020C和1020D通过链路1056耦合。路由器1020A和1020D通过链路1050耦合。路由器1020A-D分别包括IGP模块1010A-D和FFN模块1015A-D。IGP模块1010A-D分别是路由器1020A-D的应用层的一部分，并且FFN模块1015A-D分别是路由器1020A-D的数据传输层的一部分。

在图10所示示例中，网络1000遇到了网络故障。具体而言，链路1054已发生故障。为了解释的目的，路由器1020B检测到链路1052的故障。然而，应理解的是，路由器1020A也可检测故障并且执行与路由器1020B类似的操作。故障的检测可在不同实施例中以不同方式执行。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。链路1052的故障的检测是事件框架中的事件。因此，通知IGP模块1010B链路1052的故障的消息被发送到IGP模块1010B，IGP模块1010B能够更新路由器1020B的路由选择表和转发表以反映链路1052的故障。

在检测到故障后某个时间，路由器1020B始发指示链路252上故障的快速故障通知消息。快速故障通知消息用于通知已注意接收该类型的故障的消息的其它路由器。例如，快速故障通知消息指示在链路1052上存在故障。路由器1020B将快速故障通知消息发送到IP域中的每个路由器。参照图10，指示链路1052的故障的单播快速故障通知消息1060被发送到路由器1020C的目的地IP地址，以及发送到路由器1020D的目的地IP地址。此外，单播快速故障通知消息1060也可被发送到路由器1020A的目的地地址。

在路由器接收快速故障通知消息时，路由器处理快速故障通知消息，包括在适当时更新其路由选择表和/或转发表。例如，在路由器1020C接收快速洪泛通知消息1060时，它将被转发到IGP模块1010C以做进一步处理，包括更新路由选择表和/或转发表。在一些实施例中，接收路由器的IGP模块通过在分组验证期间放弃邻接检查而放宽快速故障通知消息的其接受准则。可使用域范围的认证以便针对DoS攻击或PDU回复攻击进行保护（如果邻接检查被绕过）。

不同于本文中所述其它快速故障通知消息传输技术，检测到故障的路由器负责洪泛快速故障通知消息。因此，接收快速故障通知消息的路由器无需转发或中继消息到其下一跳路由器。

图11是根据一个实施例的示出由检测到网络故障并使用基于单播的快速故障通知消息洪泛的路由器执行的示范操作的流程图。在操作1110，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作1115。

在操作1115，路由器生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息要作为在接收路由器上的快速洪泛事件来处理。因此，快速故障通知消息包括允许接收路由器更新其路由选择和转发表以反映网络故障的信息。流程随后转到操作1120。如上所述，快速故障通知消息可使用现有IGP PDU分组格式或者可使用常见消息格式而不考虑协议。

在操作1120，将快速故障通知的副本发送到在IP域中的每个路由器（例如，在路由器的路由选择和/或转发表中已识别）。例如，对于IP域中的每个路由器，分组的目的地IP地址设成该路由器。流程随后转到操作1125，并且路由器更新其路由选择和转发表以反映网络故障。

在一些实施例中，操作1125可与操作1115和/或1120同时开始或在其之前开始。在一些实施例中，在传送快速故障通知消息前，路由器不等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图12是根据一个实施例的示出由接收使用基于单播的传输技术传输的快速故障通知消息的路由器执行的示范操作的流程图。在操作1210，路由器接收包括有关网络故障的信息的快速故障通知消息。流程随后转到操作1215。在操作1215，将快速洪泛消息发送到路由器上的适当路由选择协议模块（例如，路由器上的IGP模块）以做进一步处理。流程随后转到操作1220，并且一般由路由选择协议模块执行的邻接检查被绕过（如果路由选择协议模块配置成执行邻接检查）。流程随后转到操作1225，并且路由选择协议模块更新路由选择和/或转发表以反映网络故障。

由于基于单播的快速故障通知消息洪泛技术依赖检测到网络故障的路由器生成和传送快速洪泛通知到IP域中的其它路由器，因此，对于要重复分组发送工作多次的始发路由器，这可显得太繁重。然而，实验显示，始发路由器上的负担可忽略不计。对于规模适当的100路由器网络，始发路由器生成和传送100个快速洪泛通知分组的总时间是7毫秒。始发路由器上的此小延迟能够通过预下载快速故障通知消息分组到数据平面而被最小化。由于数据平面已经具有作为IGP路由选择表的一部分的所有路由器的列表，因此，数据平面能够直接调遣分组。

实质上，基于单播的快速故障通知消息洪泛技术是基于树的，类似于多播树。然而，不存在为快速故障通知消息洪泛的目的而生成的特殊树。相反，使用了是SPF（最短路径优先）树(SPT)的普通路由选择表。这保证洪泛采用最短路径（如路由选择表所确定的一样），并且不形成洪泛环路。在中断的链路在SPT上的情况下，树被分区，并且从始发路由器的洪泛将只到达一部分树。然而，整个树将得到故障的通知，这是因为链路的另一端上的路由器能够执行类似的基于单播的快速故障通知过程以覆盖树的另一部分的路由器。例如，参照图10，除路由器1020B响应检测到链路故障1052而生成和传送单播快速故障通知消息到域中的其它路由器外，路由器1020A也能够响应检测到链路故障1052而生成和传送单播快速故障通知消息到域中的其它路由器。

通过RPF检查选通多播快速故障通知消息洪泛

在一个实施例中，用于快速故障通知消息洪泛的输送机制是基于多播的，并且洪泛环路通过RPF（反射路径转发）检查而被防止。基于选通多播的洪泛不要求建立多播树；相反，在它将快速故障通知消息洪泛到其它路由器前，它使用如IGP模块计算的相同SPT和使用该SPT的RPF检查。RPF检查确定其上接收快速故障通知消息的接口是否也是到达快速故障通知消息的外出接口。

在一个实施例中，专用多播地址被定义并用于基于选通多播的快速故障通知消息洪泛。此专用多播地址用于为快速洪泛识别快速故障通知消息。在路由器在该多播地址接收快速故障通知消息时，路由器执行RPF检查。例如，路由器访问用于始发路由器（检测到故障并且始发了快速故障通知消息的路由器）的IP单播路由选择表（例如，如IGP模块计算的SPT）以查找到达始发路由器的外出接口。快速故障通知消息的到达接口与到达始发路由器的外出接口相同时，RPF检查通过，并且路由器将通知洪泛到其它接口。如果快速故障通知消息的到达接口与用于到达始发路由器的外出接口不相同，则路由器丢弃分组，由此防止环路。

图13示出根据一个实施例的使用选通多播的快速故障通知消息的示范网络1300。示范网络1300包括路由器1320A-D，这些路由器分别包括IGP模块1310A-D和FFN模块1315A-D。路由器1320A通过链路1350与路由器1320B耦合，通过链路1352与路由器1320C耦合，以及通过链路1356与路由器1320D耦合。路由器1320B也通过链路1354与路由器1320C耦合，并且通过链路1360与路由器1320D耦合。路由器1320C也通过链路1358与路由器1320D耦合。

路由器1320A-D的IGP模块1310A-D每个重复要用作双向多播树的其SPT（最短路径树）（由该IGP模块计算），并且促使双向多播树被下载到路由器的数据平面（例如，安装在数据平面的一个或多个线路卡上），以及添加专用于基于选通多播的快速故障通知消息洪泛的多播组地址以加入该多播组。

参照图2，以路由器1320A为根的SPT包括到达路由器1320B的链路1350、到达路由器1320C的链路1352及到达路由器1320D的链路1350和1360。例如，在路由器1320A将分组发送到路由器1320D时，分组将沿链路1350和链路1360行进。链路1354、1356和1358不是以路由器1320A为根的SPT的一部分。

为了解释的目的，路由器1320A检测到链路或节点的故障，这未示出以免混淆本发明的理解。如上所述，故障的检测可在不同实施例中以不同方式执行。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。网络故障的检测是事件框架中的事件。

在检测到网络故障后某个时间，路由器1320A生成包括识别故障的信息的快速故障通知消息。例如，FFN模块1315A生成快速故障通知消息。快速故障通知消息向接收路由器指示应执行选通快速洪泛过程。例如，快速故障通知消息向接收路由器指示，独立于其应用层更新路由选择表和/或转发表以反映在快速故障通知消息中指示的网络故障，其数据传输层应确定是否将快速故障通知消息多播到其接口（以及如果适当，则多播该消息）。

数据传输层基于消息的目的地地址来识别快速故障通知消息（快速故障通知消息具有专用于选通快速故障通知消息的多播目的地地址）。路由器1320B-D每个侦听具有专用多播地址的多播分组，并且因此，路由器1320B-D每个接收多播快速洪泛通知消息1360。由于路由器1320A-D以网状被布置，因此，可能路由器能够接收多份快速故障通知消息1360。例如，路由器1320可接收通过链路1352来自路由器1320A的快速故障通知消息1360，并且也可接收通过链路1354来自路由器1320B的快速故障通知消息1360。然而，为了防止环路，执行了PF检查。例如，路由器1320C将丢弃经路由器1320B接收的来自路由器1320A的快速故障通知消息1360，这是因为路由器1320B不是其到路由器1320A的RPF下一跳。

图14是根据一个实施例的示出由检测到网络故障的路由器为使用基于选通多播的快速故障通知消息洪泛来发起域范围的FFFC而执行的示范操作的流程图。在操作1410，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作1415。

在操作1415，路由器（例如，该路由器上的FFN模块）生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息要作为在接收路由器上的快速洪泛事件处理。另外，快速故障通知消息也向接收路由器指示应执行选通多播快速洪泛过程，这包括执行PF检查，并且可包括将快速故障通知多播到其它接口。快速故障通知消息具有专用于多播选通快速故障通知的多播地址的目的地地址。独立于应用层更新路由选择和/或转发表以反映网络故障后拓扑的更改，快速故障通知消息要由那些路由器转发（如果要进行任何转发）。因此，快速故障通知消息包括向接收路由器指示更新其路由选择和/或转发表以反映网络故障，以及独立于更新，执行选通多播快速洪泛过程。流程随后转到操作1420，并且路由器将分组发送到专用于多播选通快速故障通知的多播组地址。流程随后转到操作1425，并且路由器在适当时更新其路由选择和/或转发表以反映故障（例如，IGP模块在适当时更新其路由选择和/或转发表）。

在一些实施例中，操作1425可与操作1415和/或1420同时和/或在其之前开始，然而，应理解的是，一般在生成和传送快速故障通知消息后才完成更新。也应理解的是，在生成和传送快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图15是根据一个实施例的示出由在选通多播快速故障通知消息洪泛应用中接收多播快速故障通知消息的路由器执行的示范操作的流程图。在操作1510，路由器接收包括有关网络故障的信息的多播快速故障通知消息。例如，该路由器的FFN模块接收多播快速故障通知消息。另外，快速故障通知消息也向路由器指示应执行选通多播快速洪泛过程，这包括执行PF检查，并且可包括将快速故障通知多播到其它接口。流程随后转到操作1515，并且路由器（例如，FFN模块）执行RPF检查，这包括确定快速故障通知消息的到达接口是否与到达始发方路由器的外出接口相同。例如，路由器访问用于作为多播快速故障通知分组的源的路由器的IP单播路由选择表，以确定到达该路由器的外出接口。作为特定示例，接收路由器的FFN模块使用在数据平面上基于SPT生成的双向多播树，确定到达多播快速故障通知分组的源的外出接口。如果快速故障通知消息的进入接口与到达始发了快速故障通知消息的路由器的外出接口相同，则流程转到操作1520；否则，流程转到操作1540，并且分组被丢弃。

在操作1520，路由器（例如，该路由器的FFN模块）将快速故障通知多播到路由器的其它接口。例如，参照图13，响应路由器1320B在链路1350上接收多播快速故障通知消息1360并且确定对应于链路1350的接口是用于到达路由器1320A的相同接口，FFN模块1315B在对应于链路1354和1360的接口上将快速故障通知消息1360多播出。流程从操作1520转到操作1525，并且FFN模块将快速故障通知转发到路由器上的路由选择协议模块（例如，IGP模块）。流程随后转到操作1530，并且路由选择协议模块更新路由选择和转发表以反映网络故障。

在一些实施例中，操作1530可与操作1520同时或在其之前开始，然而，应理解的是，一般在洪泛快速故障通知消息后才完成更新。也应理解的是，在洪泛快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。

最短路径树(SPT)选择根快速故障通知消息洪泛

在一个实施例中，用于快速故障通知消息的输送机制是基于多播的，使用基于选择路由器之一作为根节点的SPF（最短路径优先）计算的SPT。树类似于双向多播树，但它直接由IGP过程来构建。网络中的路由器选择路由器之一作为根节点，并且IGP模块基于当前网络拓扑构建以选择的路由器为根的SPT。在一个实施例中，路由器选择带有最高路由器id的路由器作为根节点。双向多播转发条目能够由IGP模块（例如，IS-IS或OSPF）基于构建的SPT创建，并且随后被下载到数据平面（例如，到路由器的一个或多个线路卡）以便在散布快速故障通知消息中使用。使用下载的双向多播转发条目，使用普通多播协议来转发快速故障通知消息。

图16示出根据一个实施例的用于基于在路由器执行的SPF计算构建SPT的示范操作。在操作1610，路由器选择网络的某个路由器为根节点。选择的路由器不一定是在执行操作1610的路由器。在一个实施例中，被选择为根节点的路由器具有最高路由器id。当然，根节点的选择可在不同实施例中以不同方式执行（例如，带有最低路由器id的路由器），但在任何情况下，网络中的路由器需要对哪个路由器是根节点意见一致。流程随后转到操作1615，并且路由器基于当前网络拓扑构建以选择的根节点为根的SPT。例如，路由器在路由器的LSDB（链路状态数据库）（例如，如果使用OSPF或IS-IS）上执行SPF实现。流程随后转到操作1620，并且构建的SPF作为双向多播树被下载到路由器的数据平面（例如，到路由器的数据传输层）以便在散布快速故障通知消息中使用。

图17示出根据一个实施例的由检测到网络故障的路由器使用基于SPF选择根节点SPT，为使用基于多播快速故障通知消息来发起域范围的FFFC而执行的示范操作。在操作1710，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作1715。

在操作1715，路由器（例如，该路由器上的FFN模块）生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息要作为在接收路由器上的快速洪泛事件处理。快速故障通知消息向接收路由器指示应使用SPT执行多播快速洪泛过程，这可包括多播快速故障通知，SPT基于SPT选择根节点计算。在一个实施例中，快速故障通知消息具有专用于多播快速故障通知的多播地址的目的地地址。独立于应用层更新路由选择和/转发表，那些路由器做出快速故障通知消息的多播判定和任何结果多播。因此，快速故障通知消息向接收路由器指示，以线路速率多播快速故障通知消息并且更新其路由选择和/或转发表以反映网络故障。

流程随后从操作1715转到操作1720，并且路由器将分组发送到专用于多播快速故障通知的多播组地址。流程随后转到操作1725，并且路由器在适当时更新其路由选择和/或转发表以反映故障（例如，IGP模块在适当时更新其路由选择和/或转发表）。

在一些实施例中，操作1725可与操作1715和/或1720同时和/或在其之前开始，然而，应理解的是，一般在生成和传送快速故障通知消息后才完成更新。也应理解的是，在生成和传送快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图18是根据一个实施例的示出由在基于SPT选择根节点的FFFC应用中接收多播快速故障通知消息的路由器执行的示范操作的流程图。在操作1810，路由器接收包括有关网络故障的信息的多播快速故障通知消息。例如，该路由器的FFN模块接收多播快速故障通知消息。快速故障通知消息向路由器指示，应执行基于SPT选择根节点的多播快速洪泛过程，这可包括将快速故障通知多播到其它接口（如上述基于SPT选择根过程的双向多播树所示）。流程从操作1810转到操作1815。

在操作1815，路由器（例如，路由器的FFN模块）将快速故障通知消息多播到如在其数据平面中（基于上述SPT选择根过程生成的）双向多播树所示的其它路由器。应理解的是，如果不存在如在双向多播树中所示路由器下游的多播接收器（例如，另一路由器），则路由器不多播分组。在一个实施例中，也可执行环路防止过程（例如，PRF检查）。流程从操作1815转到操作1820，并且快速故障通知消息被发送到路由选择协议模块。例如，路由器的FFN模块将快速故障通知转发到路由器上的IGP模块以做进一步处理。流程随后转到操作1825，并且路由选择协议模块在适当时更新路由选择和/或转发表以反映网络故障。在一些实施例中，操作1820和/或1825可与操作1815同时或在其之前开始，然而，应理解的是，一般在多播快速故障通知消息（如果消息要多播）后才完成更新。也应理解的是，在多播快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。

PIM双向多播分布树快速故障通知消息洪泛

在一个实施例中，用于快速故障通知消息的输送机制使用双向多播分布树，该树使用PIM（协议独立多播）协议来构建。构建的双向多播分布树专用于快速故障通知消息。在一特定实施例中，双向PIM (BIDIR-PIM)协议用于为快速故障通知消息的快速洪泛建立双向多播树。然而，在其它实施例中，PIMFLYY的其它变型（例如，PIM-ASM（任何源多播）、PIM-SSM（源特定多播））用于为快速故障通知消息的快速洪泛构建多播树。

在一个实施例中，专用多播地址被定义并用于快速故障通知消息洪泛。此专用多播地址用于为快速洪泛识别快速故障通知消息。路由器中每个参与路由器包括BIDIR-PIM协议实现，并且配置和运行BIDIR-PIM协议以生成双向多播树并促使该多播树下载到路由器的数据平面（例如，安装在一个或多个线路卡上）。在构建双向多播树时，BIDIR-PIM协议使用从路由协议（例如，IGP模块）获得的信息。在散布快速故障通知消息中使用双向多播树。另外，每个路由器添加专用多播地址以加入多播组。使用下载的双向多播树，使用普通多播协议来转发快速故障通知消息。

图19示出根据一个实施例的由检测到网络故障的路由器使用双向多播树，为使用多播快速故障通知消息来发起域范围的FFFC而执行的示范操作，双向多播树使用PIM协议来构建。在操作1910，路由器检测到网络故障。在一个实施例中，第2层链路事件监视和信号发送用于检测故障。在另一实施例中，双向转发检测(BFD)用于检测故障。在另一实施例中，第2层链路事件监视和信号发送及BFD的组合用于检测故障。流程随后转到操作1715。

在操作1915，路由器（例如，该路由器上的FFN模块）生成包括有关网络故障的信息的快速故障通知消息。快速故障通知消息要作为在接收路由器上的快速洪泛事件处理。快速故障通知消息向接收路由器指示应使用双向多播树执行多播快速洪泛过程，这可包括多播快速故障通知，双向多播树使用PIM协议来构建。在一个实施例中，快速故障通知消息具有专用于多播快速故障通知的多播地址的目的地地址。独立于应用层更新路由选择和/或转发表以反映网络故障，快速故障通知消息要由那些路由器转发（如果要进行任何转发）。因此，快速故障通知消息向接收路由器指示，以线路速率多播快速故障通知消息并且更新其路由选择和/或转发表以反映网络故障。

流程随后从操作1915转到操作1920，并且路由器将分组发送到专用于多播快速故障通知的多播组地址。流程随后转到操作1925，并且路由器在适当时更新其路由选择和/或转发表以反映故障（例如，IGP模块在适当时更新其路由选择和/或转发表）。

在一些实施例中，操作1925可与操作1915和/或1920同时和/或在其之前开始，然而，应理解的是，一般在生成和传送快速故障通知消息后才完成更新。也应理解的是，在生成和传送快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。因此，独立于路由选择和转发表的更新，执行生成和传送快速故障通知消息。

图20是根据一个实施例的示出由在使用双向多播树的FFFC应用中接收多播快速故障通知消息的路由器执行的示范操作的流程图，双向多播树使用PIM协议来构建。在操作2010，路由器接收包括有关网络故障的信息的多播快速故障通知消息。例如，该路由器的FFN模块接收多播快速故障通知消息。另外，快速故障通知消息也向路由器指示应执行多播快速洪泛过程，这可包括将快速故障通知多播到其它接口（如使用PIM协议构建的双向多播树所示）。流程从操作2010转到操作2015。

在操作2015，路由器（例如，路由器的FFN模块）将快速故障通知消息多播到如在其数据平面中（由PIM协议生成的）双向多播树所示的其它路由器。应理解的是，如果不存在如在双向多播树中所示路由器下游的多播接收器（例如，另一路由器），则路由器不多播分组。在一个实施例中，也可执行环路防止过程（例如，PRF检查）。流程从操作2015转到操作2020，并且快速故障通知消息被发送到路由选择协议模块。例如，路由器的FFN模块将快速故障通知转发到路由器上的IGP模块以做进一步处理。流程随后转到操作2025，并且路由选择协议模块在适当时更新路由选择和/或转发表以反映网络故障。在一些实施例中，操作2020和/或2025可与操作2015同时或在其之前开始，然而，应理解的是，一般在多播快速故障通知消息（如果消息要多播）后才完成更新。也应理解的是，在多播快速故障通知消息前，路由器不会等待直至完成更新路由选择表和转发表。

用于洪泛快速故障通知消息的基于PIM的解决方案具有的优点是许多路由器当前能够运行PIM，因此，需要写入的另外代码量相当小。另外，与用于散布快速故障通知消息的基于桥接的洪泛技术（它们是第2层机制）相比，基于PI贩解决方案使用第3层机制，并且可被认为对第3层路由选择/转发应用更容易。然而，基于PIM的解决方案确实增大了路由器配置和信令中的开销以便维护网络中的树状态。另外，基于PIM的解决方案比桥接更复杂，并且可在网络故障处理方面更不健壮。

快速故障通知消息格式

在一个实施例中，本文中所述快速故障通知消息使用独立于IGP并且是第2层协议分组以及由数据传输层发出的消息格式。如前面所述，用于快速故障通知消息的消息格式可使用现有IGP PDU分组格式。例如，如果IGP是OSPF，则反映断开的邻接（一个少数路由器链路）的OSPF外部LSA（链路状态通告）能够用作快速故障通知消息并且被快速洪泛到路由器而无特殊修改。使用现有IGP PDU分组格式具有的优点是格式已经存在（无需另外的数据格式），并且在相同LSA到达时自然集成到慢速洪泛中。然而，使用现有IGP PDU分组格式具有的缺点是它每IGP协议不同（例如，用于OSPF的现有IGP PDU分组格式不同于IS-IS的分组格式），并且消息格式由一般在控制平面中或者在其它情况下要求预计算并且仍要求数据平面（传输层）的调遣机制的IGP模块来始发。

本文中所述独立消息格式具有的优点是它独立于IGP（因此，相同消息格式可用于不同IGP实现），由数据平面（数据传输层）发出，并且更靠近触发点，从而产生每事件更短路径。

独立消息格式是基于TLV的。可在IP分组中打包或不打包TLV，这取决于基础快速洪泛传输的要求。图21示出根据一个实施例的用于快速故障通知消息的示范独立消息格式。示范快速故障通知消息格式2110包括指示该消息是快速故障通知消息的类型字段2115、长度字段2120和值变量字段，即通告路由器ID字段2125、通告链路ID字段2130、对等路由器ID字段2135和对等链路ID字段2140。这些字段识别始发快速故障通知消息的路由器和链路及遇到故障的路由器和链路。基于TLV的独立消息格式允许将来的开发和扩展。

独立消息格式允许快速故障通知消息的处理独立于IGP处理。在接收使用IGP独立格式的快速故障通知消息时，路由器将消息作为本文中描述的事件框架中的本地事件处理。在一个实施例中，超时手段用于针对使用独立消息格式的快速故障通知消息由于程序错误或其它错误状况或通过服务拒绝攻击而被错误地洪泛的情况进行保护。在计时器到期时，路由器将使系统回退以确保错误是短暂的，并且可自行恢复。

在一个实施例中，用于快速故障通知消息的独立消息不替代常规通知消息。因此，协议独立快速故障通知消息先通过本文中所述的FFFC架构被转发，并且随后是反映网络故障的常规IGP洪泛。

在使用协议独立消息格式接收快速故障通知后，消息将被发送到IGP模块进行处理。例如，IGP模块将相应地更新其路由选择拓扑数据库（例如，其LSDB），取消安全计时器（如果已实现），并且在更新的数据库上运行最短路径优先(SPF)过程以确定是否相应地更新路由选择和/或转发表。路由器也可根据使用的传输散布快速故障通知。

如本文中所述，FFFC架构将网络故障通知消息的转发从应用层分离，并将它移到数据传输层上。因此，转发网络故障通知消息不要求控制平面和数据平面交互，这降低了网络范围的收敛所必需的时间，这在发生网络故障的情况下最小化网络停工时间。

如本文中所述，操作可指诸如配置成执行某些操作或者具有预确定的功能性或在非暂时性计算机可读媒体中包含的存储器中存储的软件指令的专用集成电路(ASIC)等硬件的特定配置。因此，图中所示技术能够使用在一个或多个电子装置（例如，路由器）上存储和执行的代码和数据来实现。此类计算装置使用计算机可读媒体存储和传递（在内部和/或通过网络与其它电子装置）代码和数据，如非暂时性计算机可读存储媒体（例如，磁盘、光盘、随机存取存储器、只读存储器、闪存装置、相变存储器）和暂时性计算机可读通信媒体（例如，电、光、声或其它形式的传播信号 - 如载波、红外信号、数字信号）。另外，此类电子装置一般情况下包括耦合到诸如一个或多个存储装置（非暂时性机器可读存储媒体）、用户输入/输出装置（例如，键盘、触摸屏和/或显示器）和网络连接等一个或多个其它组件的一个或多个处理器的集合。处理器的集合与其它组件的耦合一般情况下是通过一个或多个总线和桥接器（也称为总线控制器）。因此，给定电子装置的存储装置一般情况下存储代码和/或数据以便在该电子装置的一个或多个处理器的集合上执行。当然，本发明的实施例的一个或多个部分可使用软件、固件和/或硬件的不同组合来实现。

虽然图中的流程图示出本发明的某些实施例执行的操作的具体顺序，但应理解，此类顺序是示范性的（例如，备选实施例可以在不同的顺序中执行操作，组合某些操作，重叠某些操作等）。

虽然本发明已根据几个实施例来描述，但本领域的技术人员将认识到本发明不限于所述实施例，而是能够通过随附权利要求的精神和范围内的修改和变化来实践。描述因此要视为是说明性的而不是限制性的。