1 引言

　　動(dòng)態(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é)點(diǎn)與目的節(jié)點(diǎn)之間查找一條具有最小跳數(shù)的可達(dá)路徑。此算法會(huì)導(dǎo)致多條最短路徑都選用同一條鏈路而發(fā)生擁塞。WSP與SWP算法基本相似,WSP算法是在多條跳數(shù)最小的侯選路徑中選擇一條可用帶寬最多的一條路徑：SWP是在多條可用帶寬最大的路徑中選擇一條跳數(shù)最小的路徑進(jìn)行路由。這兩種算法屬于貪婪算法，并且對(duì)同一節(jié)點(diǎn)對(duì)產(chǎn)生多條最小跳或是最大帶寬的幾率并不是很大，因此算法的效果并不理想。比較復(fù)雜的影響力最大的算法包括最小干擾路由算法(MIRA)，主要思想是在為當(dāng)前源、目的結(jié)點(diǎn)對(duì)選擇LSP時(shí)盡量減少對(duì)未來節(jié)點(diǎn)對(duì)建立鏈接請(qǐng)求的影響,從而優(yōu)化網(wǎng)絡(luò)性能。但是從MIRA算法對(duì)關(guān)鍵鏈路的定義來看,此算法只定義了屬于某節(jié)點(diǎn)對(duì)的最小割的鏈路為關(guān)鍵鏈路,并沒有考慮非關(guān)鍵鏈路對(duì)未來建立鏈路請(qǐng)求的影響，并且算法復(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é)點(diǎn)集合：N表示節(jié)點(diǎn)數(shù)目，E(|E|=M)表示鏈路集合，M表示鏈路數(shù)目;B表示網(wǎng)絡(luò)中鏈路容量的集合。用L表示可能產(chǎn)生建立LSP請(qǐng)求的進(jìn)出路由器對(duì)的集合。需要建立LSP鏈接請(qǐng)求r(s。d，b)表示，s和d分別表示業(yè)務(wù)流的入口和出口節(jié)點(diǎn)。b表示需要鏈接的業(yè)務(wù)流(s,d)的需求帶寬,R1表示鏈路I的剩余帶寬。

　　2.2 算法描述

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

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

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

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

　　2.2.1 離線階段

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

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

　　2.2.2 在線階段

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

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

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

　　2.3 算法流程

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

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

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

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

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

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

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

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

　　3 仿真分析研究

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

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

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

　　3.3.1 靜態(tài)鏈接

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

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

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

　　3.3.2 動(dòng)態(tài)鏈接

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

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

　　4 結(jié)束語

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