路径计算元件的重优化触发

摘要

本发明公开了一种在采用(一个或多个)路径计算元件布置MPLS流量工程隧道的网络中缓解带宽分裂的机制。一种应用是采用MPLS流量工程LSP的分布式计算的多自治系统或多区域网络。特定的路径计算元件可以基于路径计算失败(其中所需路径由于带宽约束而被阻隔)的监视来确定存在带宽分裂。响应于检测到带宽分裂状况，路径计算元件在其自治系统或区域中泛滥路由选择通知。节点通过请求对它们自身的先前请求的流量工程LSP进行重优化来对路由选择通知作出响应，从而使得路径计算元件有机会缓解带宽分裂。

权利要求

1.一种操作路径计算元件的方法，所述方法包括：确定网络中存在分裂带宽状况，其中确定网络中存在分裂带宽状况包括监视建立路径中的失败率并将监视的结果与失败率标准进行比较；以及响应于所述分裂带宽状况，执行MPLS流量工程路径的重路由选择以便提高成功布置的可能性，其中重路由选择包括：

接收对路径重优化的请求直到定时器期满；然后响应于所述请求重计算所述路径。

2.如权利要求1所述的方法，其中执行重路由选择的步骤包括：向所述网络中的多个节点分发重优化请求。

3.如权利要求1所述的方法，其中重计算步骤包括：采用虚拟最短路径树技术进行重计算。

4.如权利要求1所述的方法，其中重计算步骤包括：重计算所述路径以便减小带宽需求。

5.一种用于操作路径计算元件的设备，所述设备包括：用于确定网络中存在分裂带宽状况的装置，其中用于确定网络中存在分裂带宽状况的装置包括用于监视建立路径中的失败率的装置和用于将监视的结果与失败率标准进行比较的装置；以及用于响应于所述分裂带宽状况，执行MPLS流量工程路径的重路由选择以便提高成功布置的可能性的装置，其中用于执行重路由选择的装置包括：用于接收对路径重优化的请求直到定时器期满的装置；以及用于响应于所述请求重计算所述路径的装置。

6.如权利要求5所述的设备，其中用于执行重路由选择的装置包括：用于向所述网络中的多个节点分发重优化请求的装置。

7.如权利要求5所述的设备，其中用于重计算的装置包括：用于采用虚拟最短路径树技术进行重计算的装置。

8.如权利要求5所述的设备，其中用于重计算的装置包括：用于重计算所述路径以便减小带宽需求的装置。

说明书

路径计算元件的重优化触发

[0001] 相关申请的声明

[0002] 本申请涉及2004年1月29日提交的题为“COMPUTING INTER-AUTONOMOUS SYSTEM MPLS TRAFFIC ENGINEERING LSP PATHS”的美国专利申请10/767,574的主题，该申请的全部内容通过引用全文包含于此，以用于各种目的。

背景技术

[0003] 本发明涉及数据联网，更具体而言涉及某些类型环境中的路径计算。

[0004] MPLS(多协议标签交换)流量工程已被开发来满足诸如保证可用带宽之类的数据联网需求。MPLS流量工程利用现代标签交换技术来通过标签交换路由器(LSR)的IP/MPLS网络建立保证带宽端到端隧道。这些隧道是一种标签交换路径(LSP)，因此一般被称为MPLS流量工程LSP。

[0005] 从LSP头端(head-end)到LSP末端(tail-end)建立MPLS流量工程LSP涉及通过LSR网络的路径计算。最优地，计算出的路径是满足所有相关约束(例如所需带宽、相似性(affinity)等)的以某种量度测量的“最短”路径。路径计算可由头端LSR或某些其他工作为路径计算元件(PCE)的实体执行。头端或PCE利用其关于网络拓扑和每条链路上的可用资源的知识来根据LSP流量工程约束执行路径计算。有多种路径计算方法，包括CSPF(约束最短路径优先)。

