WDM光網(wǎng)絡(luò)中固定備選路由算法的實(shí)現(xiàn)

摘要:路由問題是WDM全光網(wǎng)絡(luò)中的一個核心問題。該文介紹了常用的固定備選路由FAR算法(前K條最短路由算法)的實(shí)現(xiàn)過程，并與固定路由FR算法性能進(jìn)行了比較。仿真結(jié)果表明，能有效降低網(wǎng)絡(luò)的阻塞率，提高網(wǎng)絡(luò)的性能。

關(guān)鍵詞:WDM光網(wǎng)絡(luò);路由;優(yōu)化;阻塞率

中圖分類號:TP393文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)32-8883-02

The Realization of Fixed-alternate Routing Algorithm in WDM Networks

HUANG Ke-jun， GONG Wen-fang

(West Branch of Zhejiang University of Technology， Quzhou 324000， China)

Abstract: The problem of routing is the core in WDM networks. As for the fixed-alternate routing algorithm， the traditional K-shortest path RWA algorithm is studied and compared with the fixed routing algorithm. Simulation results show that the algorithms can significantly reduce blocking probability and improve network performance.

Key words: WDM networks; routing; optimize; blocking probability

在以波分復(fù)用(Wavelength Division Multiplexing，WDM)技術(shù)為基礎(chǔ)的全光網(wǎng)絡(luò)中，如何在鏈路資源和波長資源有限的條件下，最大限度地提高網(wǎng)絡(luò)的吞吐量，提高網(wǎng)絡(luò)資源的利用率，改善網(wǎng)絡(luò)的阻塞性能，是人們關(guān)注的一個焦點(diǎn)，路由選擇和波長分配(Routing and Wavelength Assignment，RWA)是其中的一個核心問題，合理的路由和波長分配，不僅可以增強(qiáng)網(wǎng)絡(luò)資源的利用率，而且可以提高網(wǎng)絡(luò)的整體性能。RWA問題中的選路和波長分配是一個不可分割的問題。但僅僅其中的波長分配問題就是一個NP_C(非確定型多項(xiàng)式- 完全)問題[1-2]，要在合理的運(yùn)算時(shí)間內(nèi)解決大型網(wǎng)絡(luò)的RWA問題常常是不可能的。為便于研究，將RWA問題強(qiáng)行拆成兩個獨(dú)立的子問題，選路子問題和波長分配子問題，分別加以解決，即先計(jì)算路由，然后再為路徑上的每一鏈路通過一定的策略分配波長。

關(guān)于路由和波長分配，目前已有不少的文獻(xiàn)。在路由選擇問題中，通常有三種路由選擇策略:固定路由(FR)策略、固定備選路由(FAR)策略和自適應(yīng)備選路由(AR)策略[3]。

固定備選路由的基本思想是為每個節(jié)點(diǎn)對預(yù)先確定多條備選路由，并按一定的優(yōu)先級順序排列。排在最前面的稱為主路由，其它的視為備選路由。當(dāng)業(yè)務(wù)到達(dá)時(shí)，按排列順序依次分配給業(yè)務(wù)，當(dāng)業(yè)務(wù)阻塞時(shí)，選擇次優(yōu)路由。

假定網(wǎng)絡(luò)中已建立了一組光路，嘗試在預(yù)定的多條路由中選擇合適的路由和波長，為新到達(dá)的呼叫建立光路，使阻塞率最小，同時(shí)不會對已有光路產(chǎn)生任何影響。在選擇路由和波長時(shí)，簡單的方法就是使用找到的第一條有空閑波長的最短路由，然后再進(jìn)行波長分配，同時(shí)考慮選路和波長分配算法能夠取得較好性能。

固定選路(FR)[3]:這是最直接最簡單的選路算法，網(wǎng)絡(luò)總為同一節(jié)點(diǎn)對提供固定不變的光通道。選路是事先進(jìn)行的，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)已知后，按照標(biāo)準(zhǔn)最短路徑(比如Dijkstra算法)為每個節(jié)點(diǎn)對分配固定的光通道。網(wǎng)絡(luò)運(yùn)行中，節(jié)點(diǎn)對之間的通道連接總是建立在預(yù)定好的路由上。如圖1所示，節(jié)點(diǎn)1到節(jié)點(diǎn)3的工作路由依次經(jīng)過1、2、3節(jié)點(diǎn)。這種方法雖然簡單，但卻需要較多的波長資源。在動態(tài)流量的情況下，如果出現(xiàn)波長沖突，則會導(dǎo)致嚴(yán)重的流量阻塞。因?yàn)闆]有替代路由，所以這種算法下網(wǎng)絡(luò)不具備鏈路故障恢復(fù)能力。

圖1固定選路法圖2固定-備選選路法

