域间路径计算技术

摘要

一种用于计算从本地域的头端节点到远端域的尾端节点的跨越计算机网络的多个域的流量工程(TE)标签交换路径(LSP)的方法，包括：请求来自一个或多个远端域中的路径计算元件(PCE)的路径段(435)，所述路径段代表所述远程域中的可能路径；从所述一个或多个PCE接收路径段(440)；以及基于接收到的路径段在所述头端节点处执行路径计算，以找出从所述头端节点延伸到所述尾端节点的最佳路径(455)。

说明书

技术领域

本发明涉及计算机网络，更具体而言涉及利用计算机网络的路径计算元件计算域间路径。

背景技术

计算机网络是由用于在末端节点(例如个人计算机和工作站)之间传输数据的通信链路和网段互连的节点在地理上的分布式集合。存在从局域网(LAN)到广域网(WAN)的很多种网络。LAN一般通过位于诸如建筑物或园区等同一总的物理位置处的专用私有通信链路来连接节点。另一方面，WAN一般通过诸如公共载波电话线、光路、同步光网络(SONET)或同步数字数字体系(SDH)链路等长距离通信链路来连接地理上分散的节点。因特网是连接全世界的不同网络的WAN的示例，它提供了各个网络上节点之间的全球通信。节点一般根据诸如传输控制协议/因特网协议(TCP/IP)等预定协议通过交换分离的帧或数据分组来在网络上进行通信。在本上下文中，协议由定义了节点如何彼此交互的一组规则组成。计算机网络还可以通过诸如路由器等中间网络节点互连，从而扩展每个网络的有效“大小”。

由于互连的计算机网络的管理可能是繁重的，所以较小的计算机网络群组可被维护为路由选择域或自治系统。自治系统(AS)中的网络一般通过被配置为执行域内路由选择协议的传统“域内”路由器被耦合在一起，并一般受共同管理机构管辖。为了提高路由选择的可扩展性，服务提供商(例如ISP)可以将AS划分为多个“区域”。但是，可能希望增加能够交换数据的节点数量；在此情形下，执行域间路由选择协议的域间路由器被用来互连各个AS的节点。此外，可能希望互连在不同管理域(administrative domain)下被操作的各个AS。这里使用的AS或区域一般被称为“域”，将不同域互连在一起的路由器一般被称为“边界路由器”。

域间路由选择协议的一个示例是边界网关协议版本4(BGP)，其通过在系统的相邻域间路由器之间交换路由选择和可达性信息来执行域(AS)间路由选择。邻近性是为了交换路由选择信息消息和抽象出网络拓扑而在选定的相邻(对等)路由器之间形成的关系。BGP对等路由器交换的路由选择信息一般包括目的地地址前缀，即路由选择协议用来产生路由选择(“下一跳”)判决的目的地地址的部分。这种目的地地址的示例包括IP版本4(IPv4)和版本6(IPv6)地址。BGP一般通过诸如TCP等可靠的传输协议进行操作以建立TCP连接/会话。BGP协议是公知的，并在1995年3月公布的题为A Border Gateway Protocol 4(BGP-4)的请求注释(RFC)1771中被一般性地描述。

域内路由选择协议或内部网关协议(IGP)的示例是开放最短路径优先(OSPF)路由选择协议和中间系统到中间系统(IS-IS)路由选择协议。OSPF和IS-IS协议是基于链路状态技术的，因此一般被称为链路状态路由选择协议。链路状态协议定义了在域中交换和处理路由选择信息和网络拓扑信息的方式。该信息一般涉及域内路由器的本地状态(例如路由器的可用接口和可达邻居或邻近性)。OSPF协议在1998年4月的题为OSPF Version 2的RFC 2328中描述，在IP的上下文中使用的IS-IS协议在1990年12月的题为Use of OSI IS-IS for routing in TCP/IP and DualEnvironments的RFC 1195中有所描述，这两篇文献都通过引用结合于此。

