伍元勝，郭兵，沈艷，王繼禾，劉嘯濱

(1. 四川大學 計算機學院, 四川 成都 610065；2. 成都信息工程學院 控制工程學院, 四川 成都 610225)

1 引言

近年來，Internet的流量逐年指數(shù)增長。從2007～2011年，Internet的流量和帶寬的年平均增長率分別達到了56%和58%[1]。流量和帶寬的增長導致了Internet的能耗上升。據(jù)估計，2007年Internet的電力消耗達到了寬帶接入國家（其平均接入帶寬為30 Mbit/s）總電量的1%，當平均接入帶寬達到300 Mbit/s時，這個比例將超過4%[2]。按照目前的增長速度，到2050年網(wǎng)絡(luò)領(lǐng)域的耗電量將達到2006年的13倍[3]。Internet能耗的快速增長不僅導致電力成本的持續(xù)上升，同時也造成溫室氣體的加速排放。因此，提高能量效率和降低能耗已成為Internet面臨的重大研究課題。目前，隨著網(wǎng)絡(luò)的扁平化發(fā)展，Internet的層次變得更加簡單，逐漸演變成由接入網(wǎng)和核心網(wǎng)兩部分組成。由于接入網(wǎng)的“光進銅退”以及核心網(wǎng)對接入網(wǎng)流量的匯聚，核心網(wǎng)正經(jīng)歷比接入網(wǎng)更快的能耗增長。研究表明到2017年核心網(wǎng)能耗將超過接入網(wǎng)[4]。因此，在整個Internet中，核心網(wǎng)的節(jié)能研究正變得日益重要。

網(wǎng)絡(luò)按照峰值業(yè)務(wù)需求超額供給[5]網(wǎng)絡(luò)資源，并通過冗余設(shè)計來提高網(wǎng)絡(luò)的可靠性，這導致了網(wǎng)絡(luò)資源的平均利用率低下，而當前利用率對網(wǎng)絡(luò)資源的功耗影響卻較小[6～8]，因此，提高網(wǎng)絡(luò)資源利用率并將空閑的網(wǎng)絡(luò)資源關(guān)閉（或轉(zhuǎn)入低功耗睡眠狀態(tài)）是目前降低核心網(wǎng)能耗的一個重要途徑。目前，主要有如下文獻研究此問題。Chabarek等人[9]利用混合整數(shù)線性規(guī)劃(MILP, mixed integer linear programming)技術(shù)建模功率感知的網(wǎng)絡(luò)設(shè)計和路由問題，通過為網(wǎng)絡(luò)節(jié)點選擇合適數(shù)量和類型的線卡最小化IP網(wǎng)絡(luò)的功耗，但卻沒有設(shè)計有效的啟發(fā)式算法來求解NP難的MILP模型。文獻[10]將IP網(wǎng)絡(luò)的綠色流量工程形式化為一個MILP模型，并提出了一種啟發(fā)式算法，通過預先為每對節(jié)點計算k條候選最短路徑來降低MILP問題的解空間和求解時間，但是，解空間依然隨節(jié)點對的數(shù)量指數(shù)增長。文獻[11]提出了一種基于拉格朗日松弛的啟發(fā)式算法，將建立的形式化模型分解為容易求解的子問題，為鏈路設(shè)定合適的權(quán)值進行動態(tài)路由，關(guān)閉盡可能多的鏈路以降低IP網(wǎng)絡(luò)的能耗。與文獻[9～11]改變已有的網(wǎng)絡(luò)拓撲不同，文獻[12,13]考慮核心網(wǎng)的層次結(jié)構(gòu)，通過改變IP層的虛擬拓撲降低網(wǎng)絡(luò)能耗。其中，文獻[12]考慮光收發(fā)器和電交換的功耗，將功率感知的虛擬拓撲設(shè)計形式化為MILP問題，并提出一個簡單的貪婪算法和遺傳算法求解。該遺傳算法并沒有相應(yīng)的機制保證得到的后代個體滿足MILP模型的約束條件，而是簡單的舍棄不滿足約束的個體，這會導致算法有時找不到可行解。文獻[13]只考慮線卡的功耗，將最小化能耗的虛擬拓撲設(shè)計問題形式化為一個簡單的整數(shù)線性規(guī)劃(ILP,integer linear programming)模型，并提出了一個兩階段的啟發(fā)式算法。由于只考慮了線卡的功耗，建立的ILP模型過于簡單，網(wǎng)絡(luò)傾向于建立一個星型虛擬拓撲，最小化鏈路的數(shù)量。

筆者認為，現(xiàn)有工作存在以下不足。首先，這些文獻都只考慮網(wǎng)絡(luò)設(shè)備的部分組件的功耗，如鏈路、收發(fā)器或線卡，忽略了其他部分的功耗，這樣使得最終得到的解只能使整個網(wǎng)絡(luò)中的這些組件的功耗最低，而不是整個網(wǎng)絡(luò)的功耗最低。其次，核心網(wǎng)絡(luò)的網(wǎng)絡(luò)設(shè)備通常采用模塊化設(shè)計，現(xiàn)有的工作沒有考慮網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)。第三，由于問題的復雜性（NP問題），現(xiàn)有工作要么建立的形式化模型過于復雜，以至于不能有效求解，如文獻[9,10,12]，要么建立的模型過于簡化而忽略重要特性，如文獻[11,13]只考慮鏈路或線卡功耗，忽略了IP路由器處理流量的功耗。本文研究的內(nèi)容與文獻[12,13]相似，即以最小化網(wǎng)絡(luò)功耗為目標的綠色虛擬拓撲設(shè)計(GVTD, green virtual topology design)問題。本文首先對GVTD進行形式化建模，該模型（即GVTD模型）通過業(yè)務(wù)路由實現(xiàn)對業(yè)務(wù)流的匯聚和疏導以提高網(wǎng)絡(luò)資源利用率，根據(jù)網(wǎng)絡(luò)資源的實際利用按需地配置網(wǎng)絡(luò)資源以實現(xiàn)網(wǎng)絡(luò)設(shè)備的多粒度睡眠，根據(jù)網(wǎng)絡(luò)資源配置動態(tài)地建立虛擬拓撲，從而達到降低網(wǎng)絡(luò)能耗的目的。GVTD模型考慮整個網(wǎng)絡(luò)設(shè)備的功耗，目的是降低整個網(wǎng)絡(luò)的功耗。其次，GVTD模型考慮了網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)，利用多粒度睡眠機制配置網(wǎng)絡(luò)資源。第三，GVTD模型根據(jù)功耗與業(yè)務(wù)負載的依賴關(guān)系，同時考慮了不依賴業(yè)務(wù)負載的靜態(tài)功耗和依賴業(yè)務(wù)負載的動態(tài)功耗。最后，GVTD模型是一個NP難的ILP問題，只能在問題規(guī)模很小時精確求解，本文提出了一個基于約束路由的啟發(fā)式算法，即CBR-GVTD算法。本文的主要貢獻如下。

