基于可重構網絡的節能方法的研究

廖生權，吳春明，王濱，姜明

（1. 浙江大學 計算機科學與技術學院，浙江 杭州 310027；2. 杭州電子科技大學 軟件與智能技術研究所，浙江 杭州 310018）

1 引言

在過去的幾十年中，互聯網取得了空前的成就。各種各樣的網絡業務也應運而生，這些業務不僅要求網絡能保障信息傳輸的可靠性，而且要求網絡對信息的傳送過程具有可預見性，互聯網用戶甚至要求網絡能夠在任何情況下提供相對穩定的服務，傳統的網絡體系結構已經無法滿足這些要求[1]。可重構網絡模型為解決當前互聯網的“供需”矛盾提供了契機。與傳統的網絡不同，可重構網絡是面向業務支撐的，網絡提供的服務與網絡用戶之間是松耦合關系[2]。在這種體系結構下，網絡的服務主要是通過構建邏輯承載網(LCN, logical carrying network)的方式來提供的。邏輯承載網是按照用戶指定的要求（如出口節點、入口節點、帶寬及業務類型等）在物理網絡上構建專用網絡[3]。由此可以看出，在面向業務的可重構網絡構架下，物理鏈路上的流量表現為運載其上的邏輯承載網的流量的疊加。

國內外的學者在可重構網絡的研究方面均取得了十分顯著的成果，如邏輯承載網的構建算法[4～6]，支撐邏輯承載網的路由技術[7]等。特別是文獻[7]中提出的路由器數據面和控制面相分離的 VROOM機制，對網絡的管理具有十分重要的意義。它保證了路由器上的路由任務能夠在各路由器之間進行自由遷移，并且對用戶的業務影響十分微小，幾乎可以忽略不計。數據中心網絡中也存在著一種典型的任務遷移方案。該方案一般是關閉虛擬機，遷移虛擬機的狀態于另一臺機器上，重新開啟虛擬機并恢復其狀態。傳統的遷移方案在實施任務遷移任務過程中顯然無法保障用戶的QoS。與這種方案對比，VROOM 機制的優勢在于遷移過程對用戶是透明的，對網絡的影響十分小。

與此同時，隨著網絡應用的成功普及，其規模也相應地呈指數級增長。巨大的網絡規模也造成了整個網絡設施能耗的平行增加。文獻[8]中的數據顯示，在2007年互聯網消耗的電能約為9×1011kWh，占世界總耗電量的 5.5%，并且每年以大約20%～25%的比例增加。互聯網的節能必會在全球節能領域做出十分重要的貢獻，是可持續發展的客觀要求。因此，互聯網上的節能問題成了眾多學者關注的課題。他們的基本思想是根據物理網的拓撲結構和流量矩陣，采用流量工程的方式節能，目標是用最小的網絡鏈路去承載當前的網絡任務。

雖然可重構柔性網目前處于實驗網階段，但是其新型的網絡架構給互聯網節能方案帶來了新的挑戰。本文主要關注可重構柔性網絡的節能問題，旨在提出一個匹配其構架的節能方案，并與傳統的流量規劃做比較，分析出可重構柔性網上節能方案的特點，為未來的該構架下的節能研究提供一些思路。

2 相關工作

為了減少溫室效應和環境污染，節能問題已經是網絡研究領域的一個重要議題。在當前的網絡下，IP流主要是根據各種路由協議進行選路，這些協議算法實際上是選擇資源最大的鏈路帶寬或最短跳數進行通信，這樣的選擇方式往往與節能的目標背道而馳，所以，僅僅依靠當前的網絡路由協議無法實現互聯網節能的目標。

文獻[9]指出，承載于各種網絡類型中的鏈路上的流量負荷達到或者超過其帶寬容量的30%時，該鏈路的能耗與滿負荷時的能耗相等。因此，通過流量控制來實現網絡的節能是徒勞無功的。當前，互聯網的節能研究主要是基于互聯網中的網絡設備具有休眠控制和動態電壓控制的假設之上的[10]。網絡領域節能的基本思想是將網絡中的負荷重新映射到當前物理網絡鏈路的一個子集上，從而可以調低鏈路電壓[11]或者休眠、關閉某些鏈路，實現節能的目的。文獻[12]是基于一個啟發式算法，在給定的流量矩陣中計算可以被關閉鏈路條數的最小值。同時，文獻[13]主要是根據流量矩陣找出最少的路由節點，用來支撐當前網絡流量，使其他的路由器休眠。

