WDM網絡中一種基于分層圖模型的RWA算法

　　1 引言

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

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

　　2 研究背景

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

　　2.1 RWA的最大邊不相關問題

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

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

　　2.2 波長分層圖模型

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

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

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

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

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

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

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

　　該算法可以描述為：首先隨機地從業務請求集合D中選擇一個連接請求，記為d1，在波長分層圖的第一層上為業務請求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=φ，該過程結束。這時，建立所有光路所用到的分層圖的層數就是本算法計算出的所用波長數。下面是本算法的流程：

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

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

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

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

　　Step 5：if D=φ，則算法完畢，返回m的最大值，即業務在網絡中占用的波長數。

　　4 仿真分析

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

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

{{分頁}}

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

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

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

　　以上是在隨機生成目的節點的業務負載下，對兩種算法進行的仿真比較。為進一步評估算法的性能，我們為網絡的某個節點到其他所有的節點都建立光路，即實現網絡的全光連接。并在此條件下對兩種算法的波長使用數量進行了仿真比較。

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

　　5 結論

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