用于最小化网络中的抢占的软抢占

摘要

在实施例中，公开了一种用于最小化LSP的软抢占的方法。在接收到预留消息用于其要求带宽超过下游链路的可用带宽的LSP之后，网络节点可以选择LSP的集合用于软抢占并且将沿它们路径的其它上游和下游节点共享该选择。通过协调对LSP的选择来在路径上的节点中软抢占，更少的LSP可以需要软抢占，这可以导致最小化过度网络中断，并且因此允许网络更有效率地工作。

说明书

技术领域

本公开一般地涉及网络中基于RSVP的流量工程（TE）的。本公开更 具体地涉及解决MPLS TE网络中带宽预留的多个抢占（preemption）。

背景技术

本部分中描述的方法可以被实行，但并非必须是先前已经被构想或者 实行过的方法。因此除非在本文中以其它方式指示，本部分中描述的方法 不是本申请的权利要求的现有技术并且不被本部分的结论承认为现有技 术。

在由多个网络元件（例如路由器和交换机）组成的分组交换网络中， 资源预留协议（“RSVP”）可以用于出于提供指定类型的网络流量（例如 语音流量）的优化路由的目的来预留路由路径。RSVP被在互联网工程任 务组（IETF）的请求评论（RFC）2205，Braden等1997年9月的“资源预 留协议（RSVP）-版本1，功能说明”，中描述。

MPLS（多协议标签交换）流量工程已被开发，用于满足诸如有保障 （guaranteed）可用带宽的数据联网要求。MPLS流量工程采用现代标签交 换技术来建立通过标签交换路由器（LSR）的IP网络的有保障带宽端对端 电路。这些电路是一种标签交换路径（LSP），因此一般被称为MPLS流量 工程LSP。MPLS流量工程LSP穿过一系列节点和使节点互连的链路。MPLS 流量工程协议将链路定义为代表互连标签交换路由器的物理资源。关于包 括可用链路带宽的特定链路的信息被用于确定LSP的路由以及发送它们的 建立的信令。接纳控制被执行以确保在LSP的设立期间链路容量未被超过。 针对MPLS流量工程的对RSVP的扩展被在RFC3209和RFC3473中描述， 它们的完整引用是：RFC3209，D.Awduche等2001年12月的“针对LSP 隧道的对RSVP的扩展”；RFC3473，L.Berger等2003年1月的“通用 多协议标签交换（GMPLS）信令资源预留协议-流量工程（RSVP-TE）扩展”。

MPLS TE抢占由释放已经建立的LSP的资源以及将它们分配到新的 LSP组成。对这些流量的释放导致被抢占的LSP的流量中断。软抢占是对 RSVP TE协议的扩展，以最小化甚至（在没有由于拥塞导致的丢失的情况 下）消除被抢占的LSP的流量中断。RFC5712，M.Meyer等2010年1月 的“MPLS流量工程的软抢占”，描述了MPLS网络中的软抢占。今天， 由于对于网络中的节点，针对软抢占计算候选LSP的集合的决定是本地的， 所以设立高优先级的LSP可以导致大量LSP被抢占，导向主要网络中断。

在本文档中，对所有上述对比文件的熟悉度是假定的。在一个方面， 这些扩展使得RSVP能够与实现多协议标签交换（MPLS）的进程交互操作。

附图说明

在图示中：

图1示出了具有三条预留路径的示例性节点网络。

图2示出了示例性网络节点的功能单元。

图3示出了使用软抢占向新的更高优先级路径分配带宽。

图4示出了用于向上游节点和下游节点通知路径已经被软抢占的方法。

图5是示出了在其上实施例可以被实现的计算机网络的框图。

图6示出了在与图3中的示例类似的示例网络上下文中，使用软抢占 向新的更高优先级路径分配带宽。

图7示出了根据实施例的、在节点内本地执行软抢占的方法。

图8示出了根据实施例的、接收和响应包含对进行中的软抢占的通知 的路径错误消息的方法。

图9示出了根据实施例的、接收和响应包含对进行中的软抢占的通知 的路径改变消息的方法。

具体实施方式

描述了一种用于软抢占的技术，软抢占用于最小化MPLS网络中的抢 占的数量。在以下说明中，出于解释的目的给出了许多具体细节，从而提 供对本发明的透彻理解。然而对本领域技术人员显而易见的是，本发明可 以在没有这些具体细节的情况下被实践。在其它示例中，公知的结构和设 备被以框图的形式示出，以避免不必要地模糊本发明。

本文根据下面的大纲描述了实施例：

1.0总体概述

2.0结构和功能概述

3.0向抢占的路径上的节点通知被抢占的带宽

3.1第一示例——一条路径被抢占

3.2在节点处本地执行软抢占

3.3第二示例——进行中的软抢占的效率

3.4响应路径错误消息

3.5响应路径变化消息

4.0实现方式机制——硬件概述

5.0扩展和替代

1.0总体概述

描述了一种用于最小化MPLS网络中抢占的数量的软抢占技术。在实 施例中，一种方法包括：在第一网络节点处接收指定第一标签交换路径 （LSP）、第一优先级值和与所述第一LSP相关联的第一最小要求带宽值 的资源预留消息；在所述第一网络节点处判定所述第一最小要求带宽值以 及与先前接收的第二LSP相关联的第二最小要求带宽的和超过了所述第一 网络节点到第二网络节点的第一链路的可用带宽；判定所述第一优先级值 是否指示所述第一LSP具有比所述第二LSP更高的优先级；响应于判定所 述第一LSP具有比所述第二LSP更高的优先级，将所述第二LSP标记为被 软抢占并且避免在所述第一链路上针对所述第二LSP预留带宽；并且向第 三网络节点发送错误消息以指定所述第二LSP在所述第一节点的所述第一 链路处被软抢占，其中所述第三网络节点是所述第一网络节点和所述第二 网络节点的上游节点，并且其中所述第三网络节点不是所述第二LSP的起 点。