可重構網絡的構架是多個邏輯網(LCN)與一個物理網的對應關系，其上的流量的調整必然涉及邏輯承載網的重映射。大量的學者對邏輯承載網的映射做了深入的研究，并取得了豐富的成果。D.G.Andersen 提出了時間復雜度為O(log2k)的多通路算法來映射節點到實驗床[5]。與此同時，文獻[14]對于Overlay網絡的映射問題提出了自己的策略。值得一提的是，華盛頓大學的J.Lu等為各種特殊的拓撲提出專門的算法[15]以及佐治亞理工學院的Y.Zhu等提出的能夠根據網絡拓撲做適當調整的映射算法[16]。最后，M.Yu總結了之前的虛擬網映射算法，并提出了分流映射的思想，大大提高了映射效率[6]。

以上的這些工作都沒有從能耗的角度去考慮邏輯承載網的映射問題。當前，僅有少數的學者從流量工程的角度考慮網絡的節能，這些節能方法或者策略可以歸納到邏輯網映射的節能問題域。與邏輯網映射問題相似，他們都考慮了流束，從調整流的角度去釋放某些鏈路的負荷，再休眠或者關閉鏈路進行節能。這些節能算法中的鏈路重映射的方法也不盡相同，其中一部分是基于單徑路由的映射[17]，另一部分是基于多商品流模型的多徑路由映射[18]。無論是基于單徑映射或者是多徑映射，在IP網中，一定要切斷鏈路改變網絡的邏輯拓撲，進而改變數據流路由實現節能。在當前IP網中，網絡的邏輯拓撲和物理網拓撲是重疊的，流量規劃后，必然會依靠切斷物理鏈路進行改變邏輯網絡，實現數據流重定向路徑。同時，切斷網絡的物理鏈路無疑會造成相應網絡鏈路的大量分組丟失和網絡拓撲重構。由于互聯網路由快速恢復策略未得到實際應用，網絡的恢復時間基本上還是完全依靠互聯網協議重收斂。在這個收斂時間內網絡無法給用戶業務提供持續的網絡服務，因此在此期間內用戶的業務是中斷的。

3 問題描述

本文涉及的節能問題域與邏輯承載網映射關注的問題域不同。邏輯承載網的映射問題的核心問題是物理網資源的優化配置：即在當前的網絡資源下，接受盡可能多的LCN。而本文的節能問題域是在多個邏輯網與物理網映射關系的基礎上，調整邏輯網，使得用最少的物理網資源（節點和鏈路）去承載當前網絡的負荷。最終，通過休眠或者關閉冗余的節點和鏈路，從而實現節能的目標。

3.1 物理網定義

邏輯承載網表示為Gv=(Nv,Ev,,)。其中Nv表示邏輯承載網的節點的集合，Ev表示邏輯承載網的鏈路的集合；表示邏輯承載網的約束條件；表示邏輯承載網鏈路的約束條件。

3.2 邏輯承載網映射物理網過程

邏輯承載網映射到物理網分為節點映射和鏈路映射2個過程，故可以表示為

與傳統的網絡構架不同，可重構網路的路由節點可以同時加載多個路由構件，其構架如圖1所示，即在物理網中的同一個節點可以支撐多種不同類型的網絡。圖1中，邏輯承載網LCN1被映射到物理網{R1→R4→R3}，邏輯承載網LCN2被映射到物理網{R1→R2→R3}。LCN1和LCN2可以加載不同的協議構建，因而不同類型的網絡可以共存于同一物理網。

3.3 算法的節能原理

