陳登昭，于銀輝，黃金海，李金明

(吉林大學(xué)通信工程學(xué)院，長(zhǎng)春130012)

基于DS-TE技術(shù)的VPN的LSP搶占算法

陳登昭，于銀輝，黃金海，李金明

(吉林大學(xué)通信工程學(xué)院，長(zhǎng)春130012)

針對(duì)BH-PREPT(Bandwidth Preemption)算法因只關(guān)心最小化帶寬浪費(fèi)，而不考慮計(jì)算復(fù)雜度和當(dāng)前光纖通信的帶寬資源而引起的網(wǎng)絡(luò)時(shí)延極大增加的問題，提出了改進(jìn)算法-DH-PREPT(Delay and Bandwidth Preemption)。將用戶業(yè)務(wù)的優(yōu)先級(jí)和網(wǎng)絡(luò)時(shí)延放在首位，通過采用多個(gè)LSP(Label Switching Paths)綁定轉(zhuǎn)發(fā)等價(jià)類和快速轉(zhuǎn)發(fā)客戶常用優(yōu)先級(jí)業(yè)務(wù)的方法提高算法的時(shí)延性能。實(shí)驗(yàn)結(jié)果表明，該算法在保證帶寬利用率的前提下，極大地減少了網(wǎng)絡(luò)中的時(shí)延。當(dāng)網(wǎng)絡(luò)中發(fā)生搶占時(shí)，該算法在減少網(wǎng)絡(luò)時(shí)延方面的性能優(yōu)于BH-PREPT算法，提高了網(wǎng)絡(luò)的QoS(Quality of Service)保障能力。

區(qū)分服務(wù);流量工程;搶占算法;標(biāo)簽交換路徑

0 引 言

DS-TE(Differentiated Services-Aware Traffic Engineering)技術(shù)是區(qū)分服務(wù)模型與流量工程技術(shù)的融合［1-5］，是MPLS(Multi-Protocol Label Switching)網(wǎng)絡(luò)中重要的QoS(Quality of Service)保障技術(shù)。MPLS是下一代網(wǎng)絡(luò)中核心網(wǎng)的重要技術(shù)，可為企業(yè)用戶提供較高服務(wù)質(zhì)量的各種應(yīng)用業(yè)務(wù)，MPLS VPN(Virtual Private Network)就是其中一種安全性高、穩(wěn)定性好的應(yīng)用［6-8］。

在DS-TE網(wǎng)絡(luò)中，LSP(Label Switching Paths)搶占策略是帶寬預(yù)留和管理問題的重要策略。搶占過程主要有3個(gè)因素［9］:帶寬、優(yōu)先級(jí)和數(shù)量。在文獻(xiàn)［3］中BH-PREPT(Bandwidth Preemption)算法在節(jié)省網(wǎng)絡(luò)帶寬資源方面有較好的性能，但過多地關(guān)注了由于搶占LSP造成帶寬浪費(fèi)的代價(jià)，所以，筆者提出改進(jìn)的BH-PREPT算法，即DH-PREPT(Delay and Bandwidth Preemption)算法。該算法能兼顧避免級(jí)聯(lián)搶占［10］和搶占優(yōu)先級(jí)代價(jià)最小，從而改善網(wǎng)絡(luò)時(shí)延指標(biāo)的特點(diǎn)。

1 算法模型

BH-PREPT算法優(yōu)先考慮最小化由搶占所帶來的帶寬浪費(fèi);將可被搶占的LSP集合按照預(yù)留帶寬大小分為兩組，分別列舉出所有可能被搶占的LSP的組合，在其中尋找搶占總代價(jià)最小的組合作為算法輸出，優(yōu)先選擇LSP數(shù)目最少的組合進(jìn)行搶占。其搶占公式為其中α、β和γ是設(shè)置的3個(gè)權(quán)值，αy(l)表示搶占LSP ll的優(yōu)先級(jí)代價(jià)，l表示集合L中的第l個(gè)元素LSPl;L是LSP的集合，表示搶占LSP ll在減少搶占LSP數(shù)目方面的代價(jià)，γ(b(l)-r)表示搶占LSP ll造成帶寬浪費(fèi)的代價(jià);H(l)表示搶占LSP ll需要付出的總代價(jià)，H(l)越小，LSP ll被新LSP搶占的可能性越大。