1) 對綠色虛擬拓撲設(shè)計問題進行形式化建模，即GVTD模型，該模型通過業(yè)務(wù)匯聚提高網(wǎng)絡(luò)資源利用率，按需配置網(wǎng)絡(luò)資源和動態(tài)建立虛擬拓撲，從而達到降低網(wǎng)絡(luò)功耗的目的。

2) 提出了一種基于約束路由的啟發(fā)式算法，即CBR-GVTD算法，該算法使用基于約束的路由算法保證鏈路容量約束和最大路由跳數(shù)約束，在提高網(wǎng)絡(luò)資源利用率的同時實現(xiàn)了虛擬拓撲對業(yè)務(wù)路由的動態(tài)適應(yīng)。

3) 通過模擬實驗從網(wǎng)絡(luò)功耗、資源利用率和路由性能3個方面對CBR-GVTD算法的性能進行了評估，結(jié)果表明CBR-GVTD算法在保證路由性能的條件下獲得很高的資源利用率，最多可降低62%～90%的網(wǎng)絡(luò)功耗。

4) 探討了網(wǎng)絡(luò)最大路由跳數(shù)對網(wǎng)絡(luò)功耗的影響，發(fā)現(xiàn)可在網(wǎng)絡(luò)功耗無明顯增加的條件下大大降低網(wǎng)絡(luò)的最大路由跳數(shù)。

2 GVTD問題的形式化描述

本節(jié)對GVTD問題進行形式化描述，建立GVTD模型。在此之前，有必要對核心網(wǎng)的虛擬拓撲設(shè)計、網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)和多粒度睡眠機制進行介紹。在核心網(wǎng)中，IP網(wǎng)絡(luò)層通常構(gòu)建于高速的TDM(time division multiplexing)網(wǎng)絡(luò)層或者WDM(wavelength division multiplexing)網(wǎng)絡(luò)層之上[14]，形成所謂的IP over SONET/SDH/OTN網(wǎng)絡(luò)或IP over WDM網(wǎng)絡(luò)。下層網(wǎng)絡(luò)（即TDM層或WDM層）向IP層提供通道傳輸服務(wù)（即TDM電路服務(wù)和光路服務(wù)，電路和光路統(tǒng)稱為傳輸通道），IP層通過使用下層提供的通道傳輸服務(wù)向其上層提供分組傳輸服務(wù)。IP層的鏈路由1條或多條具有相同源節(jié)點和目的節(jié)點的傳輸通道組成，這種鏈路不同于傳統(tǒng)的物理鏈路，因此被稱為邏輯鏈路，由邏輯鏈路構(gòu)成的網(wǎng)絡(luò)拓撲被稱為虛擬拓撲（或邏輯拓撲）。根據(jù)給定的業(yè)務(wù)需求建立IP層邏輯鏈路的過程即為IP層的虛擬拓撲設(shè)計（VTD, virtual topology design）過程。對于IP層，下層提供的傳輸通道組成了其邏輯鏈路；對于下層網(wǎng)絡(luò)，IP層請求建立的傳輸通道形成了其業(yè)務(wù)需求。

根據(jù)核心網(wǎng)的網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)把網(wǎng)絡(luò)資源注1注1： 網(wǎng)絡(luò)資源通常具有很寬泛的含義，本文只關(guān)心與網(wǎng)絡(luò)功耗相關(guān)的網(wǎng)絡(luò)資源，因此，后文的網(wǎng)絡(luò)資源特指接口、線卡和機框。注2：在網(wǎng)絡(luò)優(yōu)化中，擁塞被形式化為網(wǎng)絡(luò)接口（或鏈路）的最大利用率。分成接口、線卡和機框3類：接口由一對發(fā)送/接收端口組成，每條傳輸通道起始于源節(jié)點的1個發(fā)送端口并終止于目的節(jié)點的1個接收端口；線卡由一組接口所共享，能夠與這組接口同時處于空閑或活躍狀態(tài)；除接口和線卡以外的部分全都歸入機框的范疇?；谶@種分類，提出一種多粒度睡眠機制來配置網(wǎng)絡(luò)資源：當接口空閑時讓接口睡眠，當線卡的所有接口都空閑時則線卡睡眠，當所有線卡都空閑時則機框睡眠。

GVTD模型假定網(wǎng)絡(luò)資源按照峰值需求供給，即每個網(wǎng)絡(luò)節(jié)點具有充足的接口、線卡和機框；下層網(wǎng)絡(luò)可以提供IP層所需的傳輸通道。GVTD模型主要包括以下四部分。

1) 網(wǎng)絡(luò)功耗模型，即GVTD模型的目標函數(shù)。網(wǎng)絡(luò)功耗模型同時考慮網(wǎng)絡(luò)設(shè)備的靜態(tài)功耗和動態(tài)功耗，靜態(tài)功耗指網(wǎng)絡(luò)設(shè)備獨立于業(yè)務(wù)負載的那部分功耗（即空閑狀態(tài)下的功耗），動態(tài)功耗指網(wǎng)絡(luò)設(shè)備依賴業(yè)務(wù)負載的那部分功耗。根據(jù)網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)，靜態(tài)功耗可以進一步細分為接口功耗、線卡功耗和機框功耗。目前利用率對網(wǎng)絡(luò)設(shè)備功耗的影響較少，文獻[14]實驗測得網(wǎng)絡(luò)交換機的功耗變動范圍（即動態(tài)功耗）僅為15%。

2) 業(yè)務(wù)路由，即GVTD模型的路由約束，為了避免多徑路由引發(fā)的時延抖動，GVTD模型使用單徑路由。

3) 資源配置，即GVTD模型的資源約束，該約束確定每個節(jié)點的活躍網(wǎng)絡(luò)資源，并按照多粒度睡眠機制使空閑的網(wǎng)絡(luò)資源睡眠。

