面向節點異構的能耗感知虛擬網絡映射算法

龔水清 陳 靖 王 崴

?

面向節點異構的能耗感知虛擬網絡映射算法

龔水清*①陳 靖①王 崴②

①(空軍工程大學信息與導航學院 西安 710077)②(空軍工程大學防空反導學院 西安 710051)

在底層網絡節點異構的環境中，能耗優化的虛擬網絡映射問題并不是最小化工作節點和鏈路數。該文針對此問題，構建底層網絡節點和鏈路的負載能耗模型，并以能耗最優為目標，建立虛擬網絡映射問題的數學模型，提出一種能耗感知虛擬網絡映射算法。該算法在節點映射階段以最小化能耗和協調鏈路映射為原則，將虛擬節點映射至綜合資源能力最大的底層節點上，并采用改進的能耗感知最短路徑法進行鏈路映射。仿真結果表明，該算法顯著減少虛擬網絡映射的能耗，且底層網絡節點異構性越大，能耗優勢更為明顯。

網絡虛擬化；虛擬網絡映射；能耗模型；資源能力

1 引言

隨著全球能源危機的出現，電力價格不斷上漲，能耗成本已成為互聯網服務提供商(Internet Service Provider, ISP)最主要的運營開銷。但現有互聯網絡大都采用超額資源供給以應對網絡突發性的峰值負載，并進行冗余設計以提高網絡可靠性，網絡資源和能源的利用率較低。且大型ISP骨干網的最大鏈路利用率不足40%[1]，網絡設備大多7′24 h全速運轉，這導致網絡閑時大量資源和能源的浪費。因此，減少網絡能源消耗，降低網絡運維成本，構建綠色節能的網絡已成為當前研究亟待解決的問題[2]。

網絡虛擬化[3]是近年來提出來的用于解決互聯網“僵化”問題[4]，促進未來網絡創新發展的重要技術。它通過資源抽象、聚合、隔離等機制允許多個異構的虛擬網絡(Virtual Network, VN)共享同一底層物理網絡(Substrate Network, SN)，可實現對多樣化網絡技術部署和應用的支持。虛擬網絡映射[5]作為網絡虛擬化中的核心問題，是指為帶有節點和鏈路資源需求約束的虛擬網絡請求分配底層物理網絡資源。目前，大部分虛擬網絡映射算法[5–7]主要以降低虛擬網絡映射成本，提高底層網絡映射收益為目標。然而，這些研究未考慮虛擬網絡映射過程中的能耗優化，必然帶來不必要的能耗。

當前，由于網絡節點和鏈路的能耗對流量負荷不敏感[8]，因此在滿足虛擬網絡資源請求的前提下，運營商通過讓網絡中空閑的節點和鏈路處于低功耗模式甚至關閉可以達到節能的目的。受到這一啟發，文獻[9]以最小化底層網絡工作節點和鏈路數量為目標，建立了虛擬網絡映射問題的混合整數規劃能耗優化模型，通過將虛擬網絡集中映射至底層網絡工作的節點和鏈路上，并關閉空閑的節點和鏈路以減少網絡能耗。文獻[10]進一步考慮映射成本和負載均衡，改進了文獻[9]的算法，并針對大規模虛擬網絡映射問題提出了能耗感知重配置啟發式算法。由于節點和鏈路的能耗與其負載有關，文獻[11,12]提出了節點和鏈路的能耗模型，以最小化映射能耗開銷為目標，建立虛擬網絡映射問題的整數線性規劃模型，并提出啟發式算法對該問題進行求解。文獻[13]針對不同時間不同地區的電力價格不同，以減少電力成本為目標，提出了一種跨域能耗優化的虛擬網絡映射算法。

然而，上述虛擬網絡映射算法都假設底層網絡中所有節點的功耗相同，通過優化映射過程中工作節點數并關閉空閑節點，達到節能目的。但由于底層網絡設備存在采購時間、使用年限和品牌等異構性，導致功耗各不相同，此時，虛擬網絡映射的能耗優化問題并不是最小化工作節點數量。因此，目前已提出的大部分節能虛擬網絡映射方法不能很好地應用在一般網絡的能耗管理中。

