IEEE COMMUNICATIONS LETTERS, VOL. 22, NO. 1, JANUARY 2018 73
A Generalized VNF Sharing Approach for Service Scheduling
Bo Yi , Xingwei Wang, and Min Huang
Abstract—Network function virtualization enables a flexible
service provision by introducing the concept of virtual network
function (VNF). Despite the importance of VNF scheduling, it is
largely unexplored. In this letter, we propose a new model for
VNF scheduling based on the min-plus algebra theory. The
main idea of this model is to share the deployed VNF instances
among different services, thus to improve the resource utilization
and reduce the resource fragmentation generated by deploying
many VNF instances. In addition, a weight-based VNF sharing
scheduling approach is proposed in this model to achieve a fair
scheduling among the arriving service requests. The experimental
results show that the proposed model and approach are effective
and efficient.
Index Terms— Network function virtualization, virtual net-
work function, service scheduling, min-plus algebra.
I. INTRODUCTION
T
RADITIONALLY, network services are implemented
by using dedicated hardware based middle-boxes [1]
which suffer from great inflexibility and high cost. Network
Function Virtualization (NFV) decouples network functions
from hardware and implement them as software which is
referred to as Virtual Network Function (VNF). The chaining
of several sequential VNFs is referred to as Service Function
Chain (SFC) [2]. In this way, NFV enables a flexible SFC
construction and reduces cost. Besides, Software-Defined Net-
working (SDN) [3] has emerged as an efficient paradigm for
guiding SFC provision with a centralized controller.
Nevertheless, to obtain a high performance SFC, the
VNF scheduling problem should be carefully addressed,
that is, determining the execution time slot for the traffic of
each SFC traversing the VNF that placed at the corresponding
server or Virtual Machine (VM) [4]. Existing works are usually
implemented under the assumption that VNFs are indepen-
dently deployed for each SFC, which means that one deployed
VNF instance only serves the traffic of one SFC. Such design
suffers from two issues: i) low resource utilization, because
Manuscript received August 4, 2017; revised September 19, 2017; accepted
October 6, 2017. Date of publication October 11, 2017; date of current version
January 8, 2018. This work is supported by the National Natural Science Foun-
dation of China under Grant No. 61572123, the National Science Foundation
for Distinguished Young Scholars of China under Grant No. 71325002, and
MoE and China Mobile Joint Research Fund under No. MCM20160201. The
associate editor coordinating the review of this paper and approving it for
publication was K. Navaie. (Corresponding author: Xingwei Wang.)
B. Yi is with the College of Computer Science and Engineering,
Northeastern University, Shenyang 110169, China (e-mail: yibobooscar@
gmail.com).
X. Wang is with the College of Software, Northeastern University,
Shenyang 110169, China (e-mail: wangxw@mail.neu.edu.cn).
M. Huang is with the College of Information Science and Engineer-
ing, Northeastern University, Shenyang 110819, China (e-mail: mhuang@
mail.neu.edu.cn).
Digital Object Identifier 10.1109/LCOMM.2017.2761874
Fig. 1. Sequential VNFs can be combined into one single system based
on the convolution operation of minimum-plus algebra, where through traffic
belongs to this SFC while cross traffic belongs to other SFCs.
even if some deployed VNFs have redundant capacity for
data processing, they are not shared by traffic of other SFCs;
ii) more resource fragmentation, because the more VNF
instances are deployed, the more resource fragments are
generated.
Since VNF scheduling is our focus, we assume that the
VNFs are already placed in the network, for which extensive
work are done, e.g., [5] and [6]. In this letter, we propose a
new SFC model based on min-plus algebra theory [7] as shown
in Fig. 1, and a VNF scheduling approach named Generalized
VNF Sharing (GVS). GVS achieves a fair VNF scheduling
and improves resource utilization by re-allocating the idle
resources.
II. S
YSTEM MODEL
In this model, we consider a virtual network consisting of N
VMs and L virtual links. Each virtual link is used to connect
two VMs placed on physical machines. Besides, each VM may
have already been equipped with many different VNFs. Both
the VNF placement and virtual link mapping are outside the
scope of this letter, and we focus on scheduling flows through
these VNFs with service requirements satisfied.
A. Virtual Network Function
There are many kinds of VNFs running in the whole net-
work and we denote them by F
V
={f
V
i
|i ∈[1, |F
V
|]},where
f
V
i
indicates the i-th kind of VNF. Given any f
V
i
, one or more
instances of it can be deployed, and the j-th instance of f
V
i
is denoted by f
V
i, j
.Forany f
V
i, j
, the cumulative amount of bits
arriving at it in the time interval [0,t] is denoted by A
V
i, j
(t)
which is non-negative and non-decreasing. In order to formu-
late the arrived amount of traffic more precisely, the notation
A
V
i, j
(τ, t) is used to denote it in the time interval (τ,t], where
t >τ ≥ 0. Combined with the definition of A
V
i, j
(t), A
V
i, j
(τ, t)
is expanded as follows:
A
V
i, j
(τ, t) = A
V
i, j
(t) − A
V
i, j
(τ ), (1)
where A
V
i, j
(t) = A
V
i, j
(t, t) = 0, ∀t > 0.
1558-2558 © 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.