一種最小化最大帶寬利用率的TE路由算法

26卷第3期小型微型計(jì)算機(jī)系統(tǒng)Vol.26No.3MINI-MICROSYSTEMS2005年3月Mar.2005TE王新紅1,劉富強(qiáng)1,王光興21(同濟(jì)大學(xué)電信學(xué)院,上海200092)東北大學(xué)網(wǎng)絡(luò)與通信中心,遼寧沈陽110006)2(E-mail:wangxinhong@163.com-:隨著網(wǎng)絡(luò)中流量的迅速增長,流量工程對于減小擁塞、提高網(wǎng)絡(luò)資源的使用效率、滿足業(yè)務(wù)的QoS要求,正在起著越來越重要的作用.提出了一種對Dijkstra算法進(jìn)行改進(jìn)的最小化最大帶寬利用率TE路由算法.該算法在搜尋路徑的過程中,將原來Dijkstra算法中的以路徑代價(jià)最小為目標(biāo),更改為以最小化最大帶寬利用率為目標(biāo).仿真證明,算法在一定程度上達(dá)到了均衡負(fù)載分布的作用.:流量工程;路由算法;帶寬利用率;均衡負(fù)載:TP393:A:1000-1220(2005)03-0422-03RoutingAlgorithmtoMinimizeMaximumLinkUtilizationWANGXin-hong1,LIUFu-qiang1,WANGGuang-xing21(ElectrandIormationEng,ongjiUniversity,Shanghai200092,China110006,China))2(etworkand,NortheasternUniversity,Shenyang:Withtherapidgrowthofthetrafficinthenetwork,trafficengineeringisplayingamoreandmoreimportantroleinAbstractreducingcongestion,improvingresourceutilizationandsatisfyingthequalityofservice.Inthispaper,aTEalgorithmispro-posedtominimizemaximumlinkutilizationbasedonmodificationofDijkstraalgorithm.Itreplacesfindingtheleastcostpathwithfindingthepathwithminimalbandwidthutilization.Thesimulationshowsthatthealgorithmbalancestheloaddistribu-tiontosomeextent.ds:trafficengineering;routingalgorithm;rateoflinkutilization;loadbalance1通過對流量工程的研究,可以很好地維護(hù)網(wǎng)絡(luò)均衡狀態(tài),避免擁塞的產(chǎn)生,從而使用戶的要求得以滿足QoS.隨著計(jì)算機(jī)網(wǎng)絡(luò)中業(yè)務(wù)流量的迅猛增長,如何高效的利流量工程,歸根到底是基于業(yè)務(wù)流所請求的資源和網(wǎng)絡(luò)用網(wǎng)絡(luò)資源并保證業(yè)務(wù)的QoS要求得以滿足正在變得越來當(dāng)前的可用資源,通過對業(yè)務(wù)流的合理路由來實(shí)現(xiàn)的,所以其越重要.傳統(tǒng)的最短路徑路由經(jīng)常導(dǎo)致以下問題:(1)當(dāng)來自核心問題是路徑計(jì)算問題.實(shí)現(xiàn)流量工程的路由技術(shù)稱為TE不同源的多條最短路徑都使用某一鏈路并超過該鏈路容量[4,5]路由.本文將提出一種對Dijkstra算法進(jìn)行改進(jìn)的最小化時(shí),該鏈路將發(fā)生擁塞;(2)當(dāng)源到目的間的業(yè)務(wù)流超過最短最大帶寬利用率的TE路由算法.需要說明的是,在選路過程路徑上的鏈路容量時(shí),最短路徑將發(fā)生擁塞,而它們之間的較我們考慮的約束條件僅為帶寬要求這是由于其他中QoS,,長路徑卻不被使用.為了解決這種由于負(fù)載分布不均衡而的要求如時(shí)延、丟包率等可以轉(zhuǎn)化為等效帶寬的形[1]QoS,,引起的網(wǎng)絡(luò)擁塞,提出了流量工程(,式而且很多實(shí)時(shí)應(yīng)用也對帶寬有嚴(yán)格的要求并且網(wǎng)絡(luò)TETrafficEngin,.,[6]eering)[2,3]的概念.中鏈路狀態(tài)信息的獲取和更新通過信令協(xié)議MPLSRSVP-流量工程是一個(gè)控制業(yè)務(wù)流如何經(jīng)過網(wǎng)絡(luò),以達(dá)到優(yōu)化TE或CR-LDP來進(jìn)行.網(wǎng)絡(luò)資源利用、提高網(wǎng)絡(luò)性能目的的過程.流量工程目前被公2認(rèn)為MPLS網(wǎng)絡(luò)最重要的TE發(fā)布了多個(gè)RFC和草案.在傳統(tǒng)的網(wǎng)絡(luò)中,數(shù)在近十幾年來路由得到了廣泛的關(guān)注但路由,QoS,TE據(jù)的轉(zhuǎn)發(fā)是由路由器按照Hop-by-Hop的方式完成,每個(gè)路和路由有所不同路由應(yīng)用之一,IETF已經(jīng)針對MPLS-InternetIPQoS.QoS是在一延、時(shí)延抖動(dòng)等的路由定的可用網(wǎng)絡(luò)資源下由器獨(dú)立地決定數(shù)據(jù)轉(zhuǎn)發(fā)的策略,無法要求其它路由器按照指定的路徑傳輸.在網(wǎng)絡(luò)中,數(shù)據(jù)的轉(zhuǎn)發(fā)沿著問題而路由具有更加廣泛的目標(biāo)它不僅要從個(gè)體MPLS,.TE[4,7]求解滿足單個(gè)流要求如帶寬、時(shí)QoS()進(jìn)LSP.行,只要使LSP按照指定的路徑建立,就能符合TE的要求上考慮——滿足特定流的要求,還要從全網(wǎng)的角度上QoS日期:2003-08-28介,女,1974年生,博士,主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、QoS、路由技術(shù)等,男,1965年生,教;,主要研究方向?yàn)槎嗝襟w技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)等,男,1937年生,教授、博士生導(dǎo)師,主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和多媒體通信.:授、博士生導(dǎo)師;3期王新紅等:一種最小化最大帶寬利用率的TE路由算法423考慮——優(yōu)化網(wǎng)絡(luò)性能,均衡負(fù)載分布,使網(wǎng)絡(luò)處于良好的運(yùn)請求帶寬為b的新呼叫后,鏈路(i,j)的帶寬利用率為行狀態(tài).與QoS路由的目標(biāo)有所區(qū)別,通常進(jìn)行TE路由的目標(biāo)是均衡負(fù)載分布,降低對未來請求的阻塞率,避免擁塞的產(chǎn)生.關(guān)于TE路由問題,正在引起人們的關(guān)注,目前已經(jīng)提出了一些算法.-×100.U=1-ijij3.路徑帶寬利用率:對于P(i,j)∈P,路徑P的帶寬利用率U(P)l定義為P上所有鏈路帶寬利用率的最大值,lGuerin等提出了一種最寬最短路徑算法(WSP,Widest-ShortestPath)[8].首先利用Dijkstra算法尋找源到目的之間跳數(shù)最少的路徑,如果存在多條的話,選擇其中路徑剩余帶寬最大的一條.該算法的性能優(yōu)劣依賴于網(wǎng)絡(luò)中存在多條最短路徑,如果網(wǎng)絡(luò)中只有一條最短路徑,那么該算法的性能與最短路徑路由算法是一樣的.即.U(P)=MaxUlPl(i,j)∈鏈路帶寬利用率反映常也反映該鏈路的負(fù)載情況.路徑帶寬利用率在這里由該路徑上負(fù)載最重的鏈路的帶寬利用率來表示,也就是反映了選.當(dāng)U→1,也就了某條鏈路上的帶寬使用情況,通Kodialam和Lakshman提出了一種最小干涉路由算法(MIRA,MinimumInterferenceRoutingAlgorithm)[9,10].為了減小請求的阻塞率,算法根據(jù)最大流最小割原理,在選路時(shí)選擇對入口-出口節(jié)點(diǎn)對產(chǎn)生“干涉”最小的鏈路.該算法由擇該路徑后造成的鏈路負(fù)載加重的最壞程度i,j是鏈路(i,j)的負(fù)載比較重時(shí),節(jié)點(diǎn)i和j間鏈路的可用帶寬與,將其他經(jīng)過該鏈路的連接請求.當(dāng)較小鏈連接所請求的帶寬接近,那么在這一鏈路上接納此連接后來會(huì)很難再接納路負(fù)載較輕時(shí),節(jié)點(diǎn)和間鏈路的可用帶寬比較U,i,j于需要執(zhí)行多個(gè)最大流計(jì)算,其算法復(fù)雜度較高Suri等提出了一種基于輪廓的路由(PBR,Profile-BasedRouting)[11]算法.該算法分為兩部分,離線部分根據(jù)流量輪來接納新廓,通過求解多商品流問題的方法,計(jì)算在每條鏈路上為每個(gè)為了避免擁塞的產(chǎn)生,在路由過程流量等級(jí)分配多少帶寬,才能使經(jīng)過該網(wǎng)絡(luò)的流量最大;在線使用負(fù)載重的鏈路,即最小化負(fù)載最重的鏈路的使用.因而.多,那么在這ij條鏈路上接納新的連接請求.的連接后剩余帶寬還較為充足不會(huì)影響將,,顯然,中應(yīng)該盡量避免,部分負(fù)責(zé)計(jì)算具體的路徑.PBR算法離線部分需要求解復(fù)雜在這里我們選路的目標(biāo)就是以最小化最大帶寬利用率為優(yōu)化路使用那些帶寬利用率的多商品流問題,并且需要事先已知流量輪廓,所以其擴(kuò)展性目標(biāo),以使業(yè)務(wù)流避開擁擠的熱點(diǎn)鏈,比較差.低的空閑鏈路同時(shí),最小化最大帶寬利用率也意味著鏈路上剩余帶寬所占的比率被最大化,這樣,鏈路上的剩余帶寬盡可流的方能多,有利于降低請求的阻塞率,為未來接入更多的連接請求法,把問題模型化為線性規(guī)劃問題,求解優(yōu)化解,然而優(yōu)化解留有余地.的求解比較困難,并且業(yè)務(wù)流要被拆分到多條顯式路徑上傳.Wang等[12]為了減小擁塞,以最小化最大帶寬利用率為TE目標(biāo),并提出了兩種解決方法.一種是拆分業(yè)務(wù)基于以上考慮,最小化最大帶寬利用率的TE路由問題流可以不用拆分,問題被可以描述如下輸.第二種是非拆分的方法,即業(yè)務(wù):模型化為整數(shù)規(guī)劃問題,這個(gè)問題具有NP難度,作者提出了給定一個(gè)網(wǎng)絡(luò)G(V,E),源節(jié)點(diǎn)∈sV,目的節(jié)點(diǎn)∈dV,對啟發(fā)式算法——基于拆分優(yōu)化解的重新法需要在第一種線性規(guī)劃所得拆分解的基礎(chǔ)上做重新路由優(yōu)化,實(shí)現(xiàn)起來也非常復(fù)雜.本文也以最小化最大帶寬利用率為路由算法,但是該算于P∈鏈路容量∈剩余帶寬R∈已知要求(i,j)E,CR,R,++ijij找到一條從s出發(fā),到目的節(jié)點(diǎn)d的路徑P,使之在滿足帶寬約束Bandwidth(P)≥b的前提下,路徑P的帶寬利用率U(P)最TE目標(biāo),通過一種對Dijkstra算法進(jìn)行改進(jìn)的方法來進(jìn)行求解.小,即滿足(P)=Min(()).PU∈3網(wǎng)絡(luò)模型化為一有向賦權(quán)圖和鏈路集,節(jié)點(diǎn)數(shù)為n,鏈路數(shù)為m.對于每條鏈路(i,j)∈E,C→R+表示鏈路的容量,R→R表示鏈路的剩余帶寬,請求表示為(,,),其中s,dG=(V,E),V,E分別表示本算法是在Dijkstra算法的基礎(chǔ)上為度量,尋找源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的“度量最小的路徑”.如果令節(jié)點(diǎn)i的代價(jià)cost(i)表示從源節(jié)點(diǎn)s到節(jié)點(diǎn)i的最大帶寬利用率,則上述問題是一個(gè)-,以最大帶寬利用率節(jié)點(diǎn)集+ijR+是正實(shí)數(shù)集.新到來的呼叫ijsdb,s∈V,d∈V,b為呼叫請求的帶寬數(shù).d之間存在多條路徑P,所有MinMax問題,cost(i)=min(cost(i),max(cost(j),U)).分別為源和目的節(jié)點(diǎn)假設(shè)給定的源節(jié)點(diǎn)s和目的節(jié)點(diǎn)j∈Vjil算法分為兩個(gè)階段進(jìn)行.首先,進(jìn)行初始化的工作.刪除不滿足帶寬要求的鏈路構(gòu)造一個(gè)新圖′,以后路徑的尋找就的可用帶寬是指該在這個(gè)新圖中進(jìn)行,并對算法運(yùn)行做初始值的設(shè)定.第二個(gè)階中,每一次循環(huán)都要找到k的路徑帶寬利用率最小的路徑,直到節(jié)點(diǎn)即為目的節(jié)點(diǎn)d為止.這些路徑構(gòu)成給出幾個(gè)定義1.路徑的可用帶寬:一條路徑P一個(gè)集合5(,)={,,…,P}.我們首先sdPP21lG.l段就是具體的尋路過程.在這個(gè)過程路徑的瓶頸帶寬,也就是路徑上所有鏈路可用帶寬的最小值,源節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)即k(P)=.,Bandwidthmin對網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)i都定義一個(gè)結(jié)構(gòu)Node[i],該結(jié)構(gòu)l(,)∈2.鏈路帶寬利用率:對于P(i,j)∈E,鏈路(i,j)接入包含三個(gè)元素,分別為minU、label和pre,其中minU記錄從源424小2005年節(jié)點(diǎn)s到節(jié)點(diǎn)i的最小U;label表示節(jié)點(diǎn)i是否已經(jīng)處理過,如果已經(jīng)處理,label=True,否則label=False;pre表示到達(dá)節(jié)點(diǎn)i的前一跳節(jié)點(diǎn).算法具體描述如下:出,開始時(shí)網(wǎng)絡(luò)中的連接數(shù)比較少,鏈路上的負(fù)載比較輕,表1實(shí)驗(yàn)數(shù)ANBdemand25demand10MH0.27MMLU0.27123451.如果R<b,刪除鏈路(,),得到圖G′=(V,E′).2030405048710.430.600.800.970.400.530.670.822.對圖G′中的每條鏈路(i,j)計(jì)算帶寬利用率U.3.初始化.對Pi,j∈V,如果(i,j)|E′,U=0.Node[s].minU=ij960,Node[s].label=True.對Pi∈V-{s},Node[i].pre=-1,Node[i].minU=∞,Node[i].label=False.k=s.4.do{120兩種算法的A值基本相同.隨著連接數(shù)的增多,鏈路上的負(fù)載do對每個(gè)5.節(jié)點(diǎn)i≠s{逐漸加重,隨之A值也逐漸加大,但是本算法中A值的增加要6.≠0且Node[i].label=Falsethen7.fmax(Node[k].minU,U)<Node[i].minUfki比MH算法中的小.這說明隨著鏈路負(fù)載的加重,本算法在一kithen定程度上避免了業(yè)務(wù)流走負(fù)載重的鏈路,起到了均衡負(fù)載分8.Node[i].minU=max(Node[k].minU,U)ki9.10.endf11.endf12.}enddo13.k=0,mn=∞14.do對每個(gè)節(jié)點(diǎn)i≠s{經(jīng)常使用的方法.本文提出了一種對Dijkstra算法進(jìn)行改進(jìn)15.fNode[i].label=False且Node[i].pre=k布的作用.6為了減小擁塞最小化最大帶寬利用率是實(shí)現(xiàn)路由,TENode[i].minU<mnthen.,的最小化最大帶寬利用率算法在算法搜尋路徑的過程中將16.mn=Node[i].MinU算法中的以路徑代價(jià)最小為目標(biāo)更改為以最小17.k=i18.endf19.}enddo20.Node[k].label=True21.}while(k≠d)原來Dijkstra化最大帶寬利用率為目標(biāo)最后通過仿真對本算法和.,,最小跳數(shù)算法在接的連接請求下的最大帶寬利用率的入不同數(shù)量.,,變化情況進(jìn)行了比較結(jié)果證明隨著連接數(shù)的增多本算法22.把從節(jié)點(diǎn)s到d的pre中存儲(chǔ)的節(jié)點(diǎn)連起來,即得到節(jié)點(diǎn)s到在一定程度上避免了對部分鏈路的過度使用,起到了均衡負(fù)d的路徑.載分布的作用.在該算法中,第5行到12行和第14行到19行的循環(huán)都分別需要運(yùn)行中的節(jié)點(diǎn)數(shù)),而第4行到21-1次(其中是網(wǎng)絡(luò)References:nn[1]XaoX,HannanA,BaileyB,NiL.Trafficengineeringwith行的外循環(huán)最多也要運(yùn)行n-1次,因此整個(gè)算法的時(shí)間復(fù)雜MPLSntheinternet[J].IEEENetworkmagazine,Mar.度為((-1)2(-1)),即為On().2Onn*2000.[2]AwducheDetal.RequirementsfortrafficengneeringOverMPLS[S].IETFRFC2702,Sept1999.5[3]AwducheDetal.Overviewandprinciplesofnternettrafficen-對如圖1所示的網(wǎng)絡(luò)拓?fù)溥M(jìn)行了實(shí)驗(yàn)仿真.假設(shè)每gineering[S].IETFRFC3272,May2002.我們[4]GargiBanerjee,DeepnderSidhu.Multi-constrainedpathcom-putationfortrafficengneeringnMPLSnetworks[C].In:Pro-ceedingsofSCSSPECTS,2001.[5]GargiBanerjee,DeepinderSidhu.ComparativeanalyofpathcomputationtechniquesforMPLStrafficengineering[J].Com-puterNetworks,2002,40(1):149-165.[6]RekhterYetal.Ccosystem?sTagswitchingarchitectureovervew[S].RFC2105,Feb.1997.[7]WangYu-fei,WangZheng.Explicitroutingforinternettrafficengineering[J].IEEEINFOCOM?99,582-588.圖1[8]GuerinR.ArelOrda,WilliamsD.QosroutingmechanismsandOSPFextensions[C].InProceedingsof2ndGlobalInter-個(gè)節(jié)點(diǎn)了解整個(gè)網(wǎng)絡(luò)拓?fù)浜玩溌窢顟B(tài)信息.網(wǎng)絡(luò)中所有鏈路netMnconference(ontwithGlobecom?97),Nov