為此，本文針對底層網絡節點異構的能耗優化虛擬網絡映射問題進行研究，首先建立底層網絡節點和鏈路的負載能耗模型，并以最小化映射能耗為目標，構建虛擬網絡映射問題的數學優化模型。然后，設計能耗感知虛擬網絡映射啟發式(Energy- Aware Virtual Network Embedding Heuristic, EA- VNEH)算法對模型進行求解。EA-VNEH算法以最小化能耗和協調鏈路映射為原則，將虛擬節點映射至綜合資源能力最大的底層節點上，并采用改進的能耗感知最短路徑算法進行鏈路映射。最后，在底層網絡節點不同異構性的環境下對該算法進行性能評估與分析。仿真結果表明，算法在能耗優化、映射成功率和底層網絡收益等方面明顯優于已有的虛擬網絡映射方法。

2 系統模型與問題描述

2.1網絡模型

2.2能耗模型

虛擬網絡請求映射至底層網絡產生的能耗主要包括節點能耗和鏈路能耗兩部分。

(1)節點能耗： 底層網絡中的節點主要指服務器，其功耗主要包括基本功耗和動態功耗兩部分。基本功耗是指服務器空載時的功耗，與負載無關，而動態功耗是指與載荷相關的功耗。現有研究表明服務器節點的功耗與其CPU利用率呈近似線性關系[14]，而服務器的其他部分如內存、存儲等功耗相對較小[15]。因此，本文用式(1)估計底層網絡節點的功耗。

(2)鏈路能耗：鏈路能耗主要包括底層路徑兩端點(工作節點)收發數據包的能耗和中間節點轉發數據包的能耗。現有研究通常認為網絡虛擬化中部署有專用的離線引擎[16]，用于高效的數據包處理并保持低處理延時，且無論端口是空載還是滿負荷運轉，該引擎的功耗都接近于常量[17]。

2.3虛擬網絡映射問題描述

3 能耗感知虛擬網絡映射問題的數學模型

本節以最小化虛擬網絡映射總能耗為目標函數，以滿足虛擬網絡資源需求為約束，對能耗感知虛擬網絡映射問題進行混合整數線性規劃(Mixed Integer Linear Program, MILP)建模，具體過程如下：

目標函數：

約束條件：

說明 在底層網絡節點能耗異構的環境中，能耗感知虛擬網絡映射的目標并不是最小化工作節點數量，而是最小化總映射能耗，因此本文以式(8)作為該模型的目標函數。虛擬網絡映射時，需考慮滿足虛擬網絡請求的資源需求約束，主要包括節點約束和鏈路約束。式(9)和式(11)分別是節點的CPU資源約束和位置約束。式(10)和式(12)分別表示鏈路的帶寬資源約束和連通性約束。式(13)和式(14)表示同一虛擬網絡請求的虛擬節點必須映射到底層網絡中不同的物理節點上。式(15)和式(16)為該模型的變量范圍的約束，和需滿足整數約束條件，導致該模型成為非確定性多項式時間難問題(NP-hard)。

4 EA-VNEH算法設計

由于虛擬網絡映射問題的MILP模型是一個NP-hard問題，雖然傳統的方法如分支定界法可以求得其最優解，但隨著問題規模的增長，其時間復雜度較高，計算時間過長，不適用于大規模網絡的映射。因此，本節設計EA-VNEH算法對能耗感知虛擬網絡映射問題進行求解。

4.1 節點映射

由于資源需求高的虛擬節點映射更加困難，很可能由于底層網絡節點沒有足夠多的資源而導致映射失敗，因此，在節點映射階段，優先選擇資源需求高的虛擬節點進行映射。節點的鄰接鏈路可用帶寬的多少直接影響后續的鏈路映射階段，為此，本節將節點的資源能力定義[6,11]為

在節點映射階段，首先按照式(17)計算虛擬網絡中節點的資源能力需求，并按照從大到小順序依次進行映射。針對節點，提出如下映射原則：

節點映射算法的主流程如表1所示。與已有節能映射算法[11,13]相比，EA-VNEH算法在節點映射過程中考慮了節點的資源能力和能耗，并以綜合資源能力CR作為節點的排序標準，將虛擬節點映射至CR最大的底層物理節點上，可有效節省能耗，提高映射成功率，進而增加底層網絡收益。