在实施例中，所述方法还包括：所述第三网络节点将所述第二LSP标 记为被软抢占。

在实施例中，所述方法还包括：向第四网络节点发送消息以指定所述 第二LSP被软抢占。所述第四网络节点是所述第一网络节点和所述第二网 络节点的下游节点。

在实施例中，所述方法还包括：所述第四网络节点将所述第二LSP标 记为被软抢占。

在实施例中，所述方法还包括：响应于在所述第四网络节点处接收指 定第四LSP、第四优先级值和与所述第四LSP相关联的第四最小要求带宽 的资源预留消息，判定针对它们流量被通过所述第四LSP承载的LSP集合 中的任何LSP是否必须被抢占；响应于判定被通过所述第二链路承载的至 少一个LSP必须被软抢占，选择第五LSP用于软抢占；所述第五LSP是已 被标记用于软抢占的所述第二LSP或另外的LSP中的一个；向所述第二网 网络节点发送错误消息以指定所述第五LSP被软抢占；并且所述第二网络 节点是所述第四网络节点的上游节点。

在实施例中，到所述第四网络节点的消息是RSVP新路径改变消息。

在实施例中，所述方法还包括：通过判定所述第一最小要求带宽值以 及与先前分配至所述第一链路的一个或多个LSP中的每个LSP相关联的每 个最小要求带宽值的和超过了所述第一网络节点到第二网络节点的所述第 一链路的可用带宽，来判定先前分配至所述第一链路的一个或多个LSP中 的任何LSP是否必须被抢占。

在实施例中，判定先前分配至所述第一链路的一个或多个LSP中的任 何LSP是否必须被抢占还包括：所述第一LSP具有以至少所述LSP中的一 个更高的优先级。

在实施例中，当所述第一优先级值小于与所述第二LSP相关联的第二 优先级值时，所述第一LSP具有比所述第二LSP更高的优先级，并且当所 述第一优先级值大于与所述第二LSP相关联的第二优先级值时，所述第一 LSP具有比所述第二LSP更低的优先级。

在实施例中，所述方法还包括：所述第三网络节点接收所述错误消息 以指定所述第二LSP被软抢占。所述第三网络节点通过第二链路发送针对 所述第二LSP的流量并且将所述第二LSP标记为被下游节点软抢占。所述 方法还包括：响应于在所述第三网络节点处接收指定第一标签交换路径 LSP、第一优先级值和与所述第一LSP相关联的第一最小要求带宽值的资 源预留消息，判定针对它们流量被通过所述第二LSP承载的LSP集合中的 任何LSP是否必须被抢占；所述第三网络节点向上游转发所述路径错误消 息；并且响应于判定被通过所述第二链路承载的至少一个LSP必须被软抢 占，选择第三LSP用于软抢占。所述第三LSP是已被标记用于软抢占的所 述第二LSP或另外的LSP中的一个。所述方法还包括：向所述第三节点的 下游的所述第五网网络节点发送错误消息以指定所述第三LSP被软抢占。

在实施例中，所述消息中的每个符合资源预留协议（RSVP）。

其它实施例可包括被配置为执行上述步骤的非暂时性计算机可读存储 介质和计算机装置。

2.0结构和功能概览

在实施例中，本文的技术被联系RSVP的使用应用于MPLS流量工程 的上下文中。RSVP操作可以被使用Path（路径）消息和Resv（预留）消 息来控制。通常，在RSVP操作中发送器发出Path消息；接收器接收标识 发送器的该消息。结果是，接收器获得反向路径消息并且可以开始向中间 主机处的预留资源发送Resv消息。Resv消息通过互联网传播并到达发送器 处。发送器随后开始发送数据分组，并且接收器接收数据分组。发送器和 接收器可以是网络基础设施的分组交换路由器或其它元件。

MPLS提供了建立网络中的加急路由路径（本文中也可以被称为“隧 道”）的方法。管理站可以向路由器指示，带有指定标签并且到达特定入 站端口的所有分组应当被立刻路由至特定出站端口，在出站之后指定出站 标签被应用于这些分组。以这种方式，带有标签的数据分组绕过正常的路 由处理决定，并且通过网络更迅速地移动。针对对路由延时或延迟敏感的 网络流量（例如语音流量），这样的加急处理是有益的。

通常情况下，软件过程实现路由器或交换机中的RSVP。针对通过网络 的预留路径的RSVP流规范包括要求的最小带宽。预留路径中的每个链路 必须针对该路径至少预留要求的最小带宽。此外，流规范指示路径的优先 级。当节点接收到请求预留用于新路径的预订消息时，节点判定该节点是 否具有具有充足容量的可用下游链路，以在已经被在链路上预留的带宽之 外保障要求的最小带宽。如果没有链路具有充足容量，则新请求的路径的 优先级被与当前被分配至下游链路的路径的优先级进行比较。如果相较当 前服务的路径，新请求的路径具有更高优先级，则较低优先级路径易被抢 占。

