基于DS-TE技术的VPN的LSP抢占算法

陈登昭，于银辉，黄金海，李金明

(吉林大学通信工程学院，长春130012)

基于DS-TE技术的VPN的LSP抢占算法

陈登昭，于银辉，黄金海，李金明

(吉林大学通信工程学院，长春130012)

针对BH-PREPT(Bandwidth Preemption)算法因只关心最小化带宽浪费，而不考虑计算复杂度和当前光纤通信的带宽资源而引起的网络时延极大增加的问题，提出了改进算法-DH-PREPT(Delay and Bandwidth Preemption)。将用户业务的优先级和网络时延放在首位，通过采用多个LSP(Label Switching Paths)绑定转发等价类和快速转发客户常用优先级业务的方法提高算法的时延性能。实验结果表明，该算法在保证带宽利用率的前提下，极大地减少了网络中的时延。当网络中发生抢占时，该算法在减少网络时延方面的性能优于BH-PREPT算法，提高了网络的QoS(Quality of Service)保障能力。

区分服务;流量工程;抢占算法;标签交换路径

0 引 言

DS-TE(Differentiated Services-Aware Traffic Engineering)技术是区分服务模型与流量工程技术的融合［1-5］，是MPLS(Multi-Protocol Label Switching)网络中重要的QoS(Quality of Service)保障技术。MPLS是下一代网络中核心网的重要技术，可为企业用户提供较高服务质量的各种应用业务，MPLS VPN(Virtual Private Network)就是其中一种安全性高、稳定性好的应用［6-8］。

在DS-TE网络中，LSP(Label Switching Paths)抢占策略是带宽预留和管理问题的重要策略。抢占过程主要有3个因素［9］:带宽、优先级和数量。在文献［3］中BH-PREPT(Bandwidth Preemption)算法在节省网络带宽资源方面有较好的性能，但过多地关注了由于抢占LSP造成带宽浪费的代价，所以，笔者提出改进的BH-PREPT算法，即DH-PREPT(Delay and Bandwidth Preemption)算法。该算法能兼顾避免级联抢占［10］和抢占优先级代价最小，从而改善网络时延指标的特点。

1 算法模型

BH-PREPT算法优先考虑最小化由抢占所带来的带宽浪费;将可被抢占的LSP集合按照预留带宽大小分为两组，分别列举出所有可能被抢占的LSP的组合，在其中寻找抢占总代价最小的组合作为算法输出，优先选择LSP数目最少的组合进行抢占。其抢占公式为其中α、β和γ是设置的3个权值，αy(l)表示抢占LSP ll的优先级代价，l表示集合L中的第l个元素LSPl;L是LSP的集合，表示抢占LSP ll在减少抢占LSP数目方面的代价，γ(b(l)-r)表示抢占LSP ll造成带宽浪费的代价;H(l)表示抢占LSP ll需要付出的总代价，H(l)越小，LSP ll被新LSP抢占的可能性越大。

BH-PREPT算法在避免级联抢占和带宽利用率方面有较好的性能，但由于该算法采用枚举法，将减少由抢占带来的带宽浪费的优化标准置于首位，列举所有可能被抢占LSP的集合，在其中寻找抢占总代价最小的LSP组合作为算法输出，在每种情况下都优先选择数目最少的LSP组合实施抢占。在枚举过程中，为了找出组合中的最优解，对比次数增多，由此也带来了计算复杂度和时延的增加，同时，提高了对设备芯片和存储要求。

图1 DH-PREPT算法流程图Fig.1 Flow chart of the DH-PREPT algorithm

随着用户通信中的信息量呈爆发式增长，光纤通信得到普及，带宽资源已经不成问题;然而，通信公司各部门的通信时延却没有呈现相应减小。现在，很多公司希望他们对快速变化的行情做出最快反应，以便获取最大的利润或将损失降到最低。基于新时代的计算机网络通信的新特征，笔者认为抢占原则应根据市场导向做出相应的变化，在关注带宽浪费的同时还要关注算法在网络应用的时延性能。所以提出DH-PREPT算法。其算法流程图如图1所示。

图1中r为建立新的LSP所需要的带宽，Bprempt为实际抢占的带宽，Plh是VPN(Virtual Private Network)用户常用业务类型的优先级，L为保持优先级低于Plh(新LSP的建立优先级)的所有LSP的集合，b(l)为集合L中所有LSP的预留带宽集合b中的第l个元素，P为集合L中所有LSP的保持优先级集合，H是抢占LSP时总的代价，计算公式如下