[0006] 用于MPLS流量工程LSP的路径计算是很重要的问题，因为这些LSP除了其他约束以外还有带宽需求，并且网络链路具有有限带宽和特定特性。当头端或PCE尝试布置流量工程LSP时，它考虑到LSP的带宽需求和其他约束，并且确保这些约束沿路径得到满足(例如沿所布置的路径的每条链路有足够的容量)。如果LSP被成功地布置，则其带宽需求被从所有构成链路上的容量减去。但是，在某些情况下没有能满足流量工程LSP的带宽需求的布置。

[0007] 在很多网络中，以分布式方式完成路径计算。虽然路径计算元件可以执行用于给定自治系统或区域的所有路径计算，但是它可能仅在LSP头端请求时才操作。此外，路径计算元件通常不保留先前布置的路径的状态信息。由于路径计算元件不是自由地执行LSP路径的同时重计算，因此可能出现不希望的带宽分裂(bandwidth fragmentation)状况。当带宽过度分裂时，可能理论上有足够的资源满足所有需求，但是协调分配的能力缺失导致资源分裂，从而某些需求事实上得不到满足。

[0008] 参考一个简单示例可以很容易地理解带宽分裂问题。图1示出了具有3个自治系统AS1、AS2和AS3的多自治系统网络情景。这3个自治系统的节点之间的每条链路都具有10Mbps容量。现在假设工作为路径计算元件的ASBR1通过穿越ASBR1、ASBR4、节点112、ASBR7和ASBR9，从节点108到节点104布置一条3Mbps MPLS流量工程LSP。在这样布置一段时间之后，节点110请求ASBR1从节点110到节点116布置一条3Mbps LSP。ASBR1将该LSP布置为穿越ASBR3、ASBR6、节点114、ASBR8和ASBR10。在这两条LSP被布置之后，节点102请求ASBR1从节点102到节点104布置一条8Mbps LSP。

[0009] 这是不可能的，因为两条3Mbps LSP已经占用了节点102和节点104之间每个能想到的路由上的足够带宽，从而阻碍了8Mbps LSP的布置。事实上存在支持所有3条LSP的网络资源，这是因为最初布置的3Mbps LSP可被重路由选择以包括节点108、ASBR2、ASBR5、ASBR6、节点114、ASBR8、ASBR10、节点116和节点104。如果最初的LSP以此方式被重路由选择，则容量将被释放，以允许8Mbps LSP被布置为从节点102到节点104通过节点108、ASBR1、ASBR4、节点112、ASBR7、ASBR9和节点104。使用当前可用的技术，路径计算元件ASBR1不能产生这种情况。

[0010] 带宽分裂的一种部分解决方案是向流量工程LSP指定优先级，从而对建立较高优先级LSP的请求可使得较低优先级LSP在必要时被抢占和拆除以便释放带宽。通过向具有较高带宽的流量工程LSP指定较高优先级，可以减小新的流量工程LSP由于带宽分裂而被阻隔的可能性。为了避免突然抢占的干扰，已经开发了软抢占技术，其中头端被给予一定时间以便在被抢占的LSP被中间节点拆除之前重路由选择被抢占的LSP。但是，这不是一个完全的解决方案，因为优先级的可行数量是有限的，并且很难将流量工程LSP带宽需求映射到优先级。如果这种映射是静态的，则它必须适应MPLS流量工程带宽需求的分布，并且当该分布显著改变时被手工重配置。自动执行映射将是非常复杂的。

[0011] 需要带宽分裂问题的改善的解决方案。

发明内容

[0012] 本发明的实施例提供了一种在采用(一个或多个)路径计算元件布置MPLS流量工程隧道的网络中缓解带宽分裂的机制。一种应用是采用MPLS流量工程LSP的分布式计算的多自治系统或多区域网络。特定的路径计算元件可以基于路径计算失败(其中所需路径由于带宽约束而被阻隔)的监视来确定存在带宽分裂。响应于检测到带宽分裂状况，路径计算元件在其自治系统或区域中泛滥路由选择通知。节点通过请求对它们自身的先前请求的流量工程LSP进行重优化来对路由选择通知作出响应，从而使得路径计算元件有机会缓解带宽分裂。

