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

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

關(guān)鍵詞：多協(xié)議標(biāo)簽交換; 約束路由；負(fù)載均衡；標(biāo)記交換路徑

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：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的迅猛發(fā)展，Internet上的業(yè)務(wù)種類也與日俱增，除了傳統(tǒng)的數(shù)據(jù)傳輸，語音、圖像等應(yīng)用也越來越多，這些實(shí)時業(yè)務(wù)對網(wǎng)絡(luò)的延遲、帶寬、抖動有嚴(yán)格的要求。多協(xié)議標(biāo)簽交換技術(shù)( )是一項(xiàng)在開放的通信網(wǎng)絡(luò)中利用二層的快速交換能力來提高第三層路由轉(zhuǎn)發(fā)速度的技術(shù)。將MPLS用于實(shí)施 ，是MPLS最具吸引力的應(yīng)用，流量工程是通過將大量的用戶業(yè)務(wù)，轉(zhuǎn)移到經(jīng)過服務(wù)提供商網(wǎng)絡(luò)中特定節(jié)點(diǎn)的預(yù)先設(shè)定的路徑來實(shí)現(xiàn)的，這些預(yù)先設(shè)定的路徑被稱作標(biāo)記交換路徑(LSP)。MPLS流量工程將最大程度利用現(xiàn)有網(wǎng)絡(luò)資源，優(yōu)化網(wǎng)絡(luò)的運(yùn)行性能。

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

2 網(wǎng)絡(luò)模型與參數(shù)描述

用G =(N，L)表示MPLS網(wǎng)絡(luò)拓?fù)?，N為網(wǎng)絡(luò)結(jié)點(diǎn)的集合，L為網(wǎng)絡(luò)鏈路的集合。P為網(wǎng)絡(luò)的源，目的結(jié)點(diǎn)隊(duì)的集合。

任意的(s，d)∈P，s為源結(jié)點(diǎn)，d為目的結(jié)點(diǎn)。

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

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

2) 鏈路的開銷系數(shù)：我們定義每一條鏈路l， 都有一個開銷系數(shù)用c(l)表示，c(l)與鏈路的剩余帶寬容量成反比。即在選取鏈路時盡量選取開銷?。词Ｓ嗳萘看蟮逆溌罚ヽ(l)表示為：

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

3 算法描述

提出的BHRA算法達(dá)到以下流量工程目標(biāo)：

① 使業(yè)務(wù)流量盡量均勻的分配在網(wǎng)絡(luò)中，降低請求的拒絕率。

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

③ 選取的源，目的結(jié)點(diǎn)間路徑的跳數(shù)盡量小。

為達(dá)到上述目標(biāo)，我們設(shè)鏈路權(quán)重為：

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

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

算法流程：

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

1) 首先剪除網(wǎng)絡(luò)中帶寬＜B 的鏈路，并生成新的拓?fù)渚W(wǎng)絡(luò)。

2) 計(jì)算網(wǎng)絡(luò)中每條鏈路的鏈路利用率和記錄剩余帶寬值，并根據(jù)(4)對每條鏈路確定負(fù)載系數(shù)。

3) 根據(jù)公式(5)計(jì)算每條鏈路的權(quán)重值w(l)。

4) 利用SPF算法，計(jì)算權(quán)重值的和最小的路徑。

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

4 仿真分析

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

我們將提出的算法與CSPFHopCount算法， 算法進(jìn)行比較，仿真使用[2]中著名的MIRA拓?fù)鋱D。利用TOTEM生成的MIRA拓?fù)鋱D如圖1所示。

真結(jié)果

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

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

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

5 總結(jié)

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

參考文獻(xiàn)：

[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.

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