一种方法用于标识较低优先级路径的集合，当被释放时，这些较低优 先级路径的聚合带宽至少与针对新路径要求的最小带宽一样大。这些标识 的路径可能难以抢占，意味着路径被突然从链路上的服务去分配 （deallocate），并且沿着这些路径的流量不再被在该链路上递送。

软抢占可以允许“先建后切（make before break）”的技术用于回收链 路上的带宽。软抢占可以涉及暂时预留的比链路的容量更多。在网络未被 施加重负载的时候，软抢占路径上的流量可以继续被递送，而系统判定用 于该软抢占路径的新路由。

图1示出了具有三条预留路径的示例性节点网络。为了示出网络中的 预留带宽，图1示出了具有链路101到107的节点A到G网络，在其上数 据可以直接以箭头方向从一个节点流到另一个。例如，节点A可以通过链 路101将流量发送到节点B，但由于在节点A和节点F之间没有链路，所 以节点A不能直接向节点F发送数据。数据从头端节点（例如节点A和节 点F）流到尾端节点（例如节点H和节点E）。从一个节点到另一个的路径 是通过它们数据从头端节点传输到尾端节点的链路和节点的序列。

出于示出清晰示例的目的，图1仅示出了被加标签为A到H的八（8） 个节点以及指定链路。在实践的实施例中，可以存在根据任何拓扑的任何 数量的节点和链路。节点A到H中的每个可以包括路由器、交换机或其它 计算设备。例如，如进一步描述的，节点A到H中的全部或任意个可以具 有示出在图2或图5中的类型的计算设备。

在图1中，示出在链路旁边的数字指示针对链路中的每个预留的最小 带宽用于由该链路来承载流量。数字代表已经被通过RSVP操作在假定的 先前时间处建立的假定的示例性预留带宽值。例如，在图示中存在具有如 下节点和链路的序列的两条路径：{节点A。链路101，节点B，链路102， 节点C，链路103，节点D，链路105，节点E}，其中节点A是头端100 并且节点E是尾端110。具有该序列的路径中的一条具有每次5个单位的预 留最小带宽，并且其它路径具有每次6个单位的预留最小带宽。

示出在图示中的第三路径具有序列{节点F，链路107，节点G，链路 106，节点C，链路103，节点D，链路104，节点H}其中节点F在头端120 处并且节点H在尾端130处。分配至该路径的最小带宽是每次4个单位。 链路103针对所有示出在图示中的路径来承载流量。

出于示出清晰示例的目的，图1仅示出了具有假定单位值的有限数量 的预留带宽。在实践的实施例中，可以提供任何数量的值并且使用任何有 用的单位值。

图2示出了示例性网络节点的功能单元。例如，节点C包括多个数据 处理组件200，数据处理组件200可以包括预留接收器单元210、路径错误 生成单元220、下游路径改变消息生成单元230、路径错误接收器单元240、 下游路径改变消息接收器单元250、软抢占决定单元260和LSP带宽接纳 单元270。

通常，生成单元220、230创建消息以发送至其它节点，并且接收器单 元210、240、250处理（处置）从其它节点接收的消息。

在各种实施例中，组件200包括一个或多个计算机程序、其它软件元 件、固件、ASIC、FPGA、其他的硬件元件或它们的组合。因此，网络节点 可以包括如本文所述被配置的特殊用途的计算机，以提供本文所述的特定 功能。

在实施例中，组件200可以被配置如下。

预留接收器单元210：在实施例中，预留接收器单元210从下游节点接 收路径预留消息（例如RSVP Resv消息），用于通过网络向新路径分配至 少指定的最小带宽。预留接收器单元210尝试在它的下游链路中的一个上 分配要求的最小带宽。下游链路承载朝向路径的尾端节点的流量。预留接 收器单元210判定除了已在该链路上被预留的其它带宽之外，候选链路中 的任何链路是否还具有容量来承载针对新路径要求的最小带宽。如果任何 候选链路具有可用容量来预留针对新路径的最小带宽，则该链路被选定用 于新路径，并且没有抢占是必须的。

路径错误生成单元220：在实施例中，当节点选择路径用于软抢占时， 路径错误生成单元220生成向抢占路径上的所有上游节点通知该路径被软 抢占的消息。在实施例中，消息仅被直接发送至最接近的上游节点并且被 向上游转发一跳直到错误消息到达头端。

在实施例中，路径错误生成单元220被配置为导致与沿相同抢占路径 的所有其它上游节点共享关于哪个路径已被一个节点软抢占的信息。

在实施例中，向上游节点转发路径预留消息被延时直到路径错误消息 被发送之后。延时给予了上游节点将抢占路径标记为软抢占并且在它们自 己的预留决定中使用该信息的机会。

下游路径改变消息生成单元230：在实施例中，下游路径改变消息生成 单元230生成消息来向软抢占路径上的一个或多个下游节点通知该路径已 被软抢占。在实施例中，消息仅被直接发送至最接近的下游节点并且被向 上游转发一跳直到该消息到达尾端。

路径错误接收器单元240：在实施例中，路径错误接收器单元240接收 由已抢占路径的节点向上游发送的路径错误消息。响应于接收路径错误消 息，是路径错误消息的接收器的节点（路径错误接收器）将路径标记为正 在被软抢占的过程中，但路径错误接收器继续在与抢占路径相关联的链路 上发送数据直到该路径错误接收器做出了独立判定来软抢占下游链路上的 路径。路径错误接收器随后向路径上的下一个上游节点转发路径错误消息。