多协议标签交换(MPLS)流量工程已被开发用来满足诸如保证可用带宽或快速恢复等数据联网要求。MPLS流量工程利用现代标签交换技术来建立穿过标签交换路由器(LSR)的IP/MPLS网络的保证带宽端到端隧道。这些隧道是一种标签交换路径(LSP)，因此被总称为MPLS流量工程(TE)LSP。MPLS TE的示例可在2001年12月的题为RSVP-TE：Extensions to RSVP for LSP Tunnels的RFC 3209、2004年6月的题为Intermediate-System-to-Intermediate-System(IS-IS)Extensions for TrafficEngineering(TE)的RFC 3784和2003年9月的题为Traffic Engineering(TE)Extensions to OSPF Version 2的RFC 3630中找到，这些文献的全部内容通过引用结合于此。

建立从头端LSR到尾端LSR的MPLS TE-LSP涉及计算穿过LSR的网络的路径。优选地，计算出的路径是以某种度量测得的“最短”路径，该最短路径满足所有相关LSP流量工程约束，例如要求带宽、每个链路的备用旁路隧道的可用性，以及路径中包括的节点等。可以使用包括CSPF(约束最短路径优先)在内的各种路径计算方法。

可用来计算从源到目的地的最短路径的一种示例性算法是公知的Dijkstra路径计算算法。简言之，这里使用的Dijkstra算法计算从源节点到任意目的地节点的最短路径，从而创建最短路径树(SPT)。为了到达最短路径上的目的地节点，源节点简单地遍历SPT以到达目的地节点。该计算是基于节点之间的开销度量的，并且从源节点被向外执行。因此，Dijkstra算法被视为“前向路径计算”。Dijkstra算法在1999年9月出版的作者为Radia Perlman的教科书Interconnections Second Edition的12.2.4节中被更详细地描述，该教科书被通过引用结合于此，如同在这里详细列出一样。

路径计算可以由头端LSR或充当路径计算元件(PCE)的一些其他实体执行。头端LSR(或PCE)利用其关于网络拓扑和每条链路上的资源可用性的知识来根据LSP流量工程约束执行路径计算。注意，MPLS TE-LSP可被配置在单个域(例如单个区域、单个级别或单个AS)中，或者还可以跨越多个域(例如多个区域、多个级别或多个AS)。

PCE是能够计算PCE在AS或区域中意识到的任意节点之间的路径的实体。PCE是非常有用的，因为它们更了解它们的AS或区域中的网络流量和路径选择，因此可被用于更优化的路径计算。头端LSR还可操作为路径计算客户端(PCC)，PCC被配置为向PCE发送路径计算请求，并接收具有计算出的路径的响应，并潜在地考虑来自其他PCC的其他请求。注意到当一个PCE发送对另一PCE的请求时它充当PCC这一点是很重要的。PCE传统上在它的周围区域或AS外部具有有限的可见性或不具有可见性。可以通过管理员的预配置或通过从PCC的区域或整个AS内的PCE发送的通告该PCE的服务的PCE发现(PCED)消息(通告)将PCE通知给PCC。

在跨过域边界时出现的一个困难是头端LSR处的路径计算需要头端和尾端LSR之间的跨过整个网络的网络拓扑和资源的知识。但是服务提供商一般不跨过域边界彼此共享该信息。具体而言，网络拓扑和资源信息一般不流过区域边界，即使单个服务提供商可能操作所有区域或级别。头端LSR或任意单个PCE也不会具有计算路径的足够知识。因此，需要MPLS流量工程路径计算技术来计算域间TE-LSP。

计算域间路径的第一个示例性方法是“每个域”的路径计算，该方法依靠每个域的入口节点来计算到该域的下一出口节点的路径。域的入口和出口节点(或“边界节点”)可以被头端节点指定为“松散跳”(即指明域的期望入口和出口而非指明穿过域的物理路径的标记)。或者，在接收到计算穿过其域的路径的请求时，每个域的入口节点计算同一域的优选出口节点。虽然“每个域”方法很简单，但是它不保证计算出最优(最短)域间路径，因为它是串行执行的，并且在计算当前域的路径时不考虑下一个域的开销。此外，该方法没有提供保证一组被不同地路由的路径的机制，因为每个域中的入口节点彼此独立地执行它们对所需网段的路径计算。

