邢移單

(同濟(jì)大學(xué) 浙江學(xué)院，浙江 嘉興 314051)

?

基于流量的IP OVER WDM 網(wǎng)絡(luò)多跳疏導(dǎo)節(jié)能路由算法設(shè)計(jì)

邢移單

(同濟(jì)大學(xué) 浙江學(xué)院，浙江 嘉興 314051)

摘要：降低網(wǎng)絡(luò)能耗和提高能量利用率的需求，使綠色I(xiàn)P over WDM網(wǎng)絡(luò)成為光網(wǎng)絡(luò)領(lǐng)域的研究熱點(diǎn)。針對(duì)流量業(yè)務(wù)，以降低網(wǎng)絡(luò)能耗和保證網(wǎng)絡(luò)性能為優(yōu)化目標(biāo)，建立了分層集成輔助圖模型，根據(jù)多跳疏導(dǎo)機(jī)制設(shè)計(jì)了IP over WDM 網(wǎng)絡(luò)光層節(jié)點(diǎn)優(yōu)化配置下的節(jié)能多跳疏導(dǎo)(Optical Multiple Jump Grooming，OMJG)路由算法，進(jìn)行了仿真，并與最短路徑優(yōu)先算法(Dijkstra)進(jìn)行了比較。結(jié)果表明：在網(wǎng)絡(luò)總能耗和業(yè)務(wù)請(qǐng)求阻塞率方面，設(shè)計(jì)的OMJG算法均優(yōu)于傳統(tǒng)的Dijkstra算法。

關(guān)鍵詞：IP over WDM網(wǎng)絡(luò)；網(wǎng)絡(luò)能耗；流量疏導(dǎo)；多跳路由；分層集成輔助圖

0引言

隨著互聯(lián)網(wǎng)用戶的增長和多媒體業(yè)務(wù)的普及，通信網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)能耗快速增長。IP over WDM網(wǎng)絡(luò)是通信網(wǎng)絡(luò)的重要組成部分，具有覆蓋范圍廣、傳輸距離長、業(yè)務(wù)接口豐富、傳輸容量大、組網(wǎng)方式及業(yè)務(wù)調(diào)度能力靈活等優(yōu)點(diǎn)，已成為下一代網(wǎng)絡(luò)的支撐技術(shù)之一，研究IP over WDM網(wǎng)絡(luò)的能耗優(yōu)化問題，可以為通信網(wǎng)絡(luò)帶來更大的節(jié)能空間，對(duì)構(gòu)建綠色通信網(wǎng)絡(luò)體系具有重要意義。

光通信網(wǎng)絡(luò)單個(gè)波長信道的通信速率可達(dá)Gb/s級(jí)別，而實(shí)際應(yīng)用中大多數(shù)業(yè)務(wù)的通信速率低于一個(gè)波長的最高傳輸速率，如果為單個(gè)業(yè)務(wù)提供一個(gè)專用波長或者端到端的獨(dú)立波長信道，資源利用率低且不經(jīng)濟(jì)，因此有必要進(jìn)行流量疏導(dǎo)。流量疏導(dǎo)能按物理鏈路、每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的光收發(fā)器數(shù)目、每根光纖的波長數(shù)目以及波長容量，為多個(gè)低速率的業(yè)務(wù)連接進(jìn)行路由，優(yōu)化網(wǎng)絡(luò)性能。Yetginer等[1]從能耗的角度出發(fā)研究流量疏導(dǎo)問題，并建立整數(shù)線性規(guī)劃模型，將最小化光路數(shù)量和最小化電層路由次數(shù)結(jié)合起來，加上一定的約束條件，計(jì)算取得最小能耗的解。為了評(píng)估核心網(wǎng)的能耗，Heddeghem等[2]以泛歐教育網(wǎng)為例，采取鏈路-鏈路疏導(dǎo)和端-端疏導(dǎo)機(jī)制，利用時(shí)分復(fù)用方式在電域進(jìn)行數(shù)據(jù)包交換，采用光旁路機(jī)制，在光域疏導(dǎo)本地上、下路業(yè)務(wù)，結(jié)果表明端-端疏導(dǎo)機(jī)制節(jié)能優(yōu)勢更顯著。Tucker等[3]深入研究了基于流量的IP over WDM骨干網(wǎng)中的節(jié)能，采用混合整數(shù)線性規(guī)劃(MILP)模型，基于光旁路和流量疏導(dǎo)設(shè)計(jì)了啟發(fā)式算法，通過MILP模型得到最小網(wǎng)絡(luò)能耗。宋璨、袁夢、王汝言等[4-6]針對(duì)該現(xiàn)狀提出一種基于區(qū)域擴(kuò)展的流量疏導(dǎo)算法，通過分層圖模型尋找最佳路徑，仿真結(jié)果表明在網(wǎng)絡(luò)能耗和阻塞率方面的性能優(yōu)于傳統(tǒng)算法，不足之處沒有討論光收發(fā)器、光放大器的功耗。賈曉蕾等[7]研究了無源光網(wǎng)絡(luò)的流量疏導(dǎo)問題。在目前的研究中，基于流量疏導(dǎo)機(jī)制的能耗優(yōu)化方案大多是基于不同的疏導(dǎo)策略設(shè)計(jì)相應(yīng)的啟發(fā)式算法和數(shù)學(xué)優(yōu)化方法，節(jié)能效果較優(yōu)，但仍存在如何確保網(wǎng)絡(luò)性能的問題。