下游路径改变消息接收器单元250：在实施例中，下游路径改变消息接 收器单元250接收从上游节点发送至下游节点的、指示上游节点与接收该 路径改变消息的节点（路径改变接收器）之间的路径已被软抢占的路径改 变消息。路径改变接收器将路径标记为在被软抢占的过程中的状态，但可 以继续接收路径上的数据以及在它的出口链路上发送出数据。路径改变接 收器随后向沿被抢占路径的下一个下游节点转发路径改变消息。

软抢占决定单元260：当节点（1）接收请求针对新路径预留带宽的预 留消息，（2）最小要求带宽超过从节点导向下游的任何链路的可用容量以 及（3），新链路的优先级高于来自节点的下游链路上已被抢占的一条或多 条路径时，在实施例中，软抢占决定单元260选定用于软抢占的LSP，从 而腾出链路上的带宽。软抢占决定单元260首先标识已在被软抢占过程中 的状态的LSP，并且在节点内将这些标识的LSP本地标记为被软抢占。如 果抢占已在被抢占过程中的LSP未腾出足够的带宽以适应新的更高优先级 的路径，则其它LSP可以被选定用于软抢占。只有当当前没有LSP处于软 抢占过程中的状态为节点所知时，其它路径才会被考虑用于软抢占。

如果存在具有在链路上预留带宽的多个路径，则可以存在一些不同的 方式来判定哪个路径或哪些路径将被选择用于软抢占。在实施例中，在其 它已被如此标记的路径之前，被标记为已被路径上的其它节点软抢占的某 些路径被选定。选择一条或多条路径用于软抢占可以使用，例如上面标识 的RFC或者其它技术，来被执行；选择路径用于软抢占的特定方法不是关 键性的。

LSP带宽接纳单元270：在实施例中，LSP带宽接纳单元270预留从节 点导向下游的链路上的带宽。当选择LSP用于节点内的本地软抢占时，该 LSP被重接纳为在下游链路上具有零带宽。

在实施例中，组件200中的一个或多个可以被集成进互相联网的元件 的操作系统、控制系统或者其它逻辑或软件元件。例如，在实施例中，被 配置为实现本文描述的功能的逻辑被集成进IOS-XR软件，它可以从Cisco Systems,Inc.,San Jose,California买到。在实施例中，逻辑构成了操作系统、 控制系统或其它逻辑的MPLS流量工程模块的一部分。

3.0向抢占的路径上的节点通知被抢占的带宽

3.1第一示例——一条路径被抢占

图3示出了在包括五（5）个节点的示例性网络上下文中个使用软抢占 来向新的更高优先级路径分配带宽。

图3示出了包括五（5）个节点（表示为A、B、C、D、E）的假定示 例性网络。链路310耦合节点A、B；链路320耦合节点B、C；链路330 耦合节点C、D；链路340耦合节点D、E。诸如“（容量：15）”的数字 注记指示了针对链路的带宽容量的假定单位。从左指向右的实线箭头代表 通过它流量针对路径而流的下游链路。图3中指向左的虚曲线箭头代表向 上游节点递送路径错误消息，而指向右的虚曲线箭头代表向下游节点递送 路径改变消息。值X、Y和Z示出了示例性LSP。

图3示出了示例性路径序列，包括{节点A，链路310，节点B，链路 320，节点C，链路330，节点D，链路340，节点E}。由LSP X和Y代表 的两条路径从节点A流至节点E。LSP标签可以在本文中用作意味着“由 LSP标签代表的路径”的简短表述。因此所有链路310、320、330和340 预留带宽用于LSP X和LSP。然而链路330还针对另外的LSP Z预留了带 宽。此外，从310到340的所有链路的假定容量为15个单位/次。

诸如节点A、B、C、D、E的网络元件可以存储与路径标签相关联的一 个或多个数据表、相关路径所要求的最小带宽以及优先级值。表300是路 径标签、最小带宽和优先级的示例性关联。表300的每行包含关于特定路 径的信息（包括LSP标签、最小带宽要求和优先级值）。

在实施例中，针对路径的最小带宽要求与针对沿该路径的所有链路的 相同。例如，例如，针对LSP Y承载流量的所有链路具有5个单位的带宽 被预留，并且路径的优先级值为5。在实施例中，优先级值越低，则优先级 越高。因此，在表300的所有路径中，优先级值为1的LSP W具有最高优 先级。

出于示出清晰示例的目的，图3示出了具有针对容量和LSP的特定示 例性值的五（5）个节点和四（4）个下游链路。在其它实施例中，可以使 用任何数量的节点和链路。

图4示出了用于向上游节点和下游节点通知路径已被软抢占的方法。 示出在图4中的过程在本文中被参照图3中的示例来描述，特别是从中间 点节点C的视角来描述。图4的过程可以以互补的方式被调整适应位置、 链路容量、与图3的节点和链路中的任何相关联的LSP或者任何其它网络 排布。因此，图4的过程可以被广泛地应用于任意形式的网络排布，并且 不要求图3的特定上下文。

图4中的步骤被响应于头端发送穿过节点A、B、C、D和E、结束于 尾端的路径的信令而被执行。尾端发送路径预留消息用于新被信令的路径。 在步骤400，网络节点接收包含路径标识符、优先级和最小带宽值的路径预 留。例如，在图3中，节点C接收最小带宽为3、优先级值为1的路径预 留消息用于LSP W。