4) 虛擬拓撲設(shè)計，對應(yīng)于GVTD模型的鏈路容量約束，該約束確定網(wǎng)絡(luò)中需要建立的傳輸通道。此外，筆者通過設(shè)定接口最大利用率參數(shù)實現(xiàn)了對網(wǎng)絡(luò)擁塞注2注1： 網(wǎng)絡(luò)資源通常具有很寬泛的含義，本文只關(guān)心與網(wǎng)絡(luò)功耗相關(guān)的網(wǎng)絡(luò)資源，因此，后文的網(wǎng)絡(luò)資源特指接口、線卡和機框。注2：在網(wǎng)絡(luò)優(yōu)化中，擁塞被形式化為網(wǎng)絡(luò)接口（或鏈路）的最大利用率。的控制。

GVTD模型的輸入?yún)?shù)定義如下。N表示網(wǎng)絡(luò)節(jié)點集合，i,j,ii,jj∈N表示網(wǎng)絡(luò)節(jié)點，C表示接口的容量，α表示接口（或鏈路）所允許的最大利用率，pt表示網(wǎng)絡(luò)資源處理單位(1 Gbit/s）業(yè)務(wù)負載的動態(tài)功耗，pi、pl和pc分別表示單個接口、線卡和機框的功耗，mi、ml分別表示每個線卡具有的接口數(shù)量和每個機框可配備的線卡數(shù)量，D表示網(wǎng)絡(luò)的業(yè)務(wù)需求集合，d(ii,jj)∈D表示從節(jié)點ii到節(jié)點jj的業(yè)務(wù)需求。

GVTD問題的決策變量（即GVTD模型的優(yōu)化參數(shù)）定義如下。

1) δ(ii,jj,i,j)∈{0,1}：業(yè)務(wù)需求d(ii,jj)的路徑是否經(jīng)過邏輯鏈路(i,j)，1表示經(jīng)過，0表示不經(jīng)過。

2) d'(i,j)∈Z+：邏輯鏈路(i,j)包含的傳輸通道數(shù)量，其中，Z+表示正整數(shù)集合，傳輸通道由下層網(wǎng)絡(luò)提供，而且每條傳輸通道需要消耗一個發(fā)送端口和接收端口。

3) t(i,j)∈R+：邏輯鏈路(i,j)上的總業(yè)務(wù)量，其中，R+表示正實數(shù)集合。

4) ni(i)∈Z+：網(wǎng)絡(luò)節(jié)點i的活躍接口數(shù)量。

5) nl(i)∈Z+：網(wǎng)絡(luò)節(jié)點i的活躍線卡數(shù)量。

6) nc(i)∈Z+：網(wǎng)絡(luò)節(jié)點i的活躍機框數(shù)量。

其中，δ(ii,jj,i,j)和t(i,j)表示網(wǎng)絡(luò)的業(yè)務(wù)路由，d'(i,j)表示虛擬拓撲，ni(i)、nl(i)和nc(i)表示網(wǎng)絡(luò)的資源配置。

GVTD問題可以形式化描述為

目標函數(shù)(式(1))最小化整個網(wǎng)絡(luò)的功耗。網(wǎng)絡(luò)功耗由靜態(tài)功耗和動態(tài)功耗兩部分組成，靜態(tài)功耗可進一步分為機框功耗nc(i)pc、線卡功耗nl(i)pl和接口功耗ni(i)pi；筆者使用線性函數(shù)[15]近似動態(tài)功耗與業(yè)務(wù)負載的關(guān)系，即t(i,j)pt。由于網(wǎng)絡(luò)資源的睡眠功耗遠遠小于活躍功耗，本文忽略網(wǎng)絡(luò)資源的睡眠功耗。

路由約束（式(2a)～式(2e)）為經(jīng)典的多品種流守恒[16]約束，業(yè)務(wù)需求d(ii,jj)經(jīng)過單條路徑從源節(jié)點ii到達目的節(jié)點jj。式(3)計算經(jīng)過邏輯鏈路(i,j)的業(yè)務(wù)負載（即鏈路流量），鏈路的容量約束（式(4)）確保鏈路的流量不超過鏈路的容量。IP層的鏈路(,)ij為邏輯鏈路，由下層網(wǎng)絡(luò)提供的'(,)dij條傳輸通道組成，每條傳輸通道的容量為C，并引入最大利用率α以應(yīng)對IP業(yè)務(wù)的動態(tài)特性注3注3：業(yè)務(wù)需求的動態(tài)特性可能導致網(wǎng)絡(luò)擁塞，將鏈路的最大利用率限定得越低，產(chǎn)生網(wǎng)絡(luò)擁塞的概率也越低。GVTD模型通過參數(shù) α調(diào)節(jié)鏈路的最大利用率以實現(xiàn)網(wǎng)絡(luò)擁塞與功耗的折衷。。IP層虛擬拓撲的確立過程即為決策變量'(,)dij的值的確立過程，因此，式(4)在實現(xiàn)鏈路容量約束的同時還實現(xiàn)了IP層的虛擬拓撲設(shè)計，實現(xiàn)了IP層的邏輯鏈路與下層網(wǎng)絡(luò)提供的傳輸通道的映射（即IP層與下層網(wǎng)絡(luò)的層間約束）。式(5)～式(7)為資源約束。其中，式(5a)和式(5b)可確保節(jié)點提供足夠的活躍接口，即活躍接口不應(yīng)該少于傳輸通道所需的發(fā)送端口（式(5a)）和接收端口（式(5b)）。式(6)和式(7)確保節(jié)點能提供足夠的活躍線卡和活躍機框，即活躍線卡和活躍機框提供的接口數(shù)不少于活躍接口數(shù)。

3 GVTD模型的求解

GVTD模型是一個ILP模型，由于ILP是NP難問題，在計算資源有限的條件下，目前只可在問題規(guī)模很小時進行精確求解。為此，本文提出一種快速有效的啟發(fā)式算法，將該算法命名為CBR- GVTD算法。CBR-GVTD算法主要考慮和解決以下2個問題。

1) 如何構(gòu)造可行解，即構(gòu)造解時應(yīng)滿足GVTD模型的所有約束條件。

2) 如何提高解的質(zhì)量，即構(gòu)造的最終解盡可能地近似最優(yōu)解。

對于第一個問題，首先需要分析各個約束條件以及各個決策變量之間的依賴關(guān)系。在GVTD模型中，根據(jù)約束條件間的關(guān)系可知決策變量存在以下依賴關(guān)系：nl(i)和nc(i)都依賴ni(i)，ni(i)依賴d'(i,j)，d'(i,j)依賴t(i,j)，t(i,j)依賴δ(ii,jj,i,j)。因此，根據(jù)以上依賴關(guān)系，本文使用單跳路由和基于約束的路由（多跳路由）確立δ(ii,jj,i,j)，t(i,j)和d'(i,j)的值，并同時滿足式(2a)～式(2e)所示的路由約束、式(3)，和式(4)所示的鏈路容量約束。然后使用以式(8)～式(10)確立ni(i)，nl(i)和nc(i)的值。

