ＭＰＬＳ流量工程中的約束路由算法

摘要：該文提出一種基于MPLS流量工程的約束路由算法—BHRA。該算法以帶寬為主要約束條件，兼顧跳數約束來確定鏈路權重，并利用最短路徑算法（SPF）來尋找權重和最小的路徑。仿真實驗表明與CSPFHopCount算法及MIRA算法相比該算法在網絡負載均衡，限制最大鏈路利用率，以及LSP的請求拒絕率方面表現出更好的性能。

關鍵詞：多協議標簽交換; 約束路由；負載均衡；標記交換路徑

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)30-0598-03

Constraint-based Routing Algorithm in MPLS Traffic Engineering

XU Chun-ming，ZHOU Jing-quan

(Nanjing University of Post and Telecommunications，Nanjing 210003，China)

Abstract:This paper proposes a new constraint-based routing algorithm—BHRA based on MPLS traffic engineering.This algorithm mainly based on bandwidth constraint，and also considers hop–count constraint to compute the link–weight，and use the SPF algorithm to find the optimal path using link–weight. The simulation shows the algorithm performances better in balancing the network load， optimizing the resource ultilization， and accommodating more LSP requests.

Key words:MPLS(mutiprotocal label switching); constraint-based routing; load balance; LSP(label switching path)

1 引言

隨著Internet的迅猛發展，Internet上的業務種類也與日俱增，除了傳統的數據傳輸，語音、圖像等應用也越來越多，這些實時業務對網絡的延遲、帶寬、抖動有嚴格的要求。多協議標簽交換技術( )是一項在開放的通信網絡中利用二層的快速交換能力來提高第三層路由轉發速度的技術。將MPLS用于實施 ，是MPLS最具吸引力的應用，流量工程是通過將大量的用戶業務，轉移到經過服務提供商網絡中特定節點的預先設定的路徑來實現的，這些預先設定的路徑被稱作標記交換路徑(LSP)。MPLS流量工程將最大程度利用現有網絡資源，優化網絡的運行性能。

約束路由是MPLS流量工程的核心技術，約束路由的主要目標是為業務選擇滿足其質量要求的傳輸路徑，同時優化網絡性能。目前在MPLS領域應用最廣泛的約束路由算法是最小跳(SFP)算法，在這種算法中源，目的結點間擁有最小跳數的路徑被選為LSP傳輸路徑。但是SPF算法容易使流量請求重復的在同一條或幾條路徑上傳輸，直到這些路徑達到飽和，這容易導致網絡負載的不平衡和瓶頸鏈路的產生，本文仿真中用到的CSPFHopCount算法類似于SFP算法，CSPFHopCount算法的思想是：首先剪除帶寬小與請求需要的鏈路，然后將剩余鏈路的代價函數w(l)=常值，這樣滿足帶寬約束的最小跳數的路徑被優先選擇。接著 算法被提出，MIRA算法在進行路由計算時著重選取那些對其他各個結點對未來流量請求干擾最小的鏈路。但MIRA算法不考慮鏈路均衡負載，會造成部分鏈路擁塞，從而影響服務質量。本文將在上述算法的基礎上，提出一種基于帶寬約束的動態路由算法—BHRA(Bandwidth HopCount Constrained Routing Agorithm)算法，在負載均衡分配，請求拒絕率方面性能得到到優化。并將在linux環境下，使用一種新的開源的流量工程仿真工具 ，對提出算法的性能進行仿真分析。

2 網絡模型與參數描述

用G =(N，L)表示MPLS網絡拓撲，N為網絡結點的集合，L為網絡鏈路的集合。P為網絡的源，目的結點隊的集合。

任意的(s，d)∈P，s為源結點，d為目的結點。

任意的LSP請求用(si，di，B)來表示，其中B為業務帶寬請求容量。

1) 鏈路帶寬利用率：為鏈路已用帶寬(R)和鏈路總共可用帶寬(C)的比值，鏈路l的鏈路利用率用u(l)表示為：

2) 鏈路的開銷系數：我們定義每一條鏈路l， 都有一個開銷系數用c(l)表示，c(l)與鏈路的剩余帶寬容量成反比。即在選取鏈路時盡量選取開銷小（即剩余容量大的鏈路）c(l)表示為：

3) 鏈路負載系數K：即根據鏈路負載情況不同，賦以不同的權值。鏈路的負載系數K與鏈路帶寬利用率u(l)直接相關。路帶寬利用率即反映鏈路帶寬的使用情況，也反映該鏈路的負載情況，當u(l)過高時說明該鏈路負載過重，很可能導致阻塞和“瓶頸”鏈路的產生，為了防止避免“瓶頸”鏈路的產生，使流量請求在盡可能在整個網絡中均勻分布，K定義為：

3 算法描述

提出的BHRA算法達到以下流量工程目標：

① 使業務流量盡量均勻的分配在網絡中，降低請求的拒絕率。

② 降低最大鏈路利用率，防止“瓶頸”鏈路的產生。

③ 選取的源，目的結點間路徑的跳數盡量小。