4.2鏈路映射

現有研究主要采用最短路徑法進行鏈路映射[6,11]，但此方法沒有考慮底層鏈路的能耗，導致能源利用效率不高。為此，本節綜合考慮鏈路映射的帶寬消耗和能源消耗，設計能耗優先的最短路徑鏈路映射算法，如表2所示。

表2 EA-VNEH的鏈路映射算法

在鏈路映射階段，首先按帶寬需求對虛擬鏈路進行排序，優先選擇資源需求高的虛擬鏈路進行映射。對于虛擬鏈路，采用最短路徑法[18]計算底層節點至的最短路徑集合，且對于任意，需滿足虛擬鏈路的帶寬資源需求。鏈路映射時，通過計算將映射至上新增的能耗，將虛擬鏈路映射到能耗最小的最短路徑上。

從表2中可以看出，EA-VNEH在鏈路映射階段兼顧鏈路帶寬消耗和能耗，優先選擇底層網絡最短路徑集中能耗最低的路徑作為映射目標，可有效降低鏈路映射成本，減少鏈路映射能耗，提高映射收益。

5 性能評估與分析

ALEVIN[19]是一個用于開發、比較和分析虛擬網絡映射算法的仿真平臺。本文以此作為仿真工具，對EA-VNEH和幾種能耗優化虛擬網絡映射算法進行仿真，并從虛擬網絡請求長期平均能耗、虛擬網絡請求接受率、底層網絡長期收益開銷比和運行時間等方面討論EA-VNEH算法的性能。

5.1 實驗環境設置

網絡拓撲使用GT-ITM拓撲生成器產生，底層網絡設置為50個節點，節點間的連接概率為0.5，相當于一個中小型規模的ISP運營商。底層節點的可用CPU資源和底層鏈路的可用帶寬資源均服從[50,100]的均勻分布。底層節點的位置變量與均服從[0,100]的均勻分布。虛擬網絡請求隨機生成，每100個時間單元虛擬網絡請求到達的個數服從均值為4的泊松分布，其生存期服從均值為25個時間單元的指數分布。虛擬網絡的節點數目服從[2,10]的均勻分布，虛擬節點間以0.5的概率連接。虛擬節點的CPU資源需求和虛擬鏈路的帶寬資源需求均服從[0,50]的均勻分布，且假設所有節點的位置需求D取常量50。此外，設置式(17)中的權重和均為1，鏈路映射最短路徑算法中的為5。

本節分別在底層網絡節點能耗異構性不同的兩種環境下對算法EA-VNEH, EE-VNE[9]和EA- VNE[11]進行仿真實驗。算法EE-VNE和EA-VNE均以最小化底層網絡工作節點和鏈路數量為目標，前者采用GLPK工具求解VNE的MILP模型，后者的節點映射階段采用貪婪算法，鏈路映射階段采用最短路徑法。為了使整個仿真的運行處于比較平穩的狀態，設定實驗運行時間為50000個時間單位。為避免隨機因素對實驗結果產生擾動，仿真實驗總共進行10次，并取實驗結果的平均值作為最終仿真結果。

5.2性能分析

本文從虛擬網絡請求長期平均能耗、虛擬網絡請求接受率、底層網絡長期收益開銷比和運行時間4個方面對算法進行性能比較，仿真結果表明EA- VNEH算法具有以下優勢。

(1)顯著降低了虛擬網絡映射的能耗，且底層網絡節點異構性越大，能耗減少更為明顯。

圖1表示底層網絡不同節點異構性環境下虛擬網絡請求平均能耗的變化情況。圖1(a)表明在底層節點異構性小的環境下，EA-VNEH算法的虛擬網絡請求平均能耗穩定在21.73 kW左右，較EE-VNE, EA-VNE分別降低了約19.61%和15.73%。圖1(b)表明在底層節點異構性大的環境下，EA-VNEH算法的虛擬網絡請求平均能耗穩定在23.24 kW左右，較EE-VNE, EA-VNE分別降低了約30.14%和26.32%。主要原因是EA-VNEH算法考慮了底層網絡節點的能耗異構性，在映射過程中將虛擬節點和鏈路映射到能耗更小的底層網絡節點和路徑上。而EE-VNE和EA-VNE只優先選擇工作的節點和鏈路進行VNR的映射，但在底層網絡節點能耗異構的環境下，這兩種方法并不能實現能耗最優化。

