基于路徑的整數(shù)線性規(guī)劃方法在阻塞IP over WDM網(wǎng)絡(luò)中能耗優(yōu)化的應(yīng)用

陳 彬 鮑東暉蘇恭超 代明軍 王 暉 林曉輝

(深圳大學(xué)信息工程學(xué)院 深圳 518060)

基于路徑的整數(shù)線性規(guī)劃方法在阻塞IP over WDM網(wǎng)絡(luò)中能耗優(yōu)化的應(yīng)用

陳 彬 鮑東暉*蘇恭超 代明軍 王 暉 林曉輝

(深圳大學(xué)信息工程學(xué)院 深圳 518060)

針對(duì)容量有限的透明IP over WDM網(wǎng)絡(luò)模型，該文提出一種基于路徑的整數(shù)線性規(guī)劃(ILP)方法來(lái)優(yōu)化網(wǎng)絡(luò)的能耗。相對(duì)基于連接的整數(shù)線性規(guī)劃方法，該方法可以在光層提供更多的路徑選擇組合。仿真結(jié)果顯示，基于路徑的整數(shù)線性規(guī)劃方法能夠通過(guò)選擇更優(yōu)的光路組合進(jìn)一步降低網(wǎng)絡(luò)的能耗。

光通信；IP over WDM；能耗；整數(shù)線性規(guī)劃

1 引言

據(jù)統(tǒng)計(jì)[1]，信息和通信技術(shù)的碳排放占據(jù)全球所有碳排放的2%，這一比例到2020年將翻一番。其中，通信網(wǎng)絡(luò)能耗是信息和通信技術(shù)能耗的主要構(gòu)成部分[2]。通信網(wǎng)絡(luò)的能耗研究已經(jīng)引起了廣泛的關(guān)注。IP over WDM網(wǎng)絡(luò)是核心網(wǎng)絡(luò)的主要技術(shù)，針對(duì)該網(wǎng)絡(luò)能耗問(wèn)題的研究對(duì)于節(jié)能降耗也具有重要的意義。

網(wǎng)絡(luò)能耗與網(wǎng)絡(luò)資源的使用密切相關(guān)，綠色I(xiàn)P over WDM網(wǎng)絡(luò)要求在給定的網(wǎng)絡(luò)拓?fù)洹㈡溌啡萘?、業(yè)務(wù)負(fù)載的條件下，為業(yè)務(wù)請(qǐng)求尋找路由以及分配帶寬資源(Router and Wwavelength Aassignment, RWA)，在保證規(guī)定網(wǎng)絡(luò)通信性能的同時(shí)盡量減少設(shè)備的使用[3]。業(yè)務(wù)流量疏導(dǎo)機(jī)制通過(guò)將多個(gè)低速IP業(yè)務(wù)流匯集到同一個(gè)大容量的WDM波長(zhǎng)信道進(jìn)行傳輸，重復(fù)利用已開(kāi)啟的設(shè)備，是IP over WDM網(wǎng)絡(luò)節(jié)約資源的有效方法[4]。為實(shí)現(xiàn)網(wǎng)絡(luò)配制的最優(yōu)化，該問(wèn)題往往都被轉(zhuǎn)化為一個(gè)整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)問(wèn)題。目前對(duì)IP over WDM網(wǎng)絡(luò)能耗的研究主要在無(wú)容量約束網(wǎng)絡(luò)中，假設(shè)所有業(yè)務(wù)都被接受的情況[5-8]，但是我們認(rèn)為在容量有限的網(wǎng)絡(luò)中即阻塞網(wǎng)絡(luò)中的能耗優(yōu)化研究更貼近網(wǎng)絡(luò)實(shí)際，因此我們提出一種雙目標(biāo)方法，該方法先計(jì)算出網(wǎng)絡(luò)的最大通過(guò)率，然后在此基礎(chǔ)上優(yōu)化網(wǎng)絡(luò)的能耗，解決了阻塞網(wǎng)絡(luò)中的能耗最小化求解問(wèn)題[9]。文獻(xiàn)[9]采用基于連接的ILP算法，該方法在透明光網(wǎng)絡(luò)模型下[10]，限制了光路選擇的自由度。為進(jìn)一步降低網(wǎng)絡(luò)能耗，本文嘗試采用基于路徑的ILP方法[11,12]，擴(kuò)大光路選擇的自由度，希望能夠進(jìn)一步優(yōu)化網(wǎng)絡(luò)能耗。

