一种基于MPLS-TE的流量等级区分式故障恢复方法

摘要

本发明公开了基于MPLS-TE的流量等级区分式故障恢复方法，包括离线处理和在线处理两个阶段；在离线处理阶段，TCD算法在网络初始化阶段建立和维持一份LSP状态信息库，库中含有LSP ID、主路径、备份路径、业务流属性、保持优先级属性、建立优先级属性，用于后续的流量切换和资源抢占；在线处理先后执行两个步骤：流量切换和资源抢占；该算法能够区分不同业务流的不同故障恢复需求，表现出较低的丢包率、较少的故障恢复时间和同时又有较高的资源利用效率，优于传统的故障恢复算法。

说明书

技术领域

本发明涉及一种基于MPLS-TE的流量等级区分式故障恢复方法，属于通信技术领 域。

背景技术

随着网络中数据业务量和用户量的激增，人们对网络的依赖程度日益增大，网络的 可靠性问题日益凸显，网络生存性技术由此应运而生。网络的生存性主要是指网络在节 点、链路失效以后，在不需要人为干预的情况下，能自动恢复受故障影响的业务的能力。 MPLS(Multi-Protocol Label Switching)作为下一代核心网络交换技术，通过标签交换 算法，不仅可以提供比传统IP网络更有效的QoS(Quality of Service)保证和流量工程， 而且具有很强的网络生存性能力。MPLS的保护算法在故障发生以后，可比IP层提供更 快的反应时间。MPLS保护能提供非常灵活的保护流量颗粒度，并且可以选择保护流量的 类型。

MPLS技术的重大突破之一，就是对QoS的支持，即具备可靠而高效转发流量的能 力。尽管目前的路由算法已经相对成熟，但依然无法确保网络故障后恢复时间与性能。 因此，尽管IP路由提供重路由功能，但其恢复时间较长(几秒到几分钟)，对于要求高 可靠性、高实时性的业务，这样的恢复时间显然是不能接受的。此外，对于某些需要QoS 保证的业务，不仅需要在故障后重新建立新路径来传输流量，而且需要有和原传输路径 相当的网络带宽、网络时延、丢包率。而lP路由在实施故障恢复时，却难于保证以上 要求。典型的网络业务如VOIP(Voice over IP)、语音传输、视频传输，而对于这类业 务，IP重路由常常显得力不从心。IP重路由在实施恢复时，路由算法可能收敛时间较 长，将导致较多数据包丢失，而且IP重路由无法确保网络带宽。较之于传统的IP重路 由，作为骨干网的交换技术，MPLS需要对网络故障进行更快速的响应，可以在网络故障 后有着更快的反应时间，更可靠的带宽和时延保证，并以此来提高网络的可靠性。 网络中的任何资源都有可能发生故障，要想提供一个高可靠性的网络，这个网络必须能 够预期并且有效解决这些可能的故障。在实际应用中，链路故障、节点故障或者新旧设 备交替等等都会一个短暂的中断，这个中断当然越小越好，作为下一代网络的热点技术， MPLS能够在几十毫秒级的时间内迅速恢复故障。简单的说，在一个MPLS网络中修复故 障的关键目的就是尽可能的缩短故障引起的网络数据传输中断的时间并且使修复后的 流量参数仍能尽可能的满足网络要求，如果可能的话，建立起来的标记交换路径(可能 正在传输数据)应该能不中断的进行故障恢复。这就意味着链路以及交叉连接的设备应 该不会受到故障的影响，并且丢失的数据较少。为了实现这个目的，人们提出了一些基 于MPLS的故障恢复算法，并有效的解决了网络故障恢复中存在的若干问题，但是其中 还存在一些需要改进的地方。

(1)Makam算法

Makam算法是一种典型的全局保护切换恢复算法，如图1所示。当节点2检测到故 障发生时，它向PSL(Path Switch LSR)发送FIS(Fault Indication Signal)信号， PSL在收到该信号后执行流切换，使用预先配置的备份LSP(Label Switched Path)(入 口-4-5-6-出口)代替工作路径。Makam算法故障恢复实现算法简单，而恢复操作时间相 对较小，因为恢复LSP是预先建立的。但如果发生错误的地方距离入口节点较远时，由 于需要通告FIS信号，该算法的恢复周期中的故障通告时间相对较长，使得在得知切换 前已有许多数据流传送，因而这些已经传送的数据流将会被其他LSR(Label Switch Router)丢弃导致丢包率较高。