在可重構網絡構架下，柔性網絡配置代理（FNCB, flexible network configure broker）負責對域內路由節點資源信息和拓撲信息進行管理，并且可以在同一物理網中基于不同的策略，如貪心法、分流法[6]等，去構建邏輯承載網[1]。由于這些策略不同，在映射邏輯承載網的過程中，運用統一的節能策略將是十分困難和低效的。本文關注的可重構網絡的節能研究在于當映射完所有的邏輯承載網之后，針對物理網的當前流量、拓撲結構以及邏輯承載網的分布狀況做統一的節能調度。

圖1 可重構網絡的體系結構

在IP網中，廣泛應用的路由協議是OSPF協議和RIP協議。路由器總是根據它所搜集到的鏈路狀態信息（LSA, link state advertisement）運用Dijkstra算法計算從當前節點到其他網絡節點的最優路徑樹（OPT, optimal path tree），按照這棵樹對路由表進行更新，從而使得該路由器在路由時，可以選擇最優的路徑。

網絡領域節能問題的本質是求網絡拓撲的一個子集（ST, sub-topology）去承載當前網絡的負荷，也就是說使用網絡拓撲中盡可能少的節點和鏈路，關閉或者休眠冗余的節點和鏈路，從而使得網絡的能耗降低。本文基于該思想提出了基于可重構網絡的節能方法（ESMRN, energy-saving method based on the reconfigurable network）。

ESMRN主要將路由器分成3類：一類是關鍵路由器(KR, key router)，另一類是從屬路由器(AR,associate router)，第三類是普通路由器(NR, normal router)，它既不能化歸為從屬路由也不是關鍵路由。FNCB可以根據域內路由器廣播的LSA得出網絡的拓撲信息，然后按照度數的大小為權值評估出 KR集合(SKR, set of KR)，然后再確定AR集合（SAR，其偽代碼如算法1所示）和NR集合(SNR)。

算法1 divideSets的偽代碼

在本算法中，KR利用 Dijkstra算法根據當前LSA信息庫計算 OPT，從而對自己的路由進行更新，而從屬節點AR是先計算其鄰接的KR節點的OPT，然后旋轉OPT將自己調整為根節點得出自己的OPT，NR則按照OSPF正常路由。在圖2中假設節點a是KR節點，節點b是AR節點。圖2(a)是一個帶有OSPF權值的網絡拓撲圖，圖2(b)是a節點根據Dijkstra算法計算后得到的OPT，圖2(c)是b節點根據Dijkstra算法生成的OPT，而圖2(d)則是b節點根據ESMRN算法得出的OPT。經過本算法處理后，可以得出鏈路lb,j(b, g)是可被關閉的候選鏈路。如果經過重新映射，候選鏈路上的流量可以被規劃到其他的鏈路，那么關閉候選鏈路進行實現節能的目標。

圖2 算法的節能原理

4 基于可重構網絡的節能方法

4.1 節能方法的機制

基于可重構網絡的節能方法（ESMRN, energy-saving method base on reconfigurable network）主要分成3個步驟，其偽代碼如算法2所示。第一步FCBN根據當前的網絡狀態信息，劃分網絡節點的集合類型：SKR、SAR以及SNR。第二步物理網絡中的節點分別計算自己的路由。SKR集合中的節點根據Dijkstra算法計算自己的OPT；SAR中的節點先計算其鄰接的KR的OPT，然后旋轉該OPT，使得自己為根節點，再更新路由表；SNR集合中的根據傳統的OSPF協議進行路由選擇。該算法的第三步統計SAR集合中的元素AR中可以被刪除的鄰接鏈路lij( i, j)，運用多商品流模型將該鏈路上的流量fl映射到G( Np,Ep-l)。如果該流量可以被映射到該子圖上，則休眠該鏈路lij( i, j)，并更新節點和鏈路。

算法2 ESMRN偽代碼

在經過EMRSN算法運行到第2)步后，將獲得一個可關閉的候選鏈路集合CL。第3)步link_Optimization的功能是對候選鏈路lij( i, j)上的屬于各個虛擬網的流量在對應的目標子圖G( Np,Ep-l)上，以節點s, d為源節點和目的節點，將流量為帶寬進行重新映射，如果該流量可以被重新映射，那么將該鏈路l添加到可刪除鏈路集合L，而node_Optimization則是節點檢測是否所有鄰接邊都處于休眠狀態，如果是，那么休眠該節點。