第二個問題涉及如何使目標函數(shù)（式(1)）盡可能小。首先，只要能找到目標函數(shù)的一個足夠大的下界值，通常情況下，可認為該下界值對應(yīng)的解（不一定可行）與最優(yōu)解十分接近，因此，在此基礎(chǔ)上構(gòu)造出的可行解通常質(zhì)量較好。本文通過以下方法計算目標函數(shù)的下界值。

下面考慮如何在目標函數(shù)下界值LB的基礎(chǔ)上構(gòu)造可行解。由于都依賴d'(i,j)，只需要在的基礎(chǔ)上構(gòu)造可行的即解決業(yè)務(wù)路由和虛擬拓撲設(shè)計2個子問題。通常，網(wǎng)絡(luò)的總業(yè)務(wù)量越大，網(wǎng)絡(luò)需要的活躍接口越多，網(wǎng)絡(luò)的靜態(tài)功耗（包括接口、線卡和機框功耗）越大，網(wǎng)絡(luò)的動態(tài)功耗也越大（與總業(yè)務(wù)量成正比）。因此，對業(yè)務(wù)需求進行路由時盡可能使用單跳路由，減少網(wǎng)絡(luò)的總業(yè)務(wù)量。但是對于較小的業(yè)務(wù)需求，單跳路由會導致鏈路的利用率低，造成帶寬資源的浪費，因此需要對較小的業(yè)務(wù)需求使用多跳路由，進行充分的業(yè)務(wù)疏導。在業(yè)務(wù)路由方面，本文按從大到小的順序?qū)I(yè)務(wù)需求進行業(yè)務(wù)路由，對較大的業(yè)務(wù)需求使用單跳路由，對較小的業(yè)務(wù)需求使用基于約束的路由算法進行多跳路由，并對網(wǎng)絡(luò)的最大路由跳數(shù)進行限制，以實現(xiàn)路由性能與網(wǎng)絡(luò)功耗的折衷。在虛擬拓撲設(shè)計上，本文根據(jù)業(yè)務(wù)路由動態(tài)按需建立網(wǎng)絡(luò)的虛擬拓撲，實現(xiàn)虛擬拓撲對業(yè)務(wù)路由的適應(yīng)。

3.1 基于約束路由的Dijkstra算法——CBR-Dijkstra算法

基于約束路由的Dijkstra（CBR-Dijkstra, constraint-based routing dijkstra）算法計算滿足鏈路容量約束和最大路由跳數(shù)約束的最短路徑（即跳數(shù)最少的路徑）。CBR-Dijkstra算法與標準的Dijkstra算法的不同之處有以下3點。1）CBR-Dijkstra算法在網(wǎng)絡(luò)的一個拓撲子圖上，使用Dijkstra算法計算跳數(shù)最少的路徑。該拓撲子圖去除了網(wǎng)絡(luò)中所有可用帶寬小于業(yè)務(wù)需求所需帶寬的鏈路，其中，鏈路去除是在路由計算過程中通過考慮被處理鏈路的可用帶寬的方式實現(xiàn)。2）在獲得最短路徑后，判定路徑跳數(shù)是否小于網(wǎng)絡(luò)的最大跳數(shù)，如果超過最大跳數(shù)則表明路由失敗。3）當發(fā)現(xiàn)有多條跳數(shù)相同且都滿足鏈路容量約束的路徑時，算法將優(yōu)先選擇可用帶寬最小的路徑，以提高鏈路的利用率。

CBR-Dijkstra算法的偽代碼如下所示。在本文的偽代碼中，語句塊以左花括號{開始，以右花括號加end 和對應(yīng)的關(guān)鍵字結(jié)束，如 }end if, }end for, }end while。

此算法的輸入包括業(yè)務(wù)需求d(i,j)、網(wǎng)絡(luò)節(jié)點集合N、網(wǎng)絡(luò)鏈路集合E、網(wǎng)絡(luò)鏈路的可用帶寬集合B和網(wǎng)絡(luò)的最大路由跳數(shù)H。算法輸出為d(i,j)的路徑。在算法中，predecessor(v)記錄節(jié)點v的前驅(qū)節(jié)點，hops(v)記錄從源節(jié)點i到節(jié)點v的最小跳數(shù)，visited(v)標識節(jié)點v是否已被訪問，pb(v)表示從節(jié)點i到節(jié)點v的路徑的可用帶寬，b(u,v)∈B表示鏈路(u,v)的可用帶寬，Q為候選節(jié)點列表。算法的1)～7)行首先進行一些初始化工作，然后從源節(jié)點i開始(第8)行)，計算源節(jié)點i的最短路徑生成樹，直到計算出到目標節(jié)點j的路徑時停止(第9)～25)行)。算法只考慮可用帶寬大于業(yè)務(wù)需求的鏈路（第12行），當跳數(shù)相同時，優(yōu)先選擇可用帶寬最小的路徑(第18)～22)行)。算法最后判定計算的最短路徑是否小于網(wǎng)絡(luò)的最大跳數(shù)H(第26)行)，如果路由成功，則返回前驅(qū)節(jié)點表示的最短路徑(第27)行)，否則返回空值NIL(第28)行)。

在CBR-Dijkstra算法偽代碼中，第一個for循環(huán)的執(zhí)行次數(shù)等于網(wǎng)絡(luò)的節(jié)點數(shù)，while循環(huán)中的for循環(huán)最多執(zhí)行次數(shù)等于網(wǎng)絡(luò)有向邊數(shù)，對于連通圖有，因此，CBR-Dijkstra算法的時間復雜度僅為

3.2 基于約束路由的綠色虛擬拓撲設(shè)計算法——CBR-GVTD算法

基于約束路由的綠色虛擬拓撲設(shè)計（CBR-GVTD,constraint-based routing green virtual topology design）算法的偽代碼如下所示。

此算法的輸入包括N、D、α、C、pt、pi、pl、pc、mi、ml和H，其中，H為網(wǎng)絡(luò)的最大路由跳數(shù)，其他符號已在第3節(jié)中定義。算法的輸出為網(wǎng)絡(luò)功耗和第3節(jié)定義的決策變量。CBR-GVTD算法分2個階段，即：1）從目標函數(shù)下界值構(gòu)造可行解（第1)～16)行）；2）通過移除利用率低的傳輸通道對可行解進行優(yōu)化（第17)～27)行）。

