网络环境中针对路由反射器客户端的自动最优路由反射器根地址分配和快速故障转移

相关申请

本申请根据35U.S.C.§119(e)要求如下申请的权益：由Keyur Patel等人于2015年2月20日提交的题为“METHOD AND APPARATUS FOR AUTOMATIC ROOT ADDRESS ASSIGNMENTTO ROUTE REFLECTOR CLITIONS IN A NETWORK ENVIRONMENT(用于在网络环境中针对路由反射器客户端的自动根地址分配的方法和装置)”序列号为62/119,048的美国临时申请；由Keyur Patel等人于2015年2月20日提交的题为“METHOD AND APPARATUS FOR ADVERTISINGORIGINTING ROUTER INFORMATION FOR BORDER GATEWAY PROTOCOL OPTIMAL ROUTEREFLECTION DEPLOYMENTS IN A NETWORK ENVIRONMENT(用于在网络环境中通告用于边界网关协议最优路由反射部署的发端路由器信息的方法和装置)”序列号为62/119,044的美国临时申请；由Keyur Patel等人于2015年2月21日提交的题为“INTERIOR GATEWAYPROTOCOL ROUTER CAPABILITY EXTENSIONS FOR ADVERTISING A NON-TRANSIT NODE IN ANETWORK ENVIRONMENT(网络环境中用于通告非传输节点的内部网关协议路由器能力扩展)”序列号为62/119,113的美国临时申请；由Keyur Patel等人于2015年2月21日提交的题为“METHOD AND APPARATUS FOR ALLOWING AN OPTIMAL ROUTE REFLECTOR ROOT ADDRESSAS PART OF AN ETHERNET SUBNET IN A NETWORK ENVIRONMENT(用于在网络环境中允许最优路由反射器根地址作为以太网子网的一部分的方法和装置)”序列号为62/119,115的美国临时申请；由Manish Bhardwaj等人于2015年2月21日提交的题为“METHOD ANDAPPARATUS FOR OPTIMIZING SHORTEST PATH FIRST COMPUTATIONS FOR FAST FAILOVEROF PATHS IN AN OPTIMAL ROUTE REFLECTOR IN A NETWORK ENVIRONMENT(用于在网络环境中优化最短路径优先计算方法以用于最优路由反射器中的路径的快速故障转移的方法和装置)”序列号为62/119,114的美国临时申请，以上全部申请的全部内容通过引用并入本文。

技术领域

本公开总体涉及网络领域，更具体地，涉及在网络环境中针对路由反射器客户端(RR客户端)的自动最优路由反射器(ORR)根地址分配和快速故障转移。

背景技术

在计算机网络中，网络管理员常常关心如何通过网络将流量流从一个端点最佳路由到另一个端点。可以在自主系统(AS)中使用路由器来确定通过自主系统传播的网络流量应被转发到的节点。路由器与自主系统内的其他路由器进行通信，以确定通过自主系统达到目的地地址的最佳路径。可以使用各种协议，包括用于在自主系统之间进行路由的边界网关协议(BGP)和用于在同一自主系统中的路由器之间进行路由以到达外部目的地的内部边界网关协议(iBGP)。内部网关协议(IGP)用于在自主系统内路由以到达内部目的地。

在hot potato路由中，分组不被存储(或缓冲)，而是不断地被传送以尝试将分组移动到它们的最终目的地。hot potato路由尝试将流量引导到给定BGP网络内最近的AS出口点。出口点是自主系统的可以用于到达外部目的地节点的退出点(例如，存在点(pointof presence，POP)或边缘路由器)。因此，在BGP路由反射部署中实现hot potato路由的能力可能给网络管理员带来重大挑战。

附图说明

为了提供对本公开及其特征和优点的更全面的了解，结合附图参考以下描述，其中相似的附图标记表示相似的部分，其中：

图1是根据本公开的至少一个实施例的具有用于提供最优路由反射的通信系统的网络环境的简化框图；

图2是示出根据至少一个实施例的与通信系统中的示例节点相关联的可能细节的简化框图；

图3是根据至少一个实施例的通信系统的可能配置的简化框图；

图4是示出根据至少一个实施例的具有附加可能元件的图3的通信系统的简化框图；

图5A-5B示出了例示根据至少一个实施例的与通信系统相关联的可能操作的简化流程图；

图6示出了例示根据至少一个实施例的与通信系统相关联的可能操作的简化流程图；

图7是示出根据至少一个实施例的通信系统中的可能交互的简化交互图；

图8是示出根据至少一个实施例的具有附加可能元件的图3的通信系统的简化框图；

图9示出了例示根据至少一个实施例的与通信系统相关联的可能操作的简化流程图；

图10是根据至少一个实施例的具有故障转移组策略的通信系统的可能配置的简化框图；

图11是表示根据至少一个实施例的示例通信系统中的节点的简化树图；

图12示出了例示根据至少一个实施例的与通信系统相关联的可能操作的简化流程图；

图13示出了例示根据至少一个实施例的与通信系统相关联的可能操作的简化流程图；和

图14示出了例示根据至少一个实施例的与通信系统相关联的可能操作的简化流程图。

具体实施方式

概述

本公开描述了针对路由反射器客户端的自动最优路由反射器根地址分配。在本公开的一个示例中提供了一种方法，该方法包括：由基于云的路由反射器将自主系统中的第一节点标识为第一路由组的候选根节点。该方法还包括：基于在第一路由协议中使用的邻居地址来标识客户端节点，将邻居地址映射到经由第二路由协议从客户端节点接收的路由信息，以及如果路由信息包括第一路由组的标识符，则将邻居地址与第一路由组相关联。

在具体实施例中，将第一节点标识为候选根节点包括：确定第一节点和第一路由组在第一协议分组中被通告，并且确定第一节点和第二路由组在第二协议分组中被通告。确定第一节点在第一和第二协议分组中被通告可以基于第一节点的路由器标识符。将第一节点标识为候选根节点还可以包括从第一路由协议或第二路由协议之一接收协议分组，该协议分组包括指示第一节点是根节点的信息。

在其他的具体实施例中，第一节点是被标识为第一路由组的候选根节点的多个节点之一，并且该方法还包括：从多个节点中选择主根节点。该方法还可以包括计算客户端节点和每个候选根节点之间的相应距离，以及确定相应距离中最短的一个，其中基于相应距离中最短的一个来选择主根节点。在更具体的实施例中，该方法包括从多个节点中选择备份根节点。该方法还可以包括计算根源于多个节点中的一个或多个节点的相应生成树，并且至少部分地基于主根节点是否是相应生成树中的任一生成树中的叶节点来选择备份根节点。在更具体的实施例中，多个节点中的每一个节点都是区域边界路由器。

在另外的具体实施例中，该方法包括：根据第二路由协议配置协议分组，该协议分组指示用于基于云的路由反射器的可达性信息仅用于控制面流量，其中协议分组被传输到自主系统中的一个或多个节点。在具体实施例中，该方法包括接收由第一节点发起的协议分组，并且该协议分组指示第一节点与子网相关联以及第一节点将作为根节点。在具体实施例中，该方法包括接收由第一节点发起的协议分组，以及通过检查协议分组中的类型长度值(TLV)要素来确定第一节点的路由器标识符(ID)，其中第一节点是第一路由组的边缘路由器。在更具体的实施例中，该方法包括至少部分地基于基于云的路由反射器的客户端节点的边界网关协议(BGP)邻居地址来标识该客户端节点，并且如果BGP邻居地址对应于由客户端节点通告的接口地址，则将BGP邻居地址与第一路由组进行关联。在另外的具体实施例中，第一路由协议是边界网关协议最优路由反射器(BGP-ORR)，第二路由协议是内部网关协议(IGP)。

本公开还描述了自主系统中的快速故障转移能力。该方法包括在基于云的路由反射器中确定第一根节点是否是针对第二根节点计算的生成树中的叶节点。该方法还包括确定与针对第一根节点计算的生成树和第二根节点的生成树相关联的路由度量差值，以及使用该路由度量差值来填充增量(delta)数据库。第二根节点是根据分配给自主系统中的多个客户端节点的故障转移策略组的第一根节点的备份。

在更具体的实施例中，通过确定第一根节点的第一生成树中的节点的第一路由度量与第二根节点的第二生成树中的相应节点的第二路由度量之间的差值来计算每个路由度量差值。在更具体的实施例中，该方法包括检测第一根节点的故障，从故障转移策略组标识第二节点，标识增量数据库中与故障转移策略组相关联的哪些路由度量差值不等于零，以及将所标识的路由度量差值传输至一个或多个监听客户端。一个或多个监听客户端可以包括在基于云的路由反射器中运行的边界网关协议最优路由反射器过程。一个或多个监听客户端可以包括多个客户端节点。在更具体的实施例中，该方法还包括：如果第一根节点是针对第二根节点计算的生成树中的内部节点，则针对第二根节点执行受限生成树计算以省略第一根节点。

元件、操作和特征中的一些或全部可以包括在用于执行所描述的功能的相应系统、装置和设备中。此外，一些或全部特征可以在至少一个机器可读存储介质中实现。

具体实施方式

图1是网络环境110的简化框图，其包括用于在自主系统中向路由反射器客户端提供最优路由反射器(ORR)根地址分配、提供快速故障转移以及类型长度值(TLV)扩展能力的通信系统100。网络环境110表示用于接收和发送通过网络传播的信息分组的互连通信路径的一系列点或节点。网络环境110提供节点之间的通信接口，并且可以包括任何局域网(LAN)、无线局域网(WLAN)、城域网(MAN)、内联网、外联网、广域网(WAN)(例如，互联网)、云网络、虚拟专用网(VPN)或有助于网络环境中的通信的任何其他适当的架构或系统。此外，网络环境110在本公开的特定实施例中可以实现UDP/IP连接并使用TCP/IP通信语言协议。或者，可以实现用于在网络环境110内发送和接收数据分组的任何其它合适的通信协议。

网络环境110示出了经由通信链路12互连的分布式节点20、30和50。节点50被配设在自主系统AS1中，节点20被配设在自主系统AS2中。自主系统AS1和AS2可以被配置为不同的路由域。节点50和20是诸如路由器之类的网络元件，其可以针对在它们各自的自主系统AS1和AS2内的端节点25之间的电子数据提供域内路由。节点20和50中的至少一些可以为电子数据提供域间路由。例如，电子数据可以被在自主系统AS1中的端节点25和自主系统AS2中的其他端节点25之间进行交换。节点30是诸如路由器之类的网络元件，并且可以被配设在云网络15中作为针对AS1的基于云的路由反射器。在至少一个实施例中，云网络15相对于自主系统AS1在物理上可以是远程的，并且可以通过互联网或其他广域网或者将AS1与节点30互连的任何其它合适的计算机网络可访问。节点30可以是与自主系统AS1相同的路由域的一部分。节点30与节点50协同工作以实现具有针对路由反射器客户端的自动ORR根地址分配、快速故障转移以及TLV扩展能力的基于云的路由反射。

端节点25旨在包括用于发起网络环境110中的通信的设备，例如台式计算机、膝上型计算机、服务器、电器、移动设备、或能够在网络环境110内发起语音、音频、视频、媒体或数据交换的任何其他设备、组件、元件或对象。端节点还可以包括试图代表另一个实体或元件发起通信的任何设备，例如能够在网络环境110内发起交换的程序、数据库或任何其他组件、设备、元件或对象。应当注意，图1是网络环境中的通信系统的可能元件的表示形式，其用于提供自主系统中具有针对路由反射器客户端的自动ORR根地址分配的基于云的最优路由反射、快速故障转移和TLV扩展功能。因此，可以在网络环境中，更具体地，在通信系统中配置任何数量的链路12，节点20、30和50，端节点25以及其他适当的元件。例如，一些自主系统可以包含数千个节点50和更多数量的端节点25和链路12。