2 IP over WDM網(wǎng)絡(luò)結(jié)構(gòu)

圖1 IP over WDM 網(wǎng)絡(luò)結(jié)構(gòu)

本文采用透明IP over WDM網(wǎng)絡(luò)[10]能耗模型如圖1所示。在IP層中，核心路由器從低端路由器那里匯聚業(yè)務(wù)，將其轉(zhuǎn)發(fā)給光交換節(jié)點(diǎn)。光交換節(jié)點(diǎn)之間通過(guò)光纖相互連接。在每根光纖中包含多個(gè)波長(zhǎng)。與每根光纖相連的復(fù)用器與解復(fù)用器，能夠?qū)崿F(xiàn)波長(zhǎng)復(fù)用和解復(fù)用，以便在光交叉連接器(Optical Cross-Connect, OXC)中進(jìn)行交換。在每根光纖鏈路每隔固定距離部署摻鉺光纖放大器光(Erbium Doped Fibre Amplifier, EDFA)對(duì)光信號(hào)進(jìn)行的放大。另外，光信號(hào)的傳輸距離受到光纖以及光器件線性和非線性損傷的影響，最大傳輸距離被限制[13]。對(duì)于10 Gbps的光信號(hào)來(lái)說(shuō)，最大可傳輸距離只有2000 km。由于EDFA在光網(wǎng)絡(luò)中已經(jīng)鋪設(shè)完畢，它們的能耗是固定的。對(duì)于任何一種業(yè)務(wù)量疏導(dǎo)的方法，在業(yè)務(wù)給定的情況下，業(yè)務(wù)終端節(jié)點(diǎn)路由器對(duì)信號(hào)的處理能耗也是固定的，所以在本文中我們僅僅考慮IP連接中間節(jié)點(diǎn)的能耗，它包括IP路由器、轉(zhuǎn)換器、和光交叉連接器的能耗，分別用PI, PT和PO表示。下面以圖2為例，計(jì)算在透明光網(wǎng)絡(luò)中進(jìn)行流量疏導(dǎo)的網(wǎng)絡(luò)能耗。圖2中有兩個(gè)IP連接請(qǐng)求，分別為從端點(diǎn)A到B帶寬為r1的請(qǐng)求1和從端點(diǎn)A到E帶寬為r2的請(qǐng)求2。假設(shè)波長(zhǎng)帶寬為10 Gbps。為容納請(qǐng)求1和請(qǐng)求2，網(wǎng)絡(luò)通過(guò)建立光路為IP層提供從A到B和E的可達(dá)路徑。首先，網(wǎng)絡(luò)為請(qǐng)求1建立了從A到B的光路AB。為容納請(qǐng)求2，網(wǎng)絡(luò)需要在使用已有光路AB的基礎(chǔ)上再建立連接節(jié)點(diǎn)B和E的光路。由于從B到D距離為2400 km超過(guò)了2000 km。所以網(wǎng)絡(luò)需要建立從B到C和從C到E兩條光路。請(qǐng)求2通過(guò)3條光路到達(dá)節(jié)點(diǎn)E，并分別需要在B和C節(jié)點(diǎn)處進(jìn)行光-電-光轉(zhuǎn)換和路由。網(wǎng)絡(luò)為容納兩個(gè)連接請(qǐng)求，共建立3條光路，這其中，光路AB使用了2個(gè)轉(zhuǎn)換器和2次光交換；光路BC使用了2個(gè)轉(zhuǎn)換器和2次光交換；光路CE跨越了D節(jié)點(diǎn)，增加了一次光交換，使用了2個(gè)轉(zhuǎn)換器和3次光交換。所以網(wǎng)絡(luò)總共使用了6個(gè)轉(zhuǎn)換器和7次光交換。B和C節(jié)點(diǎn)的路由器對(duì)請(qǐng)求2實(shí)施了兩次IP路由。除去源節(jié)點(diǎn)和目的節(jié)點(diǎn)路由器對(duì)業(yè)務(wù)處理的能耗，網(wǎng)絡(luò)總能耗為6PT+7PO+ 2r2?PI。