在另一示例性方法中，使用PCE来创建分布式PCE体系结构，以将MPLS TE-LSP扩展跨过域边界。这种分布式体系结构的一个示例在Vasseur等人于2003年9月18日提交的题为COMPUTING INTER-AUTONOMO US SYSTEM MPLS TRAFFIC ENGINEERING LSP PA THS的共有共同未决美国专利申请No.10/767,574中有所描述，该申请的全部内容通过引用结合于此。在分布式PCE体系结构中，计算路径所需的可见性在邻近域之间被扩展，因此PCE可以通过交换虚拟最短路径树(VSPT)并同时保留跨域保密性(例如当应用于AS时)来协作计算跨过多个域的路径。

使用可被表示为由“松散跳”构成的虚拟链路的VSPT，因为服务提供商可能希望维持它们的内部网络体系结构和设计机密。计算VSPT的一种方法是使用虚拟最短路径树(VSPT)算法。一般而言，VSPT是压缩路径描述(域的入口和出口/目的地点)，该描述以将内部路径详情对邻近域保密的方式通知前一PCE：可以从特定入口到特定出口来到达目的地。构成VSPT的虚拟链路一般将具有用于每个计算出的链路的相关网络开销。应当注意，在多个域操作于共同管理机构(例如唯一的服务提供商)之下的情况下，这些虚拟链路还指定整个路径。还可以在显式路由对象(ERO)中组织(以某种协议)一组虚拟链路，以辅助向前一PCE传输压缩的路径描述。

具体而言，根据VSPT算法，对于域间路径计算示例而言，PCC(例如头端节点)首先向它的域中的已知本地PCE发送路径计算请求，以计算到目的地(例如末端节点)的路径。该路径计算请求随后被从本地PCE传递至去往目的地途中的每个域(“下游”域)中的PCE。

一旦收到路径计算请求，包含目的地的最终域中的PCE就计算VSPT，VSPT是以目的地为根并包括一组要求约束的最短路径的从该目的地到域的每个边界路由器的最短路径树。这可以使用本领域已知的CSPF(约束最短路径优先)算法或任何其他适当算法来计算。然后，最终域的PCE利用虚拟链路(或“松散跳”)发送VSPT到前一域的PCE。VSPT可选地以下述方式使用松散跳，其中域内部的跳和它们的开销是保密的。松散跳可以具有作为内部开销的组合或代表的单个相关开销。

前一域中的PCE现在重复执行VSPT算法，并将它从最终PCE接收的VSPT与它自己域中的拓扑(包括任何域间链路)联接起来，以便计算新路径。对所有域重复该过程，直到响应到达发起PCC。因此，VSPT算法被称为“后向递归路径计算”。

为了使后向递归路径计算正确工作，邻近域之间必须存在协议以便共享计算路径所需的可见性。如果没有协议，PCE就不能通过交换VSPT来协作计算跨过多个域的路径，即使VSPT保持保密性也如此。在这些情况下，邻近域可以只通告其他域必须在它们的SPT中使用的单个虚拟链路。但是存在多个域(例如域A—B—C)的情况，其中某些域可能具有与某些其他域的协议(A和B，以及A和C)，但是其他域并不共享协议(B不和C共享协议)。协议不存在于所有邻近域之间的情况下的VSPT计算可能是无法实现的。

因此，需要允许第一域的单个头端节点高效地计算最短域间路径而不要求来自多个其他域中的多个其他节点的路径计算的技术。还需要允许头端节点计算穿过具有与第一域的协议的其他域的路径而所述其他域不具有彼此之间的协议的技术。

发明内容