[0013] 本发明的第一方面提供了一种操作路径计算元件的方法。该方法包括：确定网络中存在分裂带宽状况；以及响应于分裂带宽状况，执行MPLS流量工程路径的重路由选择以便提高成功布置的可能性。

[0014] 本发明的第二方面提供了一种操作路径计算元件以提高成功路径布置的可能性的方法。该方法包括：向网络中的多个节点分发重优化请求；接收对路径重优化的请求直到定时器期满；然后响应于请求重计算路径。

[0015] 通过参考说明书的其余部分和附图可以进一步理解本发明的本质和优点。

附图说明

[0016] 图1示出了可应用本发明实施例的多自治系统网络。

[0017] 图2示出了可应用本发明实施例的多区域网络。

[0018] 图3是描述了根据本发明一个实施例的缓解带宽分裂和/或改善网络资源使用的步骤的流程图。

[0019] 图4是描述了根据本发明一个实施例的计算通过多自治系统网络的路径的步骤的流程图。

[0020] 图5是描述了根据本发明一个实施例的计算通过多区域网络的步骤的流程图。

具体实施方式

[0021] 参考代表性网络环境描述本发明，本发明利用网络协议的某种组合来通过网络转发数据。链路可以使用任何类型的物理介质(例如光介质、无线介质、双绞线等)来实现。链路还可以是考虑到正在运行的联网协议的情况下，给予相连的节点邻接性的逻辑连接。

[0022] 在一个实施例中，这种网络的节点以由多种协议指定的方式互操作，所述协议包括例如TCP/IP和以下文档定义的但不限于以下文档定义的协议：

[0023] E.Rosen，et al.，″Multiprotocol Label Switching Architecture，″RFC3031，Internet Engineering Task Force(因特网工程任务组)，January 2001.[0024] Braden，et al.″Resource ReSerVation Protocol(RSVP)-Version 1Functional Specification，″RFC 2205，Internet Engineering Task Force，September 1997.[0025] Awduche，et al.， ″ Requirements for Traffic Engineering Over MPLS，″RFC2702，Internet Engineering Task Force，September 1999.[0026] Berger，et al.， ″ Generalized MPLS Signaling-RSVP-TE
Extensions，″RFC3473，Internet Engineering Task Force，January 2003.[0027] Vasseur，et al. ″ RSVP Path Computation Request and Reply Messages，″Internet Draft，Internet Engineering Task Force，June 2002.[0028] Lindem，et al.， ″ Extensions to OSPF for Advertising Optional RouterCapabilities，″Internet Draft，Internet Engineering Task Force，October
2003.

[0029] Vasseur，et al.， ″ OSPF Traffic Engineering Capability TLVs，″InternetDraft，Internet Engineering Task Force，October 2002.[0030] Vasseur，et al.，″Inter-AS MPLS Traffic Engineering，″Internet Draft，Internet Engineering Task Force，February 2003.

[0031] Vasseur，et al.， ″ OSPF MPLS Traffic EngineeringCapabilities，″InternetDraft，Internet Engineering Task Force，February 2004.[0032] Vasseur，et al.， ″ IS-IS MPLS Traffic Engineering
Capabilities，″InternetDraft，Internet Engineering Task Force，February 2004.[0033] 上述文档通过引用全文包含于此，以用于各种目的。

[0034] 在一个实施例中，这里描述的示例性网络的节点是实现多协议标签交换(MPLS)和工作为标签交换路由器(LSR)的IP路由器。在一种简单的MPLS情景中，在网络入口处，在将每个传入分组转发到下一跳节点之前，基于其转发等同类向每个传入分组指定标签。在每个中间节点处，通过使用在传入分组中找到的标签作为到包括该信息的标签转发表的参考来确定转发选择和新的替换标签。在网络出口处(或出口之前的一跳)，基于传入标签作出转发决定，但是可选地，当分组被发送到下一跳时不包括标签。