3 兩種ILP算法

在阻塞IP over WDM網(wǎng)絡(luò)的能耗問(wèn)題中，必須同時(shí)優(yōu)化網(wǎng)絡(luò)通過(guò)率和網(wǎng)絡(luò)能耗這兩個(gè)相互矛盾的目標(biāo)。文獻(xiàn)[9]假設(shè)通過(guò)率是更重要的目標(biāo)，采用主目標(biāo)求解法先求解最大的網(wǎng)絡(luò)通過(guò)率，然后在網(wǎng)絡(luò)最大通過(guò)率的約束下進(jìn)行能耗優(yōu)化。文獻(xiàn)[9]在透明光網(wǎng)絡(luò)模型下采用基于連接的ILP算法進(jìn)行求解。但該方法在對(duì)光路長(zhǎng)度約束的同時(shí)也限制了光路選擇的自由度。本文嘗試采用基于路徑的ILP方法，擴(kuò)大光路選擇的自由度，進(jìn)一步優(yōu)化網(wǎng)絡(luò)能耗。下面，我們將列出兩種算法并進(jìn)行比較。

在IP over WDM網(wǎng)絡(luò)中，變量m, n表示每根光纖的兩個(gè)端點(diǎn)，i, j表示每條光路的兩個(gè)端點(diǎn)，而s, d表示在IP層連接請(qǐng)求的源端點(diǎn)和目的端點(diǎn)。

3.1 基于連接的ILP算法

參數(shù)如下：G(V, E)為物理拓?fù)?，V為節(jié)點(diǎn)的集合，E為光纖連接的集合。N為每個(gè)光纖含有的波長(zhǎng)的數(shù)量，假設(shè)每個(gè)光纖攜帶同樣數(shù)量的波長(zhǎng)。B 為每個(gè)波長(zhǎng)信道的容量。x為 IP 連接請(qǐng)求的基本帶寬單位。Λ為業(yè)務(wù)量矩陣。sdΛ表示從端點(diǎn)s 到端點(diǎn)d帶寬為x的連接請(qǐng)求的個(gè)數(shù)。Dmn為相鄰節(jié)點(diǎn)m和n之間的距離。

圖2 透明IP over WDM網(wǎng)絡(luò)模型下的流量疏導(dǎo)

式(1)為IP流在虛擬拓?fù)涞穆酚杉s束。式(2)保證網(wǎng)絡(luò)中路由的業(yè)務(wù)不會(huì)超過(guò)所建立光路的容量。式(3)為光層路由的流約束。式(4)保證在鏈路(m,n)上任意波長(zhǎng)w最多只能被一條光路使用。式(5)是光路最大可達(dá)距離約束。

最大化網(wǎng)絡(luò)的通過(guò)率f1：

最小化網(wǎng)絡(luò)的能耗f2：

本文先以式(6)作為目標(biāo)函數(shù)，以式(1)～式(5)作為約束，計(jì)算出網(wǎng)絡(luò)的最大通過(guò)率，用T表示。然后以式(7)作為目標(biāo)函數(shù)，將式(8)加入約束方程組來(lái)優(yōu)化網(wǎng)絡(luò)的能耗。

3.2 基于路徑的ILP算法

在基于路徑的ILP算法中，首先使用K條最短路徑(K Shortest Path) 算法[14]計(jì)算給定的WDM光網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的K條最短路徑。

參數(shù)：Dijk為端點(diǎn)I 到 j 的第k 條路徑的長(zhǎng)度。

