EnergyAwareVirtualNetworkEmbedding资源-CSDN文库

研究论文

66 浏览量 2021-02-09 00:51:46 上传评论收藏 2.43MB PDF 举报

资源推荐

资源详情

资源评论

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 22, NO. 5, OCTOBER 2014 1607

Energy-Aware Virtual Network Embedding

Sen Su, Zhongbao Zhang, Alex X. Liu, Xiang Cheng, Yiwen Wang, and Xinchao Zhao

Abstract—Virtual network embedding, which means mapping

virtual networks requested by users to a shared substrate network

maintained by an Internet service provider, is a key function that

network virtualization needs to provide. Prior w ork on virtual

network embedding has primarily focused on maximizing the

revenue of the Internet service provider and did not consider the

energy cost in accommodating such requests. As energy cost is

more than half of the operating cost of the s ubstrate networks,

while trying to acc om modate more virtual network requests,

minimizing energy cost is critical for infrastructure providers.

In this paper, we make the ﬁrst effort toward energy-aware vir-

tual network embedding. We ﬁrst propose an energy cost model

and formulate the energy-aware virtual network embedding

problem as an integer linear programming problem. We then

propose two efﬁcient energy-aware virtual network embedding

algorithms: a heuristic-based algorithm and a particle-swarm-op-

timization-technique-based algorithm. We implemented our

algorithms in C++ and performed side-by-side comparison with

prior algorithms. The simulation results show that our algorithms

signiﬁcantly reduce the energy cost by up to 50% over the ex-

isting algorithm for accommodating the same seq uence of virtual

network requests.

Index Terms—Network virtualization, virtual network embed-

ding.

I. INTRODUCTION

A. Background and Motivation

ETWORK virtualization is the key technology that al-

lows multiple heterogeneous virtual networks (VNs) to

coexist on t

he same shared substrate network (SN). It b rings

three major b eneﬁts. First, it enables resource sharin g among

Manuscript received September 14, 2012; revised April 08, 2013; accepted

August 28, 2013; approved by IEEE/ACM T

RANSACTIONS ON NETWORKING

Editor C.-N. Chuah. Date of publication January 10, 2014; date of current ver-

sion October 13, 2014. This work was supported in part by the National Natural

Science Foundation of China under Grants 61170274, 61370226, 61375066,

61105127, and 61321491; the National Basic Research Program (973 Program)

under Grant 2011CB302704; the Innovative Research Groups of the National

Natural Science Foundation under Grant 61121061; the Important National Sci-

ence and Technology Speciﬁc Projects—Research about Architecture of Mobile

Internetunder Grant 2011ZX03002–001-01; and the China Scholarship Council.

Some p relim inary results of this paper were published in the First IEEE IN-

FOCOM Wor kshop on Commu nications and Con trol for Sustainable Ene rgy

Systems: Green Networking and Smart Grids (INFOCOM WS-CCSES), Or-

lando, FL, USA, March 25–30, 2012. (Corresponding authors: Z. Zhang and

A. X. Liu)

S. Su, Z. Zhang, X . Cheng , and Y. Wang are with the State Key

Laboratory o f Networking and Switching Technology, Beijing Unive r-

sity of Posts and Telecommunication s, Beijing 100080, China (e-mail:

susen@bupt.edu.cn; zhongbaozb@bupt.edu.cn; chengxiang@bupt.edu.cn;

wangyiwen}@bupt.edu.cn).

A. X. Liu is with the Department of Computer Science and Technology, Nan-

jing University, Nanjing 210093, China ( e-mail: alex liu@nju.edu.cn).

X. Zh ao is with the School of Science, Beijing University of Posts and

Telecommunications, Beijing 100080, China (e-mail: xcmmrc@gmail.com).

Color versions of one or more of the ﬁgures in this paper are available online

at http://ieeexplore.ieee.org.

Digital Obje c t Id e ntiﬁer 10.1109/TNET.2013.2286156

these VNs and makes most efﬁcient use of the SN. Second, it of-

fers oppo rtu nities to desig n and evaluate new n etwork protoc ols

and architectures. Third, it provides more ﬂexibil ity to expand

or shrink the VN as needed.

This pap er concerns the pro blem of VN em bedding. Network

virtualization involves one Internet service provider (ISP) and

multiple users, where the ISP manages the physical SN infra-

structure, while each user requests VNs from the ISP. Each

VN request consists of a network topology where each node

and edge have some constraints. The node constraints are typ-

