没有合适的资源?快使用搜索试试~ 我知道了~
Energy Aware Virtual Network Embedding
0 下载量 135 浏览量
2021-02-09
00:51:46
上传
评论
收藏 2.43MB PDF 举报
温馨提示
Energy Aware Virtual Network Embedding
资源推荐
资源详情
资源评论
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 first effort toward energy-aware vir-
tual network embedding. We first propose an energy cost model
and formulate the energy-aware virtual network embedding
problem as an integer linear programming problem. We then
propose two efficient 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
significantly 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
N
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 enefits. 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 Specific 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 figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Obje c t Id e ntifier 10.1109/TNET.2013.2286156
these VNs and makes most efficient 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 flexibil 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 significant 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 profit, 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 first 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 fluctuate
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
1063-6692 © 2014 IEEE. Personal use is p ermitted, but republication/red istribution requires IEEE perm ission.
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 first technical challenge is o n m odeling and quantifying
the energy cost of the complex physical network infrastruc-
ture of an ISP. Speci fically, 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 first 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, first, 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-fit strategy for the bandwidth resources. In
the ho st node mapping, we design a best-fit 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. Specifically, 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
N
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 first 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 profitfortheISPs.
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 first 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-
fied 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 five 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 classified 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 first 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 first week of Septem ber 2011
available at [14] for five 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
is
.
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 define 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 fi nd two one-to-one mappin gs:
and . Here,
is a one-to-one mapping from to a s ubset of .Th
is
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, satisfies
both virtual router quan tity and location requirements of
.
For each virtual host node
and the physical n
ode
that i t maps to, satisfies 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
to
asubstraterouter
,and denote the additional
power for mapp ing a virtual host node
to a substrate
剩余13页未读,继续阅读
资源评论
执念高
- 粉丝: 10
- 资源: 952
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功