約束如下：

式(9)保證網(wǎng)絡(luò)中路由的業(yè)務(wù)不會(huì)超過(guò)所建立光路的容量。式(10)確保沒(méi)有兩個(gè)光路在同一個(gè)鏈路上共享同一個(gè)波長(zhǎng)。式(11)為距離的限制，每個(gè)光路最大可達(dá)距離為2000 km。

最小化網(wǎng)絡(luò)能耗f3：

在基于路徑的ILP算法中，以式(6)為目標(biāo)函數(shù)，式(1)、式(9)、式(10)、式(11)作為約束條件計(jì)算出網(wǎng)絡(luò)的最大通過(guò)率T，然后以式(12)為目標(biāo)函數(shù)，將式(8)加入約束條件來(lái)優(yōu)化網(wǎng)絡(luò)能耗。

3.3 基于路徑ILP算法的優(yōu)勢(shì)

在基于連接的ILP算法中，如果從節(jié)點(diǎn)i到j(luò)有多條不共享連接的光路都使用波長(zhǎng)w，式(5)里的距離約束就變成了對(duì)多個(gè)光路路徑長(zhǎng)度之和的約束。所以只能是0-1變量，也就是從節(jié)點(diǎn)i到j(luò)使用波長(zhǎng)w的光路只能有一條，才能保證式(5)的正確性，即透明光路的最長(zhǎng)距離不大于2000 km。而基于路徑的ILP算法中，網(wǎng)絡(luò)中每?jī)蓚€(gè)節(jié)點(diǎn)之間的路徑預(yù)先被計(jì)算出來(lái)。算法可根據(jù)式(11)直接在路徑集合里選擇路徑。從節(jié)點(diǎn)i到j(luò)的多條路徑，只要不共享連接，就可以使用相同的波長(zhǎng)w建立光路。網(wǎng)絡(luò)中可選擇的路徑越多，則基于路徑的ILP算法就能比基于連接的ILP算法提供更多的路徑組合，從而為網(wǎng)絡(luò)能耗的優(yōu)化提供更多的可能。

4 仿真結(jié)果與分析

仿真采用了11個(gè)節(jié)點(diǎn)的兩種不同稠密度的網(wǎng)絡(luò)。 COST239[9]網(wǎng)絡(luò)如圖3(a)所示，有26個(gè)連接，平均節(jié)點(diǎn)度為4.73。隨機(jī)網(wǎng)絡(luò)如圖3(b)所示，有17個(gè)連接，平均節(jié)點(diǎn)度為3.09。節(jié)點(diǎn)之間連接的長(zhǎng)度單位為km。在網(wǎng)絡(luò)中每個(gè)連接兩端的節(jié)點(diǎn)被稱為一對(duì)相鄰節(jié)點(diǎn)，每對(duì)相鄰節(jié)點(diǎn)由兩根光纖連接，兩根光纖的傳輸方向相反。每根光纖里有N個(gè)波長(zhǎng)，每個(gè)波長(zhǎng)帶寬為10 Gbps。對(duì)于COST239網(wǎng)絡(luò)業(yè)務(wù)量矩陣采用文獻(xiàn)[15]中的業(yè)務(wù)量分布，共有1000個(gè)業(yè)務(wù)。每個(gè)業(yè)務(wù)帶寬為2 Gbps，所以總業(yè)務(wù)量為2000 Gbps。對(duì)于隨機(jī)網(wǎng)絡(luò)我們?cè)诠?jié)點(diǎn)間隨機(jī)分配了300個(gè)業(yè)務(wù)，每個(gè)業(yè)務(wù)帶寬為2 Gbps，總業(yè)務(wù)量為600Gbps。假定IP路由器的能耗為14.5 W/Gbps；每一個(gè)WDM轉(zhuǎn)換器的能耗為34.5 W；每波長(zhǎng)光交換的能耗為1.5 W[16]。預(yù)先采用k條最短路徑算法在每個(gè)網(wǎng)絡(luò)中為每個(gè)節(jié)點(diǎn)對(duì)計(jì)算出K = 10條最短路徑。仿真使用配備了主頻為2.80 GHz的Inter i5 CPU和4 GB RAM的HP Elite7100 MT個(gè)人計(jì)算機(jī)，在VS2010環(huán)境下用IBM公司的CPLEX線性規(guī)劃軟件對(duì)算法進(jìn)行求解。