固定-備選路由(FAR)[4-5]:網(wǎng)絡(luò)中每個節(jié)點(diǎn)維護(hù)一張路由表，里面羅列著它到其他節(jié)點(diǎn)的一系列路由，其中包括作為工作光通道的最短路由和作為備選光通道的路由。備選路由一般不跨越工作路由的鏈路段，即它們在物理上是分離的，所以這種機(jī)制又叫做鏈路分離或邊分離機(jī)制。當(dāng)節(jié)點(diǎn)收到連接請求時(shí)，按照工作路由建立光通路，若工作路由已被占用或失效，則在備選路由中選擇次短路由。如圖2所示，節(jié)點(diǎn)1到3的備選路由依次經(jīng)過1、4、5、3節(jié)點(diǎn)。以次類推還可以選擇第三短路由，如依次經(jīng)過1、4、5、6、3節(jié)點(diǎn)的備選路由。這種選路法的優(yōu)點(diǎn)是簡單且具有鏈路故障恢復(fù)機(jī)制，與固定選路法相比，流量被阻塞的概率顯著減小。

常用的固定備選路由算法是前K條最短路徑路由算法，即選取K條最短路徑，在為多條光路的一組路由分配波長時(shí)，若發(fā)生波長數(shù)不夠用的情況，則通過置換備選路由構(gòu)成另一組路由，再分配波長法，直到完成要求。下面加以詳細(xì)敘述。

1 問題描述

前K條最短路徑的問題是:設(shè)有賦權(quán)圖G(V，E)及其上給定的兩個頂點(diǎn)vi和vj，r為vi和vj之間的一條路徑，記其長度為d(r)。

R(G，vi，vj):由vi和vj之間的所有互不相同的路徑組成的集合，稱為G上vi和vj之間的路徑集合。

若按路徑長度值大小將其排列得r1，r2，…，rk，d(r1)≤d(r2) ≤…≤ d(rk)，則稱r1為G上vi和vj之間的第1條最短路徑，d1為其長度;r2為第2條最短路徑，d2為其長度;rk為第k條最短路徑，dk為其長度。求解G上vi和vj之間的第1~K(K≤M)最短路徑的問題就稱為前K條最短路徑問題。

2 算法設(shè)計(jì)分析

Dijkstra算法只能求解第1條最短路徑，為了能求得第2，…，K最短路徑，將前K條最短路徑問題轉(zhuǎn)換為狹義最短路徑問題加以求解。

賦權(quán)圖G(V，E)上兩頂點(diǎn)間的任一路徑都必然是它的某一子圖G' (V'，E')上相同頂點(diǎn)間的第1最短路徑，可將一個圖G(V，E)上兩頂點(diǎn)間的第2，…，K最短路徑轉(zhuǎn)換為第1最短路徑加以求解。將第1最短路徑r1=v0e1v1，…，vn-1envn上的每一條邊從圖G的邊集中刪除就可得到一批子圖Gk，K=1，…，n，這些子圖路徑集合的并集就等于非第1最短路徑集合{r2，…，rk}。同樣，可將路徑集合Rk，K=1，…，n分離為第1和非第1最短路徑。將所有路徑全部求出，然后按路徑長度值大小對其進(jìn)行排序即可求解前K條最短路徑問題。

根據(jù)需要定義邊、路徑、圖等結(jié)構(gòu)類型，用于表示邊、路徑、圖等，用Paths數(shù)組存放路徑類型指針變量，其大小設(shè)為N，最后經(jīng)過排序的結(jié)果就存放在這里，與此對應(yīng)的是Edge數(shù)組，它存放以邊為元素的集合變量，對應(yīng)的含義為

Edge[i] G'(V，E')Paths[i]=r

算法進(jìn)行N次循環(huán)，第i次循環(huán)確定第i最短路徑，循環(huán)中先選擇第i-1最短路徑(即Paths[i-1])，根據(jù)Edge[i-1]和Paths[i-1]中的邊產(chǎn)生若干子圖，求取其上的第1最短路徑作為候選路徑存放入Paths[k]中，k=i，…，N。每次存入新候選路徑時(shí)采用排序算法插入到正確位置，這樣Paths數(shù)組中元素始終保持按路徑長度值大小進(jìn)行存放，Paths[i]在循環(huán)結(jié)束時(shí)就指向第i最短路徑。

從算法描述可以看出，對于G(V，E)，K是所要求的最短路徑數(shù)目，與圖的大小無關(guān)，而且通常較小，可以為常數(shù)量級;EdgeNum是Paths[i-1]邊的數(shù)目，其上限是邊的總數(shù)目，由于Dijkstra算法的時(shí)間復(fù)雜度為O(n2)，因此總的時(shí)間復(fù)雜度為O(e*n2)，其中e和n分別為圖G(V，E)的邊和頂點(diǎn)的數(shù)目。