在第1階段，算法首先根據(jù)式(11)用下界值ni(i)lb初始化每個網(wǎng)絡(luò)節(jié)點的接口數(shù)ni(i)(第1)行)，然后分兩步建立網(wǎng)絡(luò)的虛擬拓撲。第1步按照從大到小的順序為每個業(yè)務(wù)需求d(i,j)建立從i到j(luò)的傳輸通道，并進行單跳路由（第4)、5)、7)行）。每個傳輸通道消耗源節(jié)點i的一個發(fā)送端口（sending port）和目的節(jié)點j的一個接收端口（receiving port）（第8)行），該過程將持續(xù)到接口耗盡、沒有傳輸通道可以建立為止（第6)行）。第2步在第1步建立的虛擬拓撲的基礎(chǔ)上，利用單跳路由的剩余帶寬，對剩余的業(yè)務(wù)需求（第1步中未能完成單跳路由的業(yè)務(wù)需求）按照從大到小的順序進行CBR-Dijkstra路由（第9)、10)行）。該路由必然是多跳路由，為了防止路由跳數(shù)過大，本文限制網(wǎng)絡(luò)的最大跳數(shù)為H。如果業(yè)務(wù)需求d(i,j)的路由失?。ǖ?1)行），則增加節(jié)點i和j的接口（因為在第1步中已經(jīng)耗盡）（第13)行），為i到j(luò)建立傳輸通道并消耗相應(yīng)的接口數(shù)（第12)、15)行），這也意味著網(wǎng)絡(luò)的虛擬拓撲發(fā)生了變化（第14)行）。通過第2步，所有的業(yè)務(wù)需求都成功完成路由，但是網(wǎng)絡(luò)的虛擬拓撲可能發(fā)生了變化，通過反復迭代使這種虛擬拓撲對業(yè)務(wù)路由的適應(yīng)性變化收斂（第2)、3)、14)、16)行）。

在第2階段，算法初始化鏈路集合E'為當前的邏輯鏈路集合E(第17)行)，然后每次從E'中取出剩余帶寬最大的邏輯鏈路(i,j)（第18)行）并將(i,j)從E'中去除（第19)行），嘗試移除從i到j(luò)的一條傳輸通道（第20)行），并對經(jīng)過邏輯鏈路(i,j)的所有業(yè)務(wù)需求進行CBR-Dijkstra重路由，如果重路由成功，則釋放該傳輸通道消耗的接口（第21)、22)行），否則恢復移除的傳輸通道（第23)行）。其中，鏈路的剩余帶寬b(i,j)在每次路由后進行更新，最大的b(i,j)表明鏈路(i,j)的某條傳輸通道的利用率最低。至此，虛擬拓撲設(shè)計和業(yè)務(wù)路由已經(jīng)完成，即δ(ii,jj,i,j)和d'(i,j)的值已經(jīng)確定。算法移除每個節(jié)點剩余（即沒用使用）的接口，確立ni(i)的最終值（第24)行），通過式(3)、式(9)和式(10)分別確定t(i,j)、nl(i)和nc(i)（第25)和26)行），最后通過式(1)計算整個網(wǎng)絡(luò)的功耗（第27)行）。

CBR-GVTD算法通過單跳路由建立虛擬拓撲，對剩余的業(yè)務(wù)需求使用CBR-Dijkstra算法進行多跳路由。由于單跳路由（算法的第5)、7)和8)行）的時間復雜度為常數(shù)級，低于多跳路由（即CBR- Dijkstra算法）的時間復雜度，因此，以CBR- Dijkstra算法為基本操作分析CBR-GVTD算法的時間復雜度。假設(shè)第2)～16)行的do-while循環(huán)了k次，則第10)行的CBR-Dijkstra算法最多執(zhí)行為業(yè)務(wù)需求數(shù)）。假設(shè)網(wǎng)絡(luò)的平均路由路數(shù)為h，所有業(yè)務(wù)需求共跳，因此，第21)行共執(zhí)行次，因此CBRGVTD算法的時間復雜度為k和h通常都很小，在第4節(jié)的實驗中，k不超過4，h不超過3。

4 性能評估

通過一系列模擬實驗從網(wǎng)絡(luò)功耗、網(wǎng)絡(luò)資源（即接口、線卡和機框）利用率和路由性能（即平均跳數(shù)和最大跳數(shù)）3個方面對CBR-GVTD算法進行性能評估，并將CBR-GVTD算法和其他算法的實驗結(jié)果進行比較，包括：GVTD模型的精確解、網(wǎng)絡(luò)功耗的下界和上界以及基于拉格朗日松弛的啟發(fā)式算法（即LR算法[12]）。其中，筆者使用數(shù)學工具GAMS/CPLEX[17]求解GVTD模型的精確解，

CPLEX是一種高性能的ILP求解器，采用分支定界算法求解ILP問題，由于ILP問題是NP難的，只能對規(guī)模較小的網(wǎng)絡(luò)精確求解。網(wǎng)絡(luò)功耗下界LB由式(11)和式(12)求得，網(wǎng)絡(luò)的功耗上界UB由式(13)和式(14)求得。在式(13)中，每個業(yè)務(wù)需求(,)dij通過條傳輸通道進行單跳路由，因此得到節(jié)點的接口上界與LB的計算類似，將代入式(9)和式(10)可求得，最后將這些值代入目標函數(shù)即得到上界值UB（即式(14)）。LR算法使用拉格朗日松弛技術(shù)將ILP模型分解成容易求解的子問題，然后對每個子問題求解并使用次梯次算法求解拉格朗日對偶問題，最后對得到的解進行可行化處理。

為了全面評估CBR-GVTD算法的性能，實驗充分考慮了多種不同大小的網(wǎng)絡(luò)、多種不同大小的業(yè)務(wù)需求和多種不同大小的網(wǎng)絡(luò)最大跳數(shù)，實驗參數(shù)設(shè)定如下所示。

1) 網(wǎng)絡(luò)規(guī)模。GVTD問題不涉及網(wǎng)絡(luò)的物理拓撲，因此，只需節(jié)點數(shù)量即可表示各種大小的網(wǎng)絡(luò)。實驗網(wǎng)絡(luò)的節(jié)點數(shù)量分別為10、20、30、40和50。