圖3 實(shí)驗(yàn)采用網(wǎng)絡(luò)拓?fù)?長(zhǎng)度單位：km)

從仿真結(jié)果得出，在不同波長(zhǎng)數(shù)目下兩種算法在同一網(wǎng)絡(luò)里的通過(guò)率相同，這是因?yàn)閮煞N算法采用了同樣的網(wǎng)絡(luò)和業(yè)務(wù)模型。通過(guò)表1和表2可以看出網(wǎng)絡(luò)通過(guò)率隨著每根光纖所含波長(zhǎng)數(shù)的增加而增大。在COST239網(wǎng)絡(luò)中，當(dāng)波長(zhǎng)數(shù)量達(dá)到9時(shí)，2000 Gbps的業(yè)務(wù)量全部通過(guò)。所以，N大于9后，該網(wǎng)絡(luò)的容量大于業(yè)務(wù)量。對(duì)于隨機(jī)網(wǎng)絡(luò)拓?fù)?，?dāng)波長(zhǎng)數(shù)量達(dá)到10時(shí)，600 Gbps的業(yè)務(wù)量全部通過(guò)。所以當(dāng)N大于10以后，該網(wǎng)絡(luò)容量也大于業(yè)務(wù)量。

表1 COST239網(wǎng)絡(luò)通過(guò)率

表2 隨機(jī)網(wǎng)絡(luò)通過(guò)率

在最大通過(guò)率(見(jiàn)表1和表2)的約束下，分別對(duì)兩個(gè)網(wǎng)絡(luò)采用兩種算法優(yōu)化能耗。圖4比較兩種網(wǎng)絡(luò)建立的光路數(shù)目。圖5比較兩種算法的電交換業(yè)務(wù)量比，用表示：它是網(wǎng)絡(luò)中路由器對(duì)經(jīng)過(guò)業(yè)務(wù)的總交換量與網(wǎng)絡(luò)接納業(yè)務(wù)總量(通過(guò)率)之比。圖6比較兩種算法的網(wǎng)絡(luò)平均能耗。網(wǎng)絡(luò)平均能耗定義為網(wǎng)絡(luò)總能耗除以相應(yīng)的網(wǎng)絡(luò)通過(guò)率：2/PfT=。

先看COST239網(wǎng)絡(luò)的仿真結(jié)果。在圖4(a)中，N = 1時(shí)，兩種算法所建立的光路數(shù)相同。隨著波長(zhǎng)數(shù)N的增加，兩種算法所建立的光路數(shù)不斷增加。N ＞5以后，基于連接方法使用的光路數(shù)增加得更快。在N = 9時(shí)，兩種算法使用的光路數(shù)量差距達(dá)到最大。隨著波長(zhǎng)數(shù)目的繼續(xù)增加，兩種算法下的光路數(shù)目開(kāi)始減少。在基于路徑的算法下，N ＞ 10以后，光路數(shù)目穩(wěn)定在216左右。而在基于連接的方法下，直到N = 15光路的數(shù)目才停止減少。當(dāng)N = 16，基于路徑的算法所建立的光路仍然明顯少于基于連接的算法。

