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

　　1 引言

　　動(dòng)態(tài)路由算法是MPLS流量工程中最關(guān)鍵的技術(shù)之一[1，2]，建立有帶寬保證的路由問(wèn)題已經(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ò )源節點(diǎn)與目的節點(diǎn)之間查找一條具有最小跳數的可達路徑。此算法會(huì )導致多條最短路徑都選用同一條鏈路而發(fā)生擁塞。WSP與SWP算法基本相似,WSP算法是在多條跳數最小的侯選路徑中選擇一條可用帶寬最多的一條路徑：SWP是在多條可用帶寬最大的路徑中選擇一條跳數最小的路徑進(jìn)行路由。這兩種算法屬于貪婪算法，并且對同一節點(diǎn)對產(chǎn)生多條最小跳或是最大帶寬的幾率并不是很大，因此算法的效果并不理想。比較復雜的影響力最大的算法包括最小干擾路由算法(MIRA)，主要思想是在為當前源、目的結點(diǎn)對選擇LSP時(shí)盡量減少對未來(lái)節點(diǎn)對建立鏈接請求的影響,從而優(yōu)化網(wǎng)絡(luò )性能。但是從MIRA算法對關(guān)鍵鏈路的定義來(lái)看,此算法只定義了屬于某節點(diǎn)對的最小割的鏈路為關(guān)鍵鏈路,并沒(méi)有考慮非關(guān)鍵鏈路對未來(lái)建立鏈路請求的影響，并且算法復雜度高。

　　2 系統模型及算法描述

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

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

　　2.2 算法描述

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

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

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

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

　　2.2.1 離線(xiàn)階段

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

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

　　2.2.2 在線(xiàn)階段

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

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

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

　　2.3 算法流程

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

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

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

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

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

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

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

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

　　3 仿真分析研究

　　為了客觀(guān)地分析MBGRA算法的性能，我們采用Kodialarn研究工作中使用的仿真網(wǎng)絡(luò )拓撲圖進(jìn)行仿真分析[6].稱(chēng)為MIRAnet網(wǎng)絡(luò )拓撲，結構如圖1所示。

　　仿真中使用了15個(gè)節點(diǎn)的無(wú)向圖網(wǎng)絡(luò )拓撲，即每條鏈路都是雙向的，為了更客觀(guān)地反映實(shí)際網(wǎng)絡(luò )結構.把網(wǎng)絡(luò )拓撲中的鏈路容量分為兩類(lèi)，用細線(xiàn)標識的鏈路帶寬容量為1200單位.代表OC-12，粗線(xiàn)標識的網(wǎng)絡(luò )鏈路帶寬容量為4800單位,代表OC-48。LSP鏈接請求的

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

　　3.3.1 靜態(tài)鏈接

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

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

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

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

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

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

　　4 結束語(yǔ)

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