面向業(yè)務(wù)的GMPLS網(wǎng)絡(luò)動(dòng)態(tài)生存性算法

朱國(guó)暉，史浩山

(1．西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安710072;2．西安郵電學(xué)院 信 息與通信學(xué)院，陜西西安710061)

通用MPLS(GMPLS)是MPLS向光網(wǎng)絡(luò)擴(kuò)展的必然產(chǎn)物，它為了適應(yīng)對(duì)智能光網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)控制和傳送信令的要求而對(duì)傳統(tǒng)的MPLS進(jìn)行了擴(kuò)展、更新．在智能光網(wǎng)絡(luò)中，基于GMPLS協(xié)議完成是實(shí)現(xiàn)光網(wǎng)絡(luò)節(jié)點(diǎn)控制平面的主要途徑，光網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)GMPLS協(xié)議可完成信令、路由、鏈路管理等功能，真正實(shí)現(xiàn)了光傳輸網(wǎng)與業(yè)務(wù)交換網(wǎng)的集成，為發(fā)展新業(yè)務(wù)創(chuàng)造了良好的條件．

對(duì)于網(wǎng)絡(luò)的流量工程問(wèn)題，人們提出了多種解決方法，但較傳統(tǒng)的解決方案相比，GMPLS實(shí)施流量工程具有更多的優(yōu)勢(shì)．GMPLS流量工程的問(wèn)題最終可以歸結(jié)為數(shù)據(jù)流傳輸?shù)穆窂酱_定問(wèn)題，即顯式路徑的確立問(wèn)題，所以研究流量工程動(dòng)態(tài)路由算法的約束條件和目標(biāo)函數(shù)，對(duì)于動(dòng)態(tài)實(shí)現(xiàn)基于MPLS的流量工程具有特別重要的意義［1-2］．

1 基于約束的路由選擇算法

基于約束的動(dòng)態(tài)路由選擇-CR(constraint-based dynamic routing)是流量工程的重要組成部分，也是實(shí)現(xiàn)QoS的關(guān)鍵．相對(duì)于傳統(tǒng)路由協(xié)議只考慮最短路徑算法(SFP)來(lái)說(shuō)，基于約束的選路需要根據(jù)多個(gè)約束條件選擇路由，利用現(xiàn)有路由協(xié)議的擴(kuò)展協(xié)議，從流量需求和網(wǎng)絡(luò)資源角度考慮，得出路徑需要滿(mǎn)足的一系列約束條件和目標(biāo)函數(shù)，計(jì)算出由入口路由器到出口路由器間的多條路徑．

1．1 CSPF 的應(yīng)用

基于約束的最短路徑優(yōu)先(CSPF)是流量工程中的核心技術(shù)，也是實(shí)現(xiàn)QoS業(yè)務(wù)的關(guān)鍵．基于約束的路由選擇既可以是采用QoS的約束條件，也可以是其他策略性的約束條件，例如從提高全網(wǎng)的網(wǎng)絡(luò)性能方面的考慮．通過(guò)網(wǎng)絡(luò)的呼叫拒絕率降低反映出網(wǎng)絡(luò)的性能的提高．在確定一條路徑時(shí)，基于約束的最短路徑優(yōu)先路由選擇不僅考慮網(wǎng)絡(luò)的拓?fù)?，還要考慮流的要求、鏈路的資源供應(yīng)及由網(wǎng)絡(luò)管理員設(shè)定的別的策略［3-5］．

圖1 CSPF計(jì)算過(guò)程Fig．1 CSPF calculation process

CSPF路由計(jì)算的基本過(guò)程是首先根據(jù)計(jì)算請(qǐng)求從TED中讀取相應(yīng)的網(wǎng)絡(luò)拓?fù)湫畔⒑图s束條件，然后根據(jù)約束條件對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行裁減，除去不符合要求的鏈路和節(jié)點(diǎn)，再在新生成的網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行路由計(jì)算，得到路徑［6-9］．

1．2 QoS路由問(wèn)題的抽象描述

