WDM網(wǎng)絡(luò)中一種基于分層圖模型的RWA算法

　　1 引言

　　寬帶視頻、多媒體等業(yè)務(wù)的日益興起,業(yè)務(wù)的快速增長,對廣域骨干網(wǎng)的帶寬提出了越來越高的要求。光纖上的波分復(fù)用技術(shù)(WDM)以它的傳輸容量大,對高層協(xié)議和技術(shù)適應(yīng)性強(qiáng),以及易于擴(kuò)展等優(yōu)點(diǎn)而備受青睞。因此,WDM光傳送網(wǎng)被認(rèn)為是下一代高速廣域骨干網(wǎng)的最具競爭力的候選者[1]。

　　WDM光網(wǎng)絡(luò)是由網(wǎng)絡(luò)節(jié)點(diǎn)和連接節(jié)點(diǎn)的光纖鏈路構(gòu)成的，不同波長的光信道復(fù)用在同一根光纖中傳輸。當(dāng)客戶層業(yè)務(wù)到達(dá)時(shí)，WDM光網(wǎng)絡(luò)需要給每條業(yè)務(wù)選擇路由和分配波長,建立光通道傳送業(yè)務(wù)。這就是WDM網(wǎng)絡(luò)的關(guān)鍵技術(shù)一路由與波長分配(RWA]問題。雖然WDM光網(wǎng)絡(luò)已經(jīng)取得了巨大的進(jìn)步,但由于各種物理的、技術(shù)的限制因素，光網(wǎng)絡(luò)還不能提供我們所要求的物理性能，因此就存在對現(xiàn)有可用資源的高效利用和優(yōu)化問題，RWA問題是最優(yōu)化網(wǎng)絡(luò)性能的核心問題之一。本文針對這個(gè)問題，將波長分層圖和網(wǎng)絡(luò)圖論的最大邊不相關(guān)理論引入RWA問題中，提出了一種基于分層圖的最大邊不相關(guān)(LG-BEDP)算法。仿真表明，該算法可以有效節(jié)省網(wǎng)絡(luò)波長資源,且易于實(shí)施。

　　2 研究背景

　　作為光網(wǎng)絡(luò)的核心問題,靜態(tài)RWA問題已被廣泛研究,且已被證明是一個(gè)問題[2],多用一些啟發(fā)式算法來解決。文獻(xiàn)[4]提出一種整數(shù)線性規(guī)劃(ILP)法，但該算法復(fù)雜度較高,且隨網(wǎng)絡(luò)規(guī)模急劇增大。本文的算法將網(wǎng)絡(luò)圖論中的最大邊不相關(guān)理論和波長分層圖模型結(jié)合起來解決這個(gè)問題,因此可同時(shí)進(jìn)行選路和波長分配,且能有效優(yōu)化網(wǎng)絡(luò)資源。

　　2.1 RWA的最大邊不相關(guān)問題

　　WDM網(wǎng)絡(luò)巾,由于波長連續(xù)性的限制,不同業(yè)務(wù)對應(yīng)的光路在網(wǎng)絡(luò)拓?fù)渲斜仨氝叢幌嚓P(guān)，因此，我們可以將圖論中最大邊不相關(guān)原理[5, 7]的一些解決方案應(yīng)用到RWA問題中。RWA的最大邊不相關(guān)問題可描述為：給定網(wǎng)絡(luò)的物理拓?fù)浜蜆I(yè)務(wù)請求集合，分別從該集合中找到不同的業(yè)務(wù)分組，要求每個(gè)分組中的業(yè)務(wù)在物理拓?fù)渖洗嬖诓幌嚓P(guān)路徑，且分組中的業(yè)務(wù)個(gè)數(shù)盡可能地多。由于每個(gè)分組中的連接請求都符合邊不相關(guān)的要求,因此,每組連接請求都可以分配相同的波長。

　　在此基礎(chǔ)上,我們又引入了波長分層圖模型，來共同解決靜態(tài)RWA問題。

　　2.2 波長分層圖模型