(2)Haskin算法

如图2所示。Haskin算法为本地加全局的混合保护切换恢复算法，其恢复路径由 两部分组成：工作路径上故障发生点的上游节点和链路构成的“反向备份路径”，以及 PSL预先配置的另一条与工作路径不相关的“上部备份路径”。由于不使用专门的FIS 信号进行故障通告，而是由反向备份路径上回传的数据包来通知PSL进行流切换，和 Makam算法比较，Haskin算法减少了故障通告时间，并且降低了丢包率。

工作路径为入口-1-2-3-出口，故障发生时，LSR3将数据包沿反向备份路径2-1传 递到PSL，PSL再将流切换到上部备份路径入口-4-5-6-出口上。

(3)Hundessa算法

Lemma Hundessa和Jordi domingo Pascual利用缓存和加标签的方法解决Haskin 方法数据包逆序的问题，该方法被称为Hundessa Approach。该算法是在每一个LSR额 外加上缓存buffer来储存数据包。

当工作路径上的每一个LSR收到反方向的数据包后便将从上游传来的数据流进入 缓存buffer内，然后在往下游传送的最后一个数据包加上标签tag，在此标签从反方向 接收到时，都一直将上游的数据流送缓存里储存起来。直到收到从反方向回来的tag后 便将缓存里的数据流切换到往入口路由方向的备份路径上传送。当入口路由器收到tag 后表示工作路径上的LSR都已经往回传送数据流且都已经由入口路由器切换到备份路径 上了，此时入口路由器便将往工作路径上传送的数据流切换到备份路径上。该方法在每 一个LSR上均增加一个缓存使得LSR的负担加大，成本也增加，而且当缓存出现溢出 overflow时，仍然会产生数据包丢失还有逆序的情况。

(4)Das算法

Das算法是Santos Kummer Das和P.Venkataram针对Makam Approach提出的改进 算法。该算法是与发生故障相邻的LSR临时建立一条备份路径以将数据流转发到出口路 由器。如图3所示，当工作路径发生故障时，则与该故障相邻的下游LSR向出口路由器 传送故障通知消息，当出口路由器收到故障通知消息FIS，便向入口路由器传送故障通 知消息和重路由请求。

而在故障通知消息未到达入口路由器前，与该故障相邻的上游LSR便立即计算一条 到达出口路由器的临时备份路径，然后将入口路由器未收到故障通知消息FIS前所传送 的数据流切换到该临时备份路径上。在入口路由器收到故障通知消息FIS和重路由请求 后便将数据流切换到备份路径上，这样可以将故障通知消息未到达入口路由器前，入口 路由器所传送的数据流通过其临时备份路径继续传送到出口路由器，以避免数据包的丢 失。

(5)Dynamic算法

Dynamic算法采用本地重路由——恢复路径按需建立恢复方式。如图4所示，当链 路(2，3)发生故障时，故障处的邻居上游节点LSR2负责按需计算一条满足带宽需求 的恢复路径2-5-6-出口LSR，然后利用信令协议建立恢复LSP，并执行流切换。如图4 所示，从资源利用率上看，这种恢复算法的恢复LSP是优化的，但是由于需要在故障发 生后按需计算恢复路径，然后还需使用信令协议建立恢复LSP，因此Dynamic算法的恢 复操作时间长，发生故障时丢包率高。

现有的方法存在以下问题：

(1)Makam算法在反向传送FIS的过程中会有大量数据包被LSR丢弃，导致丢包率较 高。Haskin算法增加了故障恢复时间，从而造成较大的时延；备份路径资源耗费严重； 当故障修复好切换回主路径时，存在较严重逆序情况。Hundessa算法中LSR负担重，维 护成本高，可能出现缓存溢出。Das算法中FIS传送路径长Dynamic算法需要在故障发 生后按需计算恢复路径，然后还需使用信令协议建立恢复LSP，因此恢复操作时间长， 发生故障时丢包率高。