ically on capacity (such as CPU computing power, mem ory

and storage capacity, etc.) and location (i.e., the location in the

topology of the substrate network of the ISP). T he edge con-

straints are typically on communication b andwidth. W hen the

ISP receives V N requests from users, the ISP needs to map

the VN to the physical nodes and links in its network, which

is called VN embedding.

B. Limitation of Prior Art

The VN embedding has received signiﬁcant attention in

recent years. The prim ary goal of prior work is to maximize the

revenue of the ISP by accommodating more VN requests on

the same SN [2]–[8]. The key limitation of prior studies is that

they did n ot consider the en ergy cost for serving VN requests.

However, energy is a major cost for ISPs. For example, in the

US, A k a mai, one of the wo rld ’s leading providers of content

delivery networking services, has an annual electricity cost of

about $10 million [ 9]. In China, China mobile Communications

Corporation, the largest m obile service provider in the world,

consumes over 13 TWH power consumption in 2011 [10].

Telecom Italia, the second largest consumer of electricity in

Italia, consumes more than 2 TWh pe r year, which is equivalent

totheenergyconsumedby660000familiesinoneyear[11].

Thus, to maximize the net proﬁt, the ISP needs to strike the

right balance between accommodating more VN requests and

minimizing energy costs for serving VN requests.

C. Proposed Approach

In this paper, we propo se to trade off between maximizing the

number of VNs that can be accomm odated by an ISP and m in-

imizing the

energy cost of the whole system. For each VN re-

quest, the ISP maps the VN to some physical n odes and links in

its network in such a way that the amount of ad ditional en ergy

cost caus

ed by accommodating the VN request is m inimized.

This app roach is based on two observations. The ﬁrst observa-

tion is that the substrate nodes are usually geographically dis-

tribut

ed to deploy and deliver service to end-users, and the elec-

tricity price m ay differ for different locations and may ﬂuctuate

over time [9 ], [12]. Based on this observation, an ISP should

try to

map the virtual nodes of a VN to the physical no des tha t

have the lowest electricit y pr ice w hile satisfying the locatio n

constraint o f the VN. The second o bserv atio n is that t he power

See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

1608 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 22, NO. 5, OCTOBER 2014

consumption of a server is approximately linear to its C PU uti-

lization with a large offset, which equals up to nearly 50% of

the peak power [13]. Based on this observation, an ISP should

try to map the vi rtu al n odes of a VN to the physical nodes that

are already actively running; thus, we can maximize the number

of nodes that do n ot have any load and therefore can be put to

sleep to save energy.

D. Technical Challenges an d Proposed So lutions

The ﬁrst technical challenge is o n m odeling and quantifying

the energy cost of the complex physical network infrastruc-

ture of an ISP. Speci ﬁcally, we need to model both electricity

price and energy consumption. For electricity price, we use a

discrete-time model to characterize the spot dynamics of elec-

tricity price. For e nergy consumption, we ﬁrst classify substrate

nodes into host nodes, which need to execute some computa-

tional tasks, and router nodes, which need to forward packets to

and from host nodes. We further classify them into active nodes,

which need to be powered up, and inactive nodes, which can be

powered off to save energy. Then, for different types of nodes,

we build the corresponding energy consumption models. Based

on such models, we carry out th e quantitative analysis o f the

overall energy consumption, including the energy consu mption

of virtual nodes and virtual links for accommodating a VN re-

quest. After the modelings, we can quantify the electricity cost

by calculating the time integral of the electricity price and the

power c o nsum ption .

The second technical challenge is on designing energy-aware

VN embedding algorithms. To address this challenge, ﬁrst, we

model our energy-aware VN embedding problem as an integer

linear programmin g problem. Second,weproposeaheuristic

algorithm called EA-VNE for solving this problem. This algo-

rithm consists of two steps: node map ping and link mapping.

The node mapping step further consists of two sub steps: r outer

node mapping and host node mapping. In the router node map-

ping, we exploit the location- an d time-varying diversities of

electricity prices to save energy cost. To max im ize the proba-

bility of performing s uccessful link mapping in the next step,

we design a worst-ﬁt strategy for the bandwidth resources. In

the ho st node mapping, we design a best-ﬁt strategy to min-

imize the number of hosting nodes and make the best use of

the reso urce while satisfying the node requirements of the VN

request. In the link mapping step , w e design an active nodes

and router ports preferred shortest path algorithm that tries to