[0035] 以此方式穿越网络的分组所采用的路径是预先配置的，并且被称为标签交换路径(LSP)。LSP的建立要求路径计算、沿路径的信令，以及沿路径的转发表修改。MPLS流量工程建立了在某些条件下具有保证带宽的LSP。

[0036] 本发明的实施例提供了带宽分裂问题的解决方案。下面将讨论示例性情景，其中可以向包含多自治系统或多区域的网络应用带宽解分裂(defragmentation)。本发明还可应用于某些区域内环境。术语“自治系统”一般指网络中的隶属于公共机构并使用相同的域内路由协议的路由器群组。术语“区域”一般指彼此共享完整的网络拓扑信息但不一定与区域外的路由器共享完整的网络拓扑信息(即使这些区域外路由器与它们共享公共管理控制)的路由器集合。这里使用的术语“区域”还包括了对于采用IS-IS作为其IGP(内部网关协议)的网络来说具有类似意义的术语“级别”。

[0037] 图1示出了可应用本发明实施例的多自治系统网络。有3个自治系统AS 1、AS2和AS3。图1示出了8个被定位以连接自治系统的边界路由器：ABR1、ABR2，…ABR8。此外，图1将AS1示为包括路由器102、106、108和110，将AS2示为包括路由器112和114，将AS3示为包括路由器104和116。

[0038] 所有边界路由器一般都是BGP(边界网关协议)对等体。用于在AS内路由选择的协议(例如IGP)不在连接边界路由器的链路上工作。在AS中，例如公知的IS-IS协议或OSPF指令的IGP协议进行工作。ASBR1、ASBR8和ASBR9工作为用于它们各自的自治系统的路径计算元件。

[0039] 图2示出了可应用本发明实施例的多区域网络。有3个区域：区域1、区域0和区域2。区域边界路由器ABR1和ABR2互连区域1和区域0。区域边界路由器ABR1’和ABR2’互连区域0和区域2。区域1还包括路由器202、204和206。区域0还包括路由器208、210和212。区域2还包括路由器204和214。

[0040] 2004年1月29日提交的美国申请10/767,574中详细描述了跨过多个自治系统或区域的MPLS流量工程LSP的计算。在其中描述的方案中，每个区域或自治系统至少有一个路径计算元件。使用后向递归路径计算，其中多个路径计算元件参与开发虚拟最短路径树(VSPT)。路径计算元件一般不维护它们布置的LSP的状态。下面将提供这些技术的进一步细节。但是应当理解，本发明提供的网络资源使用和带宽解分裂中的改善并不限于到多自治系统或多区域网络的应用。

[0041] 路径计算元件的一般工作模式是服务于来自相同区域或自治系统内的节点或来自其他路径计算元件的对MPLS流量工程LSP的布置的请求。服务于这些请求可能涉及与其他路径计算元件的合作。这些操作的进一步细节可在2004年1月29日提交的美国申请No.10/767,574中找到，下面也提供了这些细节以供参考。

[0042] 图3是描述了根据本发明一个实施例的缓解(alleviate)带宽分裂和/或改善网络资源使用的步骤的流程图。除了一般的路径计算操作之外，图3的步骤一般在特定路径计算元件处执行。随着带宽分裂状况的进展，路径计算元件布置LSP的努力越来越频繁地失败。

[0043] 任何特定路径计算元件的失败可能是例如1)没能满足来自LSP头端的直接请求，或2)没能满足另一路径计算元件对在计算整体最短路径中用作为中间结果的虚拟最短路径树进行开发或扩展的请求。注意，失败1)或2)本身都可能是发生在另一路径计算元件处的2)的结果。因此，布置特定路径的失败可以被记录为两个或更多个路径计算元件处的失败。

[0044] 在步骤302，路径计算元件监视其路径计算失败率。例如，该路径计算失败率可以被估计为尝试的布置的一个百分比。在进一步处理之前，失败率可以经历移动平均、低通滤波等等。步骤304将路径计算失败率测量值与某个标准进行比较。该标准可以例如是根据经验设置的可配置阈值，从而分裂状况被正确地识别。