本发明涉及一种计算从本地域的头端节点到远端域的尾端节点的跨越计算机网络的多个域的流量工程(TE)标签交换路径(LSP)的技术。该新颖的域间TE-LSP计算技术包括由利用位于远端域(即本地域之外的域)内的路径计算元件(PCE)的头端节点执行的计算算法。具体而言，头端节点请求来自每个远端域内的PCE的路径段，其中路径段代表所有入口边界路由器到特定远端域的所有出口边界路由器(即穿过域)或到尾端节点之间的路径。在接收到来自每个远端域的路径段时，头端节点将路径段与本地域信息相组合，并执行从头端节点到尾端节点的前向路径计算以找出最佳(即“最短”)路径。

根据本发明，在尝试建立到尾端节点的TE-LSP时，源头端节点首先确定目的地尾端节点是否在远端域中。如果是，则头端节点例如通过参考本地配置或路由选择策略来识别位于源和目的地之间的域。头端节点基于开销度量计算到它的本地域中与在目的地方向上的下一个域的一个或多个入口边界路由器通信的每个出口边界路由器的路径(例如最佳路径)。

如果存在至少一个满足所尝试的TE-LSP的约束的路径，则头端节点发送路径计算请求到下一跳域中的已知PCE，请求从与本地“上游”域通信的每个入口边界路由器到i)与下一下游域通信的每个出口边界路由器或ii)目的地尾端节点(如果它位于同一域中)的一个或多个路径。依赖于域之间的配置，头端节点接收由PCE计算出的路径段(如果有的话)作为具有相关开销的物理链路或虚拟链路。如果存在一个或多个路径，则头端节点发送路径计算请求到下一个下游域，依此类推，直到到达目的地。或者，头端节点可以首先发送路径计算请求到每个远端域中的每个PCE，并随后接收所有远端域的路径段，而不在初始时例如一次一个地检查每个域中是否存在路径。在接收到所有路径段时，头端节点将这些段与其本地路径信息相联接，并基于所有域的拓扑(物理的或虚拟的)运行从头端节点到尾端节点的最短路径优先(SPF)计算。

有益地，这里描述的技术实现了跨过网络的多个域的高效路径计算(例如域间TE-LSP和/或不同路径)。具体而言，本发明的技术提供了用于允许本地域的头端节点基于从多个域中的PCE接收的路径段的更完整的拓扑来执行到远端域的尾端节点的前向路径计算。本发明还提供了从头端节点到尾端节点的最优(最短)路径，同时保留跨过多个域的保密性。

附图说明

结合附图参考下面的描述可以更好地理解本发明的上述和其他优点，在附图中相似的标号指示完全或功能上相似的元件，其中：

图1A是可根据本发明使用的自治系统的示例性计算机网络的示意性框图；

图1B是可根据本发明使用的区域的示例性计算机网络的示意性框图；

图2是可有益地与本发明一起使用的示例性路由器的示意性框图；

图3是示出了用于根据本发明计算TE-LSP的步骤序列的流程图；

图4是示出了用于根据本发明计算TE-LSP的备选步骤序列的流程图；并且

图5A—5F是示出了根据本发明的路径段累积和路径计算的示例性序列的示意图。

具体实施方式

图1A是包括由自治系统AS2互连的自治系统AS1和AS3的示例性计算机网络100a的示意性框图。这里将自治系统(AS)定义为网络中受共同管理机构管辖并执行一个或多个域内路由选择协议的诸如域内路由器等中间节点的群组。虽然每个AS被示为自治系统，但是本领域技术人员将理解，AS也可以配置为路由选择域或其他网络或子网。自治系统AS1包括域内路由器，例如AS边界路由器ASBR1^*和ASBR2，通过这些域内路由器，诸如数据分组等通信可以传入该AS，以及传出该AS，分别传递到AS2的AS边界路由器ASBR3^*和ASBR4。AS2还包括与AS3的边界路由器ASBR7^*和ASBR8通信的AS边界路由器ASBR5和ASBR6。此外，在AS1和AS3中，分别存在示例性域内路由器A和B。此外，在AS1中有示例性域内路由器n1和n2。本领域技术人员将理解，AS中可以使用任意数量的路由器，这里示出的视图是为了简明起见。

