DS-TE环境下LSP抢占算法

徐 蕾，于银辉，李金明，王君竹

(1.中国移动通信集团吉林有限公司网管中心，长春130033;2.吉林大学通信工程学院，长春130012;3.长春理工大学电子信息工程学院，长春130022)

0 引言

针对带宽预留和管理问题，使资源抢占策略在DS-TE网络环境中成为一个重要的策略。当新的LSP(Label Switching Path)建立请求到达时，若申请宽带大于链路中的未预留带宽，则会发生抢占。Oliveira等［1］根据抢占LSP的3个主要因素，即抢占的LSP带宽总值、优先级和数量，提出了V-PREPT(Versatile Preemption)抢占算法。

由于V-PREPT算法优先考虑最小化抢占总代价，但带宽利用率不高，为避免带宽浪费［2］，笔者提出了一种对V-PREPT的改进算法，即BH-PREPT(Bandwidth Preemption)算法。该算法的优化模型及数学表达式能较准确地计算因减少抢占LSP数目及抢占LSP所造成的带宽浪费所付出的代价。

1 算法模型

V-PREPT算法允许ISP(Internet Service Provider)根据网络的实际需求对权值α、β和γ进行配置［3］，最终达到理想的优化目的，因此，具有良好的灵活性和多项式的时间复杂度，实时性良好。但同时也存在一些不足:对抢占LSP造成的带宽浪费进行判断并不准确，算法的数学表达式需要修正。笔者提出的BH-PREPT算法在最小化抢占总代价［4］的条件下将减少由抢占带来的带宽浪费的优化标准置于首位，通过使用枚举法［5］寻找总抢占代价最小的被抢占的LSP集合。图1为BH-PREPT算法流程图［6］。

图1 BH-PREPT算法流程图Fig.1 BH-PREPT algorithm flow chart

算法步骤如下:

1)p={p(1)，…，p(l)，…，p(n)}，为集合L中LSP的优先级集合［7］。将链路上每条保持优先级低于p(新LSP的建立优先级)的LSP放入可被抢占的LSP的集合L中，对每个LSP中的ll∈L，根据公式

计算其抢占代价［8］。其中α、β和γ是设置的3个权值，r为建立新LSP时的需求带宽。r=b-Abw(l)［9］，其中b为LSP中预留带宽集合，Abw(l)为链路LSPll上的可用带宽。依据值的大小，将对应的LSP进行降序排列。比较b(l)与r的大小，将集合L中的LSP进行分组:b(l)≥r的集合L1和b(l)＜r的集合L2，y={y(1)，…，y(l)，…，y(n)}，为集合L中LSP的优先级代价集合，计算时，通常取y(l)=8-p(l)［10］。

2)在集合L1中寻找出代价最小的抢占LSP，最小的抢占代价为Hmin_L1，对此LSP进行标记。

3)在集合L2中，在满足被抢占的带宽总和大于需求带宽Bpreempt≥r的约束条件下，确定所需要抢占的LSP的最小数目m。在集合L2中选取任意m条LSP进行组合，在满足Bpreempt≥r约束条件的组合中，找出具有最小抢占总代价的组合，将其抢占代价标记为Hmin_L21。若Hmin_L1＞Hmin_L21，则清除原有标记，对这m条LSP的组合进行标记，并将最终抢占总代价的值赋为Hmin_L21，抢占带有标记的LSP，退出算法。否则，判断Hmin_L1与Hmin_L21是否相等，若相等，则分别计算被标记LSP与m条LSP组合的(∑b(l)-r)值，取(∑b(l)-r)值较小的一方进行抢占。若Hmin_L1与Hmin_L21不等，在集合L2中任意选取n条(n从m开始逐条增加，直到选取(N-M)条(m≤n≤(N-M))LSP进行组合，选取具有最小抢占代价［11］LSP的组合，将其抢占代价标记为Hmin_L22。

4)若Hmin_L1＜Hmin_L21，则抢占集合L1中被标记的LSP，退出算法;否则，判断Hmin_L1与Hmin_L22是否相等，若两者相等，则分别计算被标记LSP与n条LSP组合的(∑b(l)-r)值，选取(∑b(l)-r)［12］值较小的一方进行抢占。若Hmin_L1与Hmin_L22不等，则清除原有标记，对这n条LSP的组合进行标记，并将最终抢占总代价的值赋为Hmin_L22，抢占带有标记的LSP。