本質上link_Optimization是一個多商品流的問題，多商品流問題是一個經典的NP-hard問題。本文選擇利用整數線性規劃的方法來處理該問題，如算法3所示。互聯網中的節能問題歸根結底是休眠鏈路和節點，而節點的休眠實際上是鏈路休眠的一個副產品，其前提條件是節點的所有鄰接鏈路都已休眠。

Equation 1為線性規劃的目標函數，其中，xij表示鏈路lij( i, j)或者節點i,j之間是否存在通路，如存在，取值為1，不存在則取值為0；Pij表示鏈路lij( i, j)消耗的電能，因此，T表示網絡中所有鏈路消耗的能量。Equation 2表示為經典的流約束條件，其中，表示源節點s到目的節點d的經過鏈路lij( i, j)的流量。Equation 3和Equation 6為多商品流模型的約束條件；Equation 3表示fij流量是由所有源節點和目的節點在鏈路lij( i, j)流量的分量組成，且每一組源節點和目的節點的分量之和為1。Equation 4中β為設置的最大的鏈路利用率(50%)，Cij為鏈路lij(i,j)的帶寬。Equation 5約束可刪除鏈路的搜索空間為CE。

算法3 link_Optimization的解法

4.2 算法的代價分析

物理網絡拓撲是一個圖，因此EMSRN算法需要O( N2)的空間存儲物理網拓撲。每一個邏輯承載網是一張圖，每個物理網上對應多個邏輯承載網，因此需要O( N3)的空間去存儲邏輯承載網與物理網鏈路的映射關系，綜合該算法的空間復雜度為O( N3)。EMSRN的第2)步(算法1)內主要利用了經典的最短路徑算法——Dijstra算法，需要O( N2)的時間，又因為其處于一個循環內，故整個第2)步的時間復雜度為O( N2)。該算法的第3)步是多商品流的線性規劃處理過程，其具有多項式時間復雜度，第4)步則是O( N3)。因此，EMSRN具有多項式時間的復雜度，是處于可以被接受的范圍之內。

EMSRN算法在當前網絡流量背景下，重映射LCN，使得某些鏈路能夠被釋放出來進行節能。在這個過程中，必然會涉及到中心控制，鏈路切換等問題。事實上，IP網中的節能算法都會遇到這些問題，這些問題可能會在算法運行的時間內損害網絡的QoS，導致網絡中的節能算法具有一定的局限性。同時，網絡經過調整后，網絡拓撲的冗余度降低，在處理新的LCN請求時，其接受率會有所降低。

5 仿真實驗與結果分析

5.1 實驗環境

本模擬實驗的物理拓撲圖是由Brite拓撲產生器[19]生成，它能模擬出最接近現實的網絡拓撲圖。拓撲圖的帶寬bw符合24～40之間的均勻分布的隨機數[16]，為了保證網絡能夠良好地運行，規定映射時實際可用帶寬為β×bw[18]。同時，網絡的背景流量由一系列隨機生成的邏輯承載網映射后生成，這些邏輯承載網的鏈路流量符合3～5之間的均勻分布[16]。這里的拓撲圖和LCN集合都保存在文本文件中，因此，本實驗能夠重現所有的背景流量進行反復模擬。

為了使得實驗更加完備和有說服力，Brite分別產生了節點數為{40, 60, 80, 100, 120, 140}的無向稀疏拓撲圖和無向稠密拓撲圖2種情況，其配置情況如表1所示。

表1 稀疏拓撲圖和稠密拓撲圖配置

EMSRN算法與目前已提交IETF草案的節能算法GreenTE[18]在上述背景下分別進行節能調度，并在節能效果、網絡時延和分組丟失率3個方面做充分的比較。

5.2 實驗結果

