基于網(wǎng)絡(luò)最大流的MPLS流量工程動態(tài)路由算法

　　1 引言

　　動態(tài)路由算法是MPLS流量工程中最關(guān)鍵的技術(shù)之一[1，2]，建立有帶寬保證的路由問題已經(jīng)有大量的前期工作，其中代表性的路由算法主要有最小跳算法(min-hop aIgorithm，MHA)、最寬最短路徑算法(widestshortest path，WSP)[3]、最短最寬路徑算法(shortestest widest palh，SWP)[4,5]、以及最小干擾路徑算法(minimuminterference routing algorithm，MIRA)[6，7]等。

　　MHA算法采用的是基于目的地最短路徑路由,就是在網(wǎng)絡(luò)源節(jié)點與目的節(jié)點之間查找一條具有最小跳數(shù)的可達路徑。此算法會導(dǎo)致多條最短路徑都選用同一條鏈路而發(fā)生擁塞。WSP與SWP算法基本相似,WSP算法是在多條跳數(shù)最小的侯選路徑中選擇一條可用帶寬最多的一條路徑：SWP是在多條可用帶寬最大的路徑中選擇一條跳數(shù)最小的路徑進行路由。這兩種算法屬于貪婪算法，并且對同一節(jié)點對產(chǎn)生多條最小跳或是最大帶寬的幾率并不是很大，因此算法的效果并不理想。比較復(fù)雜的影響力最大的算法包括最小干擾路由算法(MIRA)，主要思想是在為當(dāng)前源、目的結(jié)點對選擇LSP時盡量減少對未來節(jié)點對建立鏈接請求的影響,從而優(yōu)化網(wǎng)絡(luò)性能。但是從MIRA算法對關(guān)鍵鏈路的定義來看,此算法只定義了屬于某節(jié)點對的最小割的鏈路為關(guān)鍵鏈路,并沒有考慮非關(guān)鍵鏈路對未來建立鏈路請求的影響，并且算法復(fù)雜度高。

　　2 系統(tǒng)模型及算法描述

　　2.1 網(wǎng)絡(luò)模型描述

　　網(wǎng)絡(luò)路由算法研究通常借助圖論描述網(wǎng)絡(luò)模型,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以無向加權(quán)連通圖G=(V,E，B)表示，V(|V|=N)表示路由節(jié)點集合：N表示節(jié)點數(shù)目，E(|E|=M)表示鏈路集合，M表示鏈路數(shù)目;B表示網(wǎng)絡(luò)中鏈路容量的集合。用L表示可能產(chǎn)生建立LSP請求的進出路由器對的集合。需要建立LSP鏈接請求r(s。d，b)表示，s和d分別表示業(yè)務(wù)流的入口和出口節(jié)點。b表示需要鏈接的業(yè)務(wù)流(s,d)的需求帶寬,R1表示鏈路I的剩余帶寬。

　　2.2 算法描述

　　此前大多數(shù)有帶寬保證的路由算法基本只考慮鏈路剩余帶寬而沒有考慮鏈路的帶寬利用率,以至于其他條件都相同的情況下,帶寬相同的兩條鏈路同等對待,而實際上這兩條鏈路的負(fù)載相差很大，因此建立鏈路之后對網(wǎng)絡(luò)的影響截然不同。

　　定義：鏈路帶寬利用率A1：對任意節(jié)點對(s，d)，接受請求帶寬為b的鏈路請求之后的鏈路帶寬利用率為：

　　鏈路帶寬利用率反應(yīng)鏈路當(dāng)前的負(fù)載情況，也可反應(yīng)建立LSP請求后的鏈路負(fù)載情況，A1的值越小說明建立鏈接對以后的LSP鏈接請求的影響越小，當(dāng)A1 值接近為1時說明鏈路的負(fù)載非常重，接入新的鏈路請求的動態(tài)成本非常高。

　　MBGRA算法的核心思想是先計算各個鏈路的權(quán)重值，而后用最短路由算法查找權(quán)重最小的路徑。此算法在計算鏈路權(quán)值時分為離線階段和在線階段。離線階段計算的鏈路初始權(quán)值w(l)是靜態(tài)的，在網(wǎng)絡(luò)拓?fù)湟欢ǖ臈l件下不發(fā)生變化，只有當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時才需要重新計算。