圖1 虛擬網絡請求平均能耗

(2)提高了虛擬網絡請求接受率和底層網絡的收益。

圖2和圖3分別表示底層網絡不同節點異構性環境下虛網請求接受率和底層網絡長期收益開銷比的變化情況。從圖中可以看出，由于初始時段底層網絡可用資源較為豐富，3種算法的虛網請求接受率和收益開銷比都較高。隨著資源的逐步消耗，接受率和收益開銷比都逐漸下降。但由于3種算法隨著虛擬網絡請求的動態到達和離開而達到一個穩態過程，所以虛網請求接受率和收益開銷比都趨于平穩。圖2和圖3表明在底層網絡不同節點異構性環境下，EA-VNEH算法的虛擬網絡請求接收率和收益開銷比明顯高于其它兩種算法。主要原因是EA- VNEH在節點映射過程中采用了協調鏈路映射的原則，使后續鏈路映射更容易成功，從而提高了虛擬網絡請求接受率，進而映射收益較高。而EE-VNE和EA-VNE優先將虛擬節點和鏈路映射至工作的節點和鏈路上，容易產生瓶頸節點和鏈路，降低了隨后到達的虛擬網絡請求的映射成功率。

圖2 虛擬網絡請求接受率

圖3 底層網絡收益開銷比

(3)降低了虛擬網絡映射的求解時間

表3表示不同算法的虛擬網絡映射的平均求解時間。從表中可看出，相較于EA-VNEH和EA-VNE算法，EE-VNE需要運行更多的時間映射虛擬網絡請求。主要原因是EA-VNEH和EA-VNE采用啟發式算法求解虛擬網絡映射問題，有效降低了算法的運行時間，而EE-VNE采用標準的MILP求解工具GLPK來求取虛擬網絡映射的最優解，其求解時間隨網絡規模的增長呈指數增加。

表3算法運行時間

算法EE-VNEEA-VNEEA-VNEH 運行時間1.23 s41 ms52 ms

6 結束語

本文研究了底層網絡節點異構環境下的能耗優化的虛擬網絡映射問題。由于底層網絡節點的能耗異構性，虛擬網絡映射到底層網絡產生的動態能耗也不同。此時，能耗優化的虛擬網絡映射問題并不是最小化工作節點和鏈路數。針對此問題，構建了底層網絡節點和鏈路的能耗模型，并將能耗感知虛擬網絡映射問題建模為MILP模型，提出了EA- VNEH映射算法。仿真實驗結果表明，與傳統的能耗優化虛擬網絡映射算法相比，EA-VNEH提高了虛擬網絡請求接受率和底層網絡的收益，降低了運行時間，顯著減少了虛擬網絡映射的能耗，且底層網絡節點異構性越大，能耗優勢更為明顯。

參考文獻

[1] Fisher W, Suchara M, and Rexford J. Greening backbone networks: reducing energy consumption by shutting off cables in bundled links[C]. Proceedings of the first ACM SIGCOMM Workshop on Green Networking, New Delhi, India, 2010: 29-34.

[2] 林闖, 田源, 姚敏. 綠色網絡和綠色評價: 節能機制, 模型和評價[J]. 計算機學報, 2011, 34(4): 593-612.

Lin Chuang, Tian Yuan, and Yao Min. Green network and green evaluation: mechanism, modeling and evaluation[J]., 2011, 34(4): 593-612.

[3] Chowdhury N M and Boutaba R. A survey of network virtualization[J]., 2010, 54(5): 862-876.

[4] Turner J S and Taylor D E. Diversifying the Internet[C]. Proceedings of the IEEE Global Communications Conference, Saint Louis, USA, 2005, 2: 1-6.

[5] Fischer A, Botero J F, Till B M,.. Virtual network embedding: a survey[J].&, 2013, 15(4): 1888-1906.

[6] Hsu W H and Shieh Y P. Virtual network mapping algorithm in the cloud infrastructure[J]., 2013, 36(6): 1724-1734.

[7] 余建軍, 吳春明. 支持接入控制的虛擬網映射近似算法[J]. 電子與信息學報, 2014, 36(5): 1235-1241.