数据分组可以使用诸如传输控制协议/因特网协议(TCP/IP)、用户数据报协议(UDP)、异步传输模式(ATM)协议、帧中继协议、因特网分组交换(IPX)协议等预定网络通信协议在自治系统AS1—AS3之间交换。路由选择信息可以使用诸如传统距离向量协议或例如使用链路状态通告或链路状态分组的链路状态协议等预定“内部”网关协议(IGP)在路由器之间分发。此外，包含网络路由选择信息的数据分组可以使用诸如边界网关协议(BGP)等“外部”网关协议在自治系统AS1—AS3之间交换。

图1B是包括区域A1—A3的示例性计算机网络100b的示意性框图。区域A1具有示例性域内路由器A、n1和n2，而区域A3具有示例性域内路由器B。此外，A1和A2共享边界路由器ABR1^*和ABR2，而A2和A3共享ABR3^*和ABR4。这里使用的区域一词是指彼此共享全部网络拓扑信息但不一定与区域外部的路由器共享全部网络拓扑信息的路由器的集合。区域的集合可以被包含在单个AS中。这里使用的术语区域还包括术语“级别”，其与采用IS-IS作为其IGP的网络具有相似的含义，在此情形下区域边界路由器ABR1—4被实现为级别1/级别2(L1L2)路由器。这些示例仅是代表性的。本领域技术人员应当理解，不论何时提及区域或级别，都也可以使用自治系统。区域、级别和自治系统在这里总称为“域”。此外，术语ABR、L1L2路由器、ASBR和更一般的边界路由器在这里被可互换地使用。

图2是可以作为域内路由器或边界路由器有益地与本发明一起使用的示例性路由器200的示意性框图。路由器包括由系统总线250互连的多个网络接口210、处理器220和存储器240。网络接口210包含用于通过耦合到网络100a、b的物理链路传送数据的机械、电和信令电路。网络接口可以被配置为使用多种不同通信协议(包括TCP/IP、UDP、ATM、同步光网络(SONET)、无线协议、帧中继、以太网、光纤分布数据接口(FDDI)等)来发送和/或接收数据。

存储器240包括用于存储与本发明相关联的软件程序和数据结构的可由处理器220和网络接口210寻址的多个存储位置。处理器220可以包括适于执行软件程序和操纵数据结构(例如路由选择表246)的必要元件或逻辑。路由器操作系统242的一些部分一般驻留在存储器240中并由处理器执行，并且路由器操作系统242通过调用支持在路由器上执行的软件过程和/或服务的网络操作等来在功能上组织路由器。这些软件过程和/或服务包括PCC/PCE过程245、路由选择服务247、路由选择信息库(RIB)248，以及RSVP服务249。本领域技术人员将很清楚，包括各种计算机可读介质在内的其他处理器和存储器装置也可用来存储和执行与这里描述的本发明的技术有关的程序指令。

路由选择服务247包含由处理器220执行以便执行由诸如IGP(例如OSPF和IS-IS)和BGP等一个或多个路由选择协议提供的功能的计算机可执行指令。这些功能可以被配置为例如包含用于进行转发判决的数据的管理转发信息库(未示出)。RSVP服务249包含用于根据本发明实现RSVP和处理RSVP消息的计算机可执行指令。RSVP在R.Braden等人的Resource ReSer Vation Protocol(RSVP)((RFC)2005，1997年9月)中描述，该文献可从IETF获得并且通过引用结合于此，如果在这里全部列出一样，RSVP还在上文中结合的题为RSVP-TE：Extensions to RSVP for LSPTunnels的RFC 3209中有所描述。

路由选择表246例如驻留在存储器240中，并被用来存储路由选择信息(包括可达目的地地址前缀和相关属性)。这些属性包括路由器200用来到达目的地前缀的下一跳信息和到达目的地前缀的相关度量(例如开销)。路由选择表246例如由RIB 248维护和管理。因此，RIB 248维护由诸如BGP和IGP等路由选择协议提供的路由(路径)拷贝，以计算安置到路由选择表246中的最佳路径/路由。