minimize the number of forwardin g n odes and ports. To fur-

ther minimize energy cost, we design an approximation algo-

rithm called EA-VNE-EPSO, which is based on the well k now n

particle swarm optimization (PSO) technique. Speciﬁcally, we

treat a VN e mbedding solution as a particle in PSO, and thus

each particle will achieve a better and better embedding solution

through the iteration process b y learning from the experience of

other particles. To accelerate the convergence of this iterative

algorithm, we propose an energy-aware local selection strategy

based on the characteristics of VN embedding. Furthermore, we

propose a nonuniform mutation strategy to prevent premature

convergence.

E. Summary of Experimental Results

We carry out extensive sim ulation and show that our al-

gorithms outperform the state-of-the-art algorithm in terms

TABLE I

OTATIONS

of long-term average energy cost while g aining competitive

revenues for ISPs. While maintaining nearly the same revenues,

our algorith ms EA-VNE and EA-VNE-EPSO save up to 40%

and 50% of energy cost than prior art, respectively.

F. Key Contributions

We make the following key contributions in this paper.

1) We make the ﬁrst attem pt to incorporate the energy factor

in performin g V N embedding. We formulate an energy

cost model f or studying the en ergy-aware VN embeddin g

problem.

2) We design two VN embedding algorithms to reduce the

energy cost while keeping nearly the same revenue so as

to maximize the proﬁtfortheISPs.

3) We conduct side-by-side comparison between our algo-

rithms and the state-of-the-art algorithm. We show that

our algorithms outperform t he state-of-the-art algorithm in

terms of both long-term average energy cost and revenues

for ISPs.

The rest of the paper is organized as follows. In Section II, we

present the energy cost model and the energy-aware VN embed-

ding problem form ulation . In Sections III and IV, we present

our heuristic and metaheuristic energy-aware VN em bedding

algorithms, respectively. We evaluate our VN embedding algo-

rithms in Section V. Section VI reviews related work. Finally,

Section VII concludes the paper.

II. S

YSTEM MODELING

In this section, w e ﬁrst present a network model. Second,

we form ulate an energy model for VN infrastruc ture. Third, we

quantitatively analyze the energy consumption for accommo-

dating a VN r equest. Finally, we formulate the energy-aware VN

embedding problem based on the model. The notations used in

this paper are summarized in Table I.

A. Network M odeling

An SN is represented by a weighted graph

where

denotes the set of physical nodes and denotes

the set of physical links. The substrate nodes can be classi-

ﬁed into two categories: router nodes and host nodes. That is,

SU et al.: ENERGY-AWARE VIRTUAL NETWORK EMBEDDING 1609

Fig. 1. Example of VN embedding. (a) VN request. (b) Substrate network.

Fig. 2. Hourly electricity price of ﬁve locations in one week.

,where denotes t he set of routers and

denotes the set of hosts. Similar ly, the substrate links can also

be classiﬁed into two categories: the backbone link and the local

link, denoted by

and , respectively. Fig. 1(b) shows an

SN exam ple where circles and rectangles denote router and host

nodes, respectively.

For router nodes, we consider the following th ree attributes.

The ﬁrst attribute is the number of virtual rou ters t hat t he

physical router can suppo rt fo r deploying and runn ing different

personalized network protocols. In Fig. 1(b), the numbers that

are in parentheses and b eside each circle are such num bers.

The second attribute is the location that the router is located as

routers are generally geo grap hically distribu ted. For example,

in Fig. 1(b),

may be located in Los Angeles, CA, USA;

in Chicago, IL, USA; in New York, NY, USA; and

in New Jersey, USA. We use a two-dimensional coordin ate

to denote the location of nod e . The third

attribute is electricity price. The power markets of different lo-

cations are managed by different independen t system operators

(ISOs), and the ISOs are under competitive electricity mark et

structure. Therefore, different locations often have different

electricity prices. Even for the sam e location, the electricity

price m ay vary frequently over time [9], [12]. Fig. 2 show s the

hourly electricity price of the ﬁrst week of Septem ber 2011

available at [14] for ﬁve regions in the day-ahead market, in-

cluding the Eastern Hub of PJM (Pennsylvania–Maryland–New

Jersey), NP-15 Hub of CA I SO (Cali for nia), Capital Hub of

NYISO (New York), Mass Hub of ISO-NE (New England),

and Illinois Hub of MISO (Midwest). We observe that the elec-

tricity price varies over both location and time. To characterize