2 算法仿真

目标函数的优化标准如下［13］:

1)抢占带宽达到最小化，避免带宽的浪费;

2)抢占优先级较低的LSP，以避免级联抢占;

3)使抢占LSP的数目最少，以降低受影响的业务数量。

下面将建立仿真环境，利用Matlab仿真软件对V-PREPT算法和BH-PREPT算法进行仿真，并比较其在各种环境下的性能。

为使仿真环境更接近大型网络里业务流的分布，假设一个网络，链路上存在100条LSP，并且这100条LSP满足如下条件:其占用的带宽为1～100 Mbit/s的高斯分布［14］，而其保持优先级p为1～7的随机分布。

实验1 全方位考虑优化标准

图2 α=β=γ=1时两种算法的性能比较Fig.2 Comparison between V-PREPT and BH-PREPT when α=β=γ=1

如果网络运营商全面考虑3种优化标准［15］，当3者的权值相等时，仿真时选取 α=β=γ=1。对V-PREPT算法和BH-PREPT算法的性能比较如图2所示。由图2可得出，V-PREPT算法增长幅度大于BH-PREPT算法的增长幅度。V-PREPT算法完全依据各LSP的抢占总代价实施抢占，并没有详细考虑被抢占的LSP的优先级代价以及被抢占的LSP的数目和抢占造成的带宽浪费等优化标准。当 r增加时，BH-PREPT算法的抢占代价比V-PREPT算法上升的幅度更加舒缓，相对于V-PREPT算法总体性能更好。

实验2 主要考虑标准1)和3)

当网络运营商最关心抢占引起的带宽浪费以及抢占LSP的总数目时，在仿真中取α=0，β=γ=1(见图3)。从图3中可得，在r较小(θ≤r≤100 Mbit/s)的情况下，V-PREPT算法和BH-PREPT算法的性能大致相同;但当r逐渐增大时，BH-PREPT算法比V-PREPT算法性能更好，因为BH-PREPT算法避免了带宽浪费，并且与V-PREPT算法相比，其在抢占LSP的数目方面的性能更为优秀。V-PREPT算法并没有采取相应的措施避免抢占所造成的带宽浪费以及减少抢占LSP的数目。因此，当网络运营商最关心抢占引起的带宽浪费和被抢占的LSP的规模时，执行V-PREPT算法的抢占总代价高于BH-PREPT算法。

实验3 主要考虑标准1)和2)

当网络运营商最看重被抢占的LSP的优先级和抢占造成的带宽浪费时，在仿真中取β=0，α=γ=1(见图4)。从图4可看出，V-PREPT算法只关注最小化抢占代价，因此，当网络运营商需要减少抢占引起的带宽浪费、降低被抢占LSP的优先级代价时，BH-PREPT算法的性能优于V-PREPT算法。

图3 α=0，β=γ=1时两种算法的性能比较Fig.3 Comparison between V-PREPT and BH-PREPT when α =0，β = γ =1

图4 β=0，α=γ=1时两种算法的性能比较Fig.4 Comparison between V-PREPT and BH-PREPT when β =0，α = γ =1

3 结语

BH-PREPT算法将减少由抢占造成的带宽浪费这一优化标准放在首位进行优化，在保证被抢占的总带宽满足新LSP建立的需求带宽的前提下，通过采取枚举法找出抢占总代价最小的LSP组合，并且优先选择抢占LSP数目最少的组合实施抢占。从仿真结果可看出，与V-PREPT算法相比较，BH-PREPT算法的带宽利用方面的性能较为突出，计算量较大，硬件实现有一定的难度。

［1］OLIVEIRA J C DE，SCOGLIO C.A New Preemption Policy for DiffServ-Aware Traffic Engineering to Minimize Rerouting［C］∥Proceeding of IEEE INFOCOM 2002.［S.l.］:IEEE Communications Society Press，2002:695-704.