为了说明本文公开的系统的某些示例性技术，理解可能穿过网络的通信和用于实现这种通信的协议是重要的。以下基础信息可以被视为可以适当地解释本公开内容的基础。

可以在通信系统100中实现各种路由协议，以实现从自主系统AS1到自主系统AS2的适当路由。边界网关协议(BGP)是在自主系统之间实现域间路由的示例路由协议。外部BGP(eBGP)会话提供用于允许自主系统到达其他自主系统的路由的路由信息。内部BGP(iBGP)会话提供用于针对外部目的地的自主系统内的路由的路由信息。BGP是由Rekhter,Y.,Ed.、Li,T.,Ed.以及S.Hares，Ed在请求评论(RFC)4271“A Border Gateway Protocol 4(BGP-4)”(RFC 4271，DOI 10.17487/RFC4271，2006年1月，http：//www.rfc-editor.org/info/rfc4271)中定义的众所周知的路由协议。

当BGP邻居路由器(本文也称为“对等节点”)建立连接以“陈述(speak)BGP”时，可以建立BGP会话。该连接通常是使用诸如传输控制协议(TCP)之类的面向连接的协议建立的，该协议确保在所连接的对等节点之间传递消息。所连接的对等节点可以陈述BGP来交换包含路由信息的更新消息。更新消息用于更新包含在接收对等节点的路由信息库(RIB)中的信息。更新消息可以宣布新路由或撤销先前宣布的路由。更新消息可以包括诸如网络层可达性信息(NLRI)之类的各种字段。NLRI可以包括在更新消息中被通告的可行路由的互联网协议(IP)地址前缀。相反，针对撤销路由的字段可包括被撤销的路由的IP地址前缀，因为它们不再可达。路由是将一组目的地与到这些目的地的路径的属性进行配对的信息单元。路径可以由一个或多个属性定义，并且通常旨在表示网络(例如，自主系统)中的两个点之间的路由。从IPv4或IPv6池取得的IP地址可被分为网络部分和主机部分两部分。网络部分标识一组目的地，并被称为前缀。目的地地址中的前缀由路由协议用于针对路径中的下一跳呈现路由决定。前缀也可以被称为“路由前缀”。

自主系统可以使用iBGP来通告自主系统外部的目的地(例如，路由器)的网络地址前缀的可达性信息。然而，为了实现iBGP，需要完整网格(full mesh)，其中自主系统内的每个路由器通过诸如TCP之类的连接被连接到每个其他路由器。该完整网格的需求可能严重限制运行iBGP会话的自主系统的可扩展性。

在BGP网络中，路由反射通常是期望的，因为可以避免完整网格的实现方式。路由反射器部署可以大大减少网络中所需的iBGP会话数量。路由反射是Bates,T.、Chen,E.和R.Chandra在请求评论(Request for Comment(RFC))4456，“BGP路由反射：完整网格内部BGP(IBGP)的替代方案”(RFC 4456，DOI 10.17487/RFC4456，2006年4月，http://www.rfc-editor.org/info/rfc4457)中定义的众所周知的路由协议。

路由反射器(RR)是在BGP网络中用于实现路由反射的网元。路由反射使路由信息能够在路由器之间共享，而无需实现完整网格。在BGP路由反射部署中，一个或多个路由器被指定为路由反射器，并允许接受和传播iBGP路由到其客户端。所指定的路由反射器可以利用路由反射器之间的iBGP对等体会话而被完整网状关联(fully meshed)。每个路由反射器可以与多个路由器对等，这些路由器在本文中可以被称为路由反射器客户端(“RR客户端”)。在一些实现方式中，每个路由反射器的RR客户端形成该路由反射器所连接的路由器集群。路由器集群可以经由iBGP通过它们的共享路由反射器而连接。路由反射器可以将其从其他路由反射器接收的路由信息传播到其RR客户端，并将其RR客户端的路由信息传播到其他路由反射器。因此，可以大大减少BGP网络中所需的会话次数。

在hot potato路由中，路由器(例如，路由反射器)尝试呈现最佳路径路由决策，该最佳路径路由决策将网络流量定向到给定BGP网络内最接近该呈现决策的路由器的自主系统(AS)出口点。通常，路由反射器基于从其IGP数据库计算的内部网关协议(IGP)度量来选择最佳路径，并且向其RR客户端BGP陈述者宣布该路径。度量是用于测量到给定网络的距离的定量值。一般来说，对于hot potato路由，针对网络的最佳路径是具有最低度量的路径。

路由反射器可以被实现为任何类型的路由器，包括例如部署在自主系统的周边上的边界或边缘路由器，或者作为云网络中的分布式路由器。虽然路由反射器通常位于集群内的转发路径(例如，在存在点(POP)边界)处，并且与网络的实际拓扑保持一致，但虚拟路由反射器(vRR)和可能的其他路由反射器可以被放置在集群之外。例如，环形拓扑结构使得很难自然地形成路由反射器集群，并且诸如第3层虚拟专用网(L3VPN)之类的隧道化(tunneled)应用在转发路径中不一定需要路由反射器。此外，分布式路由反射器可以作为网络上的路径聚合点，以减少BGP信息向边缘路由器的分发，其中，边缘路由器可能具有有限的CPU和内存。

对于不在最优转发路径中的路由反射器(包括诸如vRR之类的集中路由反射器)而言，hot potato路由变得有问题。不在最优转发路径中的路由反射器或者以在网络中不符合网络拓扑的方式被放置的路由反射器可能会失去向其客户端通告实现hot potato路由的最佳路径的能力。因为路由反射器及其客户端的出口点的选择是最接近路由反射器的出口点，因此在路由反射器不在最优转发路径中的BGP路由反射器部署中，所选择的出口点可能对于路由反射器客户端(RR-clients)而言不一定是最接近的出口点。因此，由路由反射器呈现并通告给RR客户端的最佳路径路由决策可能不是去往目的地的最佳路径(例如，具有最优度量)。因此，路由反射器的部署可能被限制到促进最优hot potato路由的适当的集群边界或者在适当的中心位置。

BGP最优路由反射(BGP-ORR)允许路由反射器在云环境中运行，而不会影响hotpotato路由。BGP-ORR要求路由反射器(RR)将其RR客户端与最优路由反射器(ORR)根地址相关联，作为BGP-ORR功能的一部分。ORR根地址是网络中IGP SPF(内部网关协议最短路径优先)被扎根于以计算最短路径优先(SPF)拓扑的地址。SPF逻辑是确定从自身到网络中所有其他路由器的最短路径的算法。当路由协议(例如，内部网关协议(IGP))使网络中的每个路由器知道所有其他路由器和连接它们的链路时，可以执行SPF逻辑。BGP-ORR是由Raszuk,R.、Cassar,C、Aman,E.、Decraene,B.和S.Litkowski在域间路由工作组互联网草案“BGP最优路由反射(BGP-ORR)”(draft-ietf-idr-bgp-optimal-route-reflection-08，2014年10月22日，https://tools.ietf.org/html/draft-ietf-idr-bgp-optimal-route-reflection-08)中定义的路由协议。

BGP-ORR要求路由反射器向其RR客户端宣布定制的BGP最佳路径。为了宣告定制的最佳路径，路由反射器可以执行以下操作：1)存储IGP数据库，就像它已经扎根在RR客户端上一样；以及2)多次运行最佳路径算法，针对每个客户端运行一次。存储IGP数据库就好像它已经扎根在RR客户端上可能需要大量的内存和CPU资源。针对每个单独的客户端运行最佳路径算法也可能使用大量的CPU资源。随着网络扩展，这可能变得更加成问题。

BGP-ORR多次运行SPF逻辑以确定从一个路由器(这里称为“根节点”)到其网络中的其他路由器的最短路径。基于这些计算，BGP-ORR可以在一个或多个IGP拓扑中创建根源于各种被配置的节点的最小生成树(SPT)。RR客户端通过配置与SPT(作为SPF根节点)关联，并且SPT中的IGP度量用于在向RR客户端执行路由反射时进行最佳路径计算。可以针对SPT中的每个节点计算IGP度量，并且IGP度量可以表示SPT中连接的节点之间的链路成本或距离。在云环境中运行的BGP-ORR通过来自每个IGP区域的BGP链路状态(BGP-LS)馈送和/或IGP馈送可以看到所有IGP拓扑。在至少一个场景中，每个RR客户端都作为SPF根与其自身关联，从而创建根源于每个RR客户端的SPT。然而，应该注意的是，驻留在云中的节点的BGP-ORR可以针对潜在的数千个RR客户端执行路由反射。因此，在至少某些情况下，可能更具可伸缩性和充足能力来将RR客户端分组并与将其与SPF根(通常是IGP区域边界路由器(ABR))相关联。

本公开的至少一个实施例可以解决与分区BGP-ORR网络相关联的上述问题(以及更多)。本公开的实施例可以在如下通信系统中提供，在该通信系统中，将运行BGP-ORR的路由反射器实现为云网络中的虚拟或物理路由器。这种基于云的路由反射器自动进行以下处理：选择最优的SPT根并将RR客户端与这些SPT关联起来。特别地，并且在至少一个实施例中，自主系统的基于云的路由反射器(CBRR)可以通过以下方式自动地将根地址与自主系统中的给定客户端边缘路由器进行关联：1)将位于集群边界处的ABR标识为基于云的路由反射器的RR客户端；2)将边缘路由器标识为基于云的路由反射器的RR客户端，并将边缘路由器与其ABR相关联；以及3)使用ABR、边缘路由器及其关联关系来将根地址自动分配给RR客户端边缘路由器。自动标识ORR根地址在具有多个集群的复杂网络中特别有用，用于实现对ORR根地址的自动分配。除边缘路由器之外，内部路由器也可以被标识为RR客户端，被与ABR进行关联，并且被分配以根地址。一旦基于云的路由反射器标识了自主系统内的RR客户端集群，它就可以对每个集群运行一次最佳路径计算。

转到图2，图2是如图1所示的节点30和节点50的可能实施例的简化框图。在此描述的实施例中，节点30是基于云的路由反射器，节点50是基于云的路由反射器的路由反射器客户端。节点30和50可以分别包括多个网络接口35和55，至少一个存储器元件37和57以及至少一个处理器39和59。处理器39和59可以可操作地耦合到相应的网络接口35和55，其包括用于在网络环境110中通过通信链路12进行通信的合适的发送和接收组件。此外，节点30和/或50可以在物理或虚拟化环境或其任何适当的组合中实现。

可以在节点30和50中实现路由协议，以促进自动ORR根地址分配、快速故障转移和类型长度值(TLV)扩展能力。经边界网关协议优化的路由反射器(BGP-ORR)60可以在节点30中实现，边界网关协议(BGP)65可以在节点50中实现。可以在节点30与其RR客户端(例如，节点50)之间经由诸如TCP/IP之类的传输协议发送和接收BGP通信。在至少一个实施例中，节点30的BGP-ORR还包括根选择逻辑64，用于自动选择最优且通常为区域边界路由器的SPF根，标识其他RR客户端(例如，边缘路由器和内部路由器)，将其他RR客户端适当地与ABR进行关联，并且将根地址分配给RR客户端。BGP-ORR 60还包括最短路径优先(SPF)逻辑66，用于计算根源于特定IGP节点(例如，由根选择逻辑64选择的节点)的SPF，以及基于该计算来创建SPT。节点30的BGP-ORR 60还包括最佳路径选择逻辑62，用于计算穿过自主系统AS1到达诸如自主系统AS2中的节点的外部目的地的最佳路径。可以在节点50和节点30之间建立网络连接，以陈述BGP并交换可用于将数据从自主系统AS1的内部节点路由到外部目的地的路由信息。