the spot price dynamics, in this paper, we use a discrete-time

model, which has a time window (e.g., an hour) of interest

.Weuse to denote the electricity price

for node

at time-slot , to denote th e arriving time of a VN

request, and

to denote the duration of the VN request being

served in the SN. Thus, the expiration time

of the VN request

For host nod es, we consider three attributes: CPU speed,

memory size, and storage capacity. In Fig. 1 (b), the triple

beside each host node denotes the values of these attributes.

For links, we consider bandwidth. In Fig. 1(b), the number

beside each link is the bandwidth. Note that t he modeling,

analysis, and algorithms in this paper can be easily extended

to incorporate o ther attributes, such as latency and jitter con-

straints, as well.

A VN is represented as a weighted graph

Here,

,where and denote

the set of virtual router and host nodes, respectively; and

,where denotes the set of virtual links

between any two virtual routers and

denotes the set of

virtual links between host nodes and routers. Fig. 1(a) shows

the VN requested by a user on the SN in Fig. 1(b).

We now formally deﬁne th e VN embedding problem. Given

a VN request

with a set of virtual n odes

and a set of virtual links ,andanSN

with a set of physical nodes and a set of

physical links

,embed on ,which

means to ﬁ nd two one-to-one mappin gs:

and . Here,

is a one-to-one mapping from to a s ubset of .Th

mapping includes tw o submappings,

and ,where

is from to a subset of ,and is from

to a subset of . For each virtual router node a

nd the

physical node

that it maps to, satisﬁes

both virtual router quan tity and location requirements of

For each virtual host node

and the physical n

ode

that i t maps to, satisﬁes the node requirements on

CPU speed, mem ory size, and storage capacity of

. Here,

is from to a subset of , which denotes a

ll loop-free

paths composed by the physical links in

. This mappin g

also includes two subm app ings,

and ,where

is from to a subset of , denoting a ll lo

op-free paths

between any two routers, and

is from to a subset of

, denoting all loop-free paths between hosts and routers.

For each virtual link

and the ph ys

ical path

that it

maps to, the bandwidth of each physical link in

is no

less than the bandw idth requirement of

. Take the em bed-

ding in Fig. 1 as an example. The no

de mapping solution is

and the link m apping solution is

Note that we focus on consideringoneISPinthispaper.

When multiple IS Ps collabora

te to provided VN services, as

each ISP knows only the characteristics of his own infrastruc-

ture, there are many technical challenges to address this issue.

The readers can refer to [15

] for more discussion on this topic.

B. Energy Co st Modeling

1) Node Energy Cost: Let

denote the additional

power consumption for mapp ing a virtual router

asubstraterouter

,and denote the additional

power for mapp ing a virtual host node

to a substrate

剩余13页未读，继续阅读

评论收藏

内容反馈

执念高

粉丝: 10
资源: 952

Energy Aware Virtual Network Embedding

最新资源

Energy Aware Virtual Network Embedding

Context-Aware User Association for Energy Cost Saving in A Green Heterogeneous Network with Hybrid Energy Supplies

Cost-Aware Multi-Domain Virtual Data Center Embedding

An Energy-Aware Algorithm for Optimizing Resource Allocation in Software Defined Network

论文研究-An Energy-Aware Scheduling Method of Virtual Machines in DFVS-Enabled Cloud.pdf

2012A-Virtual Network Embedding Algorithms

基于CORDIC的反正弦和反余弦计算的FPGA实现

BA无标度网络中的SIR模型

使用3DCNN和卷积LSTM进行手势识别学习时空特征

基于三次贝塞尔曲线的类汽车曲率连续路径平滑

基于机器学习的设备剩余寿命预测方法综述

基于维纳过程的退化模型，具有递归过滤算法，可用于估计剩余使用寿命

基于FPGA的奇异值和特征值分解的快速实现。

磁悬浮系统自适应模糊PID控制器的设计

基于BP神经网络的人口预测

无人机协同目标的多无人机协同搜索方法

两轮平衡车的建模与控制研究

基于改进遗传算法的六自由度机器人时间最优轨迹规划

一种基于深度学习的机械臂抓取方法

基于深度神经网络的交通流量预测

一种去除ECG中基线漂移和工频干扰的高效滤波方法

适用于1-8GHz宽带应用的原始Vivaldi天线

基于稀疏贝叶斯学习的高效DOA估计方法

亮度保持和细节增强的红外图像增强方法

最新资源