2) 業(yè)務(wù)需求。Internet的流量具有重尾分布特性，本文使用重力模型[17]生成重尾分布的業(yè)務(wù)需求，網(wǎng)絡(luò)節(jié)點間的平均業(yè)務(wù)需求分別為1 Gbit/s、5 Gbit/s、10 Gbit/s、15 Gbit/s、20 Gbit/s、25 Gbit/s、30 Gbit/s、35 Gbit/s和40 Gbit/s。

3) 網(wǎng)絡(luò)設(shè)備的相關(guān)參數(shù)以Cisco CRS3-8/S 路由器的規(guī)格說明為參考，具體設(shè)定如表1所示。

表1 網(wǎng)絡(luò)設(shè)備相關(guān)的參數(shù)

4) 網(wǎng)絡(luò)最大路由跳數(shù)H的取值分別為1、2、3、4、5和∞，其中，H=∞表示不限制網(wǎng)絡(luò)的最大路由跳數(shù)。

本文對網(wǎng)絡(luò)規(guī)模、業(yè)務(wù)需求和網(wǎng)絡(luò)最大路由跳數(shù)的多種取值的各種組合（共5×9×6=270種）分別進行實驗。為了減小重力模型生成業(yè)務(wù)需求過程中隨機因素可能對實驗結(jié)果的影響，以上每種組合的實驗重復進行10次（共2 700次），每次實驗的業(yè)務(wù)需求使用不同的隨機數(shù)種子生成，結(jié)果取平均值。為了公平地比較CBR-GVTD與GAMS/CPLEX、LU、UB和LR的實驗結(jié)果，這些算法都使用完全相同的實驗參數(shù)（包括網(wǎng)絡(luò)規(guī)模、業(yè)務(wù)需求和網(wǎng)絡(luò)設(shè)備相關(guān)參數(shù)）。網(wǎng)絡(luò)最大跳數(shù)H為CBR-GVTD算法所獨有，在5.1節(jié)和5.2節(jié)的實驗中，網(wǎng)絡(luò)最大跳數(shù)都不受限，即H=∞，在5.3節(jié)中將展示H的其他取值下的實驗結(jié)果，并探討如何設(shè)定H的值。

4.1 網(wǎng)絡(luò)功耗

GVTD的目標是最小化網(wǎng)絡(luò)的功耗，考慮到網(wǎng)絡(luò)業(yè)務(wù)需求的變化，在理想的情況下，網(wǎng)絡(luò)功耗應(yīng)該與網(wǎng)絡(luò)業(yè)務(wù)需求成正比，即網(wǎng)絡(luò)應(yīng)該具有能量勻增特性[9]。為了評估CBR-VTD算法求得的網(wǎng)絡(luò)功耗與GVTD形式化模型最優(yōu)值的差距，首先對規(guī)模較?。?0個節(jié)點）的網(wǎng)絡(luò)進行模擬實驗，使用GAMS/CPLEX計算GVTD模型的最優(yōu)解（相對誤差限為2%），并將求得的網(wǎng)絡(luò)功耗與CBR-VTD算法、LR算法以及網(wǎng)絡(luò)功耗的下界(LB)和上界(UB)進行比較，結(jié)果如圖1所示。在圖1中，網(wǎng)絡(luò)功耗的上界（UB）和下界LB，CBR-GVTD、LR算法和GAMS/CPLEX求得的網(wǎng)絡(luò)功耗與業(yè)務(wù)需求呈現(xiàn)幾乎線性增長的函數(shù)關(guān)系，即表現(xiàn)出一定的能量勻增特性。其中，網(wǎng)絡(luò)功耗下界(LB)與最優(yōu)解CPLEX比較接近，這表明LB作為網(wǎng)絡(luò)功耗下界是十分緊致的，因此，在網(wǎng)絡(luò)規(guī)模更大時（此時，無法用GAMS/CPLEX獲得最優(yōu)解），LB可用于評估CBR-GVTD算法的性能。在圖1中，CBR-GVTD介于LR與CPLEX之間，這表明CBRGVTD算法求得的網(wǎng)絡(luò)功耗比LR算法的更低且更接近于GAMS/CPLEX求得的最優(yōu)值。

圖1 10個節(jié)點的網(wǎng)絡(luò)功耗：CBR-GVTD算法與CPLEX、LR、LB和UB算法的比較

為了進一步評估在其他規(guī)模的網(wǎng)絡(luò)上，CBRGVTD算法求得的網(wǎng)絡(luò)功耗的性能，本文分別在節(jié)點數(shù)為20、30、40和50的網(wǎng)絡(luò)上進行模擬實驗，實驗結(jié)果如圖2所示。由圖2可知，無論網(wǎng)絡(luò)節(jié)點數(shù)為多少，CBR-GVTD都位于LR與LB之間，這說明CBR-GVTD算法求得的網(wǎng)絡(luò)功耗始終比LR算法的更低，更接近于網(wǎng)絡(luò)功耗下界(LB)?？傊?，在網(wǎng)絡(luò)功耗方面，圖1和圖2表明CBR-GVTD算法具有比LR算法更優(yōu)的性能，能夠獲得接近最優(yōu)值的網(wǎng)絡(luò)功耗。Internet按照峰值需求供應(yīng)網(wǎng)絡(luò)資源（即超額供給）導致網(wǎng)絡(luò)資源的平均利用率較低，因此，在大多數(shù)時間里業(yè)務(wù)需求都處于非高峰期，圖3為各種規(guī)模的網(wǎng)絡(luò)在業(yè)務(wù)非高峰期時CBR-GVTD算法節(jié)省的最大功耗，即CBR-GVTD算法在業(yè)務(wù)低峰期(1 Gbit/s)時與業(yè)務(wù)高峰期(40 Gbit/s)時相比節(jié)省的網(wǎng)絡(luò)功耗。由圖3可知，在業(yè)務(wù)非高峰期時，CBR-GVTD算法最多可節(jié)省62%～90%的網(wǎng)絡(luò)功耗，且該比例隨著網(wǎng)絡(luò)規(guī)模的增大不斷上升。

圖3 不同規(guī)模網(wǎng)絡(luò)在業(yè)務(wù)非高峰期時節(jié)省的最大功耗

4.2 網(wǎng)絡(luò)資源利用率