内部网关协议(IGP)70和80可以分别在节点30和50中实现。IGP 70和IGP 80可以包括对应的发起器和接收器的扩展对(例如，逻辑，分组报头定义等)，以在IGP处理期间实现某些通信。可达性扩展发起器72和对应的可达性扩展接收器82可以使得节点30能够在IGP(例如，用于BGP会话管理)中宣布其可达性，并且明确地表明所宣布的可达性不被用于转发数据流量。在至少一个实施例中，该特征可以用IGP协议分组的子TLV要素或新的类型长度值(TLV)来实现。虽然此特征适用于BGP-ORR网络，但明显的是，该特征可以扩展到任何无法进行转发的基于云的路由器，但需要成为网络中控制面的一部分。

IGP 80和IGP 70的另一扩展对可以包括通告扩展发起器84和相应的通告扩展接收器74。扩展对74和84使BGP-ORR 60能够通过添加足够的信息以将路由协议分组关联到其发起节点，来在异步系统AS1中与多个分区区域(例如，开放最短路径优先(OSPF))或级别(例如，中间系统到中间系统(IS-IS))工作。在一个示例中，如果IGP 70和IGP 80实现OSPF路由协议，则路由协议分组可以包括链路状态通告(LSA)。在另一示例中，如果IGP 70和IGP80实现IS-IS路由协议，则路由协议分组可以包括链路状态分组(LSP)。使用通告扩展发起器84和接收器74使得根地址可以与边缘路由器相关联，而不是ABR，如果需要该实现方式的话。在至少一个实施例中，可以使用协议分组的子TLV要素或新的类型长度值(TLV)来实现该特征。

IGP 80和IGP 70的其他扩展对可以包括以太网扩展发起器86和以太网扩展接收器76。扩展对76和86使得能够将主机地址与路由协议分组(例如，LSA或LSP)相关联。因此，当根地址映射到以太网子网时，该根地址可以与给定节点相关联。在至少一个实施例中，该特征可以用链路状态通信(例如，LSA或LSP)的子TLV要素或新的类型长度值(TLV)来实现。

在至少一个实施例中，与本文所描述的实施例相关联的数据可以分别被存储在节点30和50的存储器元件37和57中。在节点30中，数据可以包括但不限于最优路由反射器路由信息库(ORR RIB)表95。ORR RIB表95可以包括在通信系统100中运行的所有路由协议的所有路由信息。例如，ORR RIB表95可以包括针对每个BGP下一跳的IGP度量(例如，成本或距离)，其可以从指定的根节点进行测量。另外，ORR RIB表95(或一些其他合适的存储结构)可以包括针对由节点30的客户端通告的网络地址前缀的可达性信息。

在至少一个实施例中，存储在节点30中的其他数据可以包括生成树(SPT)数据库92、增量数据库94(1)-94(X)、策略存储装置96和接口数据库98。SPT数据库92、增量数据库94(1)-94(X)和接口数据库98可以被配置为单个或多个存储结构，这取决于具体实现方式、设计和/或需要。这些存储元件可以与节点30中的故障转移模块90相关联，当具有主SPT的主根节点变得不可达时，节点30中的故障转移模块90可以利用备份SPT向备份根节点执行快速(或经优化的)故障转移。SPT数据库92可以包括最小生成树(SPT)，其中每个SPT根源于通信系统100中的IGP节点。SPT是一种表(其可以由树图逻辑地表示)，其具有IGP区域或级别(或多个区域或级别)中的所有节点以及与表中每个节点相关联的IGP度量。SPT可以通过BGP-ORR 60计算多个SPF(例如，通过运行SPF逻辑66)来创建。

策略存储装置96包括一个或多个故障转移策略组。每个策略组定义SPT序列，其中一个SPT可以在任何给定的时间是“活动的”。活动SPT可用于针对策略组被分配给的RR客户端计算AS1中的最佳路径。序列中至少可以包含两个SPT。一个SPT根源于被指定为主根节点的节点处。第二SPT根源于被指定为主根节点的第一备份根节点的节点。额外的SPT可以包括在序列中，并且根源于被指定为附加备份根节点的节点(例如，辅助备份，三级备份等)。故障转移策略组中的每个SPT都包含相同数量的IGP节点。此外，每个SPT可以与一个或多个策略组相关联。

增量数据库(例如，增量数据库94(1)-94(X))跟踪根源于不同节点处的两个SPT中的IGP度量之间的增量(或差值)。每个增量数据库都属于故障转移策略组。被在增量数据库中跟踪的两个SPT与该增量数据库所属的同一策略组相关联。两个SPT被包含在由策略组定义的SPT序列中。一个SPT根源于当前活动的根节点，另一个SPT根源于备份根节点。因为故障转移策略组中的所有SPT都由同一组节点组成，所以增量数据库可能与SPT数据库分开，并且只需要一个增量数据库。

在一些实施例中，增量数据库可以跟踪两个SPT中每个节点之间的IGP度量的差值。在其他实施例中，增量数据库可以跟踪两个SPT中的节点的接口的IGP度量的差值。这可能是期望的，因为诸如BGP-ORR的SPF计算过程的一些客户端可能对节点的接口的IGP度量感兴趣，而不是节点本身的IGP度量。在至少一个实施例中，通过路由协议分组(例如，LSA、LSP)学习的被附连到IGP节点的所有接口(或静态配置的路由)可以继承IGP节点的成本。

在节点50中，所存储的数据可以包括路由信息库(RIB)表51，路由信息库(RIB)表51包括路由信息以使得节点50能够对自主系统AS1内的网络流量进行路由并且可能路由到外部目的地。具体地，在最佳路径被选择并由节点30通告之后，RIB表51可以包含用于网络地址前缀的最佳路径信息。RIB表51的内容可以至少部分地基于其在自主系统AS1内的位置。例如，路由信息可以基于节点被分配到的路由器集群而变化。存储在一个集群的路由器中的特定前缀的最佳路径可以相对于存储在同一自主系统中的另一集群的另一路由器中的相同前缀的最佳路径而变化。

图3是示出用于在自主系统中针对路由反射器客户端提供自动ORR根地址分配、提供快速故障转移和TLV扩展能力的通信系统300的可能配置的框图。在至少一些实施例中，通信系统300是通信系统100的可能配置的示例。通信系统300中的节点(例如，330、350、355)被配设为自主系统，其定义不同的路由域。自主系统中的节点被划分成两个集群380(例如，集群A和集群B)。集群A中的节点包括区域边界路由器350(例如，ABR1)和边缘路由器355(例如，ER1和ER2)。集群B中的节点包括另一个区域边界路由器350(例如，ABR2)和其他边缘路由器355(例如，ER3和ER4)。在图3的实施例中，边缘路由器ER1、ER2、ER3、ER4和区域边界路由器ABR1和ABR2是CBRR 330的客户端，并且每个可以建立与CBRR 330的连接或BGP会话316(例如，TCP连接)以陈述BGP。

边缘路由器355可以表示自主系统边界路由器(ASBR)、客户边缘路由器(CE)、提供商边缘路由器(PE)、存在点(POP)以及在自主系统的边缘或周边处配设的任何其他节点(其可以是出口点)，并且参与与云网络315中的CBRR 330的BGP会话。也可以在集群中配设其他节点(未示出)，例如内部路由器(或内部节点)。通常，区域边界路由器350和边缘路由器380可以以与节点50相同或相似的方式被配置，并且CBRR 330可以以与节点30相同或相似的方式被配置。

区域边界路由器ABR1和ABR2表示位于内部网关协议(IGP)的一个或多个区域或级别的边界附近的路由器。IGP是用于在自主系统内的路由器之间交换路由信息以到达内部目的地的路由协议。IGP的示例包括开放最短路径优先(OSPF)和中间系统到中间系统(IS-IS)。在通信系统300中，每个集群可以具有其自己的IGP域(例如，OSPF的区域或IS-IS的级别)。通常，IGP的区域/级别是可能比自主系统小的自主系统的路由组。在至少一些实施例中，IGP路由组对应于通信系统300的集群。然而，在其他实现方式中，集群可能不与路由组具有一一对应关系。ABR1和ABR2各自可针对流向其相应路由组内的节点或者从其相应路由组流向自主系统内的其他路由组中的节点的网络业务提供入口和出口点。然而，在一些实现方式中，IGP可具有单个平坦区域。为了便于说明，在本示例中，集群A和B对应于不同的IGP路由组。因此，在该示例中，ABR1和ABR2可以在集群A和B之间执行数据路径转发。另外，在本实施例中，ABR1和ABR2由CBRR 330选作它们相应的集群A和B的根节点。

IGP邻居(具有公共链路的两个路由器)可以形成用于交换路由协议分组的邻接。由路由器传送的路由协议分组可以包含路由器的本地路由拓扑，例如包括路由器ID、路由器的IP地址、到路由器区域内的其他路由器的链路、以及针对每个链路的路由度量。链路状态通告(LSA)和链路状态分组(LSP)分别是用于在OSPF和IS-IS中进行通信的路由协议分组。为了便于说明，本文描述的实施例通常涉及在OSPF中使用的“链路状态通告”(或“LSA”)和“区域”。然而，显而易见的是，本文公开的实施例可以应用于任何其他合适的IGP，包括但不限于IS-IS。在IS-IS中，路由协议分组被称为“链路状态分组”(或“LSP”)，并且路由组被称为“级别”。

在IGP中，每个路由器具有其自己的唯一路由器ID。例如，OSPF可以通过在路由器的环回(loopback)接口上配置IP地址来设置路由器ID。在IS-IS中，路由器ID(或系统ID)可以由管理员以各种合适的方式配置(例如，环回接口的IP地址，介质接入控制(MAC)地址，顺序编号等)。

自主系统中的路由器可以被划分成其中路由器交换LSA的区域。例如，区域中的每个路由器在该区域中宣布其所有接口信息。指定的路由器(例如，ABR1和ABR2)可以发送和接收来自同一自主系统中的其他路由器的LSA更新。在图3中，ABR1和ABR2可以将它们相应区域的LSA分组发送到CBRR 330。

在图3的示例配置中，集群A和B被映射到两个不同的区域。第一区域(例如，区域1)对应于集群A，并且包括ABR1、ER1和ER2。第二区域(例如，区域2)对应于集群B，并且包括ABR2、ER3和ER4。在OSPF中，可以提供区域0(未示出)作为骨干，区域1和区域2通过该骨干彼此通信并且与CBRR 330进行通信。在一个示例中，区域中的每个路由器将通告其可达性的LSA发送至该区域的ABR。ABR可以将其区域中的所有路由器的LSA发送到CBRR 330。在一个实现方式中，CBRR 330可以建立到每个ABR的隧道，并建立相同协议以接收相应区域的LSA。在另一实现方式中，ABR可将其所有IGP信息放入BGP分组，并通过BGP发送给CBRR 330。然而，显而易见的是，可以采用用于传输数据的任何其他合适的技术来将路由拓扑信息从区域发送到CBRR 330。

基于云的路由反射器(CBRR)330包括路由反射能力。边缘路由器ER1、ER2、ER3和ER4以及区域边界路由器ABR1和ABR2是CBRR330的路由反射器客户端(RR客户端)。CBRR 330可以是云网络315中的虚拟或物理路由器。CBRR 330不在自主系统的转发路径中，因此可以使用根选择逻辑64和经优化的最佳路径选择逻辑62运行BGP-ORR 60，并且被配置为仅接收和发送控制面信息。

