基于K算法的綠色I(xiàn)P over WDM網(wǎng)絡(luò)設(shè)計方法

田立偉,孫 宇,張 旭

(1.廣東科技學(xué)院 計算機系，廣東 東莞，23083；2.廣東省電信規(guī)劃設(shè)計院有限公司，廣東 東莞523120)

基于K算法的綠色I(xiàn)P over WDM網(wǎng)絡(luò)設(shè)計方法

田立偉1,孫 宇2,張 旭1

(1.廣東科技學(xué)院 計算機系，廣東 東莞，23083；2.廣東省電信規(guī)劃設(shè)計院有限公司，廣東 東莞523120)

通過構(gòu)建整數(shù)線性規(guī)劃（I LP）來計算網(wǎng)絡(luò)的能耗，求解I LP的解需要的計算機內(nèi)存空間大，但內(nèi)存不足仍然是需要考慮的問題之一。針對這一問題，提出了一種基于K算法來設(shè)計綠色I(xiàn) P over W D M網(wǎng)絡(luò)的方法，該方法是基于傳統(tǒng)的虛拓?fù)渚W(wǎng)絡(luò)業(yè)務(wù)疏導(dǎo)方法，首先利用K算法求解網(wǎng)絡(luò)中節(jié)點與節(jié)點之間的K條可能路徑，然后通過構(gòu)建整數(shù)線性規(guī)劃（I LP）來求解網(wǎng)絡(luò)資源的分布。分析網(wǎng)絡(luò)能耗的模型，利用數(shù)學(xué)表達(dá)式來描述基于K算法下3種I P over W D M網(wǎng)絡(luò)的能耗。

I P over W D M網(wǎng)絡(luò)；I LP；K算法；網(wǎng)絡(luò)能耗

0 引言

目前對于光交換網(wǎng)絡(luò)的研究，很大一部分是對疏導(dǎo)問題的研究，這些研究主要集中在如何最小化網(wǎng)絡(luò)的代價，或者為了滿足業(yè)務(wù)負(fù)載的需要如何使網(wǎng)絡(luò)的收益最大。文獻(xiàn)[1～7]中提出了一些解決方法，但這些方法均是將IP層和WDM層結(jié)合起來考慮，通過求解ILP來計算網(wǎng)絡(luò)的能耗，由于受計算內(nèi)存大小的限制，這些方法不適應(yīng)大規(guī)模網(wǎng)絡(luò)的計算。針對于內(nèi)存的限制，本文將IP層和WDM層分開討論，從能耗方面著手，提出一種利用K算法來設(shè)計綠色I(xiàn)P over WDM網(wǎng)絡(luò)的方法。此方法首先利用K算法求解網(wǎng)絡(luò)中節(jié)點與節(jié)點之間的K條可能路徑，然后再來優(yōu)化網(wǎng)絡(luò)能耗?？紤]到光層的能耗比較小，忽略其能耗，假設(shè)網(wǎng)絡(luò)中的能耗等于所有路徑中器件的能耗之和，即網(wǎng)絡(luò)中的能耗就可以用光路總數(shù)與電交換總數(shù)的函數(shù)來表示。因此，新方法的優(yōu)化問題就可以用整數(shù)線性規(guī)劃來表示，它充分結(jié)合了文獻(xiàn)[3]和文獻(xiàn)[4]的業(yè)務(wù)疏導(dǎo)方法。

1 IP over WDM網(wǎng)絡(luò)中的能耗模型

圖1是IP over WDM網(wǎng)絡(luò)的結(jié)構(gòu)圖，從中可以看出，每個網(wǎng)絡(luò)節(jié)點都包含IP核心路由器和光交叉連接器兩部分。將低速路由器匯聚來的IP數(shù)據(jù)接入IP核心路由器，然后通過光旁路的方式來負(fù)載路由數(shù)據(jù)。光層提供IP層路由的通信容量，節(jié)點之間通過物理光纖相連，信號在光纖中向著相反方向傳輸，每根光纖中包含W條波長。與每根光纖相連的是復(fù)用器和解復(fù)用器，它們利用WDM技術(shù)將多個承載載波信號的光波復(fù)用到同一個光纖中去傳輸。在源端，利用多路波分復(fù)用器將信號匯聚起來；在目的端，利用解復(fù)用器將信號分解給不同的終端。為了增加接收端的靈敏度，需要在發(fā)送端增加一個前置放大器來放大信號的功率，為了簡化模型，該部分在圖1中省略。核心路由器與光交叉連接器之間的轉(zhuǎn)換器可以實現(xiàn)不同的波長數(shù)據(jù)之間的轉(zhuǎn)換。為了拓展光信號的傳播距離，在每根光纖鏈路中部署EDFA放大器。

