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

    1 引言

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

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

    2 研究背景

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

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

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

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

    2 波長(zhǎng)分層圖模型

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

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

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

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

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

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

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

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

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

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

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

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

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

    4 仿真分析

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

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

    {{分頁(yè)}}

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

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

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

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

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

    5 結(jié)論

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