在操作方面中，并且根据一个特定实施例，IGP可以针对自主系统中的每个节点(例如，ABR1，ABR2，ER1，ER2，ER3和ER4)向CBRR 330通告路由器信息。CBRR 330可以将ER1、ER2和ABR1标识为RR客户端，并且可以将其分组到集群A中。CBRR 330可以将ER3、ER4和ABR2标识为RR客户端，并且可以将其分组到集群B中。可以使用各种方法将节点分组到集群，例如包括手动配置集群或使用现有协议(例如，BGP，IGP)的信息来标识客户端并将客户端分组到集群。在至少一些实施例中，CBRR 330可以使用作为BGP属性的集群标识符来确定哪些节点在同一集群中。在其他实施例中，集群可以对应于IGP区域(或级别)，因此可以基于IGP区域成员资格来配置集群。在另外的实施例中，可以手动配置集群。

在至少一个实施例中，形成集群并且可以由CBRR 330自动选择根节点。在该实施例中，最初创建最优路由反射器根列表。CBRR 330通过检查ABR是否参与级别1-2中间系统到中间系统(IS-IS)拓扑或参与开放最短路径优先(OSPF)拓扑中区域0和的另一个区域二者来标识要添加到候选根列表中的ABR。虽然最优路由反射器根(ORR root)是IGP路由器，但它可以由路由器的接口地址标识，因为该接口地址是IGP和BGP之间的通用标识符。当LSA被发送到CBRR 330时，CBRR 330可以确定接口地址是否已经在其接口数据库(例如，接口数据库98)中，如果是，则确定其不是由不同于已经存在于其数据库中的IGP节点的另一IGP节点来宣布。执行此错误检查以确保多个生成树(SPT)不是根源于同一IGP节点。如果节点先前在另一区域的另一LSA中被宣布，那么该节点可以被标识为ABR。在至少一个实施例中，可以基于两个LSA中的节点的唯一标识符(例如，路由器ID)来进行该标识。如果在不同的区域宣布不同的接口，则LSA可包含节点的不同接口。在其他可能的较不常见的情况中，如果在不同的区域中宣布同一接口，则LSA可能包含节点的该同一接口。

也可以使用替代技术来选择根节点。例如，可以引入新的IGP类型长度值(TLV)要素，其被配置为将节点标记为给定IGP区域的潜在根。或者，可以使用新的BGP扩展团体(community)来将节点标识为ORR根。扩展团体是BGP路由的属性，并且可用于将ABR的地址指示为ORR根。该标识可以在候选IGP节点处通过配置进行。在至少一个实施例中，该显式候选ORR根可以覆盖该IGP区域的任何隐式ORR根。

如果相同区域中的ABR被标识为ORR根，则RR客户端可以与ABR相关联。RR客户端可以通过其BGP邻居地址来标识。在大多数情况下，BGP邻居地址是其环回地址。然后RR客户端邻居地址被映射到其IGP链路状态通告(LSA)，以解析IGP LSA的区域标识符(区域ID)。因此，RR客户端邻居地址与IGP区域和IGP区域ID绑定。相同的逻辑可以应用于ABR地址。具有作为RR客户端区域ID的同一区域ID的所有ABR可以是候选ORR根地址。

在存在多个候选根的情况下，可以使用许多算法来选择主根地址。示例算法涉及CBRR 330计算RR客户端与每个候选ORR根的距离并将其与具有最短距离的ABR相关联。在候选ORR根列表较长的情况下，如本文前面所述，可以使用IGP TLV扩展来将节点标记为给定IGP区域的潜在根。或者，可以向操作者呈现完整的ORR根列表并提示操作者对其进行修剪。在至少一些实现中，操作者可以通过配置来覆盖CBRR的RR客户端的自动关联。

最后，还可以至少部分地基于RR客户端与每个ORR根的距离来选择备份生成树(SPT)或备份序列。备份SPT的选择算法中的附加约束是备份SPT中主ORR根的深度。将主ORR根作为叶节点的备份SPT可能是期望的，因为如果主ORR根出现故障，则不需要重新计算备份SPT，并且备份SPT可以立即成为新的主SPT。

图4是示出通信系统300的附加元件和集群的简化框图。如图4所示，通信系统300还可以包括在第三集群380(例如，集群C)中划分的附加节点。集群C包括区域边界路由器350(例如，ABR3)和边缘路由器355(例如，ER5和ER6)。也可以在集群C中配设诸如内部路由器的其他节点(未示出)。通信系统300还可以包括实现为基于云的路由反射器(CBRR)330和ABR1之间的路由器357(例如，R1)的节点。

图4中示出了附加元件，其包括可由CBRR 330维护的最优路由反射器路由信息库(ORR RIB)表395。在至少一个实施例中，ORR RIB表395可以包括与外部网络地址的前缀相关联的路由信息。可以通过由通信系统300中的边缘节点ER1-ER6通告的路由信息来填充该路由表。在至少一个实施例中，ORR RIB表395可以包括用于自主系统中的每个集群的每集群的路由信息。

ORR RIB表395中的路由信息还可以包括但不限于对CBRR的RR客户端(例如，ER1-ER6)实现最佳路径选择的路由器ID和IGP度量(例如，成本、距离)。存储在ORR RIB表395中的IGP度量可以从集群的根节点(例如，ABR1，ABR2，ABR3)到集群内的RR客户端(例如，ER1-ER6)进行测量。在390处指示了通信系统300中的节点之间的每一跳的示例IGP度量。IGP下一跳成本390用于计算存储在ORR RIB表395中的IGP度量。例如，如集群A中所示，ORR RIB表395中的信息，ABR1到ER1和ER2的成本各自为1，因为每条路径穿过一跳，成本为1。从ABR1到ER3和ER4的成本各自为2，因为每条路径穿过两跳，每跳hop的成本为1。从ABR1到ER5和ER6的成本各自为3，因为每条路径穿过两个跳，其中一跳的成本为1，另一跳的成本为2。

转到图5A-5B，图5A-5B示出了可以与本文所述的用于针对路由反射器客户端自动分配最优路由反射器根地址的实施例相关联的操作的可能流程500的流程图。在至少一个实施例中，一组或多组操作对应于图5A-5B的活动。基于云的路由反射器(例如，30、330)可以使用一组或多组操作。基于云的路由反射器可以包括用于执行操作的装置，例如至少一个处理器(例如，39)。在实施例中，流程500的至少一些操作可以由基于云的路由反射器中的经边界网关协议优化的路由反射器(例如，60)的根选择逻辑(例如，64)来执行。为了便于说明，下面参考图4中所示的通信系统300来讨论图5A-5B。

在502，CBRR 330从通信系统300内的IGP路由协议分组中提取信息。在至少一个实施例中，可以从由通信系统300的RR客户端生成的链路状态分组(LSP)或链路状态通告(LSA)中提取信息。在一个示例中，可以在CBRR 330和在通信系统300中实现的特定IGP域(例如，OSPF区域或IS-IS级别)的区域边界路由器之间建立隧道。可以在IGP中建立CBRR330与ABR1、ABR2和ABR3中的每一个之间的邻接。特定区域内的路由器生成的LSA可以被从该区域的ABR传输到CBRR 330。在另一示例中，ABR可将其IGP信息(用于其本身和其区域内的其他路由器)放入可被转发到CBRR 330的BGP分组中。此外，用于传输数据的任何其他合适的技术(例如，文件传输协议等)可以用于将IGP域的路由信息传输到CBRR 330。

在至少一个实施例中，在IGP路由协议分组中通告的网络协议(IP)地址已经被配置为CBRR 330中的RR客户端。例如，ER1-ER6和ABR1-ABR3的IP地址可以由CBRR 330配置为RR客户端。CBRR 330使用IGP信息(例如，来自LSA，LSP等)来标识可能的(候选)ORR根，并将RR客户端与ORR根相关联。初始地，可以通过评估每个路由器的路由协议分组中包含的路由器和区域信息来标识候选ORR根。在至少一些实施例中，还可以评估包含在路由协议分组中的接口信息。路由器可以包含用于多个物理网络连接的多个接口。

在至少一个实施例中，可以针对接收的每个路由协议分组(例如，LSA，LSP等)执行操作504-516。为了便于说明，本文中使用“LSA”来描述图5A-5B的操作。然而，显而易见的是，该逻辑可以应用于其他路由协议(例如，IS-IS等)的其他路由协议分组(例如，LSP等)。

在504，可以确定在LSA中通告的路由器的接口是否先前在另一LSA中被宣布。在一个示例中，该确定可以基于接口的IP地址以及IP地址是否存在于CBRR 330的接口数据库(例如，接口数据库98)中。如果接口数据库中不存在该IP地址，那么在506，可以将该IP地址和相关联的路由器的标识(例如，路由器ID)添加到接口数据库。

如果在504确定接口已经存在于CBRR 330的接口数据库中，则可以在508处确定接口(例如，接口的IP地址)是否先前在发起于同一路由器的LSA中被通告。该确定可以基于LSA中包括的路由器的路由器ID。如果确定接口先前没有被同一路由器通告(即，接口先前被另一路由器通告)，则可以标识错误，因为多个路由器不能与接口的同一IP地址相关联。流程可以在516处继续进行，其中可以确定是否要评估另一LSA，如果是，则可以在504开始针对另一LSA的处理。

然而，如果在508确定接口先前在发起于同一路由器的另一LSA中被通告，或者如果在504确定LSA中的接口先前未在另一LSA中被宣布，则流程可以进行到512。在512，可以确定路由器是否先前针对另一区域(例如，区域1、区域2等，或级别1、级别2等)进行通告。当自主系统被划分成多个区域时，在LSA中通告其IP地址的每个路由器可以与区域标识符(区域ID)相关联。该区域ID可以被包含在路由器所通告的LSA中。特定区域中的ABR可以从该区域中的其他路由器接收LSA，并且可以将LSA传输到其他区域中的其他ABR和CBRR 330。在OSPF中，ABR可以参与多个区域(例如，ABR1可以参与区域1和区域0)，因此，ABR可以针对其参与的每个区域传输LSA。因此，CBRR 330可以从包括区域1的ABR接收一个LSA，并且从其头部中包括区域0的同一ABR接收另一LSA。确定相同路由器是否在针对不同区域的不同LSA中被通告可以基于LSA中的路由器ID。应当注意，当实现其他路由协议时，可以进行类似的评估。例如，在IS-IS中，ABR可以参与多个级别，可以对LSP进行评估，以确定是否在不同级别的不同LSP中通告了同一路由器。

如果在LSA中指示的路由器先前针对相同的区域或级别被通告，如512处进行的确定，则路由器可能不是ABR，因此不被标识为可能的ORR根。流程可以在516继续，其中可以确定是否要评估另一LSA，如果是，则可以在504开始针对另一LSA的处理。

然而，如果路由器先前针对不同的区域被通告，如在512处进行确定的那样，则在514，路由器可以被标识为ABR并被添加到候选ORR根列表。在至少一个实施例中，可以将ABR的标识符(例如，路由器ID、IP地址)添加到潜在的ORR根列表中。流程可以在516继续，其中可以确定是否要评估另一LSA，如果是，可以在504开始针对另一LSA的处理。对于CBRR接收的所有LSA，可以继续处理。