GVTD降低網(wǎng)絡(luò)功耗的一個主要原因在于提高網(wǎng)絡(luò)資源的利用率，下面從資源利用率方面評估CBR-GVTD算法的性能。圖4為CBR-GVTD算法和LR算法在30個節(jié)點的網(wǎng)絡(luò)上求得的網(wǎng)絡(luò)資源平均利用率，由于節(jié)點數(shù)為10、20、40和50的網(wǎng)絡(luò)的資源利率與圖4類似，本文僅以30個節(jié)點的網(wǎng)絡(luò)為例說明。在圖4中，CBR-GVTD算法和LR算法求得的網(wǎng)絡(luò)資源的平均利用率都隨著網(wǎng)絡(luò)業(yè)務(wù)需求的增加而增大，而且，接口和線卡的平均利用率都保持在較高的水平。對于機框和線卡的平均利用率，CBR-GVTD算法和LR算法差別不大，但是，CBR-GVTD算法對應(yīng)的接口平均利用率比LR算法更高，基本維持在80%～90%的范圍內(nèi)，而LR算法對應(yīng)的接口平均利用率基本在70%～80%左右，這解釋了為什么CBRGVTD對應(yīng)的網(wǎng)絡(luò)功耗小于LR算法的網(wǎng)絡(luò)功耗。總之，圖4表明在資源利用率方面，CBR-GVTD算法的性能也優(yōu)于LR算法，CBR-GVTD算法可以獲得很高的資源利用率。

圖4 網(wǎng)絡(luò)資源利用率：CBR-GVTD算法與LR算法比較

4.3 路由性能

通常，業(yè)務(wù)的傳輸路徑越長，端到端的網(wǎng)絡(luò)時延也越大，因此，路徑長度（即路由跳數(shù)）可用于評估CBR-GVTD算法的路由性能。圖5為30個節(jié)點的網(wǎng)絡(luò)使用CBR-GVTD算法和LR算法進行10次重復實驗得到的平均跳數(shù)、最大跳數(shù)和每次實驗的最大跳數(shù)的平均值（即平均最大跳數(shù)），圖5中，分別用avgHop、maxHop和avgMaxHop標識，CBR-GVTD算法和LR算法的平均跳數(shù)都很?。ǘ夹∮?），其中，CBR-GVTD算法的平均跳數(shù)略大于LR算法的，且都隨著網(wǎng)絡(luò)業(yè)務(wù)需求的增加而減小，表現(xiàn)出較好的路由性能。由圖5可知，總體上，最大跳數(shù)也隨網(wǎng)絡(luò)業(yè)務(wù)需求的增加而減小。由于maxHop標識的為10次重復實驗中的最大跳數(shù)，可能受隨機因素的干擾，因而表現(xiàn)出較大的起伏；而avgMaxHop標識的是平均最大跳數(shù)，因此更加平滑，反映出最大跳數(shù)隨網(wǎng)絡(luò)業(yè)務(wù)需求增加而變小的趨勢。此外，在圖5中，CBR-GVTD算法的最大跳數(shù)在6～10的范圍內(nèi)變動，明顯高于LR算法的最大跳數(shù)（變化范圍為3～7）。圖6為不同節(jié)點的網(wǎng)絡(luò)在各種大小的業(yè)務(wù)需求下的平均跳數(shù)、最大跳數(shù)和平均最大跳數(shù)。在圖6中，LR算法的平均跳數(shù)、最大跳數(shù)和平均最大跳數(shù)隨網(wǎng)絡(luò)節(jié)點數(shù)的增加而減小，CBR-GVTD算法的平均跳數(shù)隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加幾乎保持不變，但是最大跳數(shù)和平均最大跳數(shù)隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加而增大。

從平均跳數(shù)來看，圖5和圖6都表明CBR-GVTD算法具有接近LR算法的路由性能，但是最大跳數(shù)卻比LR算法的大，且隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加而增大。圖7進一步描述了30個節(jié)點的網(wǎng)絡(luò)運行CBR- GVTD算法的跳數(shù)分布。在圖7中，絕大部分路徑的跳數(shù)都很小，只有極少數(shù)路徑的跳數(shù)較大。隨著網(wǎng)絡(luò)業(yè)務(wù)需求的增加，跳數(shù)較小的路徑所占比例逐漸增大。值得注意的是，在以上實驗中，CBR-GVTD算法的網(wǎng)絡(luò)最大跳數(shù)都沒有限制，即實驗參數(shù)H=∞，因此，實驗結(jié)果也代表了CBR-GVTD算法的最壞路由性能。通過參數(shù)H，可對CBR-GVTD算法的最大跳數(shù)進行控制。本文對節(jié)點數(shù)分別為10, 20, …, 50的網(wǎng)絡(luò)，使用CBR-GVTD算法在H=1,2,3,4,5時進行實驗，并用LR算法和下界LB作比較。由于不同節(jié)點的網(wǎng)絡(luò)的實驗結(jié)果相似，下面僅以30個節(jié)點的網(wǎng)絡(luò)為例說明，網(wǎng)絡(luò)功耗如圖8所示。在圖8中，CBR-GVTD算法在H=3,4,5,∞時的網(wǎng)絡(luò)功耗基本相同，且小于LR算法的功耗。這表明CBR-GVTD算法可在網(wǎng)絡(luò)功耗基本不變的情況下減小網(wǎng)絡(luò)的最大跳數(shù)，同時獲得比LR算法更低的網(wǎng)絡(luò)功耗和更好的路由性能。

圖5 路由跳數(shù)與業(yè)務(wù)需求的關(guān)系：CBR-GVTD算法與LR算法比較

圖6 路由跳數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系：CBR-GVTD算法與LR算法比較

當最大跳數(shù)H進一步減少時，通過圖8可以知道，當H=2時，網(wǎng)絡(luò)節(jié)點間的平均業(yè)務(wù)需求為1 Gbit/s和5 Gbit/s時，CBR-GVTD算法的功耗比H=3,4,5,∞時略高，但隨著網(wǎng)絡(luò)業(yè)務(wù)需求的增大，H=2時的網(wǎng)絡(luò)功耗與H=3,4,5,∞時的功耗基本相同。由圖5可知，當H=∞，網(wǎng)絡(luò)節(jié)點間的平均業(yè)務(wù)需求為1 Gbit/s和5 Gbit/s時，CBR-GVTD算法的平均跳數(shù)大于2，因此，在圖8中，最大跳數(shù)限定為2（即H=2）時，網(wǎng)絡(luò)功耗會有所增加。當H=1時，此時網(wǎng)絡(luò)的所有業(yè)務(wù)都使用單跳路由，CBR-GVTD算法的網(wǎng)絡(luò)功耗即為式(14)的網(wǎng)絡(luò)功耗上界值UB。因此，通過調(diào)節(jié)參數(shù)H的取值，可以實現(xiàn)網(wǎng)絡(luò)功耗與路由性能的折衷，為了保證CBR-GVTD算法的性能，建議參數(shù)H不應(yīng)該小于H=∞時CBR-GVTD算法的平均跳數(shù)。