令 e∈E，c(e)、d(e)、b(e)、j(e)和 l(e)分別表示鏈路 e的代價(jià)、延時(shí)、帶寬、延時(shí)抖動(dòng)和丟包率［10-11］．求解QoS路由問(wèn)題就是要在源點(diǎn) V1到終點(diǎn)Vk之間找到一條最佳路徑P，使P代價(jià)最小，并且路徑帶寬不小于最小帶寬需求，延時(shí)、延時(shí)抖動(dòng)和丟包率均不超過(guò)特定上限．此時(shí)，QoS路由問(wèn)題可以運(yùn)用如下數(shù)學(xué)模型表示:

式中:C(p)、D(p)、B(p)、J(p)和 L*(p)分別表示路徑P的代價(jià)、延時(shí)、帶寬、延時(shí)抖動(dòng)和報(bào)文傳輸成功率;△Bandwidth表示最小帶寬，△delay表示最大延時(shí)，△jitter表示最大延時(shí)抖動(dòng)，△loss表示最大丟包率，P(V1，Vk)表示從源點(diǎn)V1到終點(diǎn)Vk之間所有可達(dá)路徑集．

為了在滿(mǎn)足業(yè)務(wù)量要求的前提下，使網(wǎng)絡(luò)的資源盡可能均勻地使用，避免出現(xiàn)部分網(wǎng)絡(luò)擁塞而其余鏈路空閑或利用率較低的不均衡狀態(tài)，本論文提出了一種新的動(dòng)態(tài)路由生存性算法-SDSA．

2 SRLG的概念

在動(dòng)態(tài)業(yè)務(wù)的環(huán)境中，當(dāng)網(wǎng)絡(luò)中到達(dá)一條業(yè)務(wù)請(qǐng)求時(shí)，為其建立2條“物理分離”的LSP，分別為工作路由和保護(hù)路由．只有業(yè)務(wù)的2條LSP均存在，才認(rèn)為業(yè)務(wù)成功分配了資源，否則業(yè)務(wù)請(qǐng)求被阻塞．

IETF在草案文本中提出共享風(fēng)險(xiǎn)鏈路組［12］(SRLG)的概念，對(duì)＂物理分離＂概念進(jìn)一步抽象和擴(kuò)展．SRLG是指共享相同物理資源(也就是具有共同失效風(fēng)險(xiǎn))的一組鏈路．每個(gè)SRLG都對(duì)應(yīng)一個(gè)唯一的標(biāo)識(shí)，稱(chēng)為 SRLG ID［13］．

設(shè)Ck(l)為尋找工作路由時(shí)使用的鏈路權(quán)重，Cp(l)為尋找保護(hù)路由時(shí)使用的鏈路權(quán)重．

設(shè)C為鏈路l的實(shí)際物理權(quán)重，這個(gè)值受到很多因素的影響，如物理長(zhǎng)度、物理設(shè)備價(jià)格、風(fēng)險(xiǎn)約束等的影響．B為鏈路l的總帶寬，U為鏈路已被占用帶寬，B-U為鏈路剩余帶寬．W表示工作路由所經(jīng)過(guò)的鏈路集，S表示工作路由所經(jīng)過(guò)鏈路的SRLG標(biāo)識(shí)集．在為到達(dá)的新業(yè)務(wù)計(jì)算保護(hù)路由時(shí)，應(yīng)根據(jù)式(7)更新鏈路的權(quán)值．再利用Dijkstra算法進(jìn)行尋路，如能找到一條，則該路由同當(dāng)前業(yè)務(wù)的工作路由SRLG無(wú)關(guān)．

式(6)和式(7)［14］是為網(wǎng)絡(luò)中每條鏈路設(shè)置的2個(gè)動(dòng)態(tài)權(quán)重，一個(gè)用于尋找工作路由，另一個(gè)用于尋找保護(hù)路由．2個(gè)權(quán)重值都根據(jù)各鏈路負(fù)載情況實(shí)時(shí)變化．目的是使業(yè)務(wù)請(qǐng)求盡量建立在空閑波長(zhǎng)資源比較富裕的路由上，來(lái)均衡鏈路的負(fù)載，避免因?yàn)槟承╂溌返牟ㄩL(zhǎng)資源耗盡而產(chǎn)生的網(wǎng)絡(luò)阻塞．可以看出，空閑波長(zhǎng)資源越多(B-U越大)，其鏈路代價(jià)值越?。虼吮舅惴〞?huì)鼓勵(lì)工作通路盡可能經(jīng)過(guò)空閑資源多的鏈路，負(fù)載就更均勻地分散到網(wǎng)絡(luò)中．其中ε1、ε2為負(fù)載均衡調(diào)整參數(shù)．