(2)在故障发生时，现有的恢复机制并不区分不同的级别和QoS要求，只是利用统 一的策略进行恢复。特别是在网络资源有限时，这些机制很难保证有较高生存性要求的 应用能够得到最快的恢复。

发明内容

为了在网络恢复过程中，区分不同的级别和QoS要求；同时在网络资源不是很充 足时，保证有较高生存性要求的应用能够得到最快的恢复。本发明提出了一种基于MPLS TE的可对流量等级进行区分服务的故障恢复方法(Traffic Classes Differentiated failure recovery algorithm，记为TCD)。该算法在考虑不同应用的不同生存性QoS 要求的同时，还把现有的几种MPLS恢复算法结合起来，适用于考虑生存性QoS环境下 的流量保护与恢复，是一种区分不同生存性QoS要求的保护恢复算法。

该发明所提出的算法结合了现有的Makam算法、Haskin算法的优点，同时引入区分 服务中的带宽抢占机制，将最小化链路中断和带宽放在首位优先考虑，解决了以往故障 恢复算法的故障恢复后高等级业务流带宽服务下降的问题，充分保证了具有高优先级的 数据流能够率先恢复，同时保障了被抢占的数据流能够最大限度的维持其基本QoS需求。 该算法能够区分不同业务流的不同故障恢复需求，表现出较低的丢包率、较少的故障恢 复时间和同时又有较高的资源利用效率，优于传统的故障恢复算法。

1.提出了一种新的可区分不同生存性QoS要求的故障恢复算法。

2.新算法在每个LSR都建立了LSP状态数据库，数据库包含了每条LSP对应的 LSPID、

主路径、备份路径、业务流属性、抢占属性、被抢占属性等信息，用于在故障发 生时及时判断流量属性，从而根据流量属性做出相应的判断。

3.数据库在网络初始化时或者拓扑发生改变时通过网络泛洪建立，在整个MPLS 域内每个LSR都维持一份相同的LSP状态数据库，并随着网络运营商的要求及时更新。

4.为了减轻靠近故障点的最近的上游LSR的负担，新算法将实时性要求较高的业 务的流量切换放在入口LSR处。

5.将对可靠性要求较高的业务的流量的切换放在靠近故障点处的LSR上进行。

6.对于实时性可靠性要求都很高的业务流，新算法采取了二次切换的方法，流量 在故障发生后先切换到反向路径上，待到达边界LSR时再第二次切换到备份路径上，这 样既保证了最大限度的减少数据包的丢失，同时也使得二次切换后的流量延时足够小。

7.新算法应用的新的抢占算法，根据LSP状态数据库中该LSP的建立优先级和保 持优先级的属性，与被抢占的LSP的相关属性进行比较，按照优先级属性较高的业务流 抢占优先级较低的业务流的原则进行抢占，从而同时保证了抢占和被抢占的业务流的 QoS要求。

附图说明

图1为现有技术中Makam算法示意图；

图2为现有技术中Haskin算法示意图；

图3为现有技术中Das算法示意图；

图4为现有技术中Dynamic算法示意图；

图5为本发明的TCD算法主流程图；

图6为本发明的流量切换流程图；

图7为本发明的抢占算法流程图；

图8为KL2网络拓扑

图9为故障中断时间

图10为丢失分组数量

图11为失序分组数量

图12为故障恢复后分组平均延时

图13为Makam算法占用带宽情况

图14为Haskin算法占用带宽情况

图15为TCD算法占用带宽情况。

具体实施方式

以下结合具体实施例，对本发明进行详细说明。

流量等级区分服务的故障恢复算法(Traffic Classes Differentiated failure recovery algorithm，TCD)的基本思想是将不同级别的流予以区分对待，每一种级别 的流对应一种流量切换算法，另外考虑到切换后高级别的业务流可能会降低服务带宽， 低级别的业务流可能会完全被高等级业务所挤占，TCD算法引入新的抢占机制。TCD算 法充分考虑带宽资源和网络性能，将最小化链路中断和带宽浪费放在首位考虑，通过采 取层层逼近的原则提高对抢占带宽的约束程度，将链路中断和带宽浪费降至最低。

TCD算法包括离线处理(也即初始化)和在线处理两个阶段，程序流程图如图5所 示。