在步骤405，过程判定针对新接收到的路径预留不存在充足的带宽。例 如，节点C判定在链路330（来自节点C的唯一下游链路）上的容量是不 充足的，以在不抢占现有路径的情况下针对LSP W预留3个单位的带宽。 带宽已被在链路330上预留用于要求带宽分别为5、6和4的LPS X、Y和 Z。链路330的容量为15个单位，并且已针对LPS X、Y和Z被预留的总 带宽为15个单位，从而链路330没有空闲空间用于另外的路径。

在步骤420，过程测试相较与现有路径相关联的优先级，新路径是否具 有更高的优先级值。例如，节点C判定相较当前被在链路上预留的LPS X、 Y和Z，LSP W是否具有更高的优先级。如果新链路不具有比链路上现有 路径中的任何都大的优先级，则新路径不能被在链路上预留。然而在该示 例中，LSP W的优先级值为1，分别小于LPS X、Y和Z的优先级值7、5 和2。因此LSP W具有比链路330上当前被预留的所有路径更高的优先级。 节点C可以选择软抢占当前被承载的路径中的任何。在步骤415，节点在 该节点处本地执行软抢占。本地执行软抢占的细节被参照图7在下文描述。 在该示例中，节点C选择软抢占LPS X。在步骤425，节点C测试在被抢 占的路径上是否存在任何上游节点。如果存在，则随后在步骤430，当前节 点向上游节点发送路径错误消息。在该示例中，节点C向上游发送路径错 误消息至节点B。在路径错误消息已被向上游发送之后，在步骤435，预留 消息被转发至上游节点。例如，节点C向节点B转发预留路径消息。在下 一次迭代中，节点B向节点A发送路径错误消息和路径预留消息。

在实施例中，软抢占节点启动定时器来等待（可能在途中的）一个或 多个RSVP预留消息到达，随后执行本文的软抢占过程。在实施例中，上 游节点在处理的路径预留消息之前接收和处理路径错误消息，确保了当决 定针对在路径预留消息中请求的新路径如何分配带宽时，关于被软抢占的 路径的信息对节点是可获得来使用的。以这种方式对消息排序消除了对定 时器的需要。然而在这样的实施例中定时器逻辑可以被使用：消息的顺序 未被保障或者需要附加的时间的情况下网络或供应商设备被使用。

在步骤440，过程测试在被软抢占的路径中是否存在更多下游节点。在 实施例中，如果存在下游节点，则随后在步骤445，路径改变消息被向下游 发送。在下一次迭代中，路径改变消息被从节点D发送到节点E。当路径 上没有更多节点时消息转发停止。当结束时，节点A、B、C、D和E中的 每个已经将LSP X标记为已被软抢占。

因此，在实施例中，通过分别保持追踪每个上游路由器和下游路由器 上的下游节点上处于软抢占未决状态的LSP，TE LSP的数量和网络中被抢 占的带宽的量可以被最小化。实施例可以使用具有指示软抢占正在过程中 的新会话属性标志0x80的RSVP路径消息，来实现本文描述的消息传递。

在实施例中，在头端接收针对新的更高优先级的路径的预留消息之前， 该头端从抢占端点以及每个节点抢占的对应路径的每个集合接收路径错误 消息。这允许头端当试图针对每个对应的被抢占的路径来计算新路径时， 排除抢占节点的列表。头端发送路径改变消息用于新的更高优先级的路径。 因此，针对被软抢占的路径的流量仍可以被在该路径上承载，但先前的有 保障的带宽可以不再被保障。

在实施例中，网络中软抢占的全部数量被最小化，并且成果是网络服 务提供商所希望的：对他们而言抢占能够导致大量信令和流量拥塞。本文 的方法不增加整体软抢占持续时间并且提升网络中的服务质量。本文的方 法可以被轻易在软件中实现。

3.2在节点处本地执行软抢占

图7示出了根据实施例的、在节点内本地执行软抢占的方法。过程开 始于步骤700处，测试来查看是否存在LSP已处于来自或者上游节点或者 下游节点的软抢占正进行的状态，但尚未被在节点内本地软抢占。如果至 少一个LSP处于软抢占的过程中，则随后在步骤710，节点选择这些LSP 中的一个，重接纳选定的LSP为零带宽，并且将选定的LSP标记为被在节 点内本地软抢占。在步骤720，节点测试来判定是否足够的带宽已被释放或 者是否仍需要更多的带宽。如果不需要更多带宽，则过程完成。如果需要 更多带宽，则过程在步骤700处重开始。

如果在步骤700，不存在已处于软抢占正进行的状态、但尚未被在节点 内本地软抢占的LSP，则随后在步骤730，LSP被选定用于之前未被它的路 径上的另外的节点软抢占过的软抢占。节点本地地重接纳选定的LSP为零 带宽，并且将该LSP标记为被本地软抢占。如前所述，在步骤720，节点 测试来查看是否足够的带宽已被释放或者是否仍需要更多的带宽。

3.3第二示例——进行中的软抢占的效率