　　2.2.1 離線階段

　　對任意給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對任意LSP請求I(s,d,b)，首先計算(s,d)∈L的結(jié)點對之間的網(wǎng)絡(luò)最大流為Fsd。由于網(wǎng)絡(luò)最大流路徑的選擇不唯一，因此我們計算出網(wǎng)絡(luò)最大流的所有可能組合，對任意的鏈路的使用無疑將改變網(wǎng)絡(luò)最大流，因此用fsd1表示在離線狀態(tài)下節(jié)點對(s,d)∈L之間的網(wǎng)絡(luò)最大流中通過鏈路L的流量,我們定義此鏈路對(s，d)∈L之間的網(wǎng)絡(luò)最大流的貢獻量為,此值反映了鏈路L對將要建立的(s,d)∈L之間的鏈路請求的相對重要程度。計算單個鏈路I相對結(jié)點對(s，d)∈L的鏈路權(quán)值為：

　　其中，F(xiàn)sd代表路由節(jié)點對(s，d)之間的網(wǎng)絡(luò)最大流，fsd1表示路由出入節(jié)點(s，d)∈E之間的網(wǎng)絡(luò)最大流中通過鏈路I的部分，n表示在路由結(jié)點對(s，d)之間的網(wǎng)絡(luò)最大流路由數(shù)目.m表示這n種網(wǎng)絡(luò)路由數(shù)目中通過鏈路I的次數(shù)。計算鏈路I的初始權(quán)值W(I)為：

　　2.2.2 在線階段

　　對于給定的網(wǎng)絡(luò)拓?fù)?在離線階段已經(jīng)計算出單條鏈路的初始權(quán)值W(I)，定義單條鏈路的及時權(quán)值為：

　　在我們的研究過程中發(fā)現(xiàn)，鏈路帶寬利用率AL對鏈路權(quán)值的影響并沒有預(yù)想的那樣大，因此我們給Al開方來定義鏈路的及時權(quán)值。此定義鏈路權(quán)值不僅定量分析了單個鏈路對網(wǎng)絡(luò)最大流的貢獻量，并且考慮了單條鏈路的負(fù)載情況,因此MBGRA算法在選擇路由路徑的過程中可以更好的優(yōu)化網(wǎng)絡(luò)資源，建立更加合理的路由路徑。

　　對到達的任意LSP鏈接請求r(s,d,b)表示，s和d分別表示業(yè)務(wù)流的入口和出口節(jié)點，b表示需要鏈接的業(yè)務(wù)流(s，d)的需求帶寬，利用式(4)計算每條具體鏈路的鏈路權(quán)值,采用Diikstra's算法選擇權(quán)值最小的路徑建立LSP鏈接,并更新剩余網(wǎng)絡(luò)帶寬參數(shù)。

　　2.3 算法流程

　　對已經(jīng)給定的網(wǎng)絡(luò)拓?fù)?，根?jù)式(3)計算單個鏈路的初始權(quán)值w(I)對任意LSP鏈接請求，處理步驟如下：

　　STEP1：檢測光路請求，如果光路請求為建立鏈路鏈接則執(zhí)行STEP3，如果請求為拆除鏈路鏈接則執(zhí)行STEP2：

　　STEP2：拆除LSP請求的鏈路，并更新網(wǎng)絡(luò)剩余帶寬：

　　STEP3：對于請求建立r(s,d,b)的路由路徑請求，對于單個鏈路節(jié)點。確定鏈路剩余帶寬R1，根據(jù)式(1)計算鏈路帶寬利用率A1;

　　STEP4：刪除網(wǎng)絡(luò)中剩余帶寬R1

　　STEP5：根據(jù)鏈路的初始權(quán)值以及鏈路帶寬利用率計算每條鏈路I∈E的及時鏈路權(quán)值W(I);

　　STEP6：以W(I)作為鏈路J的權(quán)重，使用Dijkstra's算法查找權(quán)值最小的路徑，建立鏈路鏈接;

　　SETP7：修改網(wǎng)絡(luò)剩余帶寬參數(shù)，準(zhǔn)備處理下個LSP請求。

　　3 仿真分析研究

　　為了客觀地分析MBGRA算法的性能，我們采用Kodialarn研究工作中使用的仿真網(wǎng)絡(luò)拓?fù)鋱D進行仿真分析[6].稱為MIRAnet網(wǎng)絡(luò)拓?fù)洌Y(jié)構(gòu)如圖1所示。