在离线处理阶段，TCD算法在网络初始化阶段建立和维持一份LSP状态信息库，库 中含有LSP ID、主路径、备份路径、业务流属性、保持优先级属性、建立优先级属性等 信息，用于后续的流量切换和资源抢占。

在线处理先后执行两个步骤：流量切换和资源抢占。

流量切换阶段完成的工作是：将业务流分为不同的级别，对时延敏感类应用提供低 时延、低丢失率的传输服务，网络以峰值数据速率(Peak Data Rate，PDR)传输用户负 载，以确保其具有最小的传输延时，超过服务等级协定(Service Level Agreement，SLA) 配置最大传输率的数据包被丢弃，此级别的业务流定义为SC0级。对于可靠性要求较高 和实时性要求较高的业务流分别定义为SC1级和SC2级，对于尽力而为的业务流直接进 行第三层路由转发。流量切换流程图如图6所示。

(1)对SC0级业务流的处理步骤如下：

A1：检测到故障后，在离故障点最近的LSR处，对到来的SC0级数据流首先释放标 签。

A2：根据LSP状态数据库的主路径属性，将反向路径放入包头，直接进行第三层转 发；同时向上游发送FIS信息，告知上游入口LSR某处节点已发生故障，需要进行流量 切换，因为FIS是在第二层转发的通知消息，传输速率远大于包的转发速率，因此FIS 信号会先行到达入口LSR处。

A3：入口LSR在接收到FIS信号后，立即停止MPLS层的传输，同时执行以下三件 任务：

4)将后续到达的数据存入缓存。

5)将最后一次发出去的包打上标记r。

6)根据LSP状态数据库中备份路径的信息，向下游发送标签请求，出口LSR返回 标签映射消息后，等待回传的IP包的到来。

A4：回传的IP包到来后，根据标签映射信息，将其执行MPLS层转发，同时检测每 个包是否为最后一个标记为r的包，如果不是，则继续转发；如果是，执行A5。

A5：如果标记为r的包到达，则在缓存中查找标记为r+1的包，如果找不到，则 说明已经丢弃，开始查找标记为r+2的包，以此类推，如果找到对应标记为r+n的包， 执行A6。

A6：开始将以标记为r+n的包为开头的流量切换到备份路径上，数据流进入正常转 发的状态。

(2)对SC1级业务流的处理步骤如下：

B1：检测缓冲区是否已满，如果缓冲区已满，说明其已被其他待转发的流量所占用， 则向上游LSR发送通知消息，在上游LSR处进行转发；如缓冲区未满，则在本地LSR处 进行转发；检测完毕后，数据进入缓冲区。

B2：在LSP状态数据库中查找其备份路径，将主路径中的故障点至入口LSR间的路 径与备份路径合并，作为新的备份路径，向出口LSR发送标签请求。

B3：从出口LSR返回标签映射消息，此时备份路径建立成功。

B4：将流量切换到备份路径上，数据进入正常转发状态。

(3)对SC2级业务流的处理步骤

C1：检测到故障后，向入口LSR发送FIS消息。

C2：入口LSR在接收到反向的FIS信息后，向出口LSR发送标签请求消息。

C3：出口LSR返回标签映射消息，此时备份路径建立成功。

C4：将流量切换到备份路径上，数据进入正常转发状态。

在资源抢占阶段完成的工作是：通过增强链路上节点LSR对LSP的资源控制能力， 使LSR具备管理LSP占用带宽资源的能力，LSR选择一部分优先级较低的LSP，减少它 们的传输速率以适应新LSP的带宽需求。在起始端LSR选择减少速率后，算法将更新LSP 上每个LSR带宽，当网络中存在可用带宽，再恢复LSP的带宽。

[定义1]集合L为保持优先级比p(新LSP的建立优先级)低的所有LSP的集合， 即可能被抢占的LSP的待选集合，其中包含n个元素，分别为LSPl₁、LSPl₂、…、 LSPl_i、…LSPl_n。

L′为可降低带宽的LSP的集合，分别为LSPl′₁、LSPl′₂、…、LSPl′_i、…LSPl′_n。

可降低的比率为Δ％。