為了避免SRLG自陷問(wèn)題已有很多文獻(xiàn)進(jìn)行了研究，提出了各種解決辦法［15-16］，本文對(duì)鏈路l的工作權(quán)重函數(shù)和保護(hù)權(quán)重函數(shù)做如下處理:式(7)中，M為一較大的常數(shù)，之所以沒(méi)有將這種情況下的鏈路代價(jià)設(shè)為∞，是因?yàn)橐肕來(lái)找到造成自陷的鏈路，從而避免陷阱．

3 面向業(yè)務(wù)的GMPLS動(dòng)態(tài)生存性算法

3．1 SDSA算法描述

算法基本的步驟:

1)等待業(yè)務(wù)請(qǐng)求:

如果為連接建立請(qǐng)求，則執(zhí)行2);

如果為連接釋放請(qǐng)求，則執(zhí)行5);

2)建立工作路由:

根據(jù)到達(dá)請(qǐng)求的帶寬要求b，決定鏈路的權(quán)值函數(shù)，然后，利用Dijkstra算法尋找一條工作LSP．

如果沒(méi)有找到，則拒絕該請(qǐng)求，轉(zhuǎn)至2);

否則，轉(zhuǎn)至3);

3)建立保護(hù)路由:

根據(jù)式(6)修改拓?fù)鋱D中鏈路的權(quán)值函數(shù)，如是考慮負(fù)載均衡的專(zhuān)用通路保護(hù)算法，然后利用Dijkstra算法找一條SRLG盡量分離的保護(hù)LSP，如果找到，轉(zhuǎn)至4);

否則，拒絕該請(qǐng)求，轉(zhuǎn)至2);

4)分配資源:

根據(jù)到達(dá)業(yè)務(wù)請(qǐng)求在工作路由和保護(hù)路由上預(yù)留相應(yīng)的帶寬資源．然后修改兩條通路相應(yīng)鏈路的剩余帶寬值減去b，轉(zhuǎn)至2);

5)釋放資源:

釋放所占資源，修改它對(duì)應(yīng)的工作通路和保護(hù)通路所經(jīng)鏈路的剩余帶寬值，將剩余帶寬值加上b．

采用Dijsktra最短路算法為業(yè)務(wù)請(qǐng)求計(jì)算工作通路和保護(hù)通路．在算法中，考慮2個(gè)約束:負(fù)載均衡度和資源共享度．針對(duì)這2個(gè)約束，設(shè)計(jì)了2個(gè)鏈路代價(jià)函數(shù)分別針對(duì)工作通路和保護(hù)通路的計(jì)算．

從式(6)可以看出:隨著空閑資源增多，鏈路代價(jià)逐漸減?。虼薉ijkstra算法會(huì)鼓勵(lì)工作通路盡可能經(jīng)過(guò)空閑資源多的鏈路，負(fù)載就能更均勻地分散到網(wǎng)絡(luò)中．而負(fù)載均衡會(huì)導(dǎo)致更多的工作通路滿(mǎn)足SRLG分離，其對(duì)應(yīng)的保護(hù)通路能共享資源，從而提高了資源利用率．

針對(duì)保護(hù)通路的鏈路代價(jià)函數(shù)．找到工作路徑后，在計(jì)算保護(hù)通路前，根據(jù)需要再次調(diào)整鏈路代價(jià)．該算法以鏈路利用率來(lái)反映負(fù)載均衡情況，從兩方面進(jìn)行考慮:鏈路和路徑．從鏈路的角度出發(fā)，鏈路的帶寬利用率反映鏈路的負(fù)載情況，所有鏈路的負(fù)載狀況就可以反映整個(gè)網(wǎng)絡(luò)的流量均衡程度．顯然，當(dāng)網(wǎng)絡(luò)中所有鏈路的負(fù)載都較輕時(shí)，網(wǎng)絡(luò)不會(huì)出現(xiàn)擁塞，所有用戶(hù)的QoS都能得到保證．