本文基于流量疏導(dǎo)機(jī)制，設(shè)計(jì)IP over WDM網(wǎng)絡(luò)的能耗優(yōu)化路由問題。首先從節(jié)點(diǎn)級(jí)角度，建立網(wǎng)絡(luò)分層集成輔助圖模型，然后從網(wǎng)絡(luò)級(jí)出發(fā)，引入多跳流量疏導(dǎo)機(jī)制，設(shè)計(jì)節(jié)能路由算法，并通過仿真，根據(jù)多個(gè)評(píng)價(jià)指標(biāo)，分析和評(píng)估模型與算法對(duì)網(wǎng)絡(luò)能耗和性能的影響。

1問題描述和模型定義

1.1問題描述

流量疏導(dǎo)是如何在給定網(wǎng)絡(luò)物理拓?fù)?、業(yè)務(wù)需求矩陣、節(jié)點(diǎn)資源及帶寬資源等限制條件下，為不同帶寬粒度的業(yè)務(wù)建立光路，形成最優(yōu)的虛擬拓?fù)溥M(jìn)行業(yè)務(wù)疏導(dǎo)。性能優(yōu)化目標(biāo)是：網(wǎng)絡(luò)的總能耗最小(即在給定網(wǎng)絡(luò)拓?fù)浜蜆I(yè)務(wù)需求矩陣的情況下，疏導(dǎo)所有業(yè)務(wù)消耗的節(jié)點(diǎn)設(shè)備的能耗之和最小)和平均請(qǐng)求阻塞率最小(被阻塞的業(yè)務(wù)個(gè)數(shù)與業(yè)務(wù)請(qǐng)求總數(shù)的比值最小)。流量疏導(dǎo)問題分為三個(gè)子問題：① 虛擬拓?fù)洌焊鶕?jù)連接請(qǐng)求將源節(jié)點(diǎn)所在的路由器通過OXC與目的節(jié)點(diǎn)對(duì)應(yīng)的IP路由器互聯(lián)，在物理拓?fù)涞幕A(chǔ)上建立新的邏輯拓?fù)?；?流量路由：在虛擬拓?fù)渖蠟榈退贅I(yè)務(wù)連接請(qǐng)求選路，使得該路由路徑的能耗最??；③ 波長分配：當(dāng)路由路徑確定時(shí)，為在該路徑上的每條鏈路上分配波長。

1.2分層集成輔助圖模型

流量疏導(dǎo)一般用網(wǎng)絡(luò)物理拓?fù)浜吞摂M拓?fù)涞妮o助圖模型進(jìn)行分析，本文設(shè)計(jì)綜合網(wǎng)絡(luò)物理拓?fù)浜吞摂M拓?fù)涞姆謱蛹奢o助圖模型。作為實(shí)例，圖1為6節(jié)點(diǎn)雙向單光纖的IP over WDM網(wǎng)絡(luò)，包含λ1、λ2兩個(gè)波長信道，信道容量設(shè)為單位1，有兩個(gè)建立連接業(yè)務(wù)請(qǐng)求，假定已計(jì)算得到其最短路徑，如表1所示，表中的表達(dá)式Es(s,d,t)表示源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的歸一化流量為t，Ni表示網(wǎng)絡(luò)節(jié)點(diǎn)。