[定义2]B为可被抢占的LSP的预留带宽集合，其中包含n个元素，分别为b(l₁)、 b(l₂)、…b(l_i)、…b(l_n)，简记为b(1)、b(2)、…b(i)、…b(n)，其中b(i)表示LSP l_i∈L 的预留带宽。B′也为预留带宽集合，其中包含k个元素，分别为b′(l′₁)、b′(l′₂)、… b′(l′_i)、…b′(l′_k)，简记为b′(1)、b′(2)、…b′(i)、…b′(k)，其中b′(i)表示LSP l′_i∈L′的 预留带宽。

[定义3]r为需要抢占的实际带宽，r＝b-A_bw(l)，其中b为新LSP的需求带宽，A_bw(l) 为链路上的可用带宽。

[定义4]P为优先级集合，其中包含n个元素，分别为p(l₁)、p(l₂)、…p(l_i)、… p(l_n)，简记为p(1)、p(2)、…、p(i)、…、p(n)，其中p(i)表示LSP l_i∈L的优先级。

[定义5]X为所有可降低带宽总和，即，

X＝∑b′(l′_i)×Δ％            (1)

算法充分考虑带宽资源和网络性能，将最小化链路中断和带宽浪费放在首位考虑， 通过采取层层逼近的原则来提高对抢占带宽的约束程度，将链路中断和带宽浪费降到最 低程度。抢占算法流程如图7所示，具体步骤如下：

D1：根据LSP的预留带宽b(i)的值将LSP按带宽递减排列，若带宽相同则按优先级 递减排列；设排列后序列为b(i)(1≤i≤n)。令k＝1，m＝1。

D2：如果需要抢占的实际带宽r不小于第k条链路的预留带宽，即r≥b(k)，则抢占 b(k)，更新r＝r-b(k)，k＝k+1，执行D2；否则，执行D3。

D3：如果r＜b(n)，执行[step4]；否则，执行D7。

D4：如果需要抢占的实际带宽r小于所有可降低的带宽综合X，即r＜X，执行 [step5]。否则，执行D6。

D5：如果需要抢占的实际带宽r大于第m条链路上的可降低的带宽，即 r＞b′(m)×Δ％，则抢占带宽b′(m)×Δ％，令r＝r-b′(m)×Δ％，m＝m+1，更新L′，执行 [step5]；否则，令b′(m)＝b′(m)-r，更新数据，抢占结束。

D6：抢占与b(n)带宽相同优先级最小的LSP，更新数据，抢占结束。

D7：设带宽刚好小于r的LSP(如同时有多个相同带宽的LSP，选择优先级最低的 LSP)为b(j)，如果抢占第j条链路的带宽以后，实际抢占带宽r可以小于所有可降低的 带宽总和X，即r-b(j)＜X，则抢占b(j)，令r＝r-b(j)，执行D5；否则，抢占带宽 刚好大于r的LSP，更新数据，抢占结束。

仿真实验

KL2网络是大型网络中的基本模块，也是研究流量工程的基本网络单元。本发明使 用该拓扑进行仿真实验，分别对Makam算法、Haskin算法和新算法进行故障中断时间、 丢失分组数、失序分组数、故障修复后分组延时和平均占用带宽进行对比研究。

KL2网络拓扑如图8所示，该网络由15个节点，28条双向加权链路组成。其中， 粗边的带宽容量为48Mbps的链路，即图中的2-5、2-3、3-6、3-7、6-11、6-10、10-11、 7-10、14-15，细边为带宽容量为12Mbps的链路，相应的5个源、目的节点对为(S_i，D_i) 即(1，13)、(5，9)、(4，2)、(15，5)、(13，2)。

由程序自动生成200个流，其流的建立时间和带宽由种子随机生成，并且流带宽 在64Kbps、100Kbps、128Kbps和200Kbps中随机选择，每个数据包到达时刻服从泊松 分布。仿真实验共进行20次，每次随机种子都不相同，仿真后对链路上各类型流带宽 比例进行了统计。

实验业务请求均在所有的入出口节点对之间随机产生，SC0级、SC1级、SC2级的业 务流比例各占三分之一，本文在KL2网络拓扑上进行了四组实验：第一组实验比较三种 算法在中断服务时间上对于三种不同等级的业务流的差异；第二组实验比较三种算法在 丢失分组数量上对于三种不同等级的业务流的差异；第三组实验比较三种算法在失序分 组数量上对于三种不同等级的业务流的差异；第四组实验为比较三种算法在故障恢复后 的带宽占用上对于三种不同等级的业务流的差异。