在實驗的過程中，假設每條鏈路開啟時，其消耗的能量是相同的，均為，并且將鏈路的最大利用率β設置為50%。網絡領域節能的本質是指鏈路的切斷或者休眠條數，當節點的鄰接鏈路全部切斷或者休眠之后便可關閉或休眠節點實現節能的目標。實際上，為了實現所有網絡節點的連通，需要的最少鏈路數為Lmin：N-1。假設節能算法調度后，當前網絡由LD條鏈路支撐，整個網絡的鏈路條數為LD，那么節能效率η表示為：L-LD/L-Lmin。為了使得本實驗更加具有說服力，針對每一組拓撲產生10組背景流量，最后取節能效果的均值，分別在在稀疏圖和稠密圖上進行節能調度，其調度效率如圖3和圖4所示。

圖3 稀疏拓撲圖上的節能效率

圖4 稠密拓撲圖上的節能效率

同時，為了測定節能算法對網絡的影響，在NS-2網絡仿真器[20]分別部署這2個算法用于數據分組級模擬。這里的仿真僅僅需要查看算法對網絡鏈路的影響，為了方便說明問題，僅僅考慮單流的重定向問題，并將實驗的拓撲設定為5個節點的全連接且假定這些節點之間的帶寬為2Mbit/s，然后，在節點上加載符合Pareto分布的流量[18]，取時間間隔為0.3s，分別觀察鏈路的分組丟失率與延時并取平均值，如圖5和圖6所示。

圖5 不同流量下的鏈路分組丟失率

圖6 不同流量下的鏈路延時

5.3 性能效果分析

本文所提出的EMSRN算法是針對可重構網絡架構而提出的，而GreenTE是基于當前的IP網的OSPF協議和MPLS協議。圖3和圖4給出了2種節能算法對網絡的調度效益。

由圖3和圖4可知，當物理網絡節點數比較少時（稀疏圖節點數少于60，稠密圖節點數少于80），EMSRN算法的調度相當于一個全局優化算法，而GreenTE局限于網絡的聯通度局限與一個局部的搜索，因此EMSRN效果要優于GreenTE；當網絡的節點數比較大時，其調度效果略差。

GreenTE實際上是一個局部最優的搜索算法，其搜索范圍局限于k-最短路徑算法定義的閾值，而EMSRN則是在全局范圍內選候選鏈路以及在全局范圍內重新映射該鏈路的流量，因此，可以判斷在物理網節點數較少的情況下，EMSRN的節能效益會優于GreenTE。但是，在拓撲圖十分龐大的情況下，網絡的連通度很大，因此，閾值對k-最短路徑算法的影響比較小，即一個不大的閾值便可以搜索全網的路徑，它可以近似為一個全局的最優化算法。在這種情況下，EMSRN專注于切斷AR的鄰接鏈路來實現節能的目標，并沒有從全網流量規劃的角度去考慮總體的路徑優化策略，導致了節能的效益相對于GreenTE略差。

從圖5和圖6中可以得出，EMSRN算法相對于 GreenTE具有較低的鏈路分組丟失率和延時。EMSRN算法的本質是FCBN管理的一個靜態路由的管理框架。當鏈路的路徑需要改變時，僅僅需要FCBN計算好鏈路后，重新發送路由配置命令對各關聯節點的路由進行重新配置即可。GreenTE雖然利用了MPLS的方法來減輕OSPF的收斂過程對網絡QoS的影響，但是MPLS的構建需要一個感知網絡拓撲變化的過程和一個路由的適配過程，在這 2個過程中，該鏈路中對應流量的數據分組則全被丟棄，嚴重影響了網絡的QoS。而FCBN則是根據現存的網絡拓撲信息的記錄進行選路，因此，沒有這個感知拓撲變化的過程，從而導致了其網絡延時較少，分組丟失率也較小，其分組丟失的過程主要發生在重新適配路由的時間段，GreenTE除了該階段沒法正常提供服務外，也沒有能力在感知拓撲的階段內承擔數據分組的發送，故其分組丟失率會比較大，延時也相對較大。

6 結束語

互聯網中的節能必然要對物理鏈路或者物理路由器做休眠或者關閉等處理來實現對網絡的邏輯拓撲的改造。傳統的IP網的邏輯拓撲和物理拓撲是重疊的，切斷或者休眠物理鏈路肯定會對邏輯拓撲造成影響，一定會在一定程度上停滯或者中斷用戶業務，影響QoS保障。這種情況下，節能的研究用途并不大。

