DS-TE网络中新的LSP抢占策略

陈家益， 王文娟， 谢翠萍

(1.广东医学院信息工程学院，广东湛江524023;2.湛江师范学院信息科学与技术学院，广东湛江524048;3.广东医学院 信息工程学院，广东东莞523808)

在区分服务感知的流量工程(DS-TE)网络中，抢占是带宽分配和管理的一个重要策略.当存在可用资源竞争时，具有较高建立优先级的LSP可以从一条给定的链路上抢占具有较低保持优先级的LSP，被抢占的LSP重新路由.抢占可以保证在区分服务的环境中为高优先级的LSP提供可靠的服务，尤其当网络负载很重并且连接请求到达模式未知，或当网络链路或节点发生故障时更加有效.但在LSP抢占过程中，有可能引起级联抢占和重路由问题，所以抢占是一个优化问题，抢占策略至关重要［1］.

1DS-TE网络

DS-TE是以MPLS、DiffServ和约束路由为基础，将MPLS TE技术与DiffServ技术结合起来的流量工程技术.DS-TE同时具有 DiffServ的可扩展性和MPLS TE的端到端有效路由策略，由带宽约束模型(BCM)为不同流量类别指定不同的带宽约束，从而将网络细分为具有端到端区分服务的虚拟网络.DSTE是目前实现端到端服务质量(QoS)保证的较为有效的解决方案［2］.

在DS-TE中基于建立优先级和保持优先级引进抢占机制.进入DS-TE核心网络DiffServ域的同一类型的业务被汇聚成流量中继，然后被映射到一条独立的LSP上.通过一条链路上的流量中继或流量中继组被归类为等级类型(CT)，每个CT及其建立优先级p(0≤p≤7)定义一个流量工程等级(TEClass).DS-TE将从一台边缘路由器到另一台边缘路由器之间的所有流量按照服务类别划分为不同的TE-Class，用多条LSP传输，以TE-Class为服务粒度进行网络资源优化.DS-TE网络模型的最基本要求就是为不同流量工程等级的流量预留独立的带宽资源［3］.

DS-TE网络在链路带宽资源紧张时，允许高建立优先级的LSP对低保持优先级的LSP进行带宽抢占.抢占策略保证在区分服务的环境中，为高优先级的业务提供可靠的QoS，同时优化发生抢占时网络的性能.

2 LSP抢占策略

在稳定的DS-TE网络中增加新业务时，新业务会通过LER被划入某个TE-Class i中，并向LSR提出建立新LSP的请求，新的LSP建立请求会包含两个参数:需求带宽b和建立优先级p.LSP上的每个LSR进行接纳控制操作，检查其外向链路上的未被预留带宽UBi，然后做出选择:当UBi＜b时，拒绝新LSP的建立;当UBi≥b时，判断链路上的空闲带宽Abw是否满足Abw≥b，如果满足则直接建立LSP，否则运行抢占算法，以一定的抢占代价目标函数抢占保持优先级低于p的LSP，需抢占的实际带宽为:r=b－Abw.被抢占的低优先级LSP，将释放其预留带宽并进行重路由，建立新的LSP.链路的未被预留带宽信息将被更新，并通过IGP在网络中广播.

新LSP的建立过程如图1所示.

图1 新LSP建立的过程Fig.1 The process of establishing new LSP

但是抢占同时会带来负面问题:被抢占资源的低优先级LSP需要重路由，可能会发生级联抢占和重路由问题.DS-TE网络中的资源抢占是一个优化问题，以新LSP建立请求参数为已知条件，通过建立抢占代价目标函数，在一定的约束条件下，确定使得目标函数取最小值的LSP.约束条件是:保证高优先级业务的QoS和减少因抢占而产生的级联抢占和重路由.抢占代价目标函数包括3个优化标准［4］:①抢占较低优先级的LSP，避免产生级联抢占和保证高优先级业务的QoS;②抢占最少数目的LSP，减少受影响的业务数量;③最小化抢占带宽，避免带宽浪费以有效利用带宽.目标函数可以根据网络策略包含优化标准的任意一个或几个的组合.如果完全考虑所有的优化标准，目标函数抽象为:

其中，αy(l)表示抢占LSP l的优先级代价;β/b(l)表示抢占LSP l在减少抢占LSP数目方面的代价;γ(b(l)－r)2表示抢占LSP l造成带宽浪费的代价.H(l)表示抢占LSP l的总代价，H(l)越小，表示LSP l越可能被新LSP抢占.

抢占策略的核心是抢占算法，沿着新LSP选择的过载的链路上独立运行，以确定该链路上将被抢占的LSP的集合.其最优化标准包括被抢占LSP的优先级、被抢占LSP的数目和被抢占的带宽.抢占的过程一般是:为每条保持优先级低于新LSP建立优先级p的LSP计算其H值，按照其H值升序排列，抢占H值最小的LSP，直到满足新LSP的所需带宽.

抢占算法最基本的目标是满足新LSP建立的带宽需求，保证高优先级的QoS，并且在实施资源抢占后，尽可能地减少被抢占LSP的级联抢占、重路由.在网络资源有限的情况下，尽可能地充分利用带宽资源，避免带宽浪费［5］.

3 V-PREPT算法

V-PREPT算法综合考虑了抢占代价的3个标准:被抢占LSP的优先级、被抢占LSP的数目和被抢占的带宽，在满足所需带宽r的情况下，通过配置权值α、β和γ，可实现3个优化标准的重要性排序，具有良好的灵活性.V-PREPT 算法［6－7］的基本思想是:首先为链路上每条保持优先级低于p的LSP计算H值;然后根据H值对这些LSP升序排序，若H值相等，以其预留带宽值b(l)升序排序;最后，依次选择具有较小H值的LSP进行抢占，直到有足够带宽满足新LSP的带宽需求r.算法输出被抢占的LSP信息和被抢占的带宽.

V-PREPT算法采用的最优化模型为:

其中，Z*yT表示抢占低优先级LSP的代价，Z*LT表示抢占最少数目LSP的代价，Z*bT表示抢占的总带宽的代价.Z表示最优化变量z(l)的集合，z(l)=1表示l被抢占，z(l)=0表示l不被抢占.

V-PREPT算法对应的数学表达式为:

通过配置权值α、β和γ，可实现3个标准的重要性排序.在满足约束条件:高优先级LSP的带宽需求(即Z*bT≥r)的情况下，确定使得目标函数H(Z)取最小值的集合Z.

尽管V-PREPT算法在多业务过载的网络中具有良好的性能，但存在着一些不足:通过V-PREPT算法模型计算的抢占代价与所需带宽成正比，这是不合理的，更大带宽需求的新LSP的建立并不总是会产生更大的抢占代价;在网络资源有限的情况下，需尽可能地充分利用有限的带宽资源，更应避免带宽浪费，V-PREPT算法在避免带宽浪费方面并没有优势.针对V-PREPT算法的这些不足，本文提出了最优化带宽算法:Optim-Bandwidth抢占算法.

4 Optim-Bandwidth算法

Optim-Bandwidth算法充分考虑了带宽资源，通过采用层次逼近规则提高对带宽抢占的约束程度，在避免抢占带宽浪费方面具有显著的优势.有效地规避了V-PREPT算法的缺陷，能够在保持被抢占的带宽和V-PREPT算法一致的前提下，显著减少被抢占带宽的浪费，从而保证高优先级业务的QoS需求及网络的稳定性.

Optim-Bandwidth算法采取的优化模型为:

对应的数学表达式为:

Optim-Bandwidth算法的基本思想是:

(1)根据新LSP的建立优先级p，将保持优先级低于p的LSP归入备选LSP集合L中;

(2)根据需要抢占的实际带宽:r=b－Abw，将L中的LSP分为两类，划入相应的集合，b(l)＜r类:集合LSet和b(l)≥r类:集合GSet;计算集合 LSet和GSet的LSP数目，分别为m和M.