通常，当路由器在针对不同区域的多个LSA(或不同级别的多个LSP)中被通告时，在每个LSA中包括不同的接口。例如，考虑具有两个接口I0和I1的路由器A。如果I0是区域0的接口，并且I1是区域1的接口，则可以生成一个LSA来向路由器A宣布I0和区域0，并且可以生成另一LSA来向路由器A宣布I1和区域1。LSA可以包括路由器A的相同路由器ID。因此，路由器A可以被标识为区域1(可能为区域0)的可能的ORR根候选。然而，在一些配置中，可以针对两个区域通告路由器的相同接口。例如，考虑路由器B，其针对区域0和区域1具有一个接口I2。可以生成LSA以向路由器B宣布I2和区域0，并且可以生成另一LSA以向路由器B宣布I2和区域1。在这种情况下，例如，路由器B可以被标识为区域1的可能的ORR根候选。

如果在516处确定不再有待评估的LSA，则可以执行520-530的操作以将RR客户端与ABR相关联。在至少一个实施例中，该关联可以基于自主系统中划分的区域和包括ABR在内的RR客户端的BGP邻居地址。ORR RIB表395中的路由信息可以包括RR客户端的BGP邻居地址。在至少一些实施例中，RR客户端的BGP邻居地址可以与来自RR客户端的LSA分组中通告的IGP接口地址(例如，RR客户端的环回地址)相同。

在520，CBRR 330通过其BGP邻居地址来标识RR客户端，例如在RIB表395中。在522，BGP邻居地址被映射到由RR客户端发起的LSA(或来自LSA的信息)。LSA分组可以包括被分配给发起LSA的RR客户端的区域ID。因此，在528，RR客户端的BGP邻居地址可以与IGP区域和区域ID相关联。ABR和其他RR客户端都可以与IGP区域和区域ID相关联。与其他RR客户端关联于相同的区域ID的ABR现在是这些其他RR客户端的候选根节点。

在530，如果另一RR客户端被其BGP邻居地址标识，则流程返回到522，以将BGP邻居地址映射到LSA，并且解析BGP邻居地址的区域和区域ID。然而，如果在530确定没有更多的RR客户端被标识，则在532，对于具有多个候选根节点的每个区域(例如，包含多个ABR的区域)选择单个根。可以使用各种技术从候选根节点列表中标识单个ORR根。可以使用示例性算法来计算特定RR客户端与每个候选ORR根的距离。可以选择距离RR客户端最短距离的ABR作为特定区域的ORR根。在一些实施例中，如果已知RR客户端负载信息，则可以使用具有最大负载的RR客户端(或一组RR客户端)来确定具有到该RR客户端(或该组RR客户端)的最短路径的候选根节点。可替代地，可以使用其他技术来选择候选根节点作为特定区域的ORR根。例如，可以选择具有最低或最高IP地址(或其他标识符)的候选根节点作为ORR根。在另一示例中，IGP TLV扩展可用于将节点标记为给定IGP区域的潜在根，如本文前面所述。在另一实施例中，可以向操作者呈现完整的ORR根列表并提示对其进行修剪。最后，操作者可以通过配置来覆盖CBRR的RR客户端的自动关联。

在选择单个ORR根后，在534，可以选择一个或多个备份ORR根。对于每个备份ORR根，可以计算和存储生成树(例如，生成树数据库92)。可以以与确定主ORR根相同的方式来确定备份ORR根。可以单独地或以其某种组合来使用从RR客户端到备用候选ORR根(例如另一ABR)的距离、IGP TLV扩展，操作者输入和/或经由配置的操作者覆盖。另外，也可以考虑某些策略。例如，期望的备份可以是这样的ORR根，其生成使主ORR根作为叶节点的SPT。在这种情况下，如果主ORR根出现故障，则不需要重新计算备份ORR根的SPT，并且利用备份ORR根，该SPT可立即成为主SPT。

最后，一旦所有区域都被配置有ORR根和一个或多个备份ORR根，则在536，CBRR可以等待新的路由协议分组(例如，LSA或LSP)。新的路由协议分组可以向CBRR 330提供更新的路由信息，其可以用于更新RR客户端、ABR和区域之间的关联。

针对内部网关协议的类型长度值要素

某些功能在本文公开的实施例中可能是期望的。内部网关协议(IGP)可以根据至少一些实施例进行定制，以提供期望的功能。如本文先前所述，诸如开放最短路径优先(OSPF)和中间系统到中间系统(IS-IS)之类的IGP可以被提供有定制的类型长度值要素以实现某些功能。

在至少一些实施例中，可能需要的第一功能涉及基于云的路由反射器(例如，节点30、CBRR 330)的能力。CBRR 330不在转发路径中，因此CBRR 330被配置为接收和发送控制面业务，而不是数据面业务。然而，IGP不能容纳这样的叶节点，该节点需要针对其可达性而参与路由，但不能充当数据流量的转发器。相反，IGP可以支持隐藏节点和最大度量。例如，LSA可以将路由器通告为最大度量，这表示路由器不被用于转发目的，除非是最后的偏好。然而，在本文公开的针对路由反射器客户端提供最优的路由反射器根地址分配和快速故障转移能力的实施例中可能需要在不具有转发能力的节点参与控制面。

本公开的至少一个实施例可以解决与不能转发但针对可达性目的需要参与路由的节点(例如，叶节点)相关联的上述问题(以及更多)。本文公开的实施例允许CBRR：1)在IGP中宣布其可达性信息，例如用于BGP会话管理；以及2)明确指示所宣布的可达性信息不被用于转发目的。实施例不涉及最少偏好的路径或隐藏在IGP拓扑内的节点。所宣布的可达性信息是用于通过传输层与CBRR进行通信的信息。所宣布的可达性信息不用于将分组转发到CBRR以外的目的地。虽然本文公开的实施例涉及最优的基于云的路由反射功能，但是应当显而易见的是，这些实施例可以扩展到任何不能转发但需要成为控制面的一部分的基于云的路由器。

在至少一个实施例中，路由器可以被配置为携带针对正在使用的特定协议(例如，IS-IS，OSPF等)而配置的附加类型长度值(TLV)要素。通常，分组的TLV要素包括指示值(Value)字段中的项目的类型的类型(Type)字段，指示值字段的长度的长度(Length)字段，和作为分组的数据部分的值字段。IS-IS路由器能力TLV中的新的子TLV(类型长度值)可以使用任何合适的值来定义，这可以基于特定实现和/或需要来配置。然而，在至少一个实施例中，新的子TLV可以被定义为如下：

表1-IS-IS

在OSPF版本2(OSPFv2)协议的至少一个实施例中，可以使用任何合适的值来定义新的OSPFv2路由器信息TLV(类型长度值)，这可以基于特定实现和/或需要来配置。然而，在至少一个实施例中，新的TLV可以被定义为如下：

表2-OSPFv2

在针对OSPFv3协议的至少一个实施例中，可以使用任何合适的值来定义新的OSPFv3路由器信息TLV(类型长度值)，这可以基于特定的实施方式和/或需要来配置。然而，在至少一个实施例中，新的TLV可以被定义为如下：

表3-OSPFv3

针对非运送OSPF路由器能力和非运送IS-IS路由器能力提供的新TLV要素指示，IGP陈述者能够参与IGP，但不能充当运送路由器或转发器。该指示可以帮助确保针对除了陈述者本身所通告的可达性信息之外的任何可达性信息，域中的其他IGP陈述者不会选择这样的陈述者作为运送节点。另请注意，值字段可以用“不要转发”信息进行编码。另外，值字段可以被配置为1字节以提供可扩展性。额外的比特可以允许编码其他信息，例如选择性转发信息(例如，指示在某些情况下应该允许通过CBRR转发的信息)。

图6示出了可以与本文描述的实施例相关联的使诸如CBRR之类的节点能够参与控制面而不提供转发能力的操作的可能流程600的流程图。在至少一个实施例中，一组或多组操作对应于图6的活动。基于云的路由反射器(例如，30、330)可以使用一组或多组操作。基于云的路由反射器可以包括用于执行操作的装置，例如至少一个处理器(例如，39)。在实施例中，流600的至少一些操作可以由基于云的路由反射器中的IGP(例如，70)的可达性扩展发起器(例如，72)执行。为了便于说明，下面参考图4所示的通信系统300来讨论图6。

在602，CBRR 330建立从CBRR 330到一个或多个路由器(例如ABR1-ABR3)的隧道，以指示CBRR 330希望参与IGP路由。在604，CBRR 330可以配置LSA以发送到隧道化ABR。LSA可以包括新的TLV要素，其指示CBRR 330的可达性仅用于控制面流量，而不是数据平面流量。在606，LSA可以被发送到隧道化路由器(例如，ABR1-ABR3)。隧道化路由器的IGP(例如，80)的可达性扩展接收器(例如，82)可以标识新的TLV要素并防止数据面流量被转发自CBRR330。随后，CBRR330应从通信系统300中的路由器仅接收控制面流量。

在至少一些实施例中可能期望的第二功能涉及在通信系统300中通告发起路由器信息。通常，根地址是针对给定集群或客户端边缘路由器本身(例如，提供商边缘(PE)路由器)的区域边界路由器(ABR)。在被划分为多个路由组(例如，区域、级别)的网络中，无法将根地址与给定的客户端PE路由器相关联，因为在将路由宣布给另一路由组或CBRR 330时ABR作为自身重新发起这些路由。

本公开的至少一个实施例可以解决与在分区BGP-ORR网络中通告发起路由器信息相关联的上述问题(以及更多)。在至少一个实施例中，路由器可以被配置为携带针对正在使用的特定协议(例如，IS-IS，OSPF等)配置的附加类型长度值(TLV)要素。路由器中的附加TLV要素可以被配置为将发起路由器信息绑定到重新发起的链路状态通告(LSA)或链路状态分组(LSP)。由附加TLV要素提供的信息有助于将LSA或LSP与其发起路由器相关联。LSA或LSP与其发起路由器的关联有助于CBRR计算给定根地址的SPF。

IS-IS路由器能力TLV内的新的子TLV(类型长度值)可以使用任何合适的值来定义，这可以基于特定实现和/或需要来配置。然而，在至少一个实施例中，新的子TLV可以被定义为如下：

表4-IS-IS

在OSPFv2协议的至少一个实施例中，可以使用任何适当值来定义新的OSPFv2路由器信息TLV(类型长度值)，这可以基于特定实现和/或需要来配置。然而，在至少一个实施例中，新TLV可以被定义为如下：

表5-OSPFv2

在针对OSPFv3协议的至少一个实施例中，可以使用任何合适的值来定义新的OSPFv3路由器信息TLV(类型长度值)，可以基于特定的实施方式和/或需要来配置。然而，在至少一个实施例中，新的TLV可以被定义为如下：

表6-OSPFv3

IGP路由器能力允许在IGP LSA或LSP跨越区域边界时保留原始路由器ID。因此，本文公开的实施例允许CBRR通过提供足够的信息(例如，经由附加TLV要素)将LSA或LSP与其发起路由器相关联，从而在多个区域或级别(例如，在分区IGP中)工作。

图7是示出可与本文描述的实施例相关联的通信系统300的选定组件的可能交互的交互图700。为了说明的目的，所选择的组件包括边缘路由器355(ER1)、区域边界路由器350(ABR1)和基于云的路由反射器(CBRR)330。在至少一个实施例中，一组或多组操作对应于图7。CBRR 330、ABR1和ER1可以包括用于执行操作的装置，例如至少一个处理器(例如，39、59)。在实施例中，至少一些操作可以由ER1中的IGP的通告扩展发起器(例如，84)以及CBRR 330中的IGP的通告扩展发起器(例如，74)来执行。