在一个实施例中，这里描述的路由器是实现多协议标签交换(MPLS)并充当标签交换路由器(LSR)的IP路由器。在一种简单的MPLS情景中，在网络入口处，在将每个传入分组转发到下一跳路由器之前，标签被基于传入分组的转发等价类分配给每个传入分组。在每个路由器处，通过使用在传入分组中发现的标签作为对包括该信息的标签转发表的参考来确定转发选择和新替代标签。在网络出口(或其前一跳)处，基于传入标签进行转发判决，但是当分组被发送往下一跳时可选地不包括标签。

以此方式经过网络的分组所采取的路径被称为标签交换路径(LSP)或流量工程(TE)-LSP。TE-LSP的建立需要计算路径、延路径的信令和延路径的转发表的修改。MPLS TE建立在某些条件下具有保证带宽的LSP。例如，可以通过使用RSVP协议(具体而言是RSVP TE信令消息)来通知TE-LSP。

虽然这里描述的说明性实施例涉及MPLS，但是还应当注意，本发明可以有益地应用于通用MPLS(GMPLS)，其不仅涉及基于分组和信元的网络，还涉及时分复用(TDM)和光网络。GMPLS是公知的并在2004年10月的题为Generalized Multi-Protocol Label Switching(GMPLS)的RFC3954和2004年10月的题为Generalized Multi-Protocol Label Switching(GMPLS)Extensions for Synchronous Optical Network(SONET)andSynchronous Digital Hierarchy(SDH)Control的RFC 3946中有所描述，这两篇文献的全部内容通过引用结合于此。

本发明涉及用于计算从本地域的头端节点到远端域的尾端节点的跨过多个计算机网络域的TE-LSP的技术。新颖的域间TE-LSP计算技术包括由头端节点利用位于远端域(即与本地域不同的域)中的PCE执行的计算算法。具体而言，头端节点请求来自每个远端域中的PCE的路径段，其中路径段代表特定远端域的所有入口边界路由器到所有出口边界路由器(即穿过域)之间或到尾端节点之间的路径。在从每个远端域接收到路径段时，头端节点将路径段与本地域信息组合，并执行从头端节点到尾端节点的转发路径计算，以找出最佳(即“最短”)路径。

根据本发明，在尝试建立到尾端节点的TE-LSP时，源头端节点首先使用例如本地配置或传统策略(BGP)路由选择来确定目的地尾端节点是否在远端域中。如果目的地在远端域中，则头端节点随后例如通过再次参考本地配置或策略路由选择来识别位于源和目的地之间的域。头端节点基于开销度量计算到其本地域中与目的地方向上的下一个域(即“下一跳”或“下游”域)的一个或多个入口边界路由器通信的每个出口边界路由器的路径(例如最佳路径)。诸如CSPF算法或Dijkstra算法等传统算法可被用来计算路径(其中头端节点时最小开销节点)。

如果存在满足所尝试的TE-LSP的约束的至少一个路径，则头端节点发送路径计算请求到下一跳域中的已知PCE，请求从与本地(“上游”)域通信的每个入口边界路由器到i)与下一下游域通信的每个出口边界路由器或ii)目的地尾端节点(如果它位于同一域中的话)的一个或多个路径。

例如，假设在图1A和1B中标记有“*”的边界路由器是有PCE能力的边界路由器。本地PCE的地址可以被手工配置。或者，PCE可以通过在AS内洪泛来通告自身。可根据2004年7月公布的Vasseur等人的OSPFMPLS Traffic Engineering Capabilities(draft-vasseur-ospf-te-caps.txt)来使用路径计算元件发现(PCED)技术，该文献通过引用结合于此。PCED消息可以包括对以下能力的指示，所述能力例如是计算本地路径、区域间路径、AS间路径、多域路径、不同路径(diverse path)等的能力。其他PCE地址的知识可以通过静态配置或BGP通告来获得，如本领域技术人员很容易设计的那样。