　　定義：網(wǎng)絡(luò)的物理拓?fù)錇镚(V,E]V表示節(jié)點(diǎn)集合,E表示兩條光纖形成的雙向鏈路集合。設(shè)單根光纖中共有W個(gè)波長。

　　該物理拓?fù)涞姆謱訄DLG (V*，E*)可以描述為：將物理拓?fù)鋸?fù)制W份,形成分層圖中的W層。物理拓?fù)渲械墓?jié)點(diǎn)Vi就對應(yīng)各個(gè)分層圖中的{V1i,V2i，…Vwi}，鏈路ei就對應(yīng){e1i，e2i，…ewi}。并且原來的雙向鏈路變成方向相反的兩條有向鏈路。vi∈V，ei∈E,這樣，分層圖LG(V*,E*)的每一層都代表一個(gè)波長，我們從上到下對每一層所對應(yīng)的波長進(jìn)行編號，依次為λ1、λ2、…λw。

　　如圖1(a)所示的物理網(wǎng)絡(luò)變成分層圖就如圖1(b)所示.其中W=3,波長分層圖的每一層所對應(yīng)的波長依次為λ1、λ2、和λ3。

　　在波長分層圖模型中，光路從源節(jié)點(diǎn)到目的節(jié)點(diǎn)必須要在同一個(gè)波長分層內(nèi)，即滿足波長連續(xù)性限制。對于一個(gè)連接請求，在波長分層圖上進(jìn)行選路，它所經(jīng)過的路徑，就是該光連接在物理拓?fù)渖辖?jīng)過的路徑，路徑所在的波長分層，就是它所占用的波長。如圖1(b)中，光連接(V5，V4)的路徑是V35→V32→V33→V34，即該請求在物理拓?fù)渲械穆窂綖閂5→V2→V3→V4，且該路徑被分配的波長為λ3。因此，可以說波長分層圖模型可以同時(shí)解決WDM網(wǎng)絡(luò)中的選路和波長分配問題。

　　3 基于分層圖的最大邊不相關(guān)RWA算法

　　定義：網(wǎng)絡(luò)物理拓?fù)錇镚(V，E)它所對應(yīng)的分層圖模型為LG(V*E*)：業(yè)務(wù)請求集合為D，集合中的某請求為d：波長數(shù)目為W;業(yè)務(wù)所對應(yīng)的通路集合為P,通路pi跳數(shù)長度為

　　圖2 ，要求每個(gè)通路的長度滿足hi≤h，其中，m表示拓?fù)鋱D中邊的個(gè)數(shù)。diam(G)表示拓?fù)鋱D的直徑。

　　該算法可以描述為：首先隨機(jī)地從業(yè)務(wù)請求集合D中選擇一個(gè)連接請求，記為d1，在波長分層圖的第一層上為業(yè)務(wù)請求d1找到可用的最短路徑，記為P1，長度為h1，，若h1≤h則p1∈P，為陔路徑分配波長λ1。更新LG(V*，E*)和D，使E*=E*-p1，D=D-d1。對于隨機(jī)從D中選取的請求di,從第一層依次向下對它進(jìn)行選路，若最早在波長分層圖的第m層為di找到一條最短的可用路徑pi，且它的長度hi≤h，則pi∈P，為該請求分配的波長為λmc。更新LG(V*，E*)和D為：E*=E*-pi，D=D-di。重復(fù)上述過程，直到D=φ，該過程結(jié)束。這時(shí)，建立所有光路所用到的分層圖的層數(shù)就是本算法計(jì)算出的所用波長數(shù)。下面是本算法的流程：

　　Step 1：已知給定的G(V,E)和D，初始生成LG(V*，E*);

　　Step2：將連接請求d1以最短路由p1分配在LG(V*,E*)的層，并且更新LG(V*，E*)和D。

　　SteP3：為剩余的連接請求D選擇路由并分配波長。若為隨機(jī)選擇的業(yè)務(wù)請求di尋找路徑，則從λ1層向下層開始搜索。若最早在第λm層找到滿足長度hi≤h的最短路徑pi，則更新波長分層圖LG(V*，E*)和D，該請求被分配的波長為λm。

