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

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

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

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

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

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

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

1 引言

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

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

2 IP over WDM網絡結構

圖1 IP over WDM 網絡結構

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

3 兩種ILP算法

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

在IP over WDM網絡中，變量m, n表示每根光纖的兩個端點，i, j表示每條光路的兩個端點，而s, d表示在IP層連接請求的源端點和目的端點。

3.1 基于連接的ILP算法

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

圖2 透明IP over WDM網絡模型下的流量疏導

式(1)為IP流在虛擬拓撲的路由約束。式(2)保證網絡中路由的業(yè)務不會超過所建立光路的容量。式(3)為光層路由的流約束。式(4)保證在鏈路(m,n)上任意波長w最多只能被一條光路使用。式(5)是光路最大可達距離約束。

最大化網絡的通過率f1：

最小化網絡的能耗f2：

本文先以式(6)作為目標函數，以式(1)～式(5)作為約束，計算出網絡的最大通過率，用T表示。然后以式(7)作為目標函數，將式(8)加入約束方程組來優(yōu)化網絡的能耗。

3.2 基于路徑的ILP算法

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

參數：Dijk為端點I 到 j 的第k 條路徑的長度。

約束如下：

式(9)保證網絡中路由的業(yè)務不會超過所建立光路的容量。式(10)確保沒有兩個光路在同一個鏈路上共享同一個波長。式(11)為距離的限制，每個光路最大可達距離為2000 km。

最小化網絡能耗f3：

在基于路徑的ILP算法中，以式(6)為目標函數，式(1)、式(9)、式(10)、式(11)作為約束條件計算出網絡的最大通過率T，然后以式(12)為目標函數，將式(8)加入約束條件來優(yōu)化網絡能耗。

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

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

4 仿真結果與分析

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

圖3 實驗采用網絡拓撲(長度單位：km)

從仿真結果得出，在不同波長數目下兩種算法在同一網絡里的通過率相同，這是因為兩種算法采用了同樣的網絡和業(yè)務模型。通過表1和表2可以看出網絡通過率隨著每根光纖所含波長數的增加而增大。在COST239網絡中，當波長數量達到9時，2000 Gbps的業(yè)務量全部通過。所以，N大于9后，該網絡的容量大于業(yè)務量。對于隨機網絡拓撲，當波長數量達到10時，600 Gbps的業(yè)務量全部通過。所以當N大于10以后，該網絡容量也大于業(yè)務量。

表1 COST239網絡通過率

表2 隨機網絡通過率

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

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

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

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

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

圖4 光路數量和每光纖波長數量的關系

圖5 電交換業(yè)務量比和每光纖波長數量的關系

圖6 平均能耗和每光纖波長數量的關系

5 結論

本文運用了基于路徑的ILP算法，通過充分利用光層路徑來優(yōu)化阻塞IP over WDM網絡的能耗，并與基于連接的ILP算法做了仿真比較。仿真結果顯示，在稠密網絡(COST239網絡)中，由于有豐富的路徑選擇，基于路徑的ILP算法相對基于連接的ILP算法更能夠充分調動光層資源，降低網絡能耗。

[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] 郭愛煌, 薛琳. 綠色 IP over WDM 網絡研究進展[J]. 激光與光電子學進展, 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年生，副教授， 研究領域為光網絡優(yōu)化.

鮑東暉： 男，1988年生，碩士生，研究領域為光網絡優(yōu)化.

蘇恭超： 男，1979年生，博士， 講師，研究領域為網絡優(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改回

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

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