VNF Placement in Hybrid NFV Environment:
Modeling and Genetic Algorithms
Jiuyue Cao, Yan Zhang*, Wei An, Xin Chen, Yanni Han, Jiyan Sun
State Key Laboratory of Information Security, Institute of Information Engineering,
Chinese Academy of Sciences, Beijing 100093, China
*Corresponding Author: zhangyan80@iie.ac.cn
Abstract—In this paper, we study the VNF placement
problem in hybrid NFV environment, which is important during
the transition from traditional networks to NFV networks. We
first propose a new concept of hybrid NFV environment, which is
more comprehensive and realistic than the former works. Then,
we give out a novel model of VNF placement optimization to
achieve lower bandwidth consumption and lower maximum link
utilization simultaneously, with consideration of VNF
combination. Next, to solve this problem, we propose four genetic
algorithms, which are combinations of the frameworks of two
existing algorithms (MOGA and NSGA-II) and our novel
modifications. Simulation results show that, in our 4 algorithms
Greedy-NSGA-II has the best performance. When compared
with other two non-genetic algorithms (BM and Random), the
average total bandwidth consumption of Greedy-NSGA-II is only
12.24% and 2.96% of theirs respectively, and the average
maximum link utilization of Greedy-NSGA-II is only 25.04% and
13.81% of theirs respectively.
Keywords—Network Function Virtualization; VNF Placement;
multi-objective optimization; genetic algorithm
I. INTRODUCTION
With the rise of cloud computing, big data, mobile Internet,
IOT (Internet of things) and other new technologies, new
network architectures that can support the above new
technologies will emerge as the times require, and network
function virtualization (NFV) [1] is one of them. The goal of
NFV is to achieve multiple network functions by using
virtualization technologies, and thus to realize the decoupling
of physical equipment and software. In NFV environment,
traditional network functions based on hardware are replaced
by virtual network functions (VNFs) based on software, and
VNF Forwarding Graphs (VNF-FGs) are composed of a series
of VNFs connected over logical links [2]. Multiple VNF-FGs
are mapped to the underlying resources (including network,
computing and storage resources) that can be shared by various
VNFs and logic links. This is called VNF placement, which
means mapping VNFs to underlying physical nodes and
mapping logic links between VNFs to underlying physical
links for a VNF-FG. Obviously, the efficiency of VNF
placement has great impact on the performance of NFV [2].
Intuitively, VNF placement is similar with VM (virtual
machine) placement, which has been studied a lot in the
research area of cloud computing. In fact, VNF placement has
some relationship with VM placement, since a VNF can be
instantiated by a VM. However, there are great differences
between the two concepts. First, a VNF can also be instantiated
by the service ability of an NF (network function, virtual or
real). This would leads to some new mapping relationships for
VNF placement. Second, VM placement is usually in the scope
of a single cloud, while VNF placement is in a much more
wide scope including multiple clouds as well as physical nodes
and links among them. So, research works about VM
placement could not be applied to VNF placement.
Furthermore, we can regard VNF placement as a special kind
of Virtual Network Embedding (VNE) [3]. However, the
differences between traditional VNE and VNF placement are
still obvious. First, traditional VNE only considers resource
constraints of physical nodes when performing node mapping.
However, VNF placement needs to consider resource
constraints of VMs as well as physical nodes that host the VMs.
Second, in traditional VNE problem, to achieve load balancing
in physical servers and reduce the risks of physical network
faults, virtual nodes in the same VN (virtual network) are
usually mapped according to the “one-to-one” principle. That
is, virtual nodes in the same VN will not be mapped to the
same physical node. In VNF placement problem, because of
the existence of MFTCs (multi-function Telecom Clouds) [4],
it is possible to map different VNFs in the same VNF-FG to
the same physical node (i.e., one MFTC). The above important
differences have made the VNF placement problem a hot and
valuable study topic in recent two years [4, 5, 6, 7, 8, 9].
However, existing works on VNF placement can still be
improved, which will be introduced in the next section.
In this paper, we study the problem of VNF placement in
hybrid NFV environment. The concept of hybrid NFV
environment was first proposed in [5], but its definition is
relatively simple and hard to be applied in real networks. To
make our works more realistic, we propose a more
comprehensive concept of hybrid NFV environment. Based on
this, we give a novel model of VNF placement optimization
with two objectives to achieve lower total bandwidth
consumption (TBC) and lower maximum link utilization
(MLU). Being different with former modeling works, in our
model we take VNF combination [4] into account to reduce the
TBC more effectively. Then, we present four improved genetic
algorithms to fundamentally address the unbalance when
jointly optimizing the objectives. Specifically, our four
improved genetic algorithms are based on the existing
frameworks of MOGA and NSGA-II. Extensive simulations