圖1 IP over WDM的結(jié)構(gòu)圖

網(wǎng)絡(luò)中業(yè)務(wù)的傳輸方法主要有兩種，即多跳路由和單跳路由。在單跳路由中，所有光路攜帶的業(yè)務(wù)必須通過IP路由器轉(zhuǎn)發(fā)；在多跳路由中，全部的負(fù)載信息不需要經(jīng)過IP路由器的傳輸，而直接在光區(qū)域中傳輸，這樣做的目的就是為了節(jié)省更多的能量，但是它要求光節(jié)點對光路的旁路比較敏感。光的旁路在核心路由器之間直接建立光路，而這個光路映射到IP層，我們就把它稱為一個虛鏈路。顯然多跳路由能夠充分利用網(wǎng)絡(luò)資源，因此新方案主要考慮多跳路由情況。

在IP over WDM光網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的能量主要在IP層和光層中消耗。路由器進(jìn)行電信號的交換及轉(zhuǎn)換器對信號進(jìn)行轉(zhuǎn)換都會導(dǎo)致能量消耗，這就是IP層能量消耗的主要原因，它們分別用PI、PT來表示。據(jù)文獻(xiàn)[8]可知，核心由器的數(shù)目等于所有光路承載的業(yè)務(wù)量與源節(jié)點到目的節(jié)點之間的總業(yè)務(wù)量之差，轉(zhuǎn)換器數(shù)量與光路數(shù)量呈線性關(guān)系，在以上兩種層次的能量消耗中IP層的能量消耗起主導(dǎo)作用，因此要最小化網(wǎng)絡(luò)能耗就應(yīng)首先考慮最小化路由器和轉(zhuǎn)換器的能耗。光交叉連接器中進(jìn)行信號交換也會導(dǎo)致能量損耗，這就是光層能量消耗的主因。從文獻(xiàn)[9]中可知，光層的能量消耗遠(yuǎn)小于IP層所能量消耗，故在實驗設(shè)計時將IP over WDM網(wǎng)絡(luò)拓?fù)浜喕垂鈱拥哪芰肯牟蛔骺紤]，主要考慮IP的能量消耗。同時，作如下假設(shè)：①連接到接入網(wǎng)中本地路由器端口的能耗將不考慮，因為在這些端口中添加和刪除的業(yè)務(wù)量與任何業(yè)務(wù)疏導(dǎo)方法無關(guān)；②由于EDFA總是被部署在網(wǎng)絡(luò)中，在網(wǎng)絡(luò)中它的能耗是一個常數(shù)；③在給定的負(fù)載下，在源節(jié)點和目的節(jié)點進(jìn)行疏導(dǎo)所消耗的能量是一個常數(shù)，它與采用的疏導(dǎo)方法沒有任何關(guān)系。

基于以上幾點可知，求解最消耗網(wǎng)絡(luò)能耗問題的目標(biāo)歸結(jié)為構(gòu)建IP層的可能虛拓?fù)湟约霸谔撏負(fù)渖虾侠淼芈酚蓸I(yè)務(wù)請求。

2 K算法求解原理

CPLEX雖然提供了靈活方便的優(yōu)化程序，例如采用分支切割算法來求解線性規(guī)劃問題，但它仍需要大量的內(nèi)容空間。所以，求解規(guī)模大的LP，首先要解決內(nèi)存不足的問題。針對內(nèi)存不足現(xiàn)象，CPLEX通過對可行解進(jìn)行松弛來調(diào)解，但是這樣調(diào)解后將影響到計算的性能。因此，我們提出了一種基于K條路徑來設(shè)計骨干網(wǎng)絡(luò)，使網(wǎng)絡(luò)能耗達(dá)到最低的方法。此方法先根據(jù)網(wǎng)絡(luò)中節(jié)點與節(jié)點的距離，利用K算法求解網(wǎng)絡(luò)中節(jié)點與節(jié)點之間的K條可能最短距離路徑[10]，最后再來優(yōu)化網(wǎng)絡(luò)能耗。