BH-PREPT算法在避免級(jí)聯(lián)搶占和帶寬利用率方面有較好的性能，但由于該算法采用枚舉法，將減少由搶占帶來的帶寬浪費(fèi)的優(yōu)化標(biāo)準(zhǔn)置于首位，列舉所有可能被搶占LSP的集合，在其中尋找搶占總代價(jià)最小的LSP組合作為算法輸出，在每種情況下都優(yōu)先選擇數(shù)目最少的LSP組合實(shí)施搶占。在枚舉過程中，為了找出組合中的最優(yōu)解，對(duì)比次數(shù)增多，由此也帶來了計(jì)算復(fù)雜度和時(shí)延的增加，同時(shí)，提高了對(duì)設(shè)備芯片和存儲(chǔ)要求。

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

隨著用戶通信中的信息量呈爆發(fā)式增長(zhǎng)，光纖通信得到普及，帶寬資源已經(jīng)不成問題;然而，通信公司各部門的通信時(shí)延卻沒有呈現(xiàn)相應(yīng)減小。現(xiàn)在，很多公司希望他們對(duì)快速變化的行情做出最快反應(yīng)，以便獲取最大的利潤(rùn)或?qū)p失降到最低?；谛聲r(shí)代的計(jì)算機(jī)網(wǎng)絡(luò)通信的新特征，筆者認(rèn)為搶占原則應(yīng)根據(jù)市場(chǎng)導(dǎo)向做出相應(yīng)的變化，在關(guān)注帶寬浪費(fèi)的同時(shí)還要關(guān)注算法在網(wǎng)絡(luò)應(yīng)用的時(shí)延性能。所以提出DH-PREPT算法。其算法流程圖如圖1所示。

圖1中r為建立新的LSP所需要的帶寬，Bprempt為實(shí)際搶占的帶寬，Plh是VPN(Virtual Private Network)用戶常用業(yè)務(wù)類型的優(yōu)先級(jí)，L為保持優(yōu)先級(jí)低于Plh(新LSP的建立優(yōu)先級(jí))的所有LSP的集合，b(l)為集合L中所有LSP的預(yù)留帶寬集合b中的第l個(gè)元素，P為集合L中所有LSP的保持優(yōu)先級(jí)集合，H是搶占LSP時(shí)總的代價(jià)，計(jì)算公式如下

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

1)通信鏈路中出現(xiàn)新的可用于實(shí)際搶占的帶寬Bprempt出現(xiàn)時(shí)，正在綁定轉(zhuǎn)發(fā)等價(jià)類和LSP的標(biāo)簽邊緣路由需考慮新Bprempt的使用。

2)判斷隊(duì)列前端的轉(zhuǎn)發(fā)等價(jià)類的優(yōu)先級(jí)P是否與用戶的常用業(yè)務(wù)類型的優(yōu)先級(jí)Plh相同，若相同，執(zhí)行3);否則，執(zhí)行4)。

3)判斷實(shí)際搶占帶寬是否大于新的LSP帶寬，如果滿足條件，則建立新的LSP，并綁定轉(zhuǎn)發(fā)等價(jià)類與分組;否則，執(zhí)行4)。

4)將鏈路上每條保持優(yōu)先級(jí)低于Plh(新LSP的建立優(yōu)先級(jí))的LSP放入可被搶占的LSP集合L中。

5)依據(jù)H值的大小，將對(duì)應(yīng)的LSP進(jìn)行降序排列。

6)按照降序的 H順序?qū)︻A(yù)留帶寬 b(l)與新的LSP帶寬 r進(jìn)行比較，若b(l)＞r，執(zhí)行7);否則，執(zhí)行8)。

7)如果滿足b(l)＞r條件，立刻搶占與b(l)相對(duì)應(yīng)的LSP。