表1　業(yè)務(wù)請(qǐng)求

根據(jù)波長信道個(gè)數(shù)分為多層，每層代表一個(gè)波長平面，實(shí)線連接波長通道建立初始輔助圖(見圖1(a))；虛線鏈接源節(jié)點(diǎn)和目的節(jié)點(diǎn)并標(biāo)注流量請(qǐng)求虛鏈路用虛線在波長平面中表示出來(見圖1(b))，將物理拓?fù)浜吞摂M拓?fù)涞男畔⒄显谝黄鹦纬煞謱蛹奢o助圖。

圖1　分層集成輔助

2基于流量的多跳疏導(dǎo)路由算法設(shè)計(jì)

2.1算法描述

輔助圖中每條邊都具備可用容量和邊權(quán)代價(jià)兩個(gè)基本屬性，傳統(tǒng)的最短路徑算法Dijkstra中，邊權(quán)代價(jià)定義為相鄰兩個(gè)節(jié)點(diǎn)之間的物理距離；基于流量的多跳疏導(dǎo)路由算法為了使疏導(dǎo)每個(gè)建立連接請(qǐng)求所需的能耗最小，需要將邊權(quán)進(jìn)行相應(yīng)的轉(zhuǎn)換，對(duì)圖1中的波長鏈路、虛鏈路的邊權(quán)代價(jià)重新定義為

波長鏈路的代價(jià)函數(shù)為：

(1)

虛鏈路的代價(jià)函數(shù)為：

(2)

式中，tmn表示節(jié)點(diǎn)對(duì)(m,n)之間的業(yè)務(wù)負(fù)載，T為總負(fù)載。

如果一條路由路徑包括g條波長鏈路和h條虛鏈路，波長鏈路和虛鏈路構(gòu)成的混合路徑的代價(jià)函數(shù)為：

(3)

當(dāng)路由路徑確定以后，可以根據(jù)路徑形式，選取對(duì)應(yīng)的代價(jià)函數(shù)來計(jì)算每條路徑的功耗：

(4)

在完成所有業(yè)務(wù)請(qǐng)求之后，可以由每條路徑的功耗以及使用的線卡總數(shù)，計(jì)算網(wǎng)絡(luò)總功耗為：

Ptotal=∑P

(5)

在選路過程中，優(yōu)先利用已建虛鏈路而非新建光路來承載當(dāng)前的業(yè)務(wù)請(qǐng)求時(shí)，能夠充分利用光路的帶寬資源，并且路由路徑的總代價(jià)最小，網(wǎng)絡(luò)的總能耗最少。

2.2算法實(shí)現(xiàn)

基于流量的多跳疏導(dǎo)路由算法的描述，提出光層節(jié)點(diǎn)優(yōu)化配置下的多跳疏導(dǎo)(Optical Multiple Jump Grooming Algorithm，OMJG)算法，具體的處理和實(shí)現(xiàn)過程為：

步驟1：根據(jù)輸入的網(wǎng)絡(luò)拓?fù)?、波長平面數(shù)W、波長信道容量B等信息，采用圖1的方法建立輔助圖，并根據(jù)式(1)計(jì)算所有波長鏈路的邊權(quán)值。

步驟2：對(duì)所有的業(yè)務(wù)連接請(qǐng)求按照業(yè)務(wù)負(fù)載的大小降序排列，如果負(fù)載相同，按先進(jìn)先出(First In First Out，F(xiàn)IFO)原則確定實(shí)際的路由處理隊(duì)列Seq。

步驟3：判斷隊(duì)列Seq是否為空，若不為空，則從隊(duì)列Seq中取出當(dāng)前第一個(gè)業(yè)務(wù)請(qǐng)求Es(s，d，tsd)進(jìn)行路由，排除輔助圖中波長可用帶寬小于tsd的鏈路，跳轉(zhuǎn)至步驟4；若為空，則直接跳轉(zhuǎn)至步驟8。