当PCE接收路径计算请求时，它计算它的域的每个入口边界路由器到同一域的每个出口边界路由器之间的最短路径集合。注意，PCE不请求任何其他PCE扩展该路径，而只是返回包括它的域的路径以及它们的相关开销的响应到头端节点。PCC和PCE之间的路径计算请求(和响应)可根据2004年7月的Vasseur等人的RSVP Path Computation Request and ReplyMessage，Internet Draft中规定的协议而被交换，该文献的内容通过引用结合于此，如同在这里全部列出一样。应当理解，RSVP仅被用作为示例，根据本发明也可以使用其他通信协议。

依赖于通信中的域是否被配置为共享可见性信息，头端节点接收由PCE计算出的路径段(如果有的话)作为具有相关开销的物理链路或虚拟链路。接收到的路径被存储在存储器240(例如头端节点的TE数据库(未示出))中。注意，不论网络是否被保密，链路都可以是虚拟或“松散”的。在此情形下，被完整计算的路径可被认为是穿过仅由每个保密域的入口和出口点组成的域的基本路径以及相关开销度量。在接收松散跳时，入口边界路由器计算到达下一跳(例如出口边界路由器)的路径。用于维护跨过保留有计算出的路径的域的保密性的其他方法在均由Vasseur等人在2004年5月提交的共有共同未决美国专利申请No.10/982,641(题为SYSTEM AND METHOD FOR RETREIVING COMPUTED PATHS FROMA PATH COMPUTATION ELEMENT USING A PATH KEY)和10/983,327(题为SYSTEM AND METHOD FOR RETRIEVING COMP UTED PATHSFROM A PATH COMPUTATION ELEMENT USING ENCRYPTEDOBJECTS)中描述，这两份申请的全部内容通过引用结合于此。

如果存在一个或多个路径，则头端节点发送路径计算请求到下一下游域，依此类推，直到到达目的地。在接收到所有路径段时，头端节点将这些段与其本地路径信息联接，并基于所有域的拓扑(物理的或虚拟的)从头端节点到尾端节点运行最短路径优先(SPF)计算。

图3是示出了根据本发明计算TE-LSP的步骤序列的流程图。序列300开始于步骤305，并继续到步骤310，其中头端节点确定目的地尾端节点是否驻留在远端域中。如果否(即目的地是本地的)，则头端节点在步骤315执行到尾端节点的传统SPF，序列在步骤390处结束。否则，在步骤320，头端节点识别位于本地域和包含目的地的远端域之间的远端域。在步骤325，头端节点计算到它的域中与下一跳下游域相连接的每个出口边界路由器的最短路径。如果在步骤330确定出不存在路径(例如当没有路径满足TE-LSP约束时)，序列在步骤390处结束。

但是，如果步骤330处存在至少一个路径，则序列继续到步骤335，其中确定所关心的域(“当前”域)是不是目的地域。如果不是，则在步骤340，头端节点发送请求到当前域的PCE以获得从当前域的每个入口边界路由器到当前域的每个出口边界路由器的一个或多个路径。在步骤345，头端节点接收来自PCE的响应，该响应可以是一组物理或虚拟链路，如上所述。在路径350，确定在该域中是否存在满足约束的任何路径。如果否，则序列结束。否则，头端节点在步骤355将响应中的路径与已有的被存储的拓扑相联接，并进行到关于下一个域的路径计算(步骤360)。这里，序列返回步骤335，其中所关心的域是“下一跳下游”域。

如果确定下一跳下游域是目的地域，则在步骤365，头端节点发送请求到目的地域的PCE，以获得从目的地域的每个入口边界路由器到目的地的一个或多个路径。在步骤370，头端节点接收来自PCE的响应。此外在步骤375，确定域中是否存在任何受约束路径。如果否，则序列在步骤390处结束。否则，头端节点在步骤380中将最终响应中的路径与已有的被存储的拓扑相连接。利用完整的网络拓扑(物理的或虚拟的)，头端节点在步骤385执行以头端节点(源)为根的到尾端节点(目的地)SPF，以找出源和目的地之间的最短路径以便建立TE-LSP。然后，该序列在步骤390处结束。