首先，通過初始化函數(shù)來初始網(wǎng)絡(luò)中的節(jié)點數(shù)、邊數(shù)及其每條邊上的權(quán)值（距離）等數(shù)據(jù)，然后利用Dijkstra算法求解出所有點之間的距離，其中網(wǎng)絡(luò)中所有節(jié)點之間的最小的那條作為第一條最短路徑。將其路徑信息保存在數(shù)組P(N1,L1)中，參考前面求出的最短路徑信息繼續(xù)求下一條最短路徑，不斷求出節(jié)點到所有節(jié)點的K-1條最短路徑，利用遞歸算法即可求出第K條路徑。求解第K條路徑的過程如下：遍歷前K-1條路徑中的所有點，每個被遍歷的點都需要斷開一次；重新計算路徑，如果求得的新路徑已經(jīng)存在，則將斷點復(fù)原；如果求得路徑與前面K-1條路徑中的任何路徑的前i個點重合，則將其邊值設(shè)為無窮大，繼續(xù)求新的路徑；如果總是重合，不再斷開節(jié)點，恢復(fù)邊的情況，同時需要檢測路徑上是否有環(huán)路；如果沒有環(huán)路，表明找到一條新的路徑，保存在P(N1,L1)中；如果不存在新的路徑，循環(huán)截止。

通過上述算法，即可求出網(wǎng)絡(luò)中節(jié)點與節(jié)點之間可能存在的K條路徑，并可通過ILP表達(dá)式來表示其路徑信息。

3 基于K算法的ILP表達(dá)式

假設(shè)在IP over WDM網(wǎng)絡(luò)中，WDM層的結(jié)構(gòu)可以用圖G=(N,L)來表示，PI為每發(fā)送Gb/s的數(shù)據(jù)在IP層路由器中產(chǎn)生能耗，Pt為每個光交叉連接器產(chǎn)生的能耗，N為網(wǎng)絡(luò)拓?fù)渲泄?jié)點的集合，L為物理層中點與點之間的鏈路集合，假設(shè)物理鏈路通過光纖相連，光纖中的信息向著相反方向傳輸，每一根光纖都由W條波長信道組成。每條信道的容量用C來表示，m和n表示光纖鏈路的端點。i和j表示光路的兩個端點。s和d表示在IP層中的低速負(fù)載量。相同的約束調(diào)節(jié)下，有3種表達(dá)式可以解決業(yè)務(wù)疏導(dǎo)問題。

①最小化核心路由器端口(minL)的方法：即通過減少核心路由器端口的數(shù)量來降低網(wǎng)絡(luò)的能耗。由于每個光路都終止于核心路由器端口，路由器的個數(shù)是網(wǎng)絡(luò)中建立光路的兩倍，因此最小化網(wǎng)絡(luò)端口數(shù)可以通過光路數(shù)來獲取，相應(yīng)的表達(dá)式如式(1)所示：

其中Vij表示在IP層建立的從i節(jié)點到j(luò)節(jié)點的光路數(shù)目。

②最小化電交換數(shù)（minT）的方法：文獻(xiàn)[4]考慮通過電交換數(shù)作為目標(biāo)函數(shù)，在網(wǎng)絡(luò)中任何光路所承載的業(yè)務(wù)量要么終止于目的節(jié)點，要么終止于中間節(jié)點，由中間節(jié)點復(fù)用到一個新的光路中去。因此，計算網(wǎng)絡(luò)中電交換的總數(shù)等于所有光路承載的業(yè)務(wù)量數(shù)減去源目節(jié)點之間的總業(yè)務(wù)量數(shù)。目標(biāo)表達(dá)式如式(2)所示：

其中：λsd為從源端節(jié)點s到目的端節(jié)點d之間的業(yè)務(wù)總量；為節(jié)點s到節(jié)點d的業(yè)務(wù)量中經(jīng)過鏈路(i,j)的業(yè)務(wù)量。