步驟4：在W層輔助圖上分別運(yùn)行Dijkstra算法，找出每個(gè)波長平面的最短路徑。如果不存在一條這樣的路徑，則阻塞該業(yè)務(wù)連接請(qǐng)求，并跳轉(zhuǎn)至步驟3；否則跳轉(zhuǎn)至步驟5。

步驟5：如果存在一條或多條最短路徑，它是s至d的一條直達(dá)虛鏈路，那么選取鏈路權(quán)重最小的路徑作為最終的路由路徑，若路徑權(quán)重相同，則選取波長平面序號(hào)最小的路徑，從虛鏈路中扣除業(yè)務(wù)負(fù)載tsd，并按式(1)更新虛鏈路的權(quán)重，路徑功耗P滿足式(4)，返回步驟3繼續(xù)處理下一個(gè)業(yè)務(wù)。

步驟6：如果存在一條或多條最短路徑，它全部由波長鏈路組成，那么選取鏈路權(quán)重最小的路徑作為最終的路由路徑，如果路徑權(quán)重相同，選取波長平面序號(hào)最小的路徑，刪除波長鏈路，建立s至d的一條直達(dá)虛鏈路，從虛鏈路中扣除業(yè)務(wù)負(fù)載tsd，并按式(1)更新虛鏈路的權(quán)重，路徑功耗P滿足式(4)，更新Ptotal，返回步驟3繼續(xù)處理下一個(gè)業(yè)務(wù)。

步驟7：如果存在其他形式的最短路徑，則阻塞該業(yè)務(wù)請(qǐng)求，并跳轉(zhuǎn)至步驟3，繼續(xù)處理下一個(gè)業(yè)務(wù)。

步驟8：完成所有業(yè)務(wù)連接請(qǐng)求，式(5)將每條路徑的功耗P累加得到網(wǎng)絡(luò)的總功耗Ptotal。

2.3算法實(shí)現(xiàn)舉例

改進(jìn)圖1中建立的輔助圖為圖2，其邊長上的數(shù)字表示節(jié)點(diǎn)的間距，對(duì)于采用新能源方式供電的節(jié)點(diǎn)做特殊標(biāo)記，如圖2中節(jié)點(diǎn)2是特殊節(jié)點(diǎn)。然后初始化輔助圖，按功耗參數(shù)和式(1)修改相應(yīng)的波長鏈路的權(quán)重，如圖3所示。光層節(jié)點(diǎn)優(yōu)化配置下的路由算法采用多跳疏導(dǎo)，由于特殊光節(jié)點(diǎn)的存在，導(dǎo)致部分波長鏈路的權(quán)重減小，在路由過程中，會(huì)優(yōu)先選擇這些能耗較小的路徑。具體的處理過程如下：

圖2　優(yōu)化配置物理拓?fù)?/p>

圖3　優(yōu)化配置輔助

按照文獻(xiàn)[8]的參數(shù)數(shù)據(jù)，初始化輔助圖，如圖1所示，根據(jù)式(1)計(jì)算每條波長鏈路的權(quán)重。

3仿真及數(shù)值分析

3.1仿真參數(shù)

(1)仿真數(shù)據(jù)：連接請(qǐng)求帶寬主要有四種：{B1，B2，B3，B4}，將其大小分別記作{1，3，6，10}(Gbps)，業(yè)務(wù)在網(wǎng)絡(luò)中的生成概率情況為①以小負(fù)載業(yè)務(wù)居多：B1:B2:B3:B4=3:3:3:1 ；②業(yè)務(wù)生成概率相同：B1:B2：B3：B4=1:1:1:1 ；③以大負(fù)載業(yè)務(wù)居多：B1:B2:B3:B4=1:2:2:3。

圖4　OMJG算法的過程示例

