Availability-Aware Virtual Network Embedding for
Multi-Tier Applications in Cloud Networks
Meng Shen
∗†
,KeXu
‡
, Fuliang Li
§
, Fan Li
∗
, Liehuang Zhu
∗¶
, and Lei Guan
∗
Beijing Engineering Research Center of High Volume Language Information Processing and Cloud Computing Applications,
School of Computer Science, Beijing Institute of Technology, P. R. China
†
Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, P. R. China
‡
Department of Computer Science, Tsinghua University, P. R. China
§
College of Information Science and Engineering, Northeastern University, P. R. China
¶
DNSLAB, China Internet Network Information Center, Beijing 100190, P. R. China
School of Management & Economics, Beijing Institute of Technology, P. R. China
{shenmeng, fli, liehuangz, guanlei}@bit.edu.cn; xuke@mail.tsinghua.edu.cn; lifuliang@ise.neu.edu.cn
Abstract—There is a growing trend for service providers (SPs)
to migrate their multi-tier applications from local clusters to pub-
lic cloud networks. In the cloud environment, it is a great concern
of SPs to improve the availability of their virtual networks, in
addition to guarantees of their virtual resource requirements,
such as virtual machines (VMs) and bandwidth. However, meeting
these requirements results in an inefficient utilization of physical
resources, which goes against the operational goal of cloud
providers.
To address this challenge, in this paper, we propose an
availability-aware virtual network embedding framework that
simultaneously improves the availability of virtual networks and
the resource efficiency. We first propose a new metric to quantify
the availability cost of a multi-tier virtual network, and then
formulate the embedding problem as a joint optimization of
the aggregated bandwidth and availability costs. Due to the NP-
hardness of the embedding problem, we devise a heuristic algo-
rithm that can solve the problem in polynomial time. Extensive
simulation results show that the proposed algorithm enables cloud
providers to achieve various trade-offs between resource efficiency
and availability, and to gain more revenue (e.g., 16.1% under a
datacenter load of 80%) than the availability-agonistic algorithm.
Keywords—virtual network embedding; multi-tier application;
availability-aware;
I. INTRODUCTION
There is a growing trend for service providers to migrate
their multi-tier applications from local clusters to public cloud
networks, such as Amazon AWS [1]. In a typical cloud
environment, each service provider (SP) is allocated with
an isolated virtual network (VN) to deliver its services to
end users, while the cloud provider (CP) owns the physical
infrastructure (i.e., datacenter) and offers virtual resources to
multiple SPs. The virtual network embedding deals with the
mapping of virtual networks onto the substrate network.
In order to achieve better Quality of Service (QoS) for
applications, SPs usually have specific requirements on their
VNs with certain amounts of resource guarantees (e.g., VMs
and bandwidth) [3]. However, failures of the substrate network
elements (e.g., switches and links) have severe impacts on the
availability of their services. According to the study in [2],
(a) VN embedding with higher
availability via VM spreading
(b) VN embedding with lower bandwidth
cost via VM colocation
Fig. 1. A topology with four racks to illustrate conflict goals of SPs and CP,
where the black boxes denote the VM placement for the virtual network.
the overall cost associated with unplanned datacenter outages
is $627,418 per incident. Although existing studies have pro-
posed fault-tolerant approaches to improve the reliability of
datacenter networks, such as designing new topologies with
network redundancy, the availability of virtual networks under
datacenter failures remains a great concern [13]. For instance,
network redundancy is only 40% effective in reducing the
median impact of failures [7]. Hence, there has long been a
requirement for SPs to improve the availability of their virtual
networks, in addition to guarantees for virtual resources.
Since multiple VNs run concurrently over the same infras-
tructure, it is crucial to devise a VN embedding mechanism
that achieves efficient resource utilization while satisfying
requirements from SPs. However, it is challenging to achieve
efficiency and availability simultaneously, due to conflicts
between these two goals. We leverage the simple topology
in Figure 1 for illustration, which consists of four racks, two
aggregate switches and a core switch. Assume there are 4 VMs
in the virtual network and each requires a certain amount
of bandwidth guarantee. Since Top-of-Rack (ToR) switches
account for the majority (roughly over 60%) of the downtime
in datacenters [7] and it is unlikely to have largely correlated
failures, we refer to each rack as an individual fault domain.
An intuitive way to improve the availability of an em-
bedded virtual network is to spread the required VMs across
multiple fault domains, as shown in Figure 1(a). In such a
case, the impact of any single failure on the virtual network is
minimized, at the price of increasing bandwidth consumption
in the core of the network. In contrast, as shown in Figure
2015 IEEE 17th International Conference on High Performance Computing and Communications (HPCC), 2015 IEEE 7th
International Symposium on Cyberspace Safety and Security (CSS), and 2015 IEEE 12th International Conf on Embedded Software
and Systems (ICESS)
978-1-4799-8937-9/15 $31.00 © 2015 IEEE
DOI 10.1109/HPCC-CSS-ICESS.2015.32
1