基于約束路由的綠色虛擬拓撲設計算法

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

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

1 引言

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

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

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

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

2) 提出了一種基于約束路由的啟發式算法，即CBR-GVTD算法，該算法使用基于約束的路由算法保證鏈路容量約束和最大路由跳數約束，在提高網絡資源利用率的同時實現了虛擬拓撲對業務路由的動態適應。

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

4) 探討了網絡最大路由跳數對網絡功耗的影響，發現可在網絡功耗無明顯增加的條件下大大降低網絡的最大路由跳數。

2 GVTD問題的形式化描述

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

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

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

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

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

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

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

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

GVTD問題的決策變量（即GVTD模型的優化參數）定義如下。

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

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

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

4) ni(i)∈Z+：網絡節點i的活躍接口數量。

5) nl(i)∈Z+：網絡節點i的活躍線卡數量。

6) nc(i)∈Z+：網絡節點i的活躍機框數量。

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

GVTD問題可以形式化描述為

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

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

3 GVTD模型的求解

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

1) 如何構造可行解，即構造解時應滿足GVTD模型的所有約束條件。

2) 如何提高解的質量，即構造的最終解盡可能地近似最優解。

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

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

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

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

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

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

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

在CBR-Dijkstra算法偽代碼中，第一個for循環的執行次數等于網絡的節點數，while循環中的for循環最多執行次數等于網絡有向邊數，對于連通圖有，因此，CBR-Dijkstra算法的時間復雜度僅為

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

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

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

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

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

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

4 性能評估

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

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

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

1) 網絡規模。GVTD問題不涉及網絡的物理拓撲，因此，只需節點數量即可表示各種大小的網絡。實驗網絡的節點數量分別為10、20、30、40和50。

2) 業務需求。Internet的流量具有重尾分布特性，本文使用重力模型[17]生成重尾分布的業務需求，網絡節點間的平均業務需求分別為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) 網絡設備的相關參數以Cisco CRS3-8/S 路由器的規格說明為參考，具體設定如表1所示。

表1 網絡設備相關的參數

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

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

4.1 網絡功耗

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

圖1 10個節點的網絡功耗：CBR-GVTD算法與CPLEX、LR、LB和UB算法的比較

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

圖3 不同規模網絡在業務非高峰期時節省的最大功耗

4.2 網絡資源利用率

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

圖4 網絡資源利用率：CBR-GVTD算法與LR算法比較

4.3 路由性能

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

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

圖5 路由跳數與業務需求的關系：CBR-GVTD算法與LR算法比較

圖6 路由跳數與網絡規模的關系：CBR-GVTD算法與LR算法比較

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

圖8 CBR-GVTD算法在H不同取值下的網絡功耗

5 結束語

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

[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.