8)將LSP歸入可被搶占集合L1中。

9)判斷集合L1中的LSP預(yù)留帶寬之和是否大于r，若滿足條件，則立刻搶占LSP組合;否則，執(zhí)行6)。

10)退出算法。

2 仿真結(jié)果

DH-PREPT算法相對(duì)于BH-PREPT算法的主要區(qū)別是對(duì)用戶VPN通信時(shí)延指標(biāo)的改進(jìn)。操作系統(tǒng)選擇Windows XP系統(tǒng)，仿真軟件選擇OPNET 14.5版本，輔助軟件是VC++6.0。在仿真結(jié)果中主要提取時(shí)延(delay)和用戶之間的響應(yīng)時(shí)間(response time)兩個(gè)參數(shù)進(jìn)行比較分析。節(jié)點(diǎn)模型如圖2所示，RSVP(Resource Reservation Protocol)進(jìn)程說明如圖3所示。

圖2 節(jié)點(diǎn)模型圖Fig.2 Diagram of nodemodel

圖3 資源預(yù)留協(xié)議進(jìn)程說明Fig.3 Description of resource reservation protocol process

為了驗(yàn)證兩種算法在MPLSVPN應(yīng)用中的性能差異，選擇了兩個(gè)場(chǎng)景，對(duì)路由的LSP搶占加入了BH-PREPT和DH-PREPT兩種算法，分別對(duì)同一網(wǎng)絡(luò)拓?fù)涞膬蓚€(gè)通信網(wǎng)絡(luò)進(jìn)行仿真。仿真時(shí)間設(shè)置為1 000 s，種子數(shù)量為128個(gè)，靜態(tài)值設(shè)置為100。兩個(gè)通信網(wǎng)絡(luò)中隨機(jī)產(chǎn)生3種數(shù)據(jù)流，分別是voice (語音)、http和ftp，同時(shí)設(shè)定其主要通信業(yè)務(wù)為語音業(yè)務(wù)，在路由的加權(quán)排隊(duì)機(jī)制中將語音數(shù)據(jù)的優(yōu)先級(jí)設(shè)為最高。兩種場(chǎng)景都采用DS-TE技術(shù)，最后在結(jié)果中提取不同業(yè)務(wù)流的實(shí)驗(yàn)圖像進(jìn)行比較。

1)語音業(yè)務(wù)(Voice)。語音業(yè)務(wù)的實(shí)驗(yàn)圖像如圖4、圖5所示。

圖4 DH-PREPT算法voice時(shí)延圖 Fig.4 The chart of voice delay based on DH-PREPT algorithm

圖5 BH-PREPT算法voice時(shí)延圖Fig.5 The chart of voice delay based on BH-PREPT algorithm

在語音業(yè)務(wù)測(cè)試中，由于語音業(yè)務(wù)的優(yōu)先級(jí)較高，兩種算法下網(wǎng)絡(luò)的時(shí)延性能差異不大，但DH-PREPT算法的時(shí)效性仍比BH-PREPT算法有一定改善。DH-PREPT算法使網(wǎng)絡(luò)中的語音業(yè)務(wù)時(shí)延基本控制在0.14 s以內(nèi)，而BH-PREPT算法則有一部分語音數(shù)據(jù)的延遲超過0.14 s。仿真結(jié)果說明，改進(jìn)的DH-PREPT算法在減少通信時(shí)延方面有較好的性能。

2)http業(yè)務(wù)。http業(yè)務(wù)的實(shí)驗(yàn)圖像如圖6、圖7所示。

圖6 DH-PREPT算法http響應(yīng)時(shí)間圖Fig.6 The chart of http response time based on DH-PREPT algorithm

圖7 BH-PREPT算法http響應(yīng)時(shí)間圖Fig.7 The chart of http response time based on BH-PREPT algorithm