(2)網(wǎng)絡(luò)拓?fù)洌哼x取兩種類型的網(wǎng)絡(luò)拓?fù)洧傩⌒途W(wǎng)絡(luò)(見圖5)：含6個(gè)節(jié)點(diǎn)，8條鏈路；②NSFNET網(wǎng)絡(luò)(見圖6)，包括14個(gè)節(jié)點(diǎn)，21條鏈路。圖中每條光纖鏈路都是雙向傳輸，邊上的數(shù)值代表節(jié)點(diǎn)間的物理距離，單位是km，光纖鏈路中的波長數(shù)目為W，波長信道容量為10 Gb/s，每個(gè)節(jié)點(diǎn)都具備業(yè)務(wù)疏導(dǎo)能力，但沒有波長轉(zhuǎn)換功能。

(3)業(yè)務(wù)模型：所有業(yè)務(wù)請(qǐng)求均勻分布在網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)。

圖5　小型網(wǎng)絡(luò)

圖6　NSFNET網(wǎng)絡(luò)

3.2不同算法的性能比較

為對(duì)比算法性能，分別仿真了本文設(shè)計(jì)的算法OMJG和最短路徑優(yōu)先算法(Dijkstra)。

(1)網(wǎng)絡(luò)總能耗：針對(duì)圖5的小型網(wǎng)絡(luò)，波長平面數(shù)W=8；對(duì)于圖6的NSFNET網(wǎng)絡(luò)，波長平面數(shù)W=16，當(dāng)業(yè)務(wù)總數(shù)相同，不同帶寬下的業(yè)務(wù)數(shù)量比分別滿足仿真數(shù)據(jù)中的①、②、③時(shí)，比較OMJG算法和Dijkstra算法的網(wǎng)絡(luò)總能耗(見圖7、圖8)。 由圖7、圖8看出，不同帶寬和業(yè)務(wù)量下采用光層節(jié)點(diǎn)優(yōu)化配置下的多跳疏導(dǎo)OMJG算法優(yōu)于Dijkstra算法的能耗，尤其在網(wǎng)絡(luò)規(guī)模和業(yè)務(wù)負(fù)載較大時(shí)，Dijkstra算法與OMJG算法的能耗差距增大。

(2)平均業(yè)務(wù)請(qǐng)求阻塞率：不同帶寬下的業(yè)務(wù)數(shù)量比分別滿足仿真數(shù)據(jù)中的①、②、③，當(dāng)波長平面數(shù)變化時(shí)，小型網(wǎng)絡(luò)和NFSNET網(wǎng)絡(luò)中，OMJG和Dijkstra路由算法的業(yè)務(wù)請(qǐng)求阻塞率，如圖9、圖10所示。

① 波長平面?zhèn)€數(shù)的影響：由以圖9、圖10可知，當(dāng)業(yè)務(wù)負(fù)載不變時(shí)，平均請(qǐng)求阻塞率隨波長平面的增加而大大降低；與Dijkstra算法相比，OMJG算法的阻塞率較低，特別是在大規(guī)模網(wǎng)絡(luò)NSFNET中，OMJG算法能夠疏導(dǎo)的業(yè)務(wù)請(qǐng)求數(shù)明顯優(yōu)于Dijkstra算法。

② 業(yè)務(wù)負(fù)載的影響：當(dāng)波長平面數(shù)相同時(shí)，平均請(qǐng)求阻塞率隨業(yè)務(wù)負(fù)載的增多而逐漸升高，OMJG算法算法也優(yōu)于傳統(tǒng)的Dijkstra算法。

圖7　不同B1:B2:B3:B4下小型網(wǎng)絡(luò)的總能耗

圖8　不同B1:B2:B3:B4下NSFNE網(wǎng)絡(luò)的總能耗

圖9　不同W下小型網(wǎng)絡(luò)的阻塞率

圖10　不同W下NSFNET網(wǎng)絡(luò)的阻塞率

4結(jié)語

針對(duì)以能耗優(yōu)化為目標(biāo)的流量疏導(dǎo)問題，設(shè)計(jì)了適合IP over WDM網(wǎng)絡(luò)的分層集成輔助圖，便于同時(shí)表示波長鏈路和虛鏈路的可用容量及權(quán)重信息。在分層集成輔助圖的基礎(chǔ)上，設(shè)計(jì)節(jié)能的OMJG算法，進(jìn)行了仿真。仿真結(jié)果表明，與傳統(tǒng)的Dijkstra算法相比， OMJG算法不僅網(wǎng)絡(luò)總能耗得到了降低，而且平均業(yè)務(wù)請(qǐng)求阻塞率也得到了降低，OMJG算法在網(wǎng)絡(luò)節(jié)能和降低業(yè)務(wù)請(qǐng)求阻塞率方面有著良好性能。