[0045] 如果分裂标准没被满足，则处理返回步骤302以便进一步监视。如果分裂标准被满足，则发起重优化。在替换实施例中，以规则间隔发起重优化，而不测量失败率。例如，重优化可以发生在每天的上午3-4点。如果MPLS流量工程LSP带宽被基于流量状况自动调节，则这种周期性重优化将不起作用，因为一天中任意时刻的带宽值和分裂状况都不可能代表网络状况。即使失败率测量被用来确定何时重优化，在以多大频率允许发生重优化的方面也可能有限制。

[0046] 在步骤306，路径计算元件用特殊路由选择通知泛滥(flood)其自治系统或区域，以便通知接收节点它们将请求MPLS流量工程LSP的重优化，而这些MPLS流量工程LSP是它们先前向路径计算元件请求布置的。虽然路径计算元件一般是无状态的，并且不记得它先前布置的流量工程LSP，但是请求头端节点将知道它们向该路径计算元件请求了它们的LSP中的哪些。路由选择通知的形式可以是在路由器能力消息中找到的MPLS流量工程能力TLV中的子TLV(标签(tag)长度值)中的一位，如Vasseur，et al.，″OSPF MPLS Traffic Engineering Capabilities，″Internet Draft(因特网草案)，Internet Engineering Task Force，February 2004或Vasseur，et al.，″IS-IS MPLS Traffic Engineering Capabilities，″Internet Draft，InternetEngineering Task Force，February 2004中所述。应当理解，该路由选择通知的泛滥在信令开销方面将更有效，即使路径计算元件为先前布置的MPLS流量工程LSP保留状态也是如此。

[0047] 在步骤308，接收被泛滥的路由选择通知的节点作出响应，请求对该节点已经在发送该通知的路径计算元件的帮助下建立的任何MPLS流量工程LSP的路径进行重计算。该重计算请求可通过使用在Vasseur，et al.″RSVP Path Computation Request and Reply Messages，″Internet Draft，InternetEngineering Task Force，June 2002中规定的协议来作出。路径计算元件在发送路由选择通知之后设置定时器，以在接收回复的同时向下计数。依赖于网络大小，可以使用例如15-30秒的定时器值。这将重优化延迟到接收到最大数量的请求。

[0048] 在步骤310，在定时器期满之后，路径计算元件重计算它已接收到对其的请求的LSP。计算利用下面描述的虚拟最短路径树算法。为了减少分裂并提高成功布置的可能性，LSP优选地被以带宽的降序布置。参考图4对多自治系统情形并参考图5对多区域情形提供路径计算的细节。除了它们与重优化的关系以外，这些路径计算细节还有助于提供用于理解什么事件可被记录为布置失败的上下文。

[0049] 图4是描述了根据本发明一个实施例来计算自治系统间MPLS流量工程LSP的路径的步骤的流程图。为此，我们假设具有n个自治系统AS1、AS2、AS3，...ASn的拓扑。每个AS都具有专用路径计算元件PCEi，所述专用路径计算元件可在路径计算客户端上静态配置，或通过IGP扩展被动态发现。此外，将定义互连每个AS的边界路由器。ASi的入口边界路由器是将ASi-1连接到ASi的边界路由器。ASi的出口边界路由器是将ASi连接到ASi+1的边界路由器。

[0050] 对于每个ASi，可以定义被标识为ASBR-en(k，i)的入口边界路由器的一个集合X-en(i)，ASBR-en(k，i)是ASi的第k个入口边界路由器。类似地，X-ex(i)是被标识为ASBR-ex(k，i)的出口边界路由器的集合，ASBR-ex(k，i)是ASi的第k个出口边界路由器。