圖5(a)中，N = 1時(shí)，兩種算法的電交換業(yè)務(wù)比有同樣的最大值。這是因?yàn)镹 = 1時(shí)，網(wǎng)絡(luò)主要采用單跳光路，業(yè)務(wù)的交換方式主要為電交換。隨著每光纖波長(zhǎng)數(shù)量的增加，基于路徑的ILP方法使得網(wǎng)絡(luò)的電交換業(yè)務(wù)比下降，在N ＞ 5之后開(kāi)始緩慢地增加，直到N = 9。在N＞ 9之后，網(wǎng)絡(luò)的電交換業(yè)務(wù)比又緩慢下降穩(wěn)定在5%左右。而在基于連接的方法下，隨著N值的增長(zhǎng)，網(wǎng)絡(luò)電交換業(yè)務(wù)比先下降然后明顯上升，在N = 9時(shí)達(dá)到最高峰，大約是基于路徑方法的3倍。電交換業(yè)務(wù)比上升可以歸結(jié)為兩個(gè)原因：(1)我們?cè)诜抡嬷惺褂玫耐ㄟ^(guò)率指標(biāo)指的是接受了多少個(gè)連接請(qǐng)求，而不考慮連接請(qǐng)求的實(shí)際距離。優(yōu)化算法為了達(dá)到最大的通過(guò)率自然會(huì)選擇先接受占用資源少的連接請(qǐng)求。這里的資源和物理拓?fù)淅锏木嚯x、跳數(shù)有關(guān)。(2)在該論文的主目標(biāo)優(yōu)化方法中，最大通過(guò)率為第1目標(biāo)，最小能耗為第2目標(biāo)。隨著N值的增大，所有的短距離業(yè)務(wù)都被接受了以后，網(wǎng)絡(luò)不得不開(kāi)始接受長(zhǎng)距離的業(yè)務(wù)以提高網(wǎng)絡(luò)的通過(guò)率?；谶B接的方法需要大量的使用電交換來(lái)彌補(bǔ)光路選擇受限的不足，以提高網(wǎng)絡(luò)通過(guò)率。所以在基于連接的方法下，電交換業(yè)務(wù)量比隨著N增加顯著的降低又顯著的升高。比較圖5(a)和圖4(a)，當(dāng)N ＞ 1以后，雖然兩種算法的光路數(shù)目相近，但是基于路徑的方法可以使用較少的電交換來(lái)達(dá)到相同的通過(guò)率。這說(shuō)明基于路徑的方法采用了更優(yōu)的光路組合。N ＞ 5以后，基于路徑的方法相比基于連接的方法，甚至可以使用更少的光路，在相同的通過(guò)率下將電交換業(yè)務(wù)量比維持在5%附近。而在基于連接的方法下，電交換業(yè)務(wù)量比顯著增加直到N = 9。隨著波長(zhǎng)數(shù)目的增加，網(wǎng)絡(luò)容量大于業(yè)務(wù)需求后，基于連接的方法有更多的波長(zhǎng)路徑選擇來(lái)應(yīng)付容納業(yè)務(wù)和降低網(wǎng)絡(luò)能耗的雙重需要，通過(guò)采用不同波長(zhǎng)路徑的選擇來(lái)繞過(guò)為0-1變量的約束。所以在基于連接的ILP方法下，電交換業(yè)務(wù)量比在光路數(shù)N大于9后，逐漸降低。在N = 16時(shí)，基于連接的方法才具有和基于路徑方法相近的電交換業(yè)務(wù)量比。

圖6(a)和圖5(a)的趨勢(shì)類似，這是因?yàn)殡娊粨Q在網(wǎng)絡(luò)能耗中占據(jù)主要部分[5]。在N = 9時(shí)，也就是網(wǎng)絡(luò)容量和負(fù)載匹配的情況下，基于路徑方法相比基于連接方法節(jié)約的能源最多，節(jié)約了大約25%的能耗。對(duì)比圖4(a)、圖5(a)，這主要是由于節(jié)省電交換的貢獻(xiàn)。當(dāng)N ＞ 9后，兩種算法的能耗差距逐步減小，但直到N = 16，基于路徑的ILP算法仍然有明顯的優(yōu)勢(shì)。