參考文獻(xiàn)：

[1]Yetginer E, Rouskas G. Power Efficient Traffic Grooming in Optical WDM Networks[C]. IEEE Global Telecommunications Conference 2009, 2009,1-6.

[2]Heddeghem W, Groote M, Vereecken W. Energy-Efficiency in Telecommunications Networks: Link-by-Link Versus End-to-End Grooming[C]. 2010 14thConference on Optical Network Design and Modelling, 2010, 9-15.

[3]Tucker R S. Green Optical Communications-part II: Energy Limitations in Networks, IEEE Journal of Selected Topics in Quantum Electronics[J]. 2011, Vol. 17(2): 261-274.

[4]宋璨, 侯韶華.WDM網(wǎng)絡(luò)中基于分層圖模型的ICBR路由算法[J].通信技術(shù),2012,45(02):84-89.

SONG Can, HOU Shao-hua. A Layered Graph Model-based ICBR Algorithm in WDM Network[J]. Communications Technology, 2012, 45(02): 84-89.

[5]袁夢，張民，王力. 一種新的動(dòng)態(tài)流量疏導(dǎo)算法[J]. 光通信研究，2012，38(02)：11-13.

YUAN Meng, ZHANG Min, WANG Li. A Novel Topology Integration-based Dynamic Traffic Grooming Algorithm. Study on Optical Communication, 2012,38(02)：11-13.

[6]王汝言，徐印，吳大鵬等. 基于區(qū)域擴(kuò)展的綠色業(yè)務(wù)量疏導(dǎo)算法[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2012，24(02)：133-137.

WANG Ru-yan，XU Yin，WU Da-peng，et al. Green Traffic Grooming in Zone-based Scalable Optical Networks. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012，24(02)：133-137.

[7]賈曉蕾, 沈建華.支持流量疏導(dǎo)彈性光網(wǎng)絡(luò)的共享保護(hù)策略[J]. 光通信研究,2015,189(03):24-26.

JIA Xiao-lei, SHEN Jian-hua. Shared Protection Strategyprotecion Grooming-Supporting Elastic Optical Networks.Study on Optical Communication, 2015, 189(3)：24-26.

[8]Idzikowski F. Power Consumption of Network Elements in IP over WDM Networks[EB/OL]. www.tkn.tu-berlin.de/publications/papers/powerNumbers_final.pdf.

邢移單(1988—)，女，碩士，助教，主要研究方向?yàn)閷拵ㄐ啪W(wǎng)絡(luò)與技術(shù)。

Energy-Saving Routing Algorithm for Multiple Jump Grooming in

IP over WDM Network based on Traffic

XING Yi-dan

(Zhejiang College,Tongji Univ., Jiaxing Zhejiang 314051, China)

Abstract：The demand for decrease of network energy consumption and improvement of energy efficiency makes the green IP over WDM network a research hotspot in the area of optical communication network. For the purpose to reduce the network energy consumption and ensure the network performance for the traffic load, the hierarchical integrated auxiliary graph model is established, and the saving energy multiple jump grooming (OMJG)routing algorithm for the optical layer node optimization configuration of IP over WDM network designed and simulated, Simulation and comparison with the shortest path first algorithm (Dijkstra) inidcate that the OMJG algorithm is clearly superior to the traditional Dijkstra algorithm in total energy consumption and service request blocking probability of the netwok.

Key words：IP over WDM network, network energy consumption, trafic grooming, multiple jump, hierarchical integrated auxiliary graph

作者簡介：

中圖分類號(hào)：TN915

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1002-0802(2015)12-1389-06

收稿日期：2015-07-16；修回日期：2015-11-09Received date:2015-07-16；Revised date：2015-11-09

doi:10.3969/j.issn.1002-0802.2015.12.014