　　Step4：if D≠φ，則返回第三步。

　　Step 5：if D=φ，則算法完畢，返回m的最大值，即業(yè)務(wù)在網(wǎng)絡(luò)中占用的波長數(shù)。

　　4 仿真分析

　　我們對本算法和最短路徑--首次命中SP-FF(shortest path-first fit)算法進(jìn)行了仿真比較。SP-FF即利用最短路徑算法進(jìn)行選路,采用首次命中算法分配波長的RWA算法。優(yōu)化目標(biāo)是最小化波長數(shù)目，所用的仿真拓?fù)鋱D為14個(gè)節(jié)點(diǎn)的NSFNET，見圖2。

　　首先,假設(shè)該網(wǎng)絡(luò)中每根光纖上存在40個(gè)波長，并隨機(jī)生成網(wǎng)絡(luò)的業(yè)務(wù)請求集合D，并且網(wǎng)絡(luò)的業(yè)務(wù)呈均勻分布,每個(gè)節(jié)點(diǎn)的業(yè)務(wù)量為1～13。在上述條件下,分別對LG-BEDP算法和SP-FF算法進(jìn)行了200次仿真。

{{分頁}}

　　從圖3可以看出，在不同負(fù)載下,LG-BEDP算法所使用的平均波長數(shù)都更少，并且業(yè)務(wù)負(fù)載越大,LG BEDP算法比SP-FF算法節(jié)省的波長數(shù)越多,當(dāng)負(fù)載為13時(shí)，該算法可以比SP-FF算法少用4個(gè)以上的波長。

　　圖4中對兩種算法在不同負(fù)載下所使用的最大和最小的波長數(shù)進(jìn)行了對比，LG-BEDP算法在相同負(fù)載下的波長使用數(shù)目上下波動(dòng)不大,在2～3個(gè)波長之間，且LG-BEDP-max和SP-FF-min相接近。但是SPFF算法在相同負(fù)載下使用的波長數(shù)目波動(dòng)幅度較大，且隨著負(fù)載的增大這種情況更加明顯。因此，LG BEDP算法不僅性能更優(yōu)，而且算法的穩(wěn)定性也較好。

　　表1是兩種算法在波長λ1～λ10情況下的鏈路使用率，從表中可以看出，LG-BEDP算法的鏈路使用率更高，并且在波長λ1、λ2時(shí)，鏈路使用率最高可達(dá)100%。值得注意的是，某些時(shí)候鏈路的使用率會(huì)隨著波長編號的增大而下降，這主要是因?yàn)槲覀冊谶x路時(shí)，總是傾向于選擇波長編號最小的那些路徑。

　　以上是在隨機(jī)生成目的節(jié)點(diǎn)的業(yè)務(wù)負(fù)載下，對兩種算法進(jìn)行的仿真比較。為進(jìn)一步評估算法的性能，我們?yōu)榫W(wǎng)絡(luò)的某個(gè)節(jié)點(diǎn)到其他所有的節(jié)點(diǎn)都建立光路，即實(shí)現(xiàn)網(wǎng)絡(luò)的全光連接。并在此條件下對兩種算法的波長使用數(shù)量進(jìn)行了仿真比較。

　　如圖5所示,網(wǎng)絡(luò)中共存在182個(gè)業(yè)務(wù)請求,兩種算法中，LGBEDP算法建立全光連接用的波長數(shù)最小為13,最大為14：SP-FF算法則需要16個(gè)波長。因此,LG-BEDP算法可更好地節(jié)省波長資源。

　　5 結(jié)論

　　在本文中,我們將波長分層圖模型和RWA的最大邊不相關(guān)問題結(jié)合起來,提出了一種新的RWA算法LG-BEDP,與其它算法相比,本算法可以同時(shí)解決RWA中的選路和波長分配問題。仿真證明，我們提出的LG-BEDP可以節(jié)省更多的波長資源,且算法穩(wěn)定性更好、資源利用率較高。