[0051] 在步骤402，从LSP头端(其充当路径计算客户端)发送路径计算请求到本地路径计算元件(PCE1)。在重优化上下文中，该请求是在步骤308期间发送的重优化请求，并且包括对现有LSP的标识。在步骤404，路径计算请求被传递到在到LSP末端途中的每自治系统中的路径计算元件。关于其他路径计算元件地址的知识可以是本领域技术人员利用静态配置或BGP公告很容易设计的。如果N是到LSP末端途中的自治系统的数量，则可以认为路径计算请求最终被末端的自治系统中的PCE-N接收。

[0052] 反向递归路径计算开始。步骤406将N设置为自治系统数量，下标变量n被设置为等于N。步骤408是递归循环中的第一步骤。在步骤408，PCEn计算VSPTn。VSPTn是以LSP末端为根的最短路径树，并且包括从该末端到每个ASBR-en(k，n)的路径。这可以使用本领域已知的CSPF(约束最短路径优先)算法或任何其他适当算法来计算。如果对于该VSPTn没有找到任何路径，则这是对PCEn、PCE1和其间的所有其他路径计算元件的失败率有贡献的失败。在这种失败的情形下，过程在发送通知到接收请求的最初路径计算元件的情况下终止。在计算VSPTn时，应当考虑ASn的入口边界路由器之间的链路。

[0053] 步骤410发送指定从PCEn到PCEn-1的VSPTn的信息。VSPT可以或可以不以这样的方式被指定：即自治系统内部的跳和它们的成本被指定。步骤412递减n。

[0054] 在步骤414，PCEn将它从PCEn+1接收到的VSPT与ASn的拓扑相联结。在一种实现方式中，PCEn在将ASn拓扑与VSPTn+1联结之前可以在所有ASBR-ex(k，i)和ASBR-en(k’，i+1)之间的互连上调用本地CSPF算法。步骤416测试n是否等于1，即算法是否将访问LSP头端(PCE1)的自治系统中的路径计算元件。如果n不等于1，则另一迭代开始于步骤408，计算VSPTn。

[0055] 如果步骤416确定n＝1，则在步骤218，PCE1将接收的VSPT2联结到AS1的拓扑，基于联结的拓扑计算(例如使用CSPF)最短路径，然后将指定最短路径的信息发送到请求头端。如果找到多个等成本路径，则PCE1可以将它们中的一些或全部提供给请求头端。PCE1可以返回多条路径的其他情况包括例如头端请求对N条不同路径的计算。这些不同路径可以也可以不具有等成本。如果没有找到路径，则PCE1将这记录为失败。图4的过程和美国申请No.10/767,574中描述的替换可被应用到区域间情景。

[0056] 图5示出了可被用来实现例如图1-2中任何路由器和/或执行图3-4中任何步骤的网络设备500。在一个实施例中，网络设备500是可在硬件、软件或其任意组合中实现的可编程机器。处理器502执行存储在程序存储器504中的代码。程序存储器504是计算机可读介质的一个示例。程序存储器504可以是易失性存储器。存储相同代码的计算机可读介质的另一种形式是某种类型的非易失性存储器，例如软盘、CD-ROM、DVD-ROM、硬盘、闪存，等等。通过网络运送代码的载波是计算机可读介质的另一示例。

[0057] 网络设备500经由多个线路卡506与物理介质接口。线路卡506可包含以太网接口、DSL接口、吉比特以太网接口、10吉比特以太网接口、SONET接口，等等。当分组被网络设备500接收、处理和转发时，它们可被存储在分组存储器508中。网络设备500实现上述所有网络协议及其扩展，以及本发明提供的数据联网特征。

[0058] 在一种实现方式中，诸如上述路径计算操作等控制平面操作由处理器502控制和以信号通知，而转发表在线路卡506上维护。但是，本发明并不限于分布式体系结构。为了根据本发明实现功能，线路卡506可以包含与上面结合网络设备作为整体描述的那些类似的处理和存储器资源。

[0059] 应当理解，这里描述的示例和实施例仅是说明性的，本领域的技术人员可对其作出多种修改和改变，它们都将被包括在本申请的精神和范围以及所附权利要求的范围和它们的等同物的全部范围内。例如，本发明可应用于不穿越多个自治系统或区域的流量工程LSP。