然后，新型的可重構網絡架構是下一代網絡的發展方向，其路由的配置策略對網絡服務的影響輕微，從而使得網絡節能變為現實。本文僅僅分析了可重構網絡下的節能方法，并與認可度極高的基于流量規劃的節能算法——GreenTE做了詳細比較，分析了異同點和其優勢。下一步的工作在于研究可重構網絡下的節能協議以及如何構建一個節能的下一代新型互聯網。

[1] 趙昕, 蘭巨龍等. 可重構網絡中柔性網絡配置代理服務提供模型[J]. 信息工程大學學報, 2009, 10(1): 61-63.ZHAO X, LAN J L, et al. Model of service-oriented for flexible network configure broker in the reconfigurable network[J]. Journal of Information Engineering University, 2009, 10(1): 61-63.

[2] 陳文龍, 徐恪等. 基于構件的可重構路由開發環境[J]. 信息工程大學學報,2009,10(1):28-33.CHEN W L, XU K, et al. Components-based reconfigurable routing development environment[J]. Journal of Information Engineering University, 2009, 10(1): 28-33.

[3] 姜明, 閔嘯等. 邏輯承載網構建中的數學模型[J]. 信息工程大學學報, 2009, 10(1):50-52.JIANG M, MIN X, et al. Mathematical modeling in construction of logical carrying networks[J]. Journal of Information Engineering University, 2009, 10(1): 50-52.

[4] MOSHARAF N M, CHOWDHURY K, et al. Virtual network embedding with coordinated node and link mapping[A]. Proc IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil, 2009. 783-791.

[5] ANDERSEN D G. Theoretical approaches to node assignment[EB/OL]. http: //www.cs.cmu.edu/～dga/, 2002.

[6] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. Communication, 2008,38(2):17-29.

[7] WANG Y, et al. Virtual routers on the move: live router migration as a network-management primitive[A]. Proc ACM SIGCOMM 2008[C].Seattle, USA, 2008.231-242.

[8] KOOMEY J G. Estimating total power consumption by servers in the U S and the world[D]. Staff Scientist, Lawrence Berkeley National Laboratory and Consulting Professor, Stanford University, 2007.

[9] REVIRIEGO P, HERNANDEZ J A, LARRABEITI D, et al. Performance evaluation of energy efficient Ethernet[J]. IEEE Communications Letters, 2009, 13(9):697-699.

[10] MANDVIWALLA M, et al. Energy-efficient scheme for multiprocessor-based router line cards[A]. Symposium on Applications and the Internet[C]. 2006.

[11] SUGISONO K, et al. Path Engineering for Power Consumption[R].The Institute of Electronics, Information and Communication Engineers Technical Report NS2007-1, 2007.

[12] AKIKO Y, SATOSHI I, et al. A Path-based traffic control method for green network[A]. Proc of 8th APSITT[C]. Kuching, Malaysia, 2010.1-5.

[13] YAMADA A, et al. A study for green network (3)-eco routing[A].The Institute of Electronics, Information and Communication Engineers General Conference[C]. 2009.

[14] FAN J, et al. Dynamic topology configuration in service overlay networks: a study of reconfiguration polices[A]. Proc IEEE INFOCOM 2006[C]. Barcelona, Spain, 2006.

[15] LU J, et al. Efficient Mapping of Virtual Networks Onto a Shared Substrate[R]. Washington University, Tech. Rep. WUCSE-2006-35,2006.

[16] ZHU Y, et al. Algorithms for assigning substrate network resources to virtual network components[A]. Proc IEEE INFOCOM 2006[C]. Barcelona, Spain, 2006.

[17] LAI P, et al. Configuring network topology towards energy-efficient IP networks[A]. Proc IEEE ICCSN 2011[C]. Xi’an, China, 2011.

[18] ZHANG M G, YI C, LIU B, et al. GreenTE: Power-aware traffic engineering[A]. Proc of 18th ICNP[C]. Kyoto, Japan, 2010. 21-30.

[19] BRITE [EB/OL]. http://www.cs.bu.edu/brite/.

[20] Network Simulator ns-2[EB/OL]. http://www.isi.edu/nsnam/ns/.