在交互图700所示的示例场景中，ER1是边缘路由器(例如，提供商边缘路由器)，并且也是集群A的根节点。在702处，ER1发起LSA 704以将其路由信息通告给其集群A内的邻居和CBRR 330。LSA 704包括但不一定限于ER1的路由器ID、ER1的根地址(例如，IP地址)和TLV要素。TLV要素可以包括发起路由器信息，例如ER1的路由器ID。在图7所示的交互中，LSA704的报头中的路由器ID在LSA 704到达CBRR 330之前被替换。然而，TLV要素不被改变，并且可以向CBRR 330提供该路由器ID信息。

在706，LSA 704被传输到ABR1。在一个示例中，LSA 704可洪泛集群A的节点。在708，ABR1接收LSA 704，并用LSR 704的路由器ID替换LSA 704的报头中的发起路由器信息。经修改的LSA 710包括ABR1的路由器ID、ER1的根地址和包含ER1的路由器ID的TLV要素。在712，经修改的LSA 710被传输到CBRR 330。在714，CBRR 330接收经修改的LSA 710，并且基于经修改的LSA 710的TLV中包含的路由器ID来标识发起路由器(例如，该情况下为ER1)。

因此，经修改的LSA 710与其发起路由器相关联。因为在该示例中，由于发起路由器是集群A的ORR根，所以该信息使得CBRR 330能够计算针对特定根地址的SPF。此外，提供该信息使得CBRR 330能够与分区IGP网络中的多个区域一起工作，因为来自不同区域的LSA与其发起路由器相关联。

在至少一些实施例中可能期望的第三功能涉及允许ORR根地址作为通信系统300中的以太网子网的一部分。通常，ORR根地址是给定集群的区域边界路由器(ABR)或客户端边缘路由器本身(例如，提供商边缘(PE)路由器)。在ORR根地址被映射到以太网子网的网络中，无法将根地址与给定节点相关联。在IGP中，以太网地址可以作为子网被通告，该子网可以被映射到多个IP地址。子网是与每个端处的点的链路。链路端点各自对应于作为子网一部分的路由器。当路由器二者都是候选ORR根节点时，CBRR无法确定要选择哪个路由器作为ORR根。

图8是提供通信系统300的组件的部分表示以及示出集群中的子网的附加元件的简化框图。如图8所示，通信系统300可以包括在第四集群380(例如，集群D)中划分的附加节点。集群D包括诸如区域边界路由器350(例如，ABR4)和内部路由器357(例如，IR1和IR2)之类的节点。也可以在集群D中配设其他节点(未示出)，例如边缘路由器。在至少一个实施例中，诸如IR1和IR2的内部节点可以具有与节点30相同或相似的配置。

在集群D中，IR1和IR2都具有映射到子网312的接口。作为示例，子网312可以被表示为1.1.1/24。IR1可以具有IP地址1.1.1.10，IR2可以具有IP地址1.1.1.20，两者都映射到子网312。当LSA由IR1和IR2传输以通告其路由信息时，每个LSA将其路由器的IP地址标识为1.1.1/24。因此，CBRR 330不能确定用于选择和关联到作为ORR根的特定路由器的根地址。

本公开的至少一个实施例可以解决与允许将ORR根节点作为BGP-ORR网络中以太网子网的一部分相关联的上述问题(以及更多)。在至少一个实施例中，现有的IGP可以被扩展以宣布其本地配置的地址以及它们的链路状态通告(LSA)。为了实现这些宣布，现有的路由器可被配置为携带针对正在使用的特定协议(例如，IS-IS，OSPF等)所配置的附加类型长度值(TLV)要素。由附加TLV要素提供的信息可以帮助将映射到以太网子网的ORR根地址与给定节点相关联。以下提供了扩充现有IGP协议的具体示例。

可以使用任何合适的值来定义IS-IS路由器能力TLV内的新的子TLV(类型长度值)，这可以基于特定实现和/或需要来配置。然而，在至少一个实施例中，新的子TLV可以被定义为如下：

表7-IS-IS

在针对OSPFv2协议的至少一个实施例中，可以使用任何适当的值来定义新的OSPFv2路由器信息TLV(类型长度值)，这可以基于特定实现和/或需要来配置。然而，在至少一个实施例中，新的TLV可以被定义为如下：

表8-OSPFv2

在针对OSPFv3协议的至少一个实施例中，可以使用任何合适的值来定义新的OSPFv3路由器信息TLV(类型长度值)，其可以基于特定的实施方式和/或需要来配置。然而，在至少一个实施例中，新的TLV可以被定义为如下：

表9-OSPFv3

本文公开的实施例提供了用于携带根地址信息的IGP扩展。OSPF路由器能力和IS-IS路由器能力表明IGP陈述者能够宣布其本地配置的以太网地址，并且其自身可以提供地址。该指示可以帮助CBRR标识SPF可以根源于的节点。这种对IGP的扩展使主机地址能够与LSA相关联。

图9示出了可以与本文所描述的实施例相关联的用于允许ORR根地址作为以太网子网的一部分的操作的可能流程900的流程图。在至少一个实施例中，一组或多组操作对应于图9的活动。自主系统中的路由器(例如，20、357)可以使用一组或多组操作。路由器可以包括用于执行操作的装置，例如至少一个处理器(例如59)。在实施例中，流程900的至少一些操作可以由路由器中的IGP的以太网扩展发起器(例如，86)执行。为了便于说明，下面参考图8所示的通信系统300来讨论图9，其中IR1将被选择为集群D的根节点。

在902，附连到子网的路由器(例如，附连到子网312的IR1)确定它是否是根节点。各种实现方式可以影响如何进行此确定。例如，当必须在多个候选根节点之间打破平局(tie-break)时，IR1可以由操作者配置为根节点。在另一实现方式中，候选根节点可以被配置为彼此通信以确定哪个节点是根节点。

如果在904处的确定指示路由器是根节点，则在908，路由器可以准备具有TLV的LSA，所述TLV包括路由器被附连到子网并且作为指定的根节点的指示。如果在904处的确定指示路由器不是根节点，那么在906，路由器可以准备LSA，该LSA不具有宣布它是指定的根节点的TLV。一旦LSA已经准备好，那么在910，LSA可以在区域或级别内被传输，并且ABR可以将LSA转发到CBRR 330。CBRR 330可以从LSA提取TLV并且基于TLV的内容来确定是否选择该路由器作为根节点。CBRR 330可以配置有执行该提取和确定的逻辑。该逻辑可以与以太网扩展接收机86相同或类似，参考图2中的节点30示出和描述了以太网扩展接收机86。

快速故障转移

根据至少一个实施例，基于云的路由反射器(例如，节点30)包括如下过程(例如，SPF逻辑66)：多次运行最短路径优先(SPF)计算，并且保持根源于相同或不同拓扑的不同点的多个最小生成树(SPT)(例如，在SPT数据库92中)。生成树可以包括自主系统(例如，AS1)的拓扑的子集。此过程的客户端(例如BGP-ORR(例如BGP-ORR 60))可以查询该SPT数据库，以例如从RR客户端的角度执行最佳路径计算，从而通告针对该RR客户端的最优最佳路径。因此，每个RR客户端都可以通过将RR客户端与SPT的根进行关联的配置来与SPT关联。如果SPT根无法从CBRR中可达，这可能在被通告给与SPT相关联的RR客户端的路径中产生显著扰动。

本公开的至少一个实施例可以解决与从CBRR不可达的SPT根相关联的上述问题(以及更多)。在至少一个实施例中，CBRR可以执行快速故障转移以至备份SPT。可以指定多个备份SPT。故障转移通常旨在表示可以将主系统或系统组件的网络通信、功能、操作等重定向到备份系统或系统组件的容错功能。在至少一个实施例中，执行快速故障转移可以包括：1)将RR客户端与描述用于计算RR客户端的最佳路径的SPT序列的故障转移策略组进行关联，以及2)在故障转移的情况下，每个故障转移策略组中仅SPT的最小所需变化被通告给BGP-ORR和可能的其他监听客户端的方法。在至少一个实施例中，活动的根节点(本文中也称为“主根节点”)和备份根节点相关联。确定根是否是彼此的SPT中的叶子。该关联用于减少SPF计算的数量。最后，预先计算备份路由。

转至图10，现在将提供用于执行快速故障转移以至备份SPT的实施例的更详细的描述。图10是示出根据至少一个实施例的通信系统1000的可能配置的简化框图，其示出了主根节点和备份根节点。通信系统1000包括作为自主系统的一部分的基于云的路由反射器(CBRR)1030和若干个路由器1050(R1-R9)。在该示例中，路由器1050旨在是CBRR 1030的RR客户端。在至少一个实施例中，CBRR 1030可以以与节点30相同或相似的方式配置，并且路由器R1-R9可以以与节点50相同或相似的方式配置，本文先前均已对这两个节点进行了示出和描述。

在图10的示例配置中，CBRR 1030已经针对自主系统的两个路由组(例如，区域或级别)选择了主根节点和备份根节点。在图10所示的拓扑中，对于第一路由组，R3是R1和R2的主根节点，R6是R1和R2的第一备份根节点。R3也是自身的主根节点，R6是自身的第一备份根节点，因为R3和R6是CBRR 1030的RR客户端。对于第二路由组，R6也可以是R4和R5的主根节点，而R3可以是R4和R5的第一备份根节点。R6也是自身的主根节点，R3是自身的第一备份根节点，因为R6和R3是CBRR 1030的RR客户端。然而，应该注意，该拓扑旨在表示在R3作为主根节点时的成本/距离。尽管在图10中未示出，但是存在其他备份根节点(例如，辅助备份根节点，三级备份根节点等)的配置是可能的。此外，在该示例中，故障转移策略组X 1040(1)被分配给R1和R2(和R3)，而故障转移策略组Y 1040(2)被分配给R4和R5(和R6)。此外，所连接的路由器R1-R6对之间的下一跳的示例IGP度量在1090处被指示。在该示例中，每个下一跳度量具有值10。

在图10中，可以经由R1或R5到达具有IP地址前缀6/8的节点。使用根节点R3和R6的配置，R2知道经由R1和R5可达前缀6/8，但是R1是R2的优选路由。R1优于R2，因为其成本为20，而通过R5到达前缀6/8的成本为30。如果R3出现故障，则R2的新根为R6。因此，针对前缀6/8的新的最佳路径可能会更改为R5。在主根节点发生故障时，将最佳路径选择从基于根源于主根节点的SPT的第一路径更改到第二路径的操作称为“故障转移”。

SPF计算过程可以创建SPT的数据库(例如，SPT数据库92)。CBRR中的SPF逻辑(例如，SPF逻辑66)可以执行这些计算。每个SPT都根源于网络中的IGP节点。这些SPT通过由操作者(例如，网络管理员)定义或通过如前所述自动生成的故障转移策略组进行分组。每个故障转移策略组可以通过唯一的标识符来标识。除了激活备份根节点(如果有多个备份根节点的话)的顺序之外，策略组还可以标识主根节点(或SPT)和一个或多个备份根节点(或SPT)。在图10中，例如，策略组X被分配给R1和R2，而策略组Y被分配给R4和R5。策略组X将R3标识为主节点，R6作为R3的备份节点。策略组Y将R6标识为主根节点，R3作为R6的备份根节点。如果任一策略组标识不止一个备份根节点，则策略组还可以响应于活动的根节点来定义激活多个备份根节点的顺序。每个RR客户端(例如，R1-R6)通过其故障转移组标识符(组ID)与故障转移策略组关联。