由于在優(yōu)先級(jí)方面http的級(jí)別低于voice，所以http文件數(shù)據(jù)在路由中的排隊(duì)量較大，當(dāng)使用DH-PREPT算法時(shí)ftp文件的傳輸?shù)捻憫?yīng)時(shí)間比BH-PREPT的時(shí)間短很多。DH-PREPT算法主要分布在0.4 s以內(nèi)，BH-PREPT算法有一半的數(shù)據(jù)的頁(yè)面響應(yīng)時(shí)間已經(jīng)超過了0.4 s。

3)ftp業(yè)務(wù)。ftp業(yè)務(wù)的實(shí)驗(yàn)圖像如圖8、圖9所示。

圖8 DH-PREPT算法ftp響應(yīng)時(shí)間圖Fig.8 The chart of ftp response time based on DH-PREPT algorithm

圖9 BH-PREPT算法ftp響應(yīng)時(shí)間圖Fig.9 The chart of ftp response time based on BH-PREPT algorithm

同樣的原因，當(dāng)兩家分公司使用ftp通信業(yè)務(wù)時(shí)，由圖8，圖9可看出，兩種算法對(duì)ftp文件的轉(zhuǎn)發(fā)效果明顯不同，由于在優(yōu)先級(jí)方面ftp的級(jí)別低于voice，所以ftp文件數(shù)據(jù)在路由中的排隊(duì)量較大，當(dāng)使用DH-PREPT算法時(shí)，ftp文件的傳輸響應(yīng)時(shí)間比BH-PREPT的時(shí)間短很多。

3 結(jié) 語

筆者提出了改進(jìn)的BH-PREPT算法，即DH-PREPT算法。該算法兼顧避免級(jí)聯(lián)搶占和搶占優(yōu)先級(jí)代價(jià)最小，在通信網(wǎng)絡(luò)性能方面主要體現(xiàn)在VPN用戶主要業(yè)務(wù)的時(shí)延有所減少。根據(jù)當(dāng)前VPN業(yè)務(wù)對(duì)通信網(wǎng)絡(luò)性能的需求對(duì)總代價(jià)計(jì)算公式H(l)進(jìn)行了修正，并使用OPNET仿真了兩種算法的通信場(chǎng)景，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比和分析。結(jié)果表明，新算法在減少通信時(shí)延方面有較好的性能。

［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環(huán)境下LSP搶占算法［J］.吉林大學(xué)學(xué)報(bào):信息科學(xué)版，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網(wǎng)絡(luò)中新的LSP搶占策略［J］.暨南大學(xué)學(xué)報(bào):自然科學(xué)版，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網(wǎng)絡(luò)環(huán)境中搶占算法的研究［J］.吉林大學(xué)學(xué)報(bào):信息科學(xué)版，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網(wǎng)絡(luò)中改進(jìn)的LSP搶占算法［J］.計(jì)算機(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網(wǎng)絡(luò)中的自適應(yīng)接入搶占策略［J］.電路與系統(tǒng)學(xué)報(bào)，2010，15(3):81-85. ZHU Mingying，YEWu，F(xiàn)ENG 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網(wǎng)絡(luò)中自適應(yīng)搶占算法研究［J］.東北大學(xué)學(xué)報(bào):自然科學(xué)版，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機(jī)制研究及其實(shí)現(xiàn)［D］.杭州:浙江大學(xué)信息科學(xué)與工程學(xué)院，2008. ZHANG Yufeng.Investigation and Implementation of QoSMechanism Based on MPLS［D］.Hangzhou:School of Infonmation Science and Engineering，Zhejiang University，2008.

(責(zé)任編輯:張潔)

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

長(zhǎng)春市重大科技攻關(guān)計(jì)劃基金資助項(xiàng)目(3D5143485420)

陳登昭(1991— )，男，湖南永州人，吉林大學(xué)碩士研究生，主要從事寬帶網(wǎng)絡(luò)研究，(Tel)86-15143082364(E-mail)dengzchen@163.com;于銀輝(1964— )，女，山東泰安人，吉林大學(xué)教授，主要從事寬帶通信及流量工程研究，(Tel)86-13604319589(E-mail)yuyh@jlu.edu.cn。