3 計(jì)算機(jī)仿真及結(jié)果分析

該文采用計(jì)算機(jī)仿真的方法對固定路由和固定-備選路由進(jìn)行了仿真分析。用于仿真的拓?fù)浣Y(jié)構(gòu)為3×3格型環(huán)網(wǎng)，共9個節(jié)點(diǎn)，18條鏈路。我們比較了固定路由和一條、兩條、三條備選路由下業(yè)務(wù)阻塞率隨波長和負(fù)載的變化情況。

仿真時(shí)采用的業(yè)務(wù)模型為泊松業(yè)務(wù)模型，即光路鏈接請求按參數(shù)λ的泊松過程到達(dá)網(wǎng)絡(luò)，即全網(wǎng)的總到達(dá)率為λ，所有節(jié)點(diǎn)對間的業(yè)務(wù)強(qiáng)度都相同。允許一對節(jié)點(diǎn)間同時(shí)存在多條光通道，光通道建立以后的保持時(shí)間服從均值為1/μ的負(fù)指數(shù)分布。到達(dá)網(wǎng)絡(luò)的總負(fù)載為ρ=λ/μ。一旦連接請求被拒絕，則立即被丟棄，即無等待隊(duì)列。為了方便，采用First-Fit波長分配策略。

圖3給出了3×3格型網(wǎng)的單纖情況下，固定路由和固定備選路由在不同波長數(shù)W下的阻塞率性能比較。設(shè)定耽擱波長承受的負(fù)載都相同，為6個愛爾蘭，即ρ/W=6。對于3×3格型網(wǎng)來說，兩節(jié)點(diǎn)之間都存在4條基于鏈路無關(guān)的路由，因此我們比較了固定路由和一條、兩條、三條備選路由的情況。從圖中可以看出，對于單纖網(wǎng)絡(luò)，在波長數(shù)較小時(shí)，一條備選路由對阻塞率性能的提高最大，隨著波長數(shù)的增加，兩條、三條備選路由對阻塞率性能的改善程度變大。因此對于具有多條備選路由的網(wǎng)絡(luò)中，可以根據(jù)實(shí)際情況，選用最為合理的備選路由的個數(shù)。

為了更好地表現(xiàn)出波長變換增益，圖4給出了3×3格型網(wǎng)中，采用不同選路策略時(shí)，隨著業(yè)務(wù)強(qiáng)度的變化，在不同波長數(shù)目下的阻塞率曲線圖。

從圖4的結(jié)果來看，使用固定備選路由能有效地降低網(wǎng)絡(luò)的阻塞率，特別體現(xiàn)在低負(fù)載的情況下更為明顯，波長變換增益也明顯優(yōu)于固定路由。這是因?yàn)镕R選取的是最短路徑，所以跳數(shù)最短，波長變換增益最小;FAR在最短路由上無資源時(shí)引入另一條長的路由，從而使得網(wǎng)絡(luò)中的平均路由跳數(shù)提高，波長變換增益也隨之提高。

因此，從模擬結(jié)果可以看出，為節(jié)點(diǎn)對提供多條供選擇的備選路由會有效改善網(wǎng)絡(luò)性能，提高業(yè)務(wù)分配的成功率，減小網(wǎng)絡(luò)的阻塞概率。備選路由選擇策略的性能優(yōu)于固定路由的選路策略;隨網(wǎng)絡(luò)資源增加，備選路由選路策略的優(yōu)越性更明顯，阻塞率進(jìn)一步減小。

4 小結(jié)

該文對常用的固定備選路由FAR算法(前K條最短路由算法)的實(shí)現(xiàn)過程進(jìn)行了詳細(xì)的介紹，并與固定路由FR算法性能進(jìn)行了比較。仿真結(jié)果表明，該算法的性能優(yōu)于固定路由的選路策略，能有效降低網(wǎng)絡(luò)的阻塞率，提高網(wǎng)絡(luò)的性能。

參考文獻(xiàn):

[1] Thomas E. Stern， Krishna Bala. Multiwavelength optical networks: a layered approach. Boston: Addison-Wesley Longman Publishing Co.， Inc.， 1999.

[2] Chlamtac I.， Ganz A.， Karmi G. Lightpath communications: an approach to high bandwidth optical WANs. IEEE Trans's Comm. Jul 1992， 40(7): 1171-1182.

[3] Bertsekas D.，Gallager R. Data networks. Prentice Hall，Inc.Englewood Cliffs，NJ，1992.

[4] 徐世中，李樂民，王晟.波分復(fù)用光傳送網(wǎng)中備用選路下的選路和波長分配算法[J].電子學(xué)報(bào)，2002，30(4):488-491.

[5] Alanyali M.， Ayanoglu E. Provisioning algorithms for WDM optical networks.INFOCOM'98，April 1998，Vol.2:910-918.