③最小化網(wǎng)絡(luò)能耗(minP)的方法：綜合上述2種方法，最小化網(wǎng)絡(luò)能耗的模型表達(dá)式如式(3)所示，其能耗包括電交換的能耗與光交換的能耗。

4 COST239網(wǎng)絡(luò)的仿真結(jié)果

假設(shè)IP層路由器Gb/s的能量消耗為14.5W，每個波長轉(zhuǎn)換器的能量消耗為34.5W，使用的仿真工具是ILP優(yōu)化器 “ILOG CPLEX”，采用的計算機為2× 2.00GHz的處理器，計算機存儲數(shù)據(jù)的容量為16G，具體的仿真結(jié)果在以下詳細(xì)描述。

圖2為COST239網(wǎng)絡(luò)(超大容量光傳輸網(wǎng)絡(luò))的拓?fù)鋱D，在該網(wǎng)絡(luò)中，節(jié)點與節(jié)點之間的鏈路通過光纖相連，光纖中的信息可向著相反方向傳輸。每個光纖鏈路中有W個 40Gb/s的波長。為了使仿真結(jié)果明顯，將W設(shè)置為8。

圖2 COST239網(wǎng)絡(luò)的拓?fù)鋱D

在表1中，采用類似于文獻(xiàn)[7]的業(yè)務(wù)矩陣，在IP核心骨干網(wǎng)中，基本的業(yè)務(wù)帶寬假設(shè)為1Gb/s，總的業(yè)務(wù)數(shù)量為T（即1Tb/s）。其它業(yè)務(wù)數(shù)目分別為1T、2T、3T、4T、5T、6T、7T。具體的仿真結(jié)果在以下詳細(xì)描述。

表1 COST239業(yè)務(wù)矩陣

考慮到用CPLEX求解ILP問題會受到計算機內(nèi)存容量的限制，首先根據(jù)圖2求解K調(diào)路徑的算法，離線求出節(jié)點與節(jié)點之間的12條可能路徑。保存到文件中，然后在已知12條路徑的基礎(chǔ)上，通過目標(biāo)函數(shù)(1～3)所示可以求出minL、minP和minT下網(wǎng)絡(luò)的資源使用情況。

圖3 不同業(yè)務(wù)疏導(dǎo)量下的網(wǎng)絡(luò)能量消耗

圖3為不同業(yè)務(wù)量下網(wǎng)絡(luò)消耗的變化，由此可以看出minL和minP網(wǎng)絡(luò)隨著網(wǎng)絡(luò)中業(yè)務(wù)量的不斷增加，網(wǎng)絡(luò)的能耗也不斷增加。而對于minT網(wǎng)絡(luò)，當(dāng)業(yè)務(wù)請求量從1T變化到2T時網(wǎng)絡(luò)的能耗增加比較少，但是業(yè)務(wù)請求量從2T到3T時迅速增加到最大值。這是因為隨著業(yè)務(wù)量的增加，網(wǎng)絡(luò)的資源變得不太充足，網(wǎng)絡(luò)將不惜犧牲一切代價來使電交換數(shù)達(dá)到最小值，此時沒有考慮到其它光路數(shù)對網(wǎng)絡(luò)能耗的影響，導(dǎo)致網(wǎng)絡(luò)能耗瞬間增大。之后，隨著網(wǎng)絡(luò)負(fù)載的不斷增加，網(wǎng)絡(luò)的能耗維持一個平衡狀態(tài)，當(dāng)業(yè)務(wù)量等于5T時網(wǎng)絡(luò)的能耗急劇減少。能耗之所以會急劇減少，是因為此時網(wǎng)絡(luò)的資源變得越來越緊張，為了滿足網(wǎng)絡(luò)中業(yè)務(wù)的需要，此時必須考慮通過電交換來給業(yè)務(wù)選擇合適的路徑。由于電交換數(shù)目的增加，使得網(wǎng)絡(luò)中能量消耗減少。與minT、minL相比可知，在相同網(wǎng)絡(luò)負(fù)載下，minP的網(wǎng)絡(luò)能耗最小,這是因為minP網(wǎng)絡(luò)能夠充分考慮到網(wǎng)絡(luò)中電交換與光路數(shù)對網(wǎng)絡(luò)能耗的影響，是將上述2種方法綜合運用，從而使網(wǎng)絡(luò)能量消耗達(dá)到最低。