第二示例示出了对本文描述的软抢占进行中的技术的使用如何减少被 抢占的路径的数量。再次参考图1，在本示例中图1示出的路径由针对该路 径被预留的带宽的数量称呼。例如，具有6个单位的带宽被预留的路径在 本示例中称为LSP6。尽管并未在图1中明确示出，出于示例性目的，链路 103和105没有可用带宽。因此，如果节点A设立需要7个单位的带宽的 新LSP7到节点E，并且新LSP具有比当前被在链路103和105上预留的 路径更高的优先级，则在那些链路上软抢占将是必须的。为了释放7个单 位的带宽，在链路103和105上两条路径将不得不被抢占。在不使用软抢 占进行中消息的情况下，节点D和C独立于彼此地选择哪条路径来抢占。 节点D可以选择当前被预留在链路105上的两条路径（LSP5和LSP6）， 而节点C可以选择被通过链路103承载的路径LSP4和LSP5。其结果是， 三条路径（LSP4、LSP5和LSP6）将被软抢占以与LSP7的接纳相适应。 如果节点C和D能够调整它们对哪条路径被抢占的选择，则节点C和D都 可以选择了LSP5和LSP6。其结果是，将仅有两天路径被抢占而不是三条。

图6示出了在与图3中的示例类似的示例网络上下文中，使用软抢占 向新的更高优先级路径分配带宽。示例示出了节点能够如何与它们的软抢 占选择协调以最小化需要被抢占的路径的数量，例如如图1示出的。

图6示出了包括五（5）个节点（表示为A、B、C、D、E）的另一个 假定示例性网络。链路310耦合节点A、B；链路320耦合节点B、C；链 路330耦合节点C、D；链路340耦合节点D、E。诸如“（容量：15）” 的数字注记指示了针对链路的带宽容量的假定单位。从左指向右的实线箭 头代表通过它流量针对路径而流的下游链路。图6中指向左的虚曲线箭头 代表向上游节点递送路径错误消息，而指向右的虚曲线箭头代表向下游节 点递送路径改变消息。值X、Y和Z示出了示例性LSP。

图6示出了示例性路径序列，包括{节点A，链路310，节点B，链路 320，节点C，链路330，节点D，链路340，节点E}。由LSP X和Y代表 的两条路径从节点A流至节点E。然而链路330还针对另外的LSP Z预留 了带宽。此外，从310到340的每个链路上的预留带宽等于每个链路的假 定容量。链路310、320和340的假定容量为11个单位/次，并且链路330 的假定容量为15个单位/次。

诸如节点A、B、C、D、E的网络元件可以存储与路径标签相关联的一 个或多个数据表、相关路径所要求的最小带宽以及优先级值。表300是路 径标签、最小带宽和优先级的示例性关联。表300的每行包含关于特定路 径的信息（包括LSP标签、最小带宽要求和优先级值）。与图3中示出的 示例类似，在表300的所有路径中，优先级值为1的LSP W具有最高的优 先级。

出于示出清晰示例的目的，图6示出了具有针对容量和LSP的特定示 例性值的五（5）个节点和四（4）个下游链路。在其它实施例中，可以使 用任何数量的节点和链路。

图4示出了用于向上游节点和下游节点通知路径已经被软抢占的方法。 示出在图4中的过程在本文中被参照图6中的示例来描述，特别是从中间 点节点C的视角来描述。图4的过程可以以互补的方式被调整适应位置、 链路容量、与图3的节点和链路中的任何相关联的LSP或者任何其它网络 排布。因此，图4的过程可以被广泛地应用于任何形式的网络排布，并且 不要求图6的特定上下文。

图4中的步骤响应于头端发送穿过节点A、B、C、D和E结束于尾端 的路径的信令而被执行。尾端发送路径预留消息用于新被信令的路径。在 步骤400，网络节点接收包含路径标识符、优先级和最小带宽值的路径预留。 例如，在图6中，节点D接收针对LSP W的、最小带宽为7优先级值为1 的路径预留消息。

在步骤405，过程判定针对新接收到的路径预留不存在充足的带宽。例 如，节点D判定在链路340（来自节点D的唯一下游链路）上的容量是不 充足的，以在不抢占现有路径的情况下针对LSP W预留7个单位的带宽。 带宽已被在链路340上预留用于要求带宽分别为5和6的LPS X、和LPS Y。 链路340的容量为11个单位，并且已被针对LPS X和Y预留的总带宽为 11个单位，从而链路340没有容量来分配另外7个单位的带宽用于LSP W。

在步骤410，过程测试相较与现有路径相关联的优先级，新路径是否具 有更高的优先级值。例如，节点D判定相较当前被在链路上预留的现有路 径，新路径LSP W是否具有更高的优先级。如果新链路不具有比链路上现 有路径中的任何都大的优先级，则新路径不能被在链路上预留。然而在该 示例中，LSP W的优先级值为1，分别小于针对LPS X和LPS Y的优先级 值7和5。因此LSP W具有比链路340上当前被预留的所有路径更高的优 先级。节点D可以选择软抢占当前被承载的路径中的任何。此外，软抢占 预留链路340上的两条路径中的一条将不提供预留LSP W（要求7个单位） 所要求的足够的释放带宽，这意味着节点D软抢占超过一条路径。在步骤 415，节点D执行本地软抢占。本地执行软抢占的细节被参照图7在下文描 述。在该示例中，节点D选择LPS X和LPS Y用于软抢占。

在步骤425，如果在被抢占的路径上存在上游节点，则随后在步骤430， 当前节点向上游节点发送路径错误消息。在该示例中，节点D向上游发送 路径错误消息至节点C。接收路径错误消息向节点C通知LPS X和LPS Y 在软抢占过程中，并且作为响应，节点C在节点内将LPS X和LPS Y本地 标记为正处于软抢占进行中状态。