应当注意，在备选实施例中，头端节点可以首先发送路径计算请求到每个远端域中的每个PCE的路径计算请求，并随后接收所有远端域的路径段，而不在初始时例如一次一个地检查每个域中是否存在路径。在接收到所有路径段时，头端节点将这些段与其本地路径信息相联接，并确定是否存在满足TE-LSP的要求的路径。如果存在，则头端节点基于所有域的拓扑(物理的或虚拟的)运行从头端节点到尾端节点的SPF计算。

图4是示出了用于根据本发明计算TE-LSP的备选步骤序列的流程图。序列400开始于步骤405，并继续到步骤410，其中头端节点确定目的地尾端节点是否驻留在远端域中。如果否，即，目的地是本地的，则头端节点在步骤415执行到尾端节点的传统SPF，序列在步骤460结束。否则，在步骤420，头端节点识别位于本地域和包含目的地的远端域之间的远端域。在步骤425，头端节点计算到它的域中的连接到下一跳下游域的每个出口边界路由器的最短路径。如果在步骤430确定不存在路径(例如当没有路径满足TE-LSP约束)时，序列在步骤460处结束。但是如果在步骤430至少存在一个路径，则序列继续。

在步骤435，头端节点发送请求到每个远端域的PCE，以获得从PCE的域的每个入口边界路由器到同一域的每个出口边界路由器的路径。在步骤440，头端节点接收来自每个PCE的响应，该响应如上所述可以是一组物理或虚拟链路。头端节点在步骤445响应于已有的被存储的拓扑(本地拓扑)联接路径。如果在步骤450不存在穿过远端域的满足约束的路径，则序列结束。否则，头端节点在步骤455利用完整的网络拓扑(物理的和虚拟的)执行以头端节点(源)为根的到尾端节点(目的地)的SPF，以找出源和目的地之间的最短路径从而建立TE-LSP。然后序列在步骤460处结束。

图5A到5F是示出了根据本发明的路径段累积和路径计算的示例性序列的示意图。使用图1B的网络100b，图5A示出了在本地计算出的从头端节点A分别穿过物理节点n1和n2到出口边界路由器ABR1^*和ABR2的区域A1的第一路径段。根据上面描述的方法，头端节点A向有PCE能力的ABR1^*请求穿过区域A2的路径段，并接收图5B所示的路径。头端节点将这些结果与本地信息联接，如图5C所示。图5D示出了从目的地区域A3(从有PCE能力的ABR3^*)到尾端节点B的返回的路径段，该路径段随后被与已有拓扑相联接，如图5E所示。例如，在图5E中，从头端节点到第一组边界路由器(ABR1^*和ABR2)的链路是物理链路，而其余链路是虚拟的。最后，头端节点A计算到尾端节点B的SPF，得到图5F所示的最优路径。本领域技术人员将理解，图5A—5F仅应被视为说明示例，并已经为了便于理解而被简化。注意，未示出开销值，并且所得到的最优路径仅是示例路径。此外，在远端域不具有有PCE能力的路由器或不具有与头端节点的域的协议时，本领域技术人员将理解这里描述的新颖技术和其他传统方法(例如松散跳路由选择)的组合可以被使用。

有益地，这里描述的技术实现了跨过网络的多个域的路径(例如域间TE-LSP和/或不同路径)的高效计算。具体而言，本发明的技术提供了允许本地域的头端节点基于从多个域中的PCE接收的路径段的更完整的拓扑来执行到远端域的尾端节点的前向路径计算的系统。本发明还提供了从头端节点到尾端节点的最优(最短)路径，同时保留了跨过多个域的保密性。

以上描述涉及本发明的特定实施例。但是很明显，在保留所描述的实施例的一些或全部优点的同时可以对所描述的实施例进行其他改变和修改。例如，明确地考虑到了本发明的教导可被实现为软件，包括具有在计算机、硬件、固件或其组合上执行的程序指令的计算机可读介质。因此，本发明应仅被理解为示例性的而不应限制本发明的范围。因此，所附权利要求意在覆盖落在本发明的真实精神和范围内的所有这些改变和修改。