圖4所示為不同業(yè)務(wù)請求下網(wǎng)絡(luò)中所建立的光路數(shù)，從圖中可知，minT網(wǎng)絡(luò)的光路數(shù)的變化與圖3中minT網(wǎng)絡(luò)的能耗變化趨勢相同，由此可以很明確地解釋minT網(wǎng)絡(luò)的能耗變化情況：當(dāng)業(yè)務(wù)量從1T變化到2T時，三者網(wǎng)絡(luò)所建立的光路數(shù)相差比較少，而minT建立最多。通過對比發(fā)現(xiàn)，隨著業(yè)務(wù)量的逐漸增加，minT對應(yīng)的光路數(shù)比minL和minP有較大的增加，直到業(yè)務(wù)量在6T時，三者才基本平衡。正如我們所料，minL網(wǎng)絡(luò)在業(yè)務(wù)量增加的過程中，使用的光路始終最小，而minP網(wǎng)絡(luò)的光路數(shù)始終處于兩者之間。從總的趨勢來看，隨著業(yè)務(wù)量的增加，建立的光路數(shù)也增加，其原因是為了路由更多的業(yè)務(wù)請求，必須要建立更多的光路來滿足業(yè)務(wù)需求。

圖4 不同業(yè)務(wù)量下所建立的光路數(shù)

圖5 不同業(yè)務(wù)量下進(jìn)行電交換的數(shù)目數(shù)

圖5所示為不同業(yè)務(wù)請求數(shù)下電交換數(shù)的變化，當(dāng)業(yè)務(wù)請求從1T變化到5T時，由于網(wǎng)絡(luò)在建立源端與目的端的鏈路首先選擇建立直接的光路數(shù)，導(dǎo)致電路數(shù)為0；當(dāng)業(yè)務(wù)請求從5T變化到7T時，電交換數(shù)在快速增加。由此可以很好地解釋，在圖3和圖4中為什么當(dāng)T從5T變化到6T時網(wǎng)絡(luò)所建立的光路數(shù)和能耗急劇減少，這是因為此時網(wǎng)絡(luò)中的負(fù)載不能夠通過建立直接光路來路由業(yè)務(wù)請求，為滿足負(fù)載需求，必須通過間接光路來路由，從而使網(wǎng)絡(luò)中的能耗急劇減少。當(dāng)業(yè)務(wù)量等于5T時，minP網(wǎng)絡(luò)由于電交換數(shù)的增加，所建立光路的數(shù)目減少，網(wǎng)絡(luò)的能耗也相應(yīng)地減少。而在業(yè)務(wù)請求的不斷增加過程中，minT網(wǎng)絡(luò)的電交換數(shù)始終最少，minL網(wǎng)絡(luò)的電交換數(shù)始終最多。

綜合圖3～圖5可知，minP網(wǎng)絡(luò)可以充分均衡網(wǎng)絡(luò)中電交換與轉(zhuǎn)換器的能量，由此來選擇是否建立更多的直接鏈路，從而使網(wǎng)絡(luò)的能耗始終達(dá)到最低。minP網(wǎng)絡(luò)為了使電交換數(shù)達(dá)到最小值，建立更多的光路數(shù)，從而使網(wǎng)絡(luò)的能耗變化比較劇烈；minL網(wǎng)絡(luò)所建立的光路是三種網(wǎng)絡(luò)中最少的，但是由于電交換的數(shù)目的不斷增加，使網(wǎng)絡(luò)消耗的能量不斷的增加。

5 結(jié)束語