在路径错误消息已被向上游发送之后，在步骤435，预留消息被转发至 上游节点。例如，节点D向节点C转发预留路径消息。当节点C接收预留 消息时，节点C判定链路330容量已满并且无法在不抢占预留在链路330 上的一条或多条路径的情况下分配另外7个单位的带宽用于LSP W。节点 C可以检查承载在链路330上的路径以判定哪些（如果存在的话）被标记 为被软抢占。在选择未被如此标记的路径之前，节点C可以选择标记为被 软抢占的路径。因此，节点C可以选择LPS X和LPS Y来软抢占，因为 LPS X和LPS Y都标记为被软抢占，并且它们的抢占将提供充足的带宽用 于LSP W。节点C可以不选择LSP Z因为LSP Z尚未被软抢占并且不需要 附加的带宽来针对LSP W在链路330上预留带宽。路径错误消息允许下游 节点通信哪些路径已被软抢占。从而那些路径可以在非抢占路径之前被上 游节点选择。

在下一次迭代中，节点C向节点B发送路径错误消息和路径预留消息， 并且节点B向节点A发送路径错误消息和路径预留消息。

在步骤440，过程测试在被软抢占的路径中是否存在更多下游节点。在 实施例中，如果存在下游节点，则随后在步骤445，路径改变消息被向下游 发送。例如，节点D向节点E发送路径改变消息。当路径上没有更多节点 时消息转发停止。当结束时，节点A、B、C、D和E中的每个已经将LSP X 标记为已被软抢占。因此，通过使用软抢占进行中的消息，沿着路径的节 点可以共享能够导向抢占更少路径的信息。

3.4响应路径错误消息

图8示出了根据实施例的、接收和响应包含对进行中的软抢占的通知 的路径错误消息的方法。在步骤800，节点从下游节点接收路径错误消息。 路径错误消息包含关于处于被下游节点软抢占过程中的一个或多个LSP的 信息。在步骤810，节点将指定的（一个或多个）LSP标记为正处于软抢占 过程中。在步骤820，节点将路径错误消息转发至沿该LSP的路径的上游 节点。只有在路径错误消息已被转发之后，在步骤830，预留消息才被向上 游转发。在步骤830之前执行步骤820允许接收节点在该节点必须做出软 抢占哪些路径以适应预留请求的决定之前，注意到（一个或多个）LSP已 被选定用于软抢占。

3.5响应路径变化消息

图9示出了根据实施例的、接收和响应包含对进行中的软抢占的通知 的路径改变消息的方法。在步骤900，节点从上游节点接收路径改变消息。 路径改变消息包含关于处于被下游节点软抢占过程中的一个或多个LSP的 信息。在步骤910，节点将指定的（一个或多个）LSP标记为正处于软抢占 过程中。在步骤920，节点将路径改变消息转发至沿着该被软抢占的LSP 的路径的下游节点。

在该节点已处理了路径预留消息之后，在抢占路径的节点下游的节点 可以接收路径改变消息。然而，下次节点需要选择路径用于软抢占。选择 先前已被抢占的路径而不是选择先前尚未被抢占的路径仍可以导致较少的 全部抢占。

在实施例中，网络中软抢占的全部数量被最小化，并且成果是网络服 务提供商所希望的：对他们而言抢占能够导致大量信令和流量拥塞。本文 的方法不增加整体软抢占持续时间并且提升网络中的服务质量。本文的方 法可以被轻易在软件中实现。

4.0实现方式机制——硬件概述

图5是示出了在其上实施例可以被实现的计算机网络的框图。优选的 实施例可以使用运行在网络元件（例如路由器设备）上的一个或多个计算 机程序来实现。因此，在该实施例中，计算机系统500是路由器。根据一 个实施例，本文描述的技术由一个或多个特殊用途计算设备来实现。特殊 用途计算设备可以被硬连接以执行技术，或者可以包括被持续编程以执行 技术的数字电子设备（例如一个或多个专用集成电路（ASIC）或现场可编 程门阵列（FPGA）），或者可以包括被编程为依照固件、存储器、其它存 储设备及其组合中的程序质量来执行技术的一个或多个通用硬件处理器。 这样的特殊用途计算设备还可以组合具有自定义的编程来完成技术的自定 义硬接线逻辑、ASIC或FPGA。特殊用途计算设备可以是采用硬接线和/ 或程序逻辑来实现技术的台式计算机系统、便携式计算机系统、手持设备， 联网设备或任何其它设备。

例如，图5是示出了在其上实施例可以被实现的计算机网络的框图。 计算机系统500包括用于传输信息的总线502或其它通信机构，以及与总 线502耦合、用于处理信息的硬件处理器504。例如硬件处理器504可以是 通用微处理器。

计算机系统500还包括主存储器506，例如随机存取存储器（RAM） 或其它动态存储装置，耦合到总线502用于存储将由处理器504执行的信 息和指令。主存储器506还可以用于在由处理器504执行要执行的指令的 期间存储临时变量或其它中间信息。当被存储在可由处理器504访问的非 暂时性存储介质中时，这样的指令将计算机系统500转化（render）成被自 定义为执行在指令中指定的操作的特殊用途机。

计算机系统500还包括耦合到总线502、用于存储针对处理器504的静 态信息和指令的只读存储器（ROM）508或其它静态存储设备。存储设备 510（例如磁盘或光盘）被提供并耦合到总线502用于存储信息和指令。