圖8 CBR-GVTD算法在H不同取值下的網(wǎng)絡(luò)功耗

5 結(jié)束語

本文研究Internet核心網(wǎng)的綠色虛擬拓撲設(shè)計（GVTD）問題。GVTD通過業(yè)務(wù)匯聚提高網(wǎng)絡(luò)資源利用率、按需配置網(wǎng)絡(luò)資源實現(xiàn)多粒度睡眠和動態(tài)建立網(wǎng)絡(luò)的虛擬拓撲，以達到降低網(wǎng)絡(luò)能耗的目的。筆者對GVTD問題進行了形式化描述，建立了GVTD模型。由于GVTD問題是NP難的，筆者提出一個基于約束路由的啟發(fā)式求解算法，即CBR- GVTD算法。CBR-GVTD算法以網(wǎng)絡(luò)功耗的下界為基礎(chǔ)構(gòu)造GVTD問題的解，使用CBR-Dijkstra算法以保證鏈路容量約束和網(wǎng)絡(luò)最大路由跳數(shù)約束。CBR-GVTD算法按照從大到小的順序處理網(wǎng)絡(luò)的業(yè)務(wù)需求：對大的業(yè)務(wù)需求建立點到點的傳輸通道并進行單跳路由，從而確定網(wǎng)絡(luò)的虛擬拓撲；對小的業(yè)務(wù)需求使用CBR-Dijkstra算法在虛擬拓撲的剩余帶寬上進行多跳路由，通過業(yè)務(wù)疏導[19]提高網(wǎng)絡(luò)資源利用率。CBR-GVTD算法按需配置網(wǎng)絡(luò)資源，動態(tài)地建立虛擬拓撲，實現(xiàn)了虛擬拓撲對網(wǎng)絡(luò)業(yè)務(wù)需求的動態(tài)適應(yīng)，并且可通過調(diào)節(jié)網(wǎng)絡(luò)最大路由跳數(shù)來實現(xiàn)對路由性能的控制。在不同大小的網(wǎng)絡(luò)、不同大小的業(yè)務(wù)需求下，從網(wǎng)絡(luò)功耗、資源利用率和路由性能3個方面通過模擬實驗對CBR-GVTD算法進行了性能評估。實驗結(jié)果表明，CBR-GVTD算法可在優(yōu)異的業(yè)務(wù)路由性能和很高的資源利用率的條件下，獲得接近GVTD模型最優(yōu)值的解；在業(yè)務(wù)非高峰期時，對于10和50個節(jié)點的網(wǎng)絡(luò)最多可分別降低62%和90%的網(wǎng)絡(luò)功耗，該比例隨著網(wǎng)絡(luò)規(guī)模的增大而上升。

[1] Telegeography[EB/OL].http://www.telegeography.com/product-info/gig/index.php, 2012.

[2] BALIGA J, HINTON K, TUCKER K R S. Energy consumption of the internet[A]. Proc of COIN-ACOFT[C]. Melbourne, AU, 2007. 1-3.

[3] YUN D, LEE J. Research in green network for future Internet[J].Journal of KIISE, 2010, 28(1):41-51.

[4] LANGE C. Energy-related aspects in backbone networks[A]. Proceedings of 35th European Conference on Optical Communication(ECOC2009)[C]. Wien, AU, 2009.1-8.

[5] LIN C, TIAN Y, YAO M. Green network and green evaluation: mechanism, modeling and evaluation[J]. Chinese Journal of Computers,2011, 34(4): 593-612.

[6] HLAVACS H, COSTA G D, PIERSON J. Energy consumption of residential and professional switches[A]. Int Conf on Computational Science and Engineering (CSE’09)[C]. Vancouver, Canada, 2009. 240- 246.

[7] MELLAH H, SANSO B. Review of facts, data and proposals for a greener internet[A]. Proc of Sixth International Conference on Broadband Communications, Networks, and Systems[C]. Madrid, Spain,2009.1-5.

[8] BARROSO L A, HOLZLE U. The case for energy-proportional computing[J]. Computer, 2007, 40(12): 33-37.

[9] CHABAREK J, SOMMERS J, BARFORD P,etal. Power awareness in network design and routing[A]. Proc of the 27th IEEE Conference on Computer Communications (INFOCOM'08)[C]. Phoenix, AZ, USA,2008.457-465.

[10] ZHANG M, YI C, LIU B, etal. GreenTE: power-aware traffic engineering[A]. IEEE Int Conference on Network Protocols (ICNP)[C].Kyoto, Japan, 2010.21-30.

[11] LEE S S W, TSENG P K, CHEN A. Link weight assignment and loop-free routing table update for link state routing protocols in energy-aware internet[J]. Future Generation Computer Systems, 2011,28(2): 437-439.

[12] AHMAD A, BIANCO A, BONETTO E, etal. Power-aware logical topology design heuristics in wavelength-routing networks[A]. 2011 15th International Conference on Optical Network Design and Modeling (ONDM)[C]. Bologna, Italy, 2011.1-6.

[13] COIRO A, LISTANTI M, SQUARCIA T, etal. Energy-minimized virtual topology design in IP over WDM backbone networks[J]. Optoelectronics, IET, 2012,6(4): 165-172.

[14] BERTHOLD J, SALEH A A M, BLAIR L, etal. Optical networking:past, present, and future[J]. Lightwave Technology, 2008, 26(9): 1104-1118.

[15] SIVARAMAN V, VISHWANATH A, ZHAO Z, etal. Profiling perpacket and per-byte energy consumption in the NetFPGA gigabit router[A]. IEEE INFOCOM 2011 Workshop on Green Communications and Networking[C]. Shanghai, China, 2011.331-336.

[16] JENSEN P A, BARNES J W. Network Flow Programming[M]. Beijing: Science Press, 1988.

[17] GAMS/CPLEX[EB/OL].http://www.gams.com/solvers/solvers.htm#CPLEX, 2012.

[18] NUCCI A, SRIDHARAN A, TAFT N. The problem of synthetically generating IP traffic matrices: initial recommendations[J]. ACM SIGCOMM Computer Communication Review, 2005, 35(2) :19-32.

[19] YETGINER E, ROUSKAS G N. Power efficient traffic grooming in optical WDM networks[A]. Proceedings of the 52nd Annual IEEE Global Telecommunications Conference Workshop (GLOBECOM'09)[C]. Honolulu, Hawaii, USA, 2009.1-6.