IP over WDM網(wǎng)絡(luò)的能耗問題可以歸結(jié)為求解ILP，然而它卻受到存儲容量的限制，為了減少ILP問題的復(fù)雜度，本文提出了一種基于K算法的綠色I(xiàn)P over WDM網(wǎng)絡(luò)的設(shè)計方法。本算法將物理層光路的路由與IP層的業(yè)務(wù)路由分開來求，首先求出物理層中可能的K條光路路徑，然后在IP層中通過建立ILP表達(dá)式來路由業(yè)務(wù)請求，最后通過是否使用K條路徑來將二者相關(guān)聯(lián)。考慮到能耗網(wǎng)絡(luò)是一種有效的節(jié)省網(wǎng)絡(luò)能耗的方法，我們對比了在K算法下，不同網(wǎng)絡(luò)的能耗變化。仿真結(jié)果顯示，基于K算法的綠色I(xiàn)P over WDM網(wǎng)絡(luò)能夠選擇路由業(yè)務(wù)請求的合理路徑，從而使網(wǎng)絡(luò)的能耗達(dá)到最低。

[1]ZHU K,MUKHERJEE B.Traffic grooming in an optical WDM mesh network[J].Selected Areas in Communications,IEEE Journal on,2002,20 (1):122-133.

[2]CHEN B,BOSE S K,ZHONG W D,et al.A new lightpath establishing method for dynamic traffic grooming under the overlay model[J].Photonic Network Communications,2009,17(1):11-20.

[3]陳彬,鮑東暉,蘇恭超,等.基于路徑的整數(shù)線性規(guī)劃方法在阻塞IP over WDM網(wǎng)絡(luò)中能耗優(yōu)化的應(yīng)用 [J].電子與信息學(xué)報,2015,37(3): 715-720.

[4]DUTTA R,ROUSKAS G N.On optimal traffic grooming in WDM rings[J].Selected Areas in Communications IEEE Journal on,2001,20(1): 110-121.

[5]王汝言,馬禮冬,張超,等.IP over WDM網(wǎng)絡(luò)中能耗自感知的混合疏導(dǎo)專有保護(hù)算法[J].光電子·激光，2014,25(9):1701-1708.

[6]SHEN G,TUCKER R S.Energy-minimized design for IP over WDM networks[J].Optical Communications and Networking,IEEE/OSA Journal of,2009,1(1):176-186.

[7]MUSUMECI F,TORNATORE M,PATTAVINA A.A power consumption analysis for IP-over-WDM core network architectures[J].Journal of Optical Communications and Networking,2012,4(2):108-117.

[8]XIN C.Blocking Analysis of Dynamic Traffic Grooming in Mesh WDM Optical Networks[J].IEEE/ACM Transactions on Networking,2007,15(3): 721-733.

[9]CHEN B,JIANG Z,TENG R K F,et al.An Energy Efficiency Optimization Method in Bandwidth Constrained IP over WDM Networks[C]. International Conference on Information,Tainan China:2013:1-4.

[10]白軼多,胡鵬,夏蘭芳,等.關(guān)于k次短路徑問題的分析與求解[J].武漢大學(xué)學(xué)報（信息科學(xué)版）,2009(4):492-494.

Design method of green IP over WDM network based onKalgorithm

TIAN Li-wei1,SUN Yu2,ZHANG Xu1
（1.Department of Computer,Guangdong University of Science and Technology, Dongguan Guangdong 523083,China;2.Guangdong Planning and Designing Institute of Telecommunications Co Ltd,Dongguan Guangdong 523120,China)

By constructing integer linear programming(ILP),the energy consumption of the network is calculated,and the memory space of the ILP is required.However,insufficient memory is still one of practical issues.With the consideration of such problem,this paper presented a method to design green IP over WDM networks withKalgorithm,which is based on the traditional method of virtual topology network traffic grooming.Firstly,figured out the possibleKpaths between node and node in network withKalgorithm,and then to solve the distribution of network resources by building an integer linear programming(ILP).The paper mainly analyzed the model of energy consumption：utilizing mathematical expressions to describe three models of IP over WDM network energy consumption based onKalgorithm.

IP over WDM network,ILP,Kalgorithm,network energy consumption

TP393.2

A

1002-5561（2016）02-0012-04

10.13921/j.cnki.issn1002-5561.2016.02.004

2015-11-17。

廣東省教育廳重大科研平臺項目（2014KTSCX210）資助。

田立偉(1981-)，男，碩士，高級工程師，主要從事通信網(wǎng)絡(luò)、無線傳感網(wǎng)絡(luò)方面的研究。