3．2 算法復(fù)雜度分析

算法的關(guān)鍵步驟是入口-出口節(jié)點(diǎn)對(duì)之間的可選路徑計(jì)算，網(wǎng)絡(luò)中計(jì)算最短路徑的復(fù)雜度是O(n3)，計(jì)算第二最短路徑的復(fù)雜度是O(n4)，計(jì)算第M最短路徑的復(fù)雜度是O(nM+2)．綜合分析算法各步驟，其最終的計(jì)算復(fù)雜度取決于算法實(shí)現(xiàn)中所確定的需要計(jì)算的第M條最短路徑的復(fù)雜度，即O(nM+2)．

4 性能仿真與結(jié)論

4．1 仿真實(shí)驗(yàn)

為了證明SDSA算法的有效性及其優(yōu)越性，針對(duì)圖2所示的網(wǎng)絡(luò)拓?fù)溥M(jìn)行實(shí)驗(yàn)仿真．

圖2 美國(guó)NFS網(wǎng)絡(luò)拓?fù)涫疽鈭DFig．2 The USA NFS network topology

對(duì)一個(gè)業(yè)務(wù)請(qǐng)求，工作通道和保護(hù)通道均按照Dijkstra最短路算法選擇路由．工作通道和保護(hù)通道兩者之間任何一個(gè)建路不成功時(shí)，業(yè)務(wù)即被阻塞，不允許為工作通道或保護(hù)通道重路由或發(fā)起多次重復(fù)建路的嘗試．

在仿真程序中，指定某一個(gè)節(jié)點(diǎn)為源節(jié)點(diǎn)(如節(jié)點(diǎn)0)，依次計(jì)算出源節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑和備用路徑．

表1 工作LSP和保護(hù)LSP對(duì)比Table1 Work LSP and protection LSP comparison

由表1可以看出，SDSA算法在選擇生存性方面已經(jīng)部分避開(kāi)了主用LSP經(jīng)過(guò)的路徑．其他計(jì)算的一些參數(shù)如表2所示．

表2 其他參數(shù)Table 2 Other parameters

從上述分析可知，本算法體現(xiàn)流量工程在滿(mǎn)足業(yè)務(wù)QoS參數(shù)要求的前提下均衡網(wǎng)絡(luò)資源的利用率這一目標(biāo)．

4．2 仿真結(jié)論

由仿真實(shí)驗(yàn)可知，本文提出的SDSA算法的特點(diǎn):

1)SDSA算法比普通的OSPF，對(duì)于緩解由于流量對(duì)引起的資源競(jìng)爭(zhēng)具有顯著的效果;

2)SDSA算法由于優(yōu)先選擇剩余帶寬多的鏈路，因此能夠更加有效地降低了資源利用率，避免瓶頸鏈路的產(chǎn)生;

3)SDSA算法能更好地調(diào)節(jié)流量在整個(gè)網(wǎng)絡(luò)上的分布，使網(wǎng)絡(luò)資源得到均衡分布;

4)SDSA算法考慮了SRLG對(duì)路由的影響，在避開(kāi)具有相關(guān)鏈路組的前提下提高了連接請(qǐng)求的接通率．

5 結(jié)束語(yǔ)

本文針對(duì)MPLS網(wǎng)絡(luò)，通過(guò)對(duì)路由算法的分析與研究，提出了一種新的動(dòng)態(tài)路由算法-SDSA，詳細(xì)介紹了該算法的具體實(shí)現(xiàn)，在證明了該算法的正確性的同時(shí)，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法較傳統(tǒng)的路由算法能夠更有效利用網(wǎng)絡(luò)資源的同時(shí)，提高網(wǎng)絡(luò)的吞吐量．

［1］ZHANG X J，KIM S，LUMETTA S S．Reduced flow routing:leveraging residual capacity to reduce blocking in GMPLS networks［C］//Broadnets 2007．［s．l．］，2007:394-403．

［2］KIM S，JUKAN A，LUMETTA S S．Coordinated resource scheduling in high-performance optical grids［C］//Proceedings of the Optical Fiber Communication Conference．Anaheim，USA，2007:1-3．

［3］KIM S，NWANZE N ，ZHANG X J，et al．QoT-guaranteed protection:survivability under physical layer impairments［C］//Broadnets 2008．London，United Kingdom，2008:619-26．

［4］ZHANG X J，KIM S，LUMETTA S S．On resource provisioning for multi-domain networks［C］//Proceedings of the Optical Fiber Communication Conference．San Diego，USA 2009:1-3．

［5］MOHAN G，TIEN E C．QoS routing in GMPLS-capable integrated IP/WDM networks with router cost constraints［J］．Computer Communications，2008，31(1):19-34．

［6］RUEPP S，ANDRIOLLI N，BURON J，et al．Restoration in all-optical GMPLS networks with limited wavelength conversion［J］．Computer Networks and ISDN Systems-CN，2008，52(10):1951-1964．

［7］SINGH Y，SONI M K，SWARUP A．Bandwidth sensitive multi-path routing algorithm［C］//Proceedings of the Eighth IASTED International Conference on Wireless and Optical Communications．Quebec City，Canada，2008:26-28．

［8］LOA A，Ross C，RAM D，et al．Constraint-Based LSP Setup using LDP，IETF work in progress［EB/OL］．［2010-10-13］．http:11 tools．ietf．org/html/draft-ietf-mpls-cr-ldp-05．

［9］LEE Y，SEOK Y，CHOI Y．A constrained multipath traffic engineering scheme for MPLS networks［C］//ICC'02．New York，2002:2431-2436．

［10］王宏．MPLS流量工程中動(dòng)態(tài)路由算法研究［D］．沈陽(yáng):遼寧工程技術(shù)大學(xué)，2005:42-44．WANG Hong．Research of dynamic routing algorithm in MPLS traffic engineering［D］．Shenyang:Liaoning Technical University，2005:42-44．

［11］薛希俊，孫雨耕，劉振肖．基于帶寬和跳數(shù)的流量工程動(dòng)態(tài)路由選擇算法研究［J］．電子學(xué)報(bào)，2002，30(2):274-278．

XUE Xijun，SUN Yugeng，LIU Zhenxiao．Traffic engineering dynamic routing based on bandwidth and hops［J］．Acta Electronica Sinica，2002，30(2):274-278．

［12］XIA Ming，TORNATORE M，MARTEL C，et al．Risk-aware routing for optical transport networks［C］//Proceedings of the 29th Conference on Information Communications．［s．l．］，2010:588-595．

［13］VELASCO L，SPADARO S，COMELLAS J，et al．Introducing OMS protection in GMPLS-based optical ring networks［J］．The International Journal of Computer and Telecommunications Networking，2008，52:1975-1987．

［14］呂航，孫雨耕，吳雪．流量工程中靜態(tài)路由算法的研究［J］．電子與信息學(xué)報(bào)，2003，25(10):1403-1410．

Lü Hang，SUN Yugeng，WU Xue．Research on static routing algorithm with traffic engineering［J］．Journnal of E-lectronics＆ Information Technology，2003，25(10):1403-1410．

［15］姚婕．面向流量工程的約束路由的研究和實(shí)現(xiàn)［D］．南京:東南大學(xué)，2005:20-23．

YAO Jie．Study on traffic engineering based on constraintbased routing in MPLS networks［D］．Nanjing:South-East University，2005:20-23．

［16］黃河，李偉琴．MPLS流量工程體系結(jié)構(gòu)優(yōu)化研究［J］．北京航空航天大學(xué)學(xué)報(bào)，2003，29(3):221-224．

HUANG He，LI Weiqin．Optimization of MPLS traffic engineering architecture［J］．Journal of Beijing University of Aeronautics and Astronautics，2003，29(3):221-224．