DH-PREPT算法流程描述如下。

1)通信链路中出现新的可用于实际抢占的带宽Bprempt出现时，正在绑定转发等价类和LSP的标签边缘路由需考虑新Bprempt的使用。

2)判断队列前端的转发等价类的优先级P是否与用户的常用业务类型的优先级Plh相同，若相同，执行3);否则，执行4)。

3)判断实际抢占带宽是否大于新的LSP带宽，如果满足条件，则建立新的LSP，并绑定转发等价类与分组;否则，执行4)。

4)将链路上每条保持优先级低于Plh(新LSP的建立优先级)的LSP放入可被抢占的LSP集合L中。

5)依据H值的大小，将对应的LSP进行降序排列。

6)按照降序的 H顺序对预留带宽 b(l)与新的LSP带宽 r进行比较，若b(l)＞r，执行7);否则，执行8)。

7)如果满足b(l)＞r条件，立刻抢占与b(l)相对应的LSP。

8)将LSP归入可被抢占集合L1中。

9)判断集合L1中的LSP预留带宽之和是否大于r，若满足条件，则立刻抢占LSP组合;否则，执行6)。

10)退出算法。

2 仿真结果

DH-PREPT算法相对于BH-PREPT算法的主要区别是对用户VPN通信时延指标的改进。操作系统选择Windows XP系统，仿真软件选择OPNET 14.5版本，辅助软件是VC++6.0。在仿真结果中主要提取时延(delay)和用户之间的响应时间(response time)两个参数进行比较分析。节点模型如图2所示，RSVP(Resource Reservation Protocol)进程说明如图3所示。

图2 节点模型图Fig.2 Diagram of nodemodel

图3 资源预留协议进程说明Fig.3 Description of resource reservation protocol process

为了验证两种算法在MPLSVPN应用中的性能差异，选择了两个场景，对路由的LSP抢占加入了BH-PREPT和DH-PREPT两种算法，分别对同一网络拓扑的两个通信网络进行仿真。仿真时间设置为1 000 s，种子数量为128个，静态值设置为100。两个通信网络中随机产生3种数据流，分别是voice (语音)、http和ftp，同时设定其主要通信业务为语音业务，在路由的加权排队机制中将语音数据的优先级设为最高。两种场景都采用DS-TE技术，最后在结果中提取不同业务流的实验图像进行比较。

1)语音业务(Voice)。语音业务的实验图像如图4、图5所示。

图4 DH-PREPT算法voice时延图 Fig.4 The chart of voice delay based on DH-PREPT algorithm

图5 BH-PREPT算法voice时延图Fig.5 The chart of voice delay based on BH-PREPT algorithm

在语音业务测试中，由于语音业务的优先级较高，两种算法下网络的时延性能差异不大，但DH-PREPT算法的时效性仍比BH-PREPT算法有一定改善。DH-PREPT算法使网络中的语音业务时延基本控制在0.14 s以内，而BH-PREPT算法则有一部分语音数据的延迟超过0.14 s。仿真结果说明，改进的DH-PREPT算法在减少通信时延方面有较好的性能。

2)http业务。http业务的实验图像如图6、图7所示。

图6 DH-PREPT算法http响应时间图Fig.6 The chart of http response time based on DH-PREPT algorithm

图7 BH-PREPT算法http响应时间图Fig.7 The chart of http response time based on BH-PREPT algorithm

由于在优先级方面http的级别低于voice，所以http文件数据在路由中的排队量较大，当使用DH-PREPT算法时ftp文件的传输的响应时间比BH-PREPT的时间短很多。DH-PREPT算法主要分布在0.4 s以内，BH-PREPT算法有一半的数据的页面响应时间已经超过了0.4 s。

3)ftp业务。ftp业务的实验图像如图8、图9所示。

图8 DH-PREPT算法ftp响应时间图Fig.8 The chart of ftp response time based on DH-PREPT algorithm

图9 BH-PREPT算法ftp响应时间图Fig.9 The chart of ftp response time based on BH-PREPT algorithm

同样的原因，当两家分公司使用ftp通信业务时，由图8，图9可看出，两种算法对ftp文件的转发效果明显不同，由于在优先级方面ftp的级别低于voice，所以ftp文件数据在路由中的排队量较大，当使用DH-PREPT算法时，ftp文件的传输响应时间比BH-PREPT的时间短很多。

3 结 语