SPT是IGP区域(或多个区域)中的所有节点以及通过运行根源于SPT根的SPF所计算的成本的表。因此，故障转移策略组中的所有SPT应由相同数量的IGP节点组成。这可以通过确保策略组中的所有SPT根属于同一IGP区域或管理区域来实现。SPT可以属于多个故障转移策略组，并且在每个组中具有不同的故障转移序列号。例如，SPT根可以是一个故障转移策略组中的主根，也可能是另一个故障转移策略组中的第一备份根。该示例在图10中示出，其中R3是策略组X中的主根节点，并且是策略组Y中的备份根节点。

虽然SPT由IGP节点组成，但通常，SPF计算过程的客户端(例如CBRR 1030中的BGP-ORR(例如，节点30中的BGP-ORR 60)和R1-R5中的BGP(例如，节点50中的BGP 65))对IGP节点的接口的IGP度量而不是节点本身感兴趣。附连到IGP节点(通过链路状态通告(LSA)学习)的接口(或静态配置的路由)继承节点的成本。该信息通常存储在接口数据库中。因为故障转移策略组中的所有SPT都包含相同的节点组，所以接口数据库可以与SPT数据库分开，并且只需要一个接口数据库。

当发生拓扑变化时，可以执行一个或多个算法。在第一种算法中，接口或静态路由的添加或撤销会导致接口数据库的改变。将数据库中的变化的通知提供给客户端过程(例如，BGP 65)以及路由存在于的所有故障转移策略组。在第二种算法中，邻接关系的改变(例如，度量改变，节点添加/撤销)导致受影响的SPT被重新计算。故障转移策略组然后通过路由信息库(RIB)被传输到客户端过程。通信可以包括传输所有接口或静态路由及其度量，但是仅当度量已经改变时。

客户端过程不知道故障转移策略组中的哪个SPT是当前活动的SPT，而是只知道在故障转移策略组的上下文中接口或静态路由的成本。BGP路由反射过程在其最佳路径计算中使用该成本(例如，最佳路径选择模块62)，并且通过配置向与故障转移策略组相关联的RR客户端通告最优下一跳。可以通过配置或由CBRR自动生成故障转移组(主、第一备份、辅助备份等)中SPT的排序。

设计的一个问题是，给定故障转移策略组的备份节点可能是其他一些故障转移策略组的活动根节点。针对备份根节点实施受限SPF(即，某些节点被排除)要求CBRR根据对于给定策略组而言节点是活动根节点还是备份根节点来针对该给定根节点多次运行SPF过程。

因此，本文公开的实施例可以优化整个ORR路由收敛。在至少一个实施例中，可以使用CBRR 1030中跟踪主SPT和备份SPT之间的IGP度量差值的增量数据库(例如，增量数据库94(1)-94(X))来实现优化。当主根节点发生故障时，只有已经更改的度量被传输到监听客户端(例如，RR客户端中的BGP过程，CBRR中的BGP-ORR过程等)。可以将增量数据库配置为跟踪活动SPT和备份SPT之间IGP度量的差值。例如，在图10中，与策略组X相关联的增量数据库可以跟踪根源于R3的SPT的IGP度量和根源于R6的SPT的IGP度量之间的差值。类似地，与策略组Y相关联的增量数据库可以跟踪根源于R6为根的SPT的IGP度量和根源于R3的SPT的IGP度量之间的差值。SPT的IGP度量通常是与表中每个节点相关联的成本(或距离)。例如，在图10中，对于根源于R3的SPT，R3的成本为0，R1的成本为10，R2的成本为10，R6的成本为10，R4的成本为20，R5的成本为20。由于R3距离R5的度量单位为20，R6距离R5的度量单位为10，针对R5，R3与R6之间的度量单位的差值为-10。值-10可以被映射到属于策略X的增量数据库中的R5。

然而，如前所述，在至少一些实施例中，SPF计算过程的客户端(例如，节点50中的BGP 65、节点30的BGP-ORR 60)对IGP的接口的IGP度量感兴趣，而不是节点本身。附连到IGP节点的所有接口(或静态配置的路由)都会继承节点的IGP度量(例如，成本/距离)。在至少一个实施例中，主SPT的接口度量可以从SPT数据库获得并被存储在针对主根节点的接口数据库中。还可以从SPT数据库获取针对备份SPT的接口指标，并将其存储在针对备份根节点的接口数据库中。主接口数据库中接口的IGP度量与备份接口数据库中接口的IGP度量之间的差值可以被存储在增量数据库中。然而，在至少一些实施例中，存储在备份接口数据库中的信息可以在增量数据库中被组合。另外，应该注意，接口数据库可以以任何数量的可能方式进行配置。例如，接口数据库(主、备份和增量)可以被存储在单个存储元件中，如接口数据库98所示。或者，可以基于特定实现方式和需要将这些接口数据库中的每一个单独地或共同地存储在所期望的组中。

现在将参考图11所示的示例SPT 1100来解释优化。SPT 1100包括根节点1130(R10)、内部节点1120(R11-R16)和叶节点1140(R17-R24)。此优化可以按照如下实现：

(1)使用标准最小生成树算法来评估给定故障转移策略组的活动根和备份根，以确定它们是否是彼此的树中的叶子(即，它们都不使用彼此作为运送者)。例如，如果R17是R10的备份根节点，并且如果R10是R17的SPT中的叶节点，则满足该条件。

(2)当满足上述(1)时(即，活动和备份根节点是彼此的树中的叶节点)，可以针对活动根和备份根创建接口数据库，并且来自这两个数据库的路由度量的差值可以被跟踪(例如，在delta数据库中)，以便可以逐步下载这些路由度量。在至少一些实施例中，增量数据库可以与备份接口数据库分开。在其他实施例中，备份接口数据库中的信息可以被存储在增量数据库中，而不是单独的备份接口数据库中。

(3)当不满足上述(1)时(即，活动和备份根是彼此的树中的内部节点)，对备份根执行受限制的SPF处理。来自这两个数据库的路由度量的差值可以被跟踪(例如，在delta数据库中)，以便可以逐步下载这些路由度量。例如，如果R11是RIO的备份根节点，并且如果R1O是R11的SPT的内部节点，则不满足上述条件(1)。在这种情况下，可以通过省略R1O来针对备份根节点R11执行受限的SPF过程。因此，根源于R11的SPT将不包括R1O。然而，在至少一些实施例中，如果主根是备份根的树的内部节点，则即使备用根不是活动根的树的内部节点，也可以执行受限的SPF过程。

上述策略优化当拓扑发生变化(例如邻接关系发生变化或SPT根发生故障)时执行的SPF运行的数量。例如，假设有两个故障转移策略组：

组1：活动1.1.1.1和备份2.2.2.2

组2：活动2.2.2.2和备份1.1.1.1

在这种情况下，CBRR通常生成4个SPT。然而，在本文公开的至少一个实施例中，CBRR可以在最好情况下仅生成2个SPT，在最坏情况下可以生成4个SPT。此外，CBRR仅生成2个SPT的机会较高，因为所选择的根可能是集群区域边界路由器(ABR)，因此可能成为彼此的树中的叶节点。

转到图12、图13和图14，简化的流程图示出了可能的流程1200、1300和1400，其分别可以与本文所公开的与快速故障转移相关的一个或多个实施例相关联。在至少一个实施例中，一组或多组操作对应于图12-14的活动。基于云的路由反射器(例如，30、330、1030)可以使用一组或多组操作。基于云的路由反射器可以包括用于执行操作的装置，例如至少一个处理器(例如，39)。在实施例中，流程1200、1300和1400的至少一些操作可以由基于云的路由反射器中的故障转移模块(例如，90)来执行。

为了便于说明，下面参考图10的通信系统1000来讨论图12。参考图12，在1202处，可以创建故障转移策略组。这可以在已经针对通信系统1000选择了ORR根节点并且已经针对每个ORR根节点创建了SPT之后发生。故障转移策略组可以定义要用于针对策略组所分配到的RR客户端(例如，R1和R2)计算最佳路径的SPT序列。故障转移策略组可以包括主根节点和一个或多个备份根节点。故障转移策略组(例如，故障转移策略组X)可以由授权用户进行配置，也可以自动生成。在1204，故障转移策略组可以被分配给一个或多个RR客户端。

在1206，可以创建增量数据库以跟踪根源于主(活动)根节点的SPT和根源于故障转移策略组的备份根节点的SPT之间的度量差值。在一些实施例中，该增量数据库可以跟踪两个SPT的节点之间的度量差值。在其他实施例中，可以创建主根节点的主接口数据库和备份根节点的备份接口数据库。可以在增量数据库中跟踪接口度量之间的差值。如前所述，可以组合备份接口数据库和增量数据库。将参考图13更详细地描述用于创建增量数据库的过程。

在1208，监控网络的变化。针对路由器、接口或静态路由已被撤销或添加到网络的指示，对接口变化、静态路由变化和邻接关系变化进行监控。在1210，确定是否检测到接口或静态路由方面的变化。如果检测到变化，则在1212，CBRR可以通知BGP客户端过程(例如BGP 65、BGP-ORR 60)和其中存在接口或静态路由的故障转移策略组。

在1214，确定是否检测到邻接关系的变化。邻接关系的变化可以包括例如度量变化、节点添加或节点撤销。如果没有检测到任何变化，流程继续到1208，其中，监测网络中的变化继续。然而，如果检测到邻接关系发生变化，那么在1216，可以重新计算受影响的SPT(或SPT的受影响部分)，并可以将所得到的经改变的度量通告给监听客户端。将参照图14对重新计算受影响的SPT的过程进行更详细地描述。

转至图13，为了便于说明，下面参考图11的SPT 1100来讨论图13。在至少一个实施例中，对应于流程1300的一组或多组操作与如下处理有关：创建增量数据库以跟踪主路由和备份路由之间的度量变化。图13的处理可以对应于图12的1206。

在1302，CBRR确定主(或活动的)根节点和备份根节点是否是彼此的生成树中的叶子或者彼此的生成树中的内部节点。例如，参考图11，如果R10是主根节点，则如果备份根节点被指定为节点R11-R16中的任一个，则备份根节点被确定为R10的SPT 1100的内部节点。如果备份根节点被指定为节点R17-R24中的任一个，则备份根节点被确定为R10的SPT1100的叶节点。类似地，可以评估R10在备份根节点的SPT中的位置以确定R10是否为备份根节点的SPT的叶节点或内部节点。

在1304，如果确定主根节点不是备份根节点的SPT中的叶节点(即，主根节点是备份根节点的SPT的内部节点)，则在1306，可以针对备份根节点执行受限的SPF过程。例如，如果R10是主根节点R11的备份根节点，则可以针对R10运行受限的SPF。在这种情况下，SPF假设R11不可用，并在该假设下运行针对R10的SPF过程。因此，所产生的R10(作为R11的备份)的SPT将不包括R11。

如果在1304确定主根节点是备份根节点的SPT中的叶节点(或者如果在1306执行了受限的SPF)，则在1308，可以针对主根节点创建接口数据库。该主接口数据库可以包括基于主根节点的SPT的接口的度量。在1310，可以创建增量数据库。在至少一个实施例中，增量数据库可以包括基于备份根节点的SPT的接口度量。此外，备份根节点SPT的接口度量与主根节点SPT的接口度量之间的差值可以被跟踪在增量数据库中。在其他实施例中，备份根节点SPT的接口度量可以被存储在单独的备份接口数据库中。在另一实施例中，增量数据库可以包括主根节点的SPT中的节点与备份根节点的SPT中的节点之间的度量差值。如果主节点发生故障，则可以使用增量数据库来仅传输将由于备份根节点成为活动根节点而改变的度量。例如，可以只传达增量数据库中不等于零的度量。此外，可能不需要重新计算SPT(例如，当备份根节点是主根节点SPT中的叶子时)，这可能潜在地节省大量网络资源和带宽。

