Coding-aware Virtual Network Mapping for
Surviving Single Link Failure
Zhiming Wang
Ъ
, Jiangxing Wu
Ъ
, Dongnian Cheng
Ъ
Ъ
National Digital Switching System Engineering & Technology Research Center
Henan Zhengzhou, 450002, China
wangzm05@gmail.com
Abstract—With network virtualization more and more
popular, how to protect the virtual networks (VNs) from a single
substrate link failure is increasingly important. Existing
protection schemes like dedicated backup and shared backup,
suffer from high resource cost and delayed recovery, respectively.
To offer instantaneous recovery with less redundant resource, in
this paper, we propose a coding-aware VN mapping framework
which applies network coding on the VN protection for the first
time. This algorithm framework includes two network coding
mechanisms with their corresponding link mapping algorithms.
The simple coding mechanism is resource-efficient and suitable
for high nodal degree network. The general coding mechanism
relaxes two restrictions in simple coding, and is so flexible to
make more VNs be mapped successfully. The simulation
experiments show that our proposed algorithms can significantly
improve the request acceptance ratio and revenue to cost ratio,
while reducing the backup bandwidth gain of VNs.
Keywords—virtual network mapping; network coding;
survivability; path splitting
I. INTRODUCTION
Network virtualization is believed as a promising way for
overcoming the ossification of the Internet [1] by enabling a
number of diverse VNs to coexist on a shared physical
Substrate Network (SN). So even a single failure in the SN can
impact a number of VNs and the services they offer. In fact, the
network failures are common in IP backbone where the single
link failures account for around 70% of all failures [2].
Therefore, how to map a VN to the substrate network while
guaranteeing the survivability, i.e. Survivable Virtual Network
Mapping (SVNM), has become an increasingly critical issue.
Currently, there are two main SVNM mechanisms:
protection and restoration [3]. The restoration mechanism [4, 5]
usually wastes more time on path selection after the failure
occurs, and some data loss is possible. The protection
mechanism can also be divided in two groups namely
dedicated and shared. In the dedicated case [6-8], the backup
resources are not shared for other backups. In the shared case
[9-11], the resources for the backup may be shared with other
backups. The dedicated protection provides instantaneous
recovery due to the simultaneous data flow on both primary
and protection paths, just like 1+1 mechanism in [6], but
suffers from high resource cost. On the contrary, in the shared
protection, the backup capacity is shared by multiple primary
paths. If a failure happens, the traffic in the failed path is
switched to the protection path, just like SBPP (Shared Backup
Path Protection) mechanism in [10]. So the shared protection is
resource-efficient, but it suffers from delayed recovery.
Therefore, it’s quite necessary to provide instantaneous
recovery with less redundant resource for VNs.
In recent years, some attention has been paid on protection
using network coding [12] in optical, overlay and wireless
network, which provides instantaneous and resource-efficient
recovery. However, all these mechanisms [13-15] don’t
involve any resource allocation like that in SVNM, and suffer
from two restrictions on the paths that those paths must be link-
disjoint and have equal capacity.
In this paper, we apply network coding on the SVNM
problem for the first time. We first present a coding-aware VN
mapping framework, and then design two network coding
mechanisms with their corresponding link mapping algorithms.
The first mechanism, i.e. simple coding, still uses link-disjoint
paths like those in 1+N mechanism [13]. It is more applicable
to high nodal degree network, and resource-efficient. The
second mechanism, i.e. general coding, relaxes the restrictions
in simple coding mechanism, and the used paths are not full
link-disjoint and allowed to have different capacity. This
general mechanism is so flexible to make more VNs be
mapped successfully. Our framework provides instantaneous
recovery, and outperforms other algorithms in terms of request
acceptance ratio and backup bandwidth gain.
The main contributions of this paper are the following:
z We design link mapping algorithms to find the optimal
paths for our coding mechanisms, thereby providing
instantaneous recovery with the least redundant
resource. To the best of our knowledge, this work is the
first to apply network coding on the SVNM problem.
z We design a new general coding mechanism to relax the
restrictions in existing mechanisms, and thus the general
mechanism is so flexible and applicable for SVNM
problem to make more VNs be mapped successfully.
II. R
ELATED WORK
A. Survival Virtual Network Mapping
In restoration case, Guo et al. [4] propose an Internal Node
Migration Protection (I-NMP) approach to survive a link
failure. Houidi et al. [5] propose an adaptive VN embedding
*This research was sponsored by the National Natural
ation of China (61372121, 61309020), the National
Basic Research
Program (973 program) of China
(2012CB315901, 2013CB329104)
Tech Research and Development Program (863 Program) of
China (2011AA01A103, 2011AA01A101, 2013AA013505).
IEEE ICC 2014 - Next-Generation Networking Symposium
978-1-4799-2003-7/14/$31.00 ©2014 IEEE 3025