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

　　1 引言

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

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

　　2 研究背景

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

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

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

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

　　2.2 波長(cháng)分層圖模型

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

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

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

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

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

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

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

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

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

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

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

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

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

　　4 仿真分析

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

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

{{分頁(yè)}}

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

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

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

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

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

　　5 結論

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