面向業務的GMPLS網絡動態生存性算法

朱國暉，史浩山

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

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

對于網絡的流量工程問題，人們提出了多種解決方法，但較傳統的解決方案相比，GMPLS實施流量工程具有更多的優勢．GMPLS流量工程的問題最終可以歸結為數據流傳輸的路徑確定問題，即顯式路徑的確立問題，所以研究流量工程動態路由算法的約束條件和目標函數，對于動態實現基于MPLS的流量工程具有特別重要的意義［1-2］．

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

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

1．1 CSPF 的應用

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

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

CSPF路由計算的基本過程是首先根據計算請求從TED中讀取相應的網絡拓撲信息和約束條件，然后根據約束條件對網絡拓撲進行裁減，除去不符合要求的鏈路和節點，再在新生成的網絡拓撲中進行路由計算，得到路徑［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路由問題可以運用如下數學模型表示:

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

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

2 SRLG的概念

在動態業務的環境中，當網絡中到達一條業務請求時，為其建立2條“物理分離”的LSP，分別為工作路由和保護路由．只有業務的2條LSP均存在，才認為業務成功分配了資源，否則業務請求被阻塞．

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

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

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

式(6)和式(7)［14］是為網絡中每條鏈路設置的2個動態權重，一個用于尋找工作路由，另一個用于尋找保護路由．2個權重值都根據各鏈路負載情況實時變化．目的是使業務請求盡量建立在空閑波長資源比較富裕的路由上，來均衡鏈路的負載，避免因為某些鏈路的波長資源耗盡而產生的網絡阻塞．可以看出，空閑波長資源越多(B-U越大)，其鏈路代價值越?。虼吮舅惴〞膭罟ぷ魍繁M可能經過空閑資源多的鏈路，負載就更均勻地分散到網絡中．其中ε1、ε2為負載均衡調整參數．

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

3 面向業務的GMPLS動態生存性算法

3．1 SDSA算法描述

算法基本的步驟:

1)等待業務請求:

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

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

2)建立工作路由:

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

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

否則，轉至3);

3)建立保護路由:

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

否則，拒絕該請求，轉至2);

4)分配資源:

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

5)釋放資源:

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

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

從式(6)可以看出:隨著空閑資源增多，鏈路代價逐漸減?。虼薉ijkstra算法會鼓勵工作通路盡可能經過空閑資源多的鏈路，負載就能更均勻地分散到網絡中．而負載均衡會導致更多的工作通路滿足SRLG分離，其對應的保護通路能共享資源，從而提高了資源利用率．

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

3．2 算法復雜度分析

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

4 性能仿真與結論

4．1 仿真實驗

為了證明SDSA算法的有效性及其優越性，針對圖2所示的網絡拓撲進行實驗仿真．

圖2 美國NFS網絡拓撲示意圖Fig．2 The USA NFS network topology

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

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

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

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

表2 其他參數Table 2 Other parameters

從上述分析可知，本算法體現流量工程在滿足業務QoS參數要求的前提下均衡網絡資源的利用率這一目標．

4．2 仿真結論

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

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

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

3)SDSA算法能更好地調節流量在整個網絡上的分布，使網絡資源得到均衡分布;

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

5 結束語

本文針對MPLS網絡，通過對路由算法的分析與研究，提出了一種新的動態路由算法-SDSA，詳細介紹了該算法的具體實現，在證明了該算法的正確性的同時，通過仿真實驗驗證了該算法較傳統的路由算法能夠更有效利用網絡資源的同時，提高網絡的吞吐量．

［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］．沈陽:遼寧工程技術大學，2005:42-44．WANG Hong．Research of dynamic routing algorithm in MPLS traffic engineering［D］．Shenyang:Liaoning Technical University，2005:42-44．

［11］薛希俊，孫雨耕，劉振肖．基于帶寬和跳數的流量工程動態路由選擇算法研究［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］呂航，孫雨耕，吳雪．流量工程中靜態路由算法的研究［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］姚婕．面向流量工程的約束路由的研究和實現［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流量工程體系結構優化研究［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．