隨機(jī)網(wǎng)絡(luò)的仿真結(jié)果如圖4(b)、圖5(b)、圖6(b)所示。從仿真結(jié)果看出， 基于路徑的方法相對(duì)基于連接的方法沒(méi)有顯著的優(yōu)勢(shì)。圖4(b)中，隨著波長(zhǎng)數(shù)目N的增大，網(wǎng)絡(luò)中建立的光路不斷增多。當(dāng)N=10時(shí)，網(wǎng)絡(luò)中的光路數(shù)達(dá)到最大值。隨著波長(zhǎng)數(shù)的繼續(xù)增大，光路數(shù)開(kāi)始降低直到N=13。圖5(b)中，網(wǎng)絡(luò)的電交換業(yè)務(wù)量比在N = 1時(shí)具有最大值，隨著N的增大網(wǎng)絡(luò)能耗先降低再升高，直到N =10，然后下降。在N＞11后，繼續(xù)增加波長(zhǎng)不能再改善網(wǎng)絡(luò)的電交換業(yè)務(wù)量比。圖6(b)和圖5(b)的趨勢(shì)相似，12＞N＞3時(shí)，基于路徑的方法的網(wǎng)絡(luò)平均能耗有微弱的優(yōu)勢(shì)。比較圖4(b)和圖5(b)，我們發(fā)現(xiàn)基于路徑的方法和基于連接的方法建立的光路數(shù)接近，并且采用的電交換量也接近，以至于圖6(b)中的網(wǎng)絡(luò)平均能耗表現(xiàn)也接近。這是因?yàn)樵谙∈杈W(wǎng)絡(luò)中，雖然預(yù)先對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)對(duì)之間計(jì)算了10條最短路徑，但大部分的路徑長(zhǎng)度都大于2000 km。在長(zhǎng)度小于2000 km的路徑中，不共享同一光纖的路徑數(shù)量少。所以基于路徑的方法并沒(méi)有很多的路徑選擇。而對(duì)基于連接的算法來(lái)說(shuō)，稀疏網(wǎng)絡(luò)導(dǎo)致的可能取值少，0-1變量的限制對(duì)算法的影響沒(méi)有在復(fù)雜網(wǎng)絡(luò)里的大。所以在稀疏網(wǎng)絡(luò)中，基于路徑的方法與基于連接的方法有相似的網(wǎng)絡(luò)表現(xiàn)。

圖4 光路數(shù)量和每光纖波長(zhǎng)數(shù)量的關(guān)系

圖5 電交換業(yè)務(wù)量比和每光纖波長(zhǎng)數(shù)量的關(guān)系

圖6 平均能耗和每光纖波長(zhǎng)數(shù)量的關(guān)系

5 結(jié)論

本文運(yùn)用了基于路徑的ILP算法，通過(guò)充分利用光層路徑來(lái)優(yōu)化阻塞IP over WDM網(wǎng)絡(luò)的能耗，并與基于連接的ILP算法做了仿真比較。仿真結(jié)果顯示，在稠密網(wǎng)絡(luò)(COST239網(wǎng)絡(luò))中，由于有豐富的路徑選擇，基于路徑的ILP算法相對(duì)基于連接的ILP算法更能夠充分調(diào)動(dòng)光層資源，降低網(wǎng)絡(luò)能耗。

[1] Neves L, Krajewski J, Jung P, et al.. SMARTer2020[R]. Global e-Sustainability Initiative (GeSI), 2012.

[2] Yun D and Lee J. Research in green network for future Internet[J]. Journal of Computing Science and Engineering (KIISE), 2010, 28(1): 41-51.

[3] 郭愛(ài)煌, 薛琳. 綠色 IP over WDM 網(wǎng)絡(luò)研究進(jìn)展[J]. 激光與光電子學(xué)進(jìn)展, 2012, 49(7): 1-8.

Guo Ai-huang and Xue Lin. A review of green IP over WDM networks grooming[J]. Laser and Optoelectronics Progress, 2012, 49(7): 1-8.

[4] Lee C and Rhee J K. Traffic grooming for IP-over-WDM Networks: energy and delay perspectives[J]. Journal of Optical Communications and Networking, 2014, 6(2): 96-103.

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