為達到上述目標，我們設鏈路權重為：

在鏈路選擇時選取w(l)和的值最小的路徑。其中u(l)×c(l)表示鏈路選取的標準，即在選取鏈路時，盡量選取鏈路利用率低和鏈路剩余帶寬容量大，即c(l)小的鏈路。但兩者相乘可能產生的問題是：可能選取利用率高但剩余容量相對過大(即c(l)過小)的鏈路，從而會導致過高鏈路利用率的鏈路被選中，為此我們乘以鏈路負載系數K，當鏈路利用率過高時加以一定的權值，從而盡量“限制”過高利用率的鏈路繼續使用。

H是跳數限制系數，H的設定是參照CSPFHopCount算法，CSPFHopCount算法是基于跳數最小的CSPF算法。該算法在進行路徑選擇時將鏈路的代價函數設為常值：w(l)=常值。所以在這里把H設為常值，其中H的大小決定跳數占的比重。這里我們設H =5，考慮當網絡輕負載時沒有必要進行負載均衡，隨著請求的不但增加[u(l)×c(l)]×L的值會遠大于H，因此 H只作用于最初的輕負載時。

算法流程：

對于到達的流量請求 (si，di，B):

1) 首先剪除網絡中帶寬＜B 的鏈路，并生成新的拓撲網絡。

2) 計算網絡中每條鏈路的鏈路利用率和記錄剩余帶寬值，并根據(4)對每條鏈路確定負載系數。

3) 根據公式(5)計算每條鏈路的權重值w(l)。

4) 利用SPF算法，計算權重值的和最小的路徑。

5) 使請求流量沿選取路徑傳輸，并更新網絡鏈路的剩余容量。

4 仿真分析

仿真用一種專門針對流量工程的仿真軟件— 對提出的算法進行仿真，TOTEM是一種在LINUX環境下使用的開源流量工程仿真“工具箱”。

我們將提出的算法與CSPFHopCount算法， 算法進行比較，仿真使用[2]中著名的MIRA拓撲圖。利用TOTEM生成的MIRA拓撲圖如圖1所示。

真結果

在此圖中有15個結點和26條鏈路。其中粗鏈路帶寬容量設為4800M，細鏈路帶寬容量設為1200M。每條鏈路都可以雙向傳輸，其中選4組結點對作為源，目的結點對，分別為(1，13)，(4，2)，(5，9)，(15，5)。仿真時4組源，目的結點對隨機選擇作為源，目的結點對，假設到達的LSP請求一經建立便不再撤消，永久存在與網絡中，LSP請求隨機產生在 (10M，20M，30M，40M) 中隨機產生。分別發送2000和1000個LSP請求，分別仿真計算到達指定數目LSP請求的拒絕率和最大鏈路利用率，仿真結果如圖2和圖3。

如圖2可見CSPFHopCount算法LSP請求拒絕率最大，MIRA 次之，而BHRA算法具有最小的拒絕率，從而可以容納更多的鏈路請求。但到1600以后整個網絡可用鏈路基本達到飽和，所以三種算法的拒絕率開始趨于相同。

如圖3可見CSPFHopCount算法最大鏈路利用率值最快達到最大，MIRA則在大約300個路徑建立請求時達到最大，BHRA算法則最后達到最大。在40個路徑建立請求前BHRA算法接近CSPFHopCount算法，因為在輕負載時BHRA算法主要以跳數來決定路徑的選取。而隨著請求的增加，跳數占得比重逐漸被忽略，最大鏈路利用率的增大得到了限制，避免了鏈路瓶頸的產生。

5 總結

本文提出的基于MPLS流量工程的約束算法BHRA，以鏈路帶寬為主要約束標準，并考慮鏈路利用率和路徑的跳數，以此來確定每一條鏈路的權重。仿真結果表明，本算法與CSPFHopCount算法和MIRA算法相比在請求拒絕率以及限制最大鏈路利用率方面有優良的性能，能為更多的LSP請求建立傳輸路徑，并能夠避免瓶頸鏈路的產生，有效的達到網絡負載均衡的目標。

參考文獻：

[1] Awduche D. MPLS and traffic engineering in IP networks，IEEE Commun.37 (12)，1999.

[2] Awduche D.Overview and Principles of Internet Traffic Engineering [S].RFC 3272，IETF，2002，05.

[3] Blanchy F，Melon L，Leduc G.Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engneering applications， IEEE J.Selected Areas Commum.18 (12) (2000) 2566-2579.

[4] Xiao X， Hanna A， Bailey B，et al.Traffic engineering with MPLS in the Internet[J].IEEE Network Magnazine，，2000，14 (2);28-33.

[5] Leduc G，Abrahamsson H，Balon S，Bessler S，Arienzo M，Delcourt O，Domingo-Pascal J，Cerav-Erbas S，Gojmerac I， Masip X，Pescaph A，Quoitin B，Romano S F，Salvatori E，Skivee F，Tran H T，Uhlig S，Umit H， An open source traffic engineering toolbox， Computer Communications，29 (5):593-910， March 2006.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文