笔者提出了改进的BH-PREPT算法，即DH-PREPT算法。该算法兼顾避免级联抢占和抢占优先级代价最小，在通信网络性能方面主要体现在VPN用户主要业务的时延有所减少。根据当前VPN业务对通信网络性能的需求对总代价计算公式H(l)进行了修正，并使用OPNET仿真了两种算法的通信场景，对实验结果进行了对比和分析。结果表明，新算法在减少通信时延方面有较好的性能。

［1］MICHAELMENTH，BOB BRISCOE，TINA TSOU.Precongestion Notification:New QoSSupport for Differentiated Services IP Networks［J］.IEEE Communication Magazine，2012，50(3):94-103.

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

［3］徐蕾，于银辉，李金明，等.DS-TE环境下LSP抢占算法［J］.吉林大学学报:信息科学版，2013，31(3):223-227. XU Lei，YU Yinhui，LI Jinming，et al.New Preempting Algorithm of LSP for DS-TE Networks［J］.Journal of JilinUniversity:Information Science Edition，2013，31(3):223-227.

［4］陈家益，王文娟，谢翠萍.DS-TE网络中新的LSP抢占策略［J］.暨南大学学报:自然科学版，2013，34(1):31-34. CHEN Jiayi，WANGWenjuan，XIE Cuiping.The New LSP Preemption Strategy for DS-TE Networks［J］.Journal of Jinan University:Natural Science，2013，34(1):31-34.

［5］徐蕾，于银辉，董小刚，等.DS-TE网络环境中抢占算法的研究［J］.吉林大学学报:信息科学版，2011，29(3):202-206. XU Lei，YU Yinhui，DONG Xiaogang，et al.Preempting Algorithm for DS-TE Networks［J］.Journal of Jilin University: Information Science Edition，2011，29(3):202-206.

［6］邵海霞，刘炯，李智勇，等.DS-TE网络中改进的LSP抢占算法［J］.计算机工程，2011，37(18):106-108. SHAO Haixia，LIU Jiong，LI Zhiyong，et al.Improved LSP Preemption Algorithm for DS-TE Networks［J］.Computer Engineering，2011，37(18):106-108.

［7］ZHU Mingying，XING Yu，HU Junjun.A New Preemption Policy for Minimizing Path Preemption Cost in MPLSNetworks［C］∥Wireless Communications Networking and Mobile Computing，2010 6th International Conference on Guangzhou Res Inst China Telecom Corp Ltd.Guangzhou，China:［s.n.］，2010:1-4.

［8］朱明英，叶梧，冯穗力，等.MPLS网络中的自适应接入抢占策略［J］.电路与系统学报，2010，15(3):81-85. ZHU Mingying，YEWu，FENG Suili，et al.An Adaptive Preemption Policy of Access Control in MPLS Networks［J］. Journal of Circuits and Systems，2010，15(3):81-85.

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

［10］张育峰.基于MPLS的QoS机制研究及其实现［D］.杭州:浙江大学信息科学与工程学院，2008. ZHANG Yufeng.Investigation and Implementation of QoSMechanism Based on MPLS［D］.Hangzhou:School of Infonmation Science and Engineering，Zhejiang University，2008.

(责任编辑:张洁)

Preempting Algorithm of LSP in VPN Based on DS-TE

CHEN Dengzhao，YU Yinhui，HUANG Jinhai，LIJinming

(College of Communication Engineering，Jilin University，Changchun 130012，China)

The BH-PREPT(Bandwidth Preemption)algorithm only concerns with minimizing the waste of bandwidth without considering the computational complexity and the current development of optical fiber communication，leading to excessive increase of delay in the networks.An algorithm greatly reducing the delay of the networks，named DH-PREPT(Delay and Bandwidth Preemption)is proposed.The DH-PREPT algorithm makes the computational complexity lower under the premise ofminimizing the utilization rate of bandwidth.It considers the delay indicator by the bound of forwarding equivalence class and LSPs(Label Switching Paths)and fast forward the data of custom.Simulation results show that the proposed algorithm significantly outperforms the BH-PREPT algorithm when preemption occurs in the network.

differentiated services;traffic engineering;preemption algorithm;label switching path

TN914

A

1671-5896(2015)06-0615-05

2014-06-25

长春市重大科技攻关计划基金资助项目(3D5143485420)

陈登昭(1991— )，男，湖南永州人，吉林大学硕士研究生，主要从事宽带网络研究，(Tel)86-15143082364(E-mail)dengzchen@163.com;于银辉(1964— )，女，山东泰安人，吉林大学教授，主要从事宽带通信及流量工程研究，(Tel)86-13604319589(E-mail)yuyh@jlu.edu.cn。