(3)在集合GSet中找出抢占代价H最小的LSP，将此最小抢占代价标识为Hmin，并将该LSP标识为 LSP lpre.

(4)令n=2，在集合SM中任意选取n条LSP，看能否满足∑b(li)≥r且抢占代价比Hmin更小，若满足则更新Hmin值，清除原预抢占标识，将这n条LSP标识为预抢占;增加选取LSP的条数:n=n+1，再比较，直到选取m(n=m)条LSP;当Hmin相等时，选取令∑b(li)－r更小的那些LSP.

(5)抢占标识为预抢占的LSP.Optim-Bandwidth算法在确定将被抢占的LSP前，将备选LSP集合L中的LSP根据需抢占的实际带宽r划分为两个集合，其中一个集合中任一LSP的带宽都满足:b(l)＜r，另一个集合中任一LSP的带宽都满足:b(l)≥r.然后比较两个集合满足条件∑b(li)≥r的抢占目标函数的最小值Hmin，小者标记为预抢占，若出现Hmin相等，则选取具有较小预留带宽的LSP.

Optim-Bandwidth算法概要描述如下:

随着网络规模的扩大，链路上的LSP数量达到一定的规模时，利用单一固定的抢占代价标准判断时，会遇到重复值的情况，这时的抢占就不是最优化的，而只是一个近似最优化的结果.根据标准的重要程度，在首要标准重复值的范围内使用次重要标准进行判断，得出最优化抢占的结果.Optim-Bandwidth算法的抢占代价目标函数H(l)综合考虑了抢占的优先级代价、抢占在减少抢占LSP数目方面的代价和抢占造成带宽浪费的代价3个标准.通过比较，抢占令目标函数H(l)最小的LSP;当出现Hmin相等时，选取最优化目标为最优化被抢占的带宽，最大限度地减少被抢占带宽的浪费.

5 结束语

DS-TE网络在链路带宽资源紧张时，允许高建立优先级的LSP对低保持优先级的LSP进行带宽抢占.本文提出的新的抢占策略:Optim-Bandwidth算法，它的基本思想是:在满足抢占带宽的前提下，综合考虑3个抢占代价标准，在抢占目标函数值相等时，以最优化被抢占的带宽为优化目标，解决了V-PREPT算法近似最优化的误差问题.特别是在避免由抢占带来的带宽浪费方面，Optim-Bandwidth算法使用的层次逼近规则明显提高了对带宽抢占的约束程度，优化了发生抢占时的网络性能.研究的下一步工作，是研究如何在DS-TE网络中实现Optim-Bandwidth抢占算法与路由算法的有机结合.

［1］BLANCHY F，MELON L，LEDUC G.Routing in MPLS Networking Featuring Preemption Mechanisms［J］.Proceedings of the ICT 2003，2003:253 －260.

［2］FAUCHEUR F L，LAI W.Requirements for Support of Differentiated Servive-aware MPLS Traffic Engineering［S］.IETF RFC 3564，July 2003.

［3］FAUCHEUR F L.Russian Dolls Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering［S］.IETF RFC 4127，June 2005.

［4］de OLIVEIRA J，WASSEUR J P，CHEN L，et al.Label Switched Path(LSP)Preemption Policies for MPLS Traffic Engineering［S］.RFC 4829，April 2007.

［5］YU Ke，ZHANG Lin，ZHANG Hui-min.A Preemption-aware Path Selection Algorithm for DiffServ/MPLS Networks［J］.Proceedings of IEEE IPOM 2004，Otc.2004.

［6］OLIVEIRA J C，SCOGLIO C，AKYILDIZ I F，et al.A New Preemption Policy for DiffServ-aware Traffic Engineering to Minimize Rerouting［J］.Proceedings of IEEE INFOCOM 2002，2002(2):23－27.

［7］OLIVEIRA J C，SCOGLIO C，AKYILDIZ I F，et al.New Preemption Policies for DiffServ-aware Traffic Engineering to Minimize Rerouting in MPLS Network［J］.IEEE/ACM Transactions on Networking，2004，12(4):733－745.