[6] Zhang Y, Tornatore M, Chowdhury P, et al.. Energy optimization in IP-over-WDM networks[J]. Optical Switching and Networking, 2011, 8(3): 171-180.

[7] Schondienst T and Vokkarane V M. Renewable energy-aware grooming in IP-over-WDM networks[C]. Proceedings of the IEEE International Conference on Computing, Networking and Communications (ICNC), Honolulu, Hawaii, USA,. 2014: 163-167.

[8] Hasan M M, Farahmand F, Jue J P, et al.. A study of energy-aware traffic grooming in optical networks: Static and dynamic cases[J]. IEEE Systems Journal, 2013, 7(1): 161-173.

[9] Chen B, Jiang Z M, Teng R K F, et al.. An energy efficiency optimization method in bandwidth constrained IP over WDM networks[C]. Proceedings of the 9th International Conference on Communications and Signal Processing (ICICS), Tainan, 2013: 1-4.

[10] Chowdhury P, Tornatore M, Nag A, et al.. On the design of energy-efficient Mixed-Line-Rate (MLR) optical networks[J]. Journal of Lightwave Technology, 2012, 30(1): 130-139.

[11] Liu Z and Rouskas G N. A fast path-based ILP formulation for offline RWA in mesh optical networks[C]. Proceedings of the IEEE Global Communications Conference (GLOBECOM), Anaheim, California, USA, Dec. 2012: 2990-2995.

[12] Yoon Y R, Lee T J, Chung M Y, et al.. Traffic grooming based on shortest path in optical WDM mesh networks[C]. Proceedings of the IEEE International Conference on Computacional Science (ICCS’05), Heidelberg, Berlin, 2005: 1120-1124.

[13] Rizzelli G, Musumeci F, Tornatore M, et al.. Wavelength–aware translucent network design[C]. Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference (OFC/NFOEC 2011), Los Angeles, California, USA, 2011: OThAA2.

[14] Yen J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716.

[15] Morea A, Perelló J, Spadaro S, et al.. Protocol enhancements for “Greening” optical networks[J]. Bell Labs Technical Journal, 2013, 18(3): 211-230.

[16] Francesco M, Tornatore M, and 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.

陳 彬： 男，1975年生，副教授， 研究領(lǐng)域?yàn)楣饩W(wǎng)絡(luò)優(yōu)化.

鮑東暉： 男，1988年生，碩士生，研究領(lǐng)域?yàn)楣饩W(wǎng)絡(luò)優(yōu)化.

蘇恭超： 男，1979年生，博士， 講師，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)優(yōu)化.

The Application of the Path Based Integer Linear Programming Method for Optimizing Energy Consumption in Blocking IP over WDM Networks

Chen Bin Bao Dong-hui Su Gong-chao Dai Ming-jun Wang Hui Lin Xiao-hui
(College of Information Engineering, Shenzhen University, Shenzhen 518060, China)

A path based Integer Linear Programming (ILP) method is proposed to optimize the network energy consumption under the bandwidth constrained transparent IP over WDM network model. Compared with the link based ILP method, this method can provide more lightpath combinations in the optical layer. The simulation results show that the path based ILP method can select the better lightpath combinations than the link based ILP method, and achieve lower network energy consumption.

Optical communication; IP over WDM; Energy consumption; Integer Linear Programming (ILP)

TN915.63

A

1009-5896(2015)03-0715-06

10.11999/JEIT140704

2014-05-27收到，2014-09-24改回

國(guó)家自然科學(xué)基金(61301182)，廣東省自然科學(xué)基金(S20130400 16857), 教育部博士點(diǎn)基金(20134408120004)，廣東省教育廳育苗工程基金(S2013LYM_0077), 深圳市基礎(chǔ)研究項(xiàng)目(JCYJ201404180 95735590)和深圳大學(xué)科研基金資助面上項(xiàng)目(00036107，00002501)資助課題

*通信作者：鮑東暉 dhbao@foxmail.com