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

    1 引言

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

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

    2 研究背景

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

    2.1 RWA的最大邊不相關問題

WDM網(wǎng)絡巾,由于波長連續(xù)性的限制,不同業(yè)務對應的光路在網(wǎng)絡拓撲中必須邊不相關，因此，我們可以將圖論中最大邊不相關原理[5, 7]的一些解決方案應用到RWA問題中。RWA的最大邊不相關問題可描述為：給定網(wǎng)絡的物理拓撲和業(yè)務請求集合，分別從該集合中找到不同的業(yè)務分組，要求每個分組中的業(yè)務在物理拓撲上存在不相關路徑，且分組中的業(yè)務個數(shù)盡可能地多。由于每個分組中的連接請求都符合邊不相關的要求,因此,每組連接請求都可以分配相同的波長。

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

    2 波長分層圖模型

    定義：網(wǎng)絡的物理拓撲為G(V,E]V表示節(jié)點集合,E表示兩條光纖形成的雙向鏈路集合。設單根光纖中共有W個波長。

    該物理拓撲的分層圖LG (V*，E*)可以描述為：將物理拓撲復制W份,形成分層圖中的W層。物理拓撲中的節(jié)點Vi就對應各個分層圖中的{V1i,V2i，…Vwi}，鏈路ei就對應{e1i，e2i，…ewi}。并且原來的雙向鏈路變成方向相反的兩條有向鏈路。vi∈V，ei∈E,這樣，分層圖LG(V*,E*)的每一層都代表一個波長，我們從上到下對每一層所對應的波長進行編號，依次為λ1、λ2、…λw。

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

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

    3 基于分層圖的最大邊不相關RWA算法

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

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

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

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

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

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

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

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

    4 仿真分析

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

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

    {{分頁}}

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

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

    表1是兩種算法在波長λ1～λ10情況下的鏈路使用率，從表中可以看出，LG-BEDP算法的鏈路使用率更高，并且在波長λ1、λ2時，鏈路使用率最高可達100%。值得注意的是，某些時候鏈路的使用率會隨著波長編號的增大而下降，這主要是因為我們在選路時，總是傾向于選擇波長編號最小的那些路徑。

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

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

    5 結論

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