Yu Jian-jun and Wu Chun-ming. Virtual network mapping approximation algorithm with admission control[J].&, 2014, 36(5): 1235-1241.

[8] Chabarek J, Sommers J, Barford P,.. Power awareness in network design and routing[C]. Proceedings of the IEEE International Conference on Computer Communications, Phoenix, USA, 2008: 1130-1138.

[9] Botero J F, Hesselbach X, Duelli M,.. Energy efficient virtual network embedding[J]., 2012, 16(5): 756-759.

[10] Botero J F and Hesselbach X. Greener networking in a network virtualization environment[J]., 2013, 57(9): 2021-2039.

[11] Su S, Zhang Z, Cheng X,.. Energy-aware virtual network embedding through consolidation[C]. Proceedings of the IEEE International Conference on Computer Communications Workshops, Orlando, USA, 2012: 127-132.

[12] Su S, Zhang Z, Liu A X,.. Energy-aware virtual network embedding[J]./, 2014, 22(5): 1607-1620.

[13] Zhang Z, Su S, Niu X,.. Minimizing electricity cost in geographical virtual network embedding[C]. Proceedings of the IEEE Global Communications Conference, Anaheim, USA, 2012: 2609-2614.

[14] Rivoire S, Ranganathan P, and Kozyrakis C. A comparison of high-level full-system power models[J]., 2008, 15(8): 3-9.

[15] Economou D, Rivoire S, Kozyrakis C,.. Full-system power analysis and modeling for server environments[C]. Proceedings of Workshop Modeling, Benchmarking, Simulation, Boston, USA, 2006: 70-77.

[16] Turner J S, Crowley P, DeHart J,.. Supercharging planetlab: a high performance, multi-application, overlay network platform[J]., 2007, 37(4): 85-96.

[17] Sivaraman V, Vishwanath A, Zhao Z,.. Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[C]. Proceedings of the 30th IEEE International Conference on Computer Communications Workshops, Shanghai, China, 2011: 331-336.

[18] Eppstein D. Finding theshortest paths[C]. Proceedings of IEEE Symposium on Foundations of Computer Science, Santa Fe, USA, 1994: 154-165.

[19] Beck M T, Linnhoff-Popien C, Fischer A,.. A simulation framework for Virtual Network Embedding algorithms[C]. Proceedings of the IEEE Telecommunications Network Strategy and Planning Symposium (Networks), Madeira Island, Portugal, 2014: 1-6.

[20] Lu G H, Guo C X, Li Y L,.. Serverswitch: a programmable and high performance platform for data center networks[C]. Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, Berkeley, USA, 2011: 1-14.

Energy-aware Virtual Network Embedding Algorithm for Heterogeneous Nodes

Gong Shui-qing①Chen Jing①Wang Wei②

①(,,,710077,)②(,,,710051,)

The energy optimized virtual network embedding problem in the substrate network with heterogeneous nodes is not to minimize the number of working nodes and links. The load-based energy consumption models of the node and link in the substrate network are built, a mathematical model of the virtual network embedding problem is modeled in order to reduce energy consumption, and an energy-aware virtual network embedding heuristic algorithm is proposed. Based on the principles of energy optimization and coordination with link mapping, the virtual node is mapped onto the substrate node with the highest comprehensive resource capacity in the node mapping phase, and the link mapping phase is based on the energy-awareshortest path algorithm. Simulation results show that the proposed algorithm reduces the energy consumption significantly, and the heterogeneity of substrate network nodes is greater, reducing the energy consumption is more obvious.

Network virtualization; Virtual network embedding; Energy consumption model; Resource capacity

TP393

A

1009-5896(2015)08-2021-07

10.11999/JEIT141527

龔水清 gsq0121@126.com

2014-12-02收到，2015-03-06改回，2015-06-09網絡優先出版

國家自然科學基金(51075395)和國家863計劃項目(2013AA040604)資助課題

龔水清： 男，1987年生，博士生，研究方向為網絡虛擬化、下一代互聯網.

陳 靖： 女，1963年生，博士，教授，研究方向為分布式計算、移動自組織網絡、網絡虛擬化等.

王 崴： 男，1974年生，博士，副教授，研究方向為云計算、網絡虛擬化等.