仿真结果分析

1故障中断时间的验证

图9反映了三种算法的故障中断时间。在Makam算法中，三种业务流恢复时间都很 短，因为发现故障后向入口LSR发送FIS通知消息，流量在收到消息后迅速切换，其代 价是在发送FIS的过程会有大量数据包丢失。在Haskin算法中，因为多了一段反向传 输路径，因此标签请求时间会较长，故其中断时间也较长。在新算法中，因为区分对待 不同级别的数据流，SC0级的业务流在故障后丢弃标签，新标签的请求与映射都是在事 先建好的备份路径上的，因此其路径建立时间较短，故中断时间较短，但仍比不上Makam 算法的基于传输层的通知消息快速转发、流量快速切换。

对于SC1级因采用了类似Haskin的算法，故恢复时间较长，对SC2级采用类似Makam 的方法故恢复时间较短，和Makam方法的中断时间基本持平。

2丢失分组和失序分组数量的验证

图10和图11反映了三种算法的丢失分组和失序分组数量。可以看到，在Makam 算法中，因为其在通知消息的时候不理会期间到达的分组的情况，导致在整个标签请求 的过程中包丢失现象较严重，在故障修复好后切换回主路径的过程中，因备份路径都是 预先设置好的，主路径和备份路径的延时情况基本相仿，因此，在故障修复后的切换时， 主路径备份路径上的数据流几乎同时到达，因而失序分组较少。

在Haskin算法中，因为直接在离故障最近LSR处进行切换，因此包的丢失最少， 但因为备份路径要比主路径长的多，因此故障修复后，从备份路径切换回主路径时会有 较多的分组丢失。在TCD算法中，因为SC0级业务流中断后向上游发送FIS故障指示信 息，与此同时，故障点最近处LSR并未将分组丢弃，而是直接反向做第三层转发，当其 到达入口LSR时，正好赶上收到出口LSR的标签映射消息，开始做MPLS转发，因此丢 弃分组很少。失序分组的情况同Makam算法的类似，也使得失序分组很少。SC1级业务 流因为在切换时，采用类似Haskin的方法，数据直接转发，因此包丢失较少，又因为 故障修复后主路径备份路径延时差很多因而失序分组较多。SC2级业务流在切换时采用 类似Makam的方法，丢失分组较多但失序分组都较少。

3故障修复后分组延时的验证

图12反映了故障得到恢复之后的分组平均延时，Makam算法因为在故障恢复后启用 的是事先设置好的备份路径，因此延时能够得到保证，故延时较短。Haskin算法因为其 在实际运行过程是走了两倍的反向路径加上备份路径，因此其延时较长。在TCD算法中， 对于SC0级业务流，在业务流切换后是沿备份路径传输的，因此时延较短，对于SC1级 业务流，因为其基于Haskin模式，流量流经两倍的反向路径和备份路径，因此其延时 较长。对于SC2级业务流，流量切换后直接沿备份路径传输，故其延时也较少。 4分级带宽占用的验证

图13、图14和图15分别是Makam算法、Haskin算法和新算法的带宽占用情况：

从图13中和图14中可以看出，在第6.0秒出现故障后，Makam算法和Haskin算法 经过一段时间的恢复，业务流因为需要和备份路径上的数据流分享带宽，带宽略有下降， 最后都基本维持在7000Kbps这一区间段内，但是对于高等级的业务流来说，恢复后只 剩下7000Kbps左右，因此业务流带宽得不到保证，服务质量下降。

图15表示了SC0级、SC1级、SC2级业务流在TCD算法下的占用带宽情况。可以看 到各个级别的业务流虽略有下降，但是都能报证其基本的流量要求，三种业务流在恢复 后能够继续维持其业务流的平稳传输，流量带宽下降不大，流量的服务质量得到保证。 其中SC1级因为采用类似Haskin的恢复方法，其在故障的恢复过程中备份路径多了一 份反向路径，故其流量中断时间稍长。

应当理解的是，对本领域普通技术人员来说，可以根据上述说明加以改进或变换， 而所有这些改进和变换都应属于本发明所附权利要求的保护范围。