计算机系统500可以通过总线502被耦合到显示器512（例如阴极射线 管（CRT））用于向计算机用户显示信息。包括字母数字和其它键的输入 设备514被耦合到总线502用于向处理器504传输信息和命令选择。另一 类用户输入设备是光标控制516（例如鼠标、轨迹球或光标方向键）用于向 处理器504传输信息和命令选择以及用于控制显示屏512上的光标移动。 该输入设备通常在两个轴（第一轴（例如x）和第二轴（例如y））上具有 两个自由度，这允许设备指定平面内的位置。

计算机系统500可以使用与计算机系统结合以将计算机系统500变得 或编程为特殊用途机的自定义硬接线逻辑、一个或多个ASIC或FPGA、固 件和/或程序逻辑。根据一个实施例，本发明的技术由计算机系统500响应 于处理器504执行包含在主存储器506中的一个或多个指令的一个或多个 序列来执行。这样的指令可以被从另外的存储介质（例如存储设备510）读 入到主存储器506。对包含在主存储器506中的指令序列的执行使得处理器 504执行本文描述的处理步骤。在替代的实施例中，硬接线电路可用于代替 软件指令或者与软件指令结合使用。

本文所用的术语“存储介质”指存储使得机器以具体方式操作的数据 和/或指令。这样的存储介质可以包括非易失性介质和/或易失性介质。非易 失性介质包括，例如光盘或磁盘（如存储设备510）。易失性介质包括动态 存储器，例如主存储器506。存储介质的常见形式包括，例如软盘、柔性盘、 硬盘、固态驱动器、磁带或任何其它磁性数据存储介质、CD-ROM、任何 其它光学数据存储介质、任何具有孔图案的物理介质、RAM、PROM和 EPROM、FLASH–EPROM、NVRAM、任何其它存储器芯片或盒式磁带。

存储介质与传输介质是有区别的，但可以与传输介质结合使用。传输 介质参与在存储介质之间传递信息。例如，传输介质包括同轴电缆、铜线 和光纤，包括组成总线502的导线。传输介质也可采取声波或光波的形式， 例如在无线电波和红外数据通信期间所产生的声波或光波。

在向处理器504承载一个或多个指令的一个或多个序列用于执行中， 可能涉及各种形式的介质。例如，指令最初可以被承载在远程计算机的磁 盘或固态驱动器上。远程计算机可以加载指令到它的动态成初期，并使用 调制解调器来通过电话线发送指令。对计算机系统500为本地的调制解调 器可以接收电话线路上的数据，并使用红外发射器将数据转换成红外线信 号。红外检测器可以接收承载在红外信号中的数据，并且适当的电路可以 将该数据放置在总线502上。总线502将数据承载到主存储器506，处理器 504从主存储器506检索和执行指令。在由处理器504执行或者之前或者之 后，由主存储器506接收的指令可以被可选地存储在存储设备510上。

计算机系统500还包括耦合到总线502的通信接口518。通信接口518 提供耦合到连接至本地网络522的网络链路520的双向数据通信。例如， 通信接口518可以是提供到相应类型电话线的数据通信连接的综合业务数 字网（ISDN）卡、线缆调制解调器、卫星调制解调器或者调制解调器。作 为另一个示例，通信接口518可以是局域网（LAN）卡，以提供到兼容LAN 的数据通信连接。无线链路也可以被实现。在任何这样的实现方式中，通 信接口518发送和接收承载代表各种类型的信息的数字数据流的电、电磁 或光信号。

网络链路520通常通过一个或多个网络来向其它数据设备提供数据通 信。例如，网络链路520可以通过本地网络522向主机524或由互联网服 务提供商（ISP）526操作的数据仪器提供连接。ISP526通过现在通常被称 为“互联网”528的全球分组数据通信网络来依次提供数据通信服务。本地 网络522和互联网528都使用承载数字数据流的电、电磁或光信号。（承 载来自和去往计算机系统500的数字数据的）通过各种网络的信号以及网 络链路520上通过通信接口518信号是传输介质的示例性形式。

计算机系统500可以经由（一个或多个）网络、网络链路520和518 通信接口来发送消息并接收数据。在互联网的示例中，服务器530可能通 过互联网528、ISP526、本地网络522和通信接口518来传输针对应用程 序的请求代码。

接收到的代码可以在它被接收后就由处理器504执行，和/或存储在存 储设备510或其它非易失性存储设备上用于以后执行。

在上文的说明书中，已经参考可能根据实现方式不同而变化的一些具 体细节描述了本发明的实施例。因此，说明书和附图应被视为说明性的而 非限制性的。本发明范围的唯一和排它的指标，以及申请人对本发明的范 围的意图，是从本申请发布的权利要求的集合的字面范围和等同范围，这 样的权利要求被以该种形式发布的具体形式包括任何后续修改。

5.0扩展和替代

在实施例中，软抢占技术可以被增强，以处置由于多个高优先级路径 被设置在网络中导致的多个软抢占。参考图3中的示例，如果第二高优先 级的路径LSP V被在LSP W被设立后一某段特定时间内设立，则例如节点 E，可以在某一小段时间内接收用于LSP V和LSP W预留消息。节点E可 以存储指示多个新路径被设立的信息。当节点E基于存储的信息来接收路 径消息用于LSP W时，在开始针对LSP W的软抢占过程之前节点E可以 等候直到针对LSP V的路径消息也被接收。因此，响应于设立针对LSP V 和LSP W的路径的组合软抢占可以被同时执行。在针对LSP V和LSP W 的路径预留消息被传播之前，针对所有结果软抢占的路径错误消息可以被 发送至节点D。