［2］IOANNIS TOMKOS，LEONID KAZOVSKY，KEN-ICHI KITAYAMA.Next-Generation Optical Access Networks:Dynamic Bandwidth Allocation，Resource Use Optimition，and QoS Improvements［J］.IEEE Network，2012，26(2):4-6.

［3］LE FAUCHEUR F，LAI W.RFC 3564.Requirements for Support of Differentiated Services-Aware MPLS Traffic Engineering［S/OL］.IETF，2003［2013-01］.http:www.ietf.org/rfc/rfc3564.txt.

［4］MCNANUS J.IETF RFC 2702.Requirements for Traffic Engineering over MPLS［S/OL］.1999［2013-01］.http:www.hjp.at/doc/rcf/rcf2702.txt.

［5］OLIVEIRA J D E，VASSEUR J P，CHEN L，et al.IETF RFC 4829.Label Switched Path(LSP)Preemption Policies for MPLS Traffic Engineering［S/OL］.2007［2013-01］.http://tools.ietf.org/thml/rcf4829.

［6］张育峰.基于MPLS的QoS机制研究及其实现［D］.杭州:浙江大学信息科学与工程学院，2008.ZHANG Yu-feng.Based on the MPLS QoS Mechanism Research and Implementation［D］.Hangzhou:College of Information Science and Engineering，Zhengjiang University，2008.

［7］ZHU Ming-ying，XING Yu，HU Jun-jun，et al.A New Preemption Policy for Minimizing Path Preemption Cost in MPLS Networks［C］∥IEEE，2010 6th International Conference on.Guangzhou:China Telecom Corp Ltd，2010:1-4.

［8］何晓明，唐宏，叶梧.MPLS流量工程中的最小化抢占路径选择方法［J］.北京邮电大学学报，2009，32(1):19-23.HE Xiao-ming，TANG Hong，YE Wu.A Method of Path Selection for MPLS Traffic Engineering to Minimize Preemption［J］.Journal of Beijing University of Posts and Telecommunications，2009，32(1):19-23.

［9］朱明英，叶梧，冯穗力.MPLS网络中支持Diffserv流量工程的抢占算法［J］.华南理工大学学报:自然科学版，2008，36(8):55-58.ZHU Ming-ying，YE Wu，FENG Hui-li.Preemption Algorithm for Diffserv-Aware Traffic Engineering in MPLS Network［J］.Journal of South China University of Technology:Natural Science Edition，2008，36(8):55-58.

［10］LAU CHUN HAU，SONG BOON-HEE.Preemption Algorithm with Re-Routing to Minimize Service Disruption［C］∥IEEE Communication Systems.2004:521-525［2013-04］.http:∥ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true＆queryText=Preemption+Algorithm+with+Re-Routing+to+Minimize+Service+Disruption＆x=62＆y=11.

［11］徐蕾，于银辉.DS-TE网络环境抢占算法的研究［J］.吉林大学学报:信息科学版，2011，29(3):202-206.XU Lei，YU Yin-hui.Preemption Algorithm for DS-TE Network［J］.Journal of Jilin University:Information Science Edition，2011，29(3):202-206.

［12］ZHU Ming-ying，YE Wu.An Improved Adaptive Preemption Policy in MPLS Networks［C］∥WiCOM’08.4th International Conference.Guangzhou，China:［s.n.］，2008:1-4.

［13］IFTEKHAR AHMAD，JOARDER KAMRUZZAMAN.Revenue Aware Preemption Policy in Multimedia Communication Networks［C］∥Multimedia and Expo，2005.IEEE International Conference.［S.l.］:IEEE Communications Society Press，2005:1374-1377.

［14］朱明英，叶梧，冯穗力.MPLS网络中的自适应接入抢占策略［J］.电路与系统学报，2010，15(3):81-85.ZHU Ming-ying，YE Wu，FENG Hui-li.An Adaptive Preemption Policy of Access Control in MPLS Network［J］.Journal of Circuits Systems，2010，15(3):81-85.

［15］杜荔，李海涛.DS-TE网络中自适应抢占算法研究［J］.东北大学学报:自然科学版，2010，34(2):178-180.DU Li，LI Hai-tao.On the Adaptive Preemption Algorithm in DS-TE Networks ［J］.Journal of Northeastem University:Natural Science，2010，34(2):178-180.