转至图14，为了便于说明，下面参考图10的通信系统1000来讨论图14。在至少一个实施例中，对应于流程1400的一组或多组操作与如下处理有关：当主根节点或备份根节点发生故障时，重新计算受影响的SPT。图14的处理可对应于图12的1216。

初始地，在1402，确定发生故障的节点是主根节点(例如，R3)还是备份根节点(例如，R6)。如本文所使用的，针对节点的术语“发生故障”旨在表示节点不再执行转发动作。这可以包括例如已经失灵、停电、遭受恶意软件攻击、有意或无意地被从网络撤销、或者可能导致节点不再转发流量的任何其他原因的节点。

如果节点被确定为主根节点，则在1404，故障转移组策略中的第一备份根节点被指定为新的主根节点。例如，如果当前主根节点被确定为发生故障，则在策略组X中的SPT序列中定义的R6的SPT可以成为新的主根节点。在1406，与故障转移策略组相关联的增量数据库中的度量差值可以被通告给任何监听客户端(例如，CBRR中的BGP-ORR、被分配了故障转移策略的RR客户端中的BGP)。例如，这些差值可用于更新监听客户端中的度量信息，而不必对备份根节点执行SPF，并下载备份根节点的整个SPT。例如，如果R3是通信系统1000中的R1和R2的主节点，并且如果R3发生故障，则与策略组X相关联的增量数据库可以用于将度量差值(例如，不等于零)传输到R1和R2。R1和R2可以使用这些度量差值来更新它们自己的SPT数据库。

在1420，可以从故障转移策略组确定下一个可用的备份根节点，并将其指定为新的主根节点的第一备份根节点。在1422，可以创建新的增量数据库以跟踪当前主根节点的接口和/或节点与当前第一备份根节点的接口和/或节点之间的度量差值。用于创建新的增量数据库的过程可以与参照图13描述的处理相同或相似。

再次参考1402，如果故障节点在1402被确定为备份根节点，则在1412，可以确定故障节点是否是根源于主根节点的SPT的内部节点。如果故障节点不是内部节点(即，故障备份根节点是主根节点的SPT的叶节点)，则不需要对主根节点执行SPF。相反，在1414，可以将故障备份根节点的度量差值传输到监听客户端(例如，CBRR中的BGP-ORR、分配了故障转移策略的RR客户端中的BGP)。然后，流程可以进行到1420，其中，可以根据故障转移策略组来标识下一可用的备份节点，并且在1422，可以基于新的主根节点和新的备份根节点来创建新的增量数据库。

然而，在1412处，如果故障备份根节点被确定为主根节点的SPT的内部节点，则在1416，可以针对主根节点的SPT中的备份根节点的所有孩子节点(和更低的节点)重新计算主根节点的SPT。在1418年，SPT的变化可被传输给监听客户端。在1420，可以根据故障转移策略组来标识下一个可用的备份节点，并且在1422，可以基于新的主根节点和新的备份根节点来创建新的增量数据库。本文先前已经描述了1420和1422。

可以通过使用本文公开的实施例来提供许多优点。例如，本文公开的实施例提供有效的SPF计算。另外，在网络改变的情况下(包括SPT故障转移)，可以将最小所需变化通告给客户端BGP路由反射过程(例如，BGP-ORR 60)和其他监听客户端(例如，BGP 65)。

变型和实现方式

在本公开的上下文中，本文使用的网络表示用于接收和发送通过通信系统传播的信息分组的互连通信路径的一系列点、节点或网络元件。网络提供源和/或主机之间的通信接口，并且可以是任何局域网(LAN)、无线局域网(WLAN)、虚拟专用网(VPN)或有助于基于网络拓扑的网络环境中的通信的任何其它适当的架构或系统。网络可以包括通过通信介质彼此耦合(并且彼此进行通信)的任何数量的硬件和/或软件元件。

网络环境中的通信在本文中被称为“网络流量”或“流量”，其可以包括分组。分组是格式化的数据单元，并且可以包含控制信息(例如，源和目的地地址等)以及也称为有效载荷的数据。可以根据任何合适的通信消息收发协议来发送和接收网络流量。合适的通信消息收发协议可以包括诸如开放系统互连(OSI)模型或其任何衍生物或变体(例如，传输控制协议/IP(TCP/IP)、用户数据报协议/IP(UDP/IP)等)之类的多层方案。本文所用的术语“数据”是指任何类型的二进制、数字、语音、视频、文本或脚本数据，或任何类型的源或目标代码，或采用可以在电子设备和/或网络中从一点传输到另一点的任何适当格式的任何其他适合的信息。此外，消息、请求、响应、回复、查询、通信等是网络流量的形式，因此可以包括分组。

如本文所使用的，术语“网络元件”意在包括上述任何元件以及路由器、交换机、无线接入点(WAP)、网关、网桥、负载均衡器、设备、防火墙、服务器、处理器、模块(其中任何一个可以是在物理硬件上物理地或虚拟地实现的)或可操作以在网络环境中交换信息的任何其他合适的设备、组件、元件、专用设备或对象。网络元件可以包括促进其操作的任何合适的硬件、软件、组件、模块、接口或对象。这可包括允许数据或信息的有效交换的适当算法和通信协议。

在至少一个示例实现方式中，具有自动ORR根地址分配和快速故障转移能力的节点包括实现(或促进)如本文所概述的活动的逻辑。这可以包括实施TLV要素以针对不具有转发能力的节点提供可达性信息，提供发起路由器的通告，和/或允许ORR根地址作为以太网子网的一部分。注意，在至少一个示例中，这些元件中的每一个可以具有内部结构(例如，处理器、存储器元件、网络接口卡等)以促进本文所述的一些操作。在一些实施例中，这些活动可以在这些元件的外部执行，或者被包括在一些其他网络元件中以实现预期功能。在至少一个实施例中，这些节点可以包括可以与其他网络元件协调以实现这些操作的逻辑(或往复式逻辑)，如本文所概述的。此外，一个或多个设备可以包括促进其操作的任何合适的算法、硬件、固件、软件、组件、模块、接口或对象。

在某些示例实现方式中，本文概述的自动根地址分配、快速故障转移和TLV扩展功能可以由在一个或多个有形介质中所编码的逻辑来实现，所述逻辑例如可以是在专用集成电路(ASIC)中提供的嵌入式逻辑，数字信号处理器(DSP)指令，由一个或多个处理器或其他类似机器执行的软件(可能包括目标代码和源代码)，软件、硬件、固件或其任何组合中的指令等。这种有形介质在至少一个实施例中可能是非暂态的。在这些情况中的一些情况下，一个或多个存储器元件可以存储用于本文描述的操作的数据。这包括能够存储被执行以实施本文所描述的活动的软件、逻辑、代码和/或处理器指令的存储器元件。处理器可以执行与数据相关联以实现本文详细描述的操作的任何类型的指令。在一个示例中，处理器可以将元件或物品(例如，数据)从一个状态或事物转换到另一个状态或事物。在另一示例中，本文概述的活动可以用固定逻辑或可编程逻辑(例如，由处理器执行的软件/计算机指令)来实现，并且本文标识的元件可以是某种类型的可编程处理器、可编程数字逻辑(例如，现场可编程门阵列(FPGA)、可擦除可编程只读存储器(EPROM)、电可擦除可编程ROM(EEPROM))或ASIC，其包括数字逻辑、软件、代码、子指令或其任何合适的组合。

这些元件(例如，网络元件)中的任一个可以包括用于存储用于实现如本文所概述的自动根地址分配、快速故障转移和TLV特征的信息的存储器。此外，这些网络元件可以包括至少一个处理器，其可以执行软件、算法或其他指令以执行自动根地址分配、快速故障转移和TLV扩展操作，如本文所公开的。基于特定需要并且在适当的时候，这些网络元件还可以将用于实现如本文所讨论的自动根地址分配、快速故障转移和TLV扩展活动的信息保存在任何合适的存储器元件(随机存取存储器(RAM)、只读存储器(ROM)、EPROM、EEPROM、ASIC等)、软件、硬件或任何其他合适的组件、设备、元件或对象中。这里讨论的任何存储器项(例如，存储库、存储装置、数据库、表、缓存、缓冲器等)应当被解释为包含在广义术语“存储器元件”内。类似地，本文描述的任何潜在的处理元件、模块和机器应被解释为包含在广义术语“处理器”内。每个网络元件还可以包括用于在网络环境中接收、发送和/或以其他方式传输数据或信息的适当接口。

注意，对于本文提供的示例，可以用两个、三个或更多个网络元件来描述交互。然而，这仅仅是为了清楚和示例的目的而做出的。在某些情况下，通过仅引用有限数量的网络元件来描述给定的一组流程的一个或多个功能可能更容易。应该说明的是，本文描述的系统是易于扩展的，并且可以容纳大量组件以及更复杂/精细的布置和配置。因此，所提供的示例不应该限制范围或禁止自动根地址分配、快速故障转移和TLV特征可能被应用于无数其他架构或实现的广泛教导。

如本文所使用的，除非有明确相反陈述，否则对短语“至少一个”的使用是指所指定的元件、条件或活动的任何组合。例如，“X、Y和Z中的至少一个”意在表示以下任何一个：1)X，而不是Y和Z；2)Y，而不是X和Z；3)Z，而不是X和Y；4)X和Y，但不是Z；5)X和Z，但不是Y；6)Y和Z，但不是X；或者7)X、Y和Z。另外，除非有明确相反陈述，否则术语“第一”、“第二”、“第三”等旨在区分它们修饰的特定名词(例如元件、条件、模块、活动、操作等)。除非有明确相反陈述，否则使用这些术语并不意味着表示所修饰的名词的任何类型的顺序、等级、重要性、时间序列或层级。例如，“第一X”和“第二X”旨在表示两个不同的X元件，这两个不同的X元件不一定受到这两个元件的任何顺序、等级、重要性、时间序列或层级的限制。

请注意，在本说明书中，对“优化(optimize)”、“优化(optimization)”、“经优化的(optimized)”、“最优(optimal)”和相关术语的提及涉及与指定结果的速度和/或效率的提高相关的方面，并不意味着表明实现指定结果的过程已经实现或能够实现、具有完美快速/完美有效的状态。

同样重要的是要注意，本文所示和描述的活动、交互和操作仅示出了可以由具有自动根地址分配、快速故障转移和TLV扩展能力的节点执行或在其内执行的一些可能的互操作性场景和模式。这些活动、交互和/或操作中的一些可以在适当的情况下被删除或移动，或者可以在不脱离本公开的范围的情况下被修改或更改。此外，一些这些活动、交互和/或操作已被描述为与一个或多个附加活动、交互和/或操作同时或并行执行。但是，这些活动、交互和/或操作的时序可能会被大幅更改。上述操作流程是为了举例和讨论的目的而提供的。具有自动根地址分配、快速故障转移和TLV扩展能力的节点提供了大量的灵活性，因为可以在不脱离本公开的教导的情况下提供任何合适的布置、时间、配置和时序机制。此外，可以基于特定的配置和/或配设需求，通过可以任何适当的方式适当地组合或以任何适当的方式进行划分的各种模块和/或组件来促进这些活动。

虽然已经参考特定布置和配置详细描述了本公开，但是在不脱离本公开的范围的情况下，可以大幅更改这些示例配置和布置。此外，某些组件可以根据特定的需要和实现方式来组合、分离、消除或添加。另外，尽管已经参考特定元件和协议来说明本文的实施例，但是这些元件和协议可以由实现具有自动根地址分配、快速故障转移和TLV扩展能力的节点的预期功能的任何合适的架构、协议和/或过程所替代。