朱國暉，史浩山

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

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

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

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

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

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

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

圖1 CSPF計算過程Fig．1 CSPF calculation process

CSPF路由計算的基本過程是首先根據(jù)計算請求從TED中讀取相應(yīng)的網(wǎng)絡(luò)拓撲信息和約束條件，然后根據(jù)約束條件對網(wǎng)絡(luò)拓撲進行裁減，除去不符合要求的鏈路和節(jié)點，再在新生成的網(wǎng)絡(luò)拓撲中進行路由計算，得到路徑［6-9］．

1．2 QoS路由問題的抽象描述

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

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

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

2 SRLG的概念

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

IETF在草案文本中提出共享風險鏈路組［12］(SRLG)的概念，對＂物理分離＂概念進一步抽象和擴展．SRLG是指共享相同物理資源(也就是具有共同失效風險)的一組鏈路．每個SRLG都對應(yīng)一個唯一的標識，稱為 SRLG ID［13］．

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

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

式(6)和式(7)［14］是為網(wǎng)絡(luò)中每條鏈路設(shè)置的2個動態(tài)權(quán)重，一個用于尋找工作路由，另一個用于尋找保護路由．2個權(quán)重值都根據(jù)各鏈路負載情況實時變化．目的是使業(yè)務(wù)請求盡量建立在空閑波長資源比較富裕的路由上，來均衡鏈路的負載，避免因為某些鏈路的波長資源耗盡而產(chǎn)生的網(wǎng)絡(luò)阻塞．可以看出，空閑波長資源越多(B-U越大)，其鏈路代價值越小．因此本算法會鼓勵工作通路盡可能經(jīng)過空閑資源多的鏈路，負載就更均勻地分散到網(wǎng)絡(luò)中．其中ε1、ε2為負載均衡調(diào)整參數(shù)．

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

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

3．1 SDSA算法描述

算法基本的步驟:

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

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

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

2)建立工作路由:

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

如果沒有找到，則拒絕該請求，轉(zhuǎn)至2);

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

3)建立保護路由:

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

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

4)分配資源:

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

5)釋放資源:

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

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

從式(6)可以看出:隨著空閑資源增多，鏈路代價逐漸減小．因此Dijkstra算法會鼓勵工作通路盡可能經(jīng)過空閑資源多的鏈路，負載就能更均勻地分散到網(wǎng)絡(luò)中．而負載均衡會導(dǎo)致更多的工作通路滿足SRLG分離，其對應(yīng)的保護通路能共享資源，從而提高了資源利用率．

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

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

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

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

4．1 仿真實驗

為了證明SDSA算法的有效性及其優(yōu)越性，針對圖2所示的網(wǎng)絡(luò)拓撲進行實驗仿真．

圖2 美國NFS網(wǎng)絡(luò)拓撲示意圖Fig．2 The USA NFS network topology

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

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

表1 工作LSP和保護LSP對比Table1 Work LSP and protection LSP comparison

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

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

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

4．2 仿真結(jié)論

由仿真實驗可知，本文提出的SDSA算法的特點:

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

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

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

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

5 結(jié)束語

本文針對MPLS網(wǎng)絡(luò)，通過對路由算法的分析與研究，提出了一種新的動態(tài)路由算法-SDSA，詳細介紹了該算法的具體實現(xiàn)，在證明了該算法的正確性的同時，通過仿真實驗驗證了該算法較傳統(tǒng)的路由算法能夠更有效利用網(wǎng)絡(luò)資源的同時，提高網(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流量工程中動態(tài)路由算法研究［D］．沈陽:遼寧工程技術(shù)大學，2005:42-44．WANG Hong．Research of dynamic routing algorithm in MPLS traffic engineering［D］．Shenyang:Liaoning Technical University，2005:42-44．

［11］薛?？?，孫雨耕，劉振肖．基于帶寬和跳數(shù)的流量工程動態(tài)路由選擇算法研究［J］．電子學報，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］．電子與信息學報，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］姚婕．面向流量工程的約束路由的研究和實現(xiàn)［D］．南京:東南大學，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］．北京航空航天大學學報，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．