　　仿真中使用了15個節(jié)點的無向圖網(wǎng)絡(luò)拓?fù)?，即每條鏈路都是雙向的，為了更客觀地反映實際網(wǎng)絡(luò)結(jié)構(gòu).把網(wǎng)絡(luò)拓?fù)渲械逆溌啡萘糠譃閮深?，用?xì)線標(biāo)識的鏈路帶寬容量為1200單位.代表OC-12，粗線標(biāo)識的網(wǎng)絡(luò)鏈路帶寬容量為4800單位,代表OC-48。LSP鏈接請求的

　　入口路由器節(jié)點在S1-S4之間隨機選擇,出口路由器節(jié)點在D1-D4之間隨機選擇,請求帶寬需求服從均勻分布。仿真過程分為靜態(tài)鏈接請求和動態(tài)鏈接請求兩種,在靜態(tài)請求中成功建立鏈接的LSP的生命是永久性的,在動態(tài)請求中LSP的到達按泊松分布,持續(xù)時間按指數(shù)分布。

　　3.3.1 靜態(tài)鏈接

　　在靜態(tài)鏈接試驗中每種路由算法做50次建立12000條LSP請求的試驗,并且從零開始每增加500次LSP做一次數(shù)據(jù)統(tǒng)計,根據(jù)試驗結(jié)果得出的LSP數(shù)目與鏈接拒絕率的曲線關(guān)系如圖2。

　　從圖中可以看出在網(wǎng)絡(luò)負(fù)載較低時,三種算法的路由性能沒有明顯差別,但當(dāng)鏈接數(shù)目增加到3000時MHA算法的拒絕率從零開始上升,而MIRA算法和MBGRA算法是在5000次請求之后才開始有拒絕鏈接。在7000次路由之后MBGRA算法的性能開始優(yōu)于MIRA算法,在12000次時MHA算法的性能明顯低于后兩種算法,并且依據(jù)圖形走勢有繼續(xù)惡化的趨勢。由圖2明顯看出MBGRA算法在路由性能上明顯好于MHA算法,并在高負(fù)載情況下性能優(yōu)于MIRA算法,因此更有利于均衡網(wǎng)絡(luò)負(fù)載。

　　為了更進一步驗證MBGRA算法的性能,直接在MIRAnet網(wǎng)絡(luò)中加載5500個LSP請求,連續(xù)做20次試驗,記錄三種算法的拒絕數(shù)目,從圖3可以直觀的看出MHA算法的拒絕數(shù)目一直處于最高,而MBGRA算法的拒絕數(shù)目一直處于最低層,性能高于MIRA算法。

　　3.3.2 動態(tài)鏈接

　　上面通過仿真試驗證實在靜態(tài)網(wǎng)絡(luò)中MBGRA算法優(yōu)化網(wǎng)絡(luò)資源的優(yōu)越性.在本節(jié)我們將在動態(tài)接人條件下仿真MBGRA算法的性能。假設(shè)LSP到達以平均速率為R的泊松分布到達每一個節(jié)點對,持續(xù)時間符合I/Q的指數(shù)分布。加載1000000 LSP在MIRAnet網(wǎng)絡(luò)中,并且假設(shè)R/Q=1500。

　　通過圖4的統(tǒng)計數(shù)據(jù)顯示,在MIRAnet網(wǎng)絡(luò)動態(tài)請求過程中MHA算法的拒絕率明顯最高,MIRA算法比MHA算法性能好,但是拒絕率也高于MBGRA算法,MBGRA算法的拒絕率一直處于最低,因此此算法在減少網(wǎng)絡(luò)擁塞率和優(yōu)化網(wǎng)絡(luò)資源上有優(yōu)越的性能,并且鏈路復(fù)雜度低。

　　4 結(jié)束語

　　本文針對MPLS技術(shù)提出了一種高效能的有帶寬保證的動態(tài)負(fù)載均衡路由算法MBGRA。通過靜態(tài)鏈接以及動態(tài)鏈接的仿真試驗表明MBGRA算法在均衡網(wǎng)絡(luò)負(fù)載、優(yōu)化網(wǎng)絡(luò)資源方面的有良好的性能。