# End-to-End Delay Guaranteed SFC Deployment:
A Multi-level Mapping Approach

Fatemeh Yaghoubpour<EMAIL_ADDRESS>Bahador Bakhshi
<EMAIL_ADDRESS>Fateme Seifi<EMAIL_ADDRESS>Amirkabir University
of Technology, Hafez Avenue, Tehran, Iran

###### Abstract

Network Function Virtualization (NFV) enables service providers to maximize
the business profit via resource-efficient QoS provisioning for customer
requested Service Function Chains (SFCs). In recent applications, end-to-end
delay is one of the crucial QoS requirement needs to be guaranteed in SFC
deployment. While it is considered in the literature, accurate and
comprehensive modeling of the delay in the problem of maximizing the service
provider’s profit has not yet been addressed. In this paper, at first, the
problem is formulated as a mixed integer convex programming model. Then, by
decomposing the model, a two-level mapping algorithm is developed, that at the
first level, maps the functions of the SFCs to virtual network function
instances; and in the second level, deploys the instances in the physical
network. Simulation results show that the proposed approach achieves a near
optimal solution in comparison the performance bound obtained by the
optimization model, and also superiors the existing solutions.

###### keywords:

Network Function Virtualization (NFV) , Service Function Chain (SFC) , end-to-
end delay , queuing theory , decomposition.

††journal: Computer Communications

##  1 Introduction

Recently, due to the advent of the Internet of Things (IoT) and 5G, Network
Function Virtualization (NFV) has received much attention to address
heterogeneous requirements of services. Since NFV decouples Network Functions
(NFs) from the physical substrate network, it creates this opportunity for
Telecommunication Service Providers (TSPs) to effectively upgrade their
network to guarantee a wide range of QoS metrics, such as high data rate and
reliability as well as low end-to-end delay and packet loss. That obviously
reduces the Capital Expenses (CAPEX) as well as the Operational Expenses
(OPEX). Moreover, this decoupling makes a drastic increase in agility and
time-to-market of network services. To exploit its potential, extensive
researches have been done on NFV-based networks during the last years [1, 2,
3].

Resource allocation to customer services is the main challenge in NFV. In this
context, the services are described as Service Function Chains (SFCs)
containing a sequence of Virtual Network Functions (VNFs) connected with
virtual links. To serve the customers, the TSP needs to deploy the SFCs by
allocating the required resources, like processing, storage, and bandwidth.
Service providers attempt to allocate the shared substrate network resources
to SFCs efficiently to achieve objectives such as maximum gain, acceptance
rate, reliability, and energy efficiency. This problem is named SFC mapping
[4].

Quality of Service (QoS) provisioning is the crucial requirement in SFC
mapping, and end-to-end delay is one of its essential metrics which is
considered in recent mission-critical and multimedia applications. End-to-end
delay is a combination of heterogeneous delay factors, including propagation,
transmission, processing, and queuing delays. Accordingly, not only modeling
the different factors but also provisioning the requirement in such a complex
network is a serious challenge in SFC mapping.

In recent years, the SFC mapping problem is concerned by network researchers,
and several papers have investigated it from different aspects [1, 3, 5].
However, even though delay is one of the most significant requirements of
SFCs, it has not been addressed significantly. In [6, 7], and [8] the end-to-
end delay is calculated by accumulating the propagation delay and other
factors such as transmission, and queuing delays are ignored. In [9], only
processing delay is concerned and the other factors are neglected. Although
authors in [10] consider propagation and processing delays, they do not pay
attention to queuing and transmission delay. In [11], the authors calculate
processing and transmission delays; however, they ignore the queuing and
propagation factors. In [12], processing, transmission, and queuing delays are
considered in a cloud environment, and in [13], queue length is considered as
a queuing delay metric.

The propagation, transmission, and processing delays can be formulated as
linear functions, while the queuing delay depends on the traffic distribution,
and in the simplest form, is a fractional function that makes the model non-
linear. Hence, for the sake of simplicity, most researchers tend to eliminate
it. However, queuing delay is one of the important factors in end-to-end delay
and mostly is not negligible in comparison to the other factors. Therefore,
considering queuing delay is inevitable. In this paper, for this purpose, we
define a convex model that takes into account propagation, transmission,
processing, and queuing delays as the constraints with the aim of maximizing
the business profit of the TSP. To the best of our knowledge, the problem of
gain maximization subject to assuring the end-to-end delay considering all the
affecting factors, which is named Delay Constrained SFC Mapping (DCSM), has
not been addressed in the literature yet. Hereupon, for filling this research
gap, we model the problem as a mixed-integer convex problem and develop an
efficient algorithm to solve it. This paper extends our previous work [14].

In the DCSM problem, there is a set of input SFCs that the service provider
can whether or not accept them. In addition to processing and bandwidth
resources, each SFC has its end-to-end bandwidth requirement. The objective is
gain maximization while satisfying the end-to-end delay in terms of
propagation and queuing delays. Briefly, our contributions comparing to the
previous researches are:

  * 1.

For the first time, we formulate the DCSM problem as a mixed integer convex
model.

  * 2.

We develop a multi-level mapping algorithm by decomposing the optimization
model.

  * 3.

We evaluate the proposed solution in different setting against to theoretical
performance bound and existing solutions.

The remainder of this paper is organized as follows. In Section 2, we review
related work, categorize them, and identify the research gap. In Section 3,
first, the system model is explained; afterward, DCSM is formulated as a mixed
integer convex optimization problem. The optimization model is decomposed and
a multi-level mapping algorithm is presented in Section 4 to solve the problem
efficiently. Section 5 evaluates the simulation results. Finally, we will make
a conclusion and introduce some new ideas as future work in Section 6.

##  2 Related Work

In this section, related work to the DCSM problem are reviewed, the
differences with this paper are investigated, and finally, the research gap is
identified.

In [10], the authors investigated resource allocation scheme for balancing the
load among NF instances, and maximizing the total network utilization. They
considered CPU, disk, and memory of physical nodes and bandwidth capacity of
physical links. For end-to-end delay, only propagation and processing delays
were assumed; and the authors proposed a heuristic algorithm. This work
ignores the queuing delays and also does not consider the license costs of VNF
instance and the cost of physical resources. In the SFC mapping problem in
[15], physical nodes and links capacity limitations are considered. However,
VNF instances are not shared among chains and no end-to-end delay is
guaranteed. Moreover, the authors ignored the licensing and physical resources
activating costs.

In [6], an ILP111Integer Linear Programming model is proposed to address the
chain deployment problem considering the delay of the chain and the maximum
load among edge devices. Only CPU is considered as the physical node resource
while disk and memory are ignored. Moreover, only the propagation delay is
considered. In [11], a formulation of the SFC scheduling (SFCS) problem is
presented that exploits interactions between NFs mapping onto VNFs, service
scheduling, and traffic routing. Physical nodes and virtual instances are
shared among multiple SFCs. The authors assume that all SFCs are accepted
without considering any cost for provisioning. The authors in [12], proposed
an ILP model that considers CPU, disk, and bandwidth constraints. The
processing, transmission, and queuing delays are addressed in a cloud
environment. However, VNF instances are not shared among chains and it is
assumed that all requested chains are accepted, i.e., there is no CAC (Call
Admission Control) mechanism. This paper proposes an affinity based heuristic
algorithm to solve the problem.

The work presented in [7], which is the improved version of [12], assigns
fixed delays to physical nodes and physical links. The work aims at cost
minimization and considers physical nodes and links costs; however, it
neglects the cost of activating VNF instances as well as the transmission and
queuing delays. This paper does not have any CAC mechanism and assumes that
all SFCs have to be accepted. A heuristic algorithm named Annealing Based
Simulation Approach (ABSA) is proposed, wherein the affinity-based algorithm
proposed in [12] is used. The SFC mapping problem to minimize the time-average
cost is formulated as a MILP model in [13]. This paper considers CPU and
bandwidth as the substrate network resource. It aims at minimizing the lengths
of queues in order to decrease the end-to-end delay. Both physical nodes and
virtual instances are shared among multiple SFCs.

The objective of the problem proposed in [9] is delay minimization, but the
transmission delay is the only considered metric. It only considers physical
links bandwidth as the constraint. It shares the physical nodes among multiple
chains. The CAC problem and cost are also considered. In [8], the objective is
solving the SFC mapping problem such that satisfies the reliability and end-
to-end delay requirements while minimizing the communication bandwidth usage.
It just considers CPU and bandwidth resources, and does not share instances
among multiple chains. The only considered delay metric is the propagation
delay. In [16], a system model based on deep reinforcement learning (DRL) is
defined to minimize the overall network delay while ensuring fairness among
different flows. It calculates queuing delays and assumes it is the only
parameter affecting the end-to-end delay. It does not pay attention neither to
CAC nor VNF instance sharing.

In paper [17], the problem of VNF placement is studied with the objective of
minimizing the overall delay. To do so, it assigns a list of shortest path to
each chain using Dijkstra’s algorithm [18] in a weighted network. It considers
queuing and propagation delays. It considers CPU, memory, and bandwidth as
physical resource restrictions. It shares physical nodes and virtual instances
among different SFCs. In this paper, no CAC mechanism is considered. Paper
[19] formulates an energy cost optimization problem considering resource
capacities restriction and satisfying a delay threshold as constraints.
Queuing delay is the only considered delay metric. This problem assumes that
all SFCs are accepted and there is no CAC problem. Energy consumption is the
cost metric.

Table 1 summarizes the discussed works related to the DCSM problem. The
columns of the table identify the categorizing criteria and the last row is
this paper. Comparing the previous work, we can conclude that the problem of
gain maximization while modeling the end-to-end delay regarding queuing,
processing, transmission, and propagation delays, and sharing the instances
among multiple SFCs is a research gap that we will go through it in this
paper.

Table 1: Summary of Related Work

Paper | Delay | Capacity Constraint | Sharing |  CAC |  Optimization Model |  Heuristic Algorithm
---|---|---|---|---|---|---
Propagation |  Transmission |  Processing |  Queuing |  CPU |  Storage |  Memory |  Networking |  Bandwidth |  Physical Nodes |  VNF Instance
[10] | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$
[15] |  |  |  |  | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$ |  | $\surd$ | $\surd$ | $\surd$
[6] | $\surd$ |  |  |  | $\surd$ |  |  |  | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$
[11] |  | $\surd$ | $\surd$ |  | $\surd$ |  |  |  | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$
[12] |  | $\surd$ | $\surd$ | $\surd$ | $\surd$ |  |  | $\surd$ | $\surd$ | $\surd$ |  |  | $\surd$ | $\surd$
[7] | $\surd$ |  | $\surd$ |  | $\surd$ | $\surd$ |  | $\surd$ | $\surd$ | $\surd$ |  |  | $\surd$ | $\surd$
[13] |  |  |  | $\surd$ | $\surd$ | $\surd$ |  |  | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$
[9] |  |  | $\surd$ |  |  |  |  |  | $\surd$ | $\surd$ |  | $\surd$ |  |
[8] |  |  |  |  | $\surd$ |  |  |  | $\surd$ | $\surd$ |  | $\surd$ | $\surd$ | $\surd$
[16] |  |  |  | $\surd$ | $\surd$ |  |  |  | $\surd$ | $\surd$ |  |  | $\surd$ | $\surd$
[17] | $\surd$ |  |  | $\surd$ | $\surd$ |  | $\surd$ |  | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$
[19] |  |  |  | $\surd$ | $\surd$ |  |  |  | $\surd$ | $\surd$ | $\surd$ |  | $\surd$ | $\surd$
[14] | $\surd$ |  | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ |
This paper | $\surd$ |  | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$

##  3 System Model AND Problem Statement

In this section, we first discuss the assumptions and present the system
model, then we state the problem with an illustrative example, and finally
formulate it.

###  3.1 Assumptions and System Model

In this paper, $G_{p}=\left(N_{p},E_{p}\right)$ demonstrates the substrate
network wherein $N_{p}$ and $E_{p}$ respectively represent the physical nodes
and links. Each $n\in N_{p}$ indicates a physical server wherein
$\theta_{n}^{CPU}$,$\theta_{n}^{mem}$, and $\theta_{n}^{strg}$ denote its
total available CPU, memory, and storage, respectively. Additionally, link
$\left(n,m\right)\in E_{p}$ shows a physical connection between two physical
nodes $n,m\in N_{p}$. This link has a limited data transfer capacity
$\theta_{\left(n,m\right)}$ and propagation delay $d_{\left(n,m\right)}$.

Set $T$ contains all available VNF types that can be requested by users. In
case of requesting a type in a chain, the service provider activates an
instance of the VNF type by running the image of the VNF on a virtual machine
and installing the required licenses. $I_{t}$ represents all available
instances of type $t\in T$ that can be activated on-demand. The instances of
each type have three specific characteristics. The first one is the required
physical resources (CPU, storage, and memory) that need to be allocated for
activating each instance of the type. The second characteristic is the traffic
processing capacity of the instances of that type. These two characteristics
are determined by the VNFs vendors wherein the CPU, memory, and storage
requirements of each instance of type $t\in T$ are denoted by ${CPU}_{t}$,
${mem}_{t}$, and ${strg}_{t}$ respectively, and the traffic processing
capacity of the type is indicated by $\mu_{t}$. At last, the third
characteristic of type $t\in T$ is the license fee, i.e., the amount of money
that the service provider should pay to the VNF vendor to activate a license
of that type; it is denoted by $C_{t}$. It worth mentioning that we assume
that each instance has the sufficient capacity to serve at least one chain,
and therefore a VNF of a chain is never split among multiple instances.
Similarly, we assume that each instance also has to be mapped exactly one one
individual physical server, and it cannot be split among multiple servers.

All SFCs requested by users are gathered in set $G_{v}$. Each requested SFC
$r\in G_{v}$, is defined as a sequence of VNFs which are connected by virtual
links. Set $N_{v}^{r}$ contains all VNFs of SFC $r$ and $E_{v}^{r}$ contains
all directed virtual links connecting the sequence of the VNFs of the SFC.
Parameter $w_{\left(u,v\right)}^{r}$ denotes the required bandwidth for
virtual link $\left(u,v\right)\in E_{v}^{r}$ connecting two consecutive VNFs
$u,v\in N_{v}^{r}$ of SFC $r$. As mentioned, each VNF $u\in N_{v}^{r}$ has a
specific type which is denoted by $t_{u}^{r}\in T$. Table 2 summarizes the
notations used throughout this paper.

Table 2: Notations and Definitions

Notation | Definition
---|---
$G_{p}$ | Infrastructure network graph
$N_{p}$ | The set of substrate nodes
$E_{p}$ | The set of substrate links
${\theta_{\left({n,m}\right)}}$ |  The available capacity of physical link $\left({n,m}\right)\in{E_{p}}$
$\theta_{n}^{CPU}$ |  The available CPU cores of physical node $n\in{N_{p}}$
$\theta_{n}^{mem}$ |  The available memory of physical node $n\in{N_{p}}$
$\theta_{n}^{strg}$ |  The available storage of physical node $n\in{N_{p}}$
${\mu_{n}}$ |  Processing rate of physical node $n\in{N_{p}}$
$d_{\left({n,m}\right)}$ |  The propagation delay of link $\left({n,m}\right)\in E_{p}$
${\rho}$ | Bandwidth fee of physical link
${\sigma}_{n}$ |  The cost paid for activating physical node $n\in N_{p}$
$G_{v}$ | Set of all requested service function chains
$N_{v}$ | Set of all VNFs of all SFCs
$E_{v}$ | Set of all virtual links of all SFCs
$N^{v}_{r}$ |  Set of all VNFs of SFC $r\in{G_{v}}$
$E^{v}_{r}$ |  Set of all virtual links of SFC $r\in{G_{v}}$
$d_{r}^{th}$ |  The maximum end-to-end delay threshold of SFC $r\in G_{v}$
$f_{r}$ |  The input traffic of each VNF $u\in N^{r}_{v}$
$rev_{r}$ |  The revenue of SFC $r\in G_{v}$
$w_{\left({k,l}\right)}^{r}$ |  The required bandwidth of link $\left({k,l}\right)\in E^{r}_{v}$
$T$ | Set of all available VNF types
$I_{t}$ |  Set of available instances of types $t\in T$
$\mu_{t}$ |  Traffic capacity of type $t\in T$
$C_{t}$ |  The cost that the provider pays for the activation of each instance of type $t\in T$
$CPU_{t}$ |  The required CPU of each instance of type $t\in T$
$mem_{t}$ |  The required memory of each instance of $t\in T$
$strg_{t}$ |  The required storage of each instance of $t\in T$
$t_{u}^{r}$ |  The type of VNF $u\in N_{v}^{r}$ of chain $r\in G_{v}$

In this paper, similar to [12, 13, 17, 16, 19, 21, 22, 23], we consider the
average end-to-end delay between the source and the destination of each
service chain as the QoS metric. Threshold $d_{r}^{th}$ indicates the utmost
average tolerable end-to-end delay of SFC $r$.

The following assumptions are made about the business model of the service
provider. The provider’s revenue is made by accepting SFCs which is $R_{r}$
for SFC $r$. On the other hand, it should pay license cost for activating the
VNF instances as well as the cost of allocating bandwidth on physical links as
it is assumed that the physical links are leased from another transmission
carrier network. Here, we assume that to minimize the cost of service
provider, the activated VNF instances in the network can be shared among
multiple chains subject to the traffic processing capacity of the instance.

In this paper, we consider propagation, processing, and queuing delays as the
most significant parameters imposing the end-to-end delay. In each physical
node, the processing and queuing delays are induced by the hypervisor of the
machine and also the VNF instances running on the hypervisor. More precisely,
each packet at each node:

  1. 1.

enters the physical node’s hypervisor queue,

  2. 2.

is processed by the hypervisor and conducted to the virtual machine running
the corresponding VNF,

  3. 3.

enters the queue of the virtual machine, and

  4. 4.

takes the required service from the VNF instance.

We model the delay induced by these steps as a queuing network depicted in
figure 1, where the left-hand server is the hypervisor and the right-hand
servers are the VNF instances. The queues in this network are assumed as an
$M/M/1$ system [20], wherein the arrival process is Poisson, the service time
is distributed exponentially, and there is just a single server processing the
incoming traffic. Therefore, the average delay in each queue is

$\bar{d}=\frac{1}{{\mu-\lambda}}$ (1)

where, $\lambda$ and $\mu$ are respectively, the arrival rate, the departure
rate of the packets.

Figure 1: Queuing network at each physical node.

For physical node $n\in N_{p}$, the arrival rate into the hypervisor queue,
shown by $\lambda_{n}$, equals to the summation of all incoming flows to the
node, and the service rate of the hypervisor, shown by $\mu_{n}$, is a given
parameter. Therefore, the average delay of the hypervisor is:

${\bar{d}_{n}}=\frac{1}{{{\mu_{n}}-{\lambda_{n}}}}.$ (2)

By taking logarithm from (2), we have

$\log\left({{{\bar{d}}_{n}}}\right)+\log\left({{\mu_{n}}-{\lambda_{n}}}\right)=0,$
(3)

which is more convenient to hand it in the optimization formulations.

In a similar way, the average delay in each instance $i$ of type $t$, denoted
by $\bar{d}_{i,t}$, is

${\bar{d}_{i,t}}=\frac{1}{{{\mu_{t}}-{\lambda_{i,t}}}},$ (4)

where $\lambda_{i,t}$ and $\mu_{t}$ are the total flow rate and the processing
rate of of the instance respectively. And, again by taking logarithm from (4),
we have

$\log\left({{{\bar{d}}_{i,t}}}\right)+\log\left({{\mu_{t}}-{\lambda_{i,t}}}\right)=0.$
(5)

###  3.2 Problem Statement

In this paper, we investigate the DCSM problem, where, a service provider, who
operates the infrastructure network $G_{p}$, aims to deploy the set $G_{v}$ of
SFCs in order to maximize its profit while satisfying the SFCs requirements.
The profit is a function of the revenue of accepting the demands as well as
the cost paid for VNFs license fee. The SFCs requirements include not only
processing and bandwidth but also the end-to-end delay which is a function of
processing, queuing and propagation delays. In the following, we clarify the
problem by an illustrative example shown in Figure 2.

Figure 2: The inputs of the DCSM problem. The left side is the set of SFCs
with a specified type per VNF. The right side is the substrate network.

In this figure, the left side represents 5 input SFCs which are composed of
different types of VNFs, indicated by the numbers inside the VNFs; and the
right side represents the substrate network topology. Table 3 and Table 4
respectively show the settings of the SFCs and VNF types in this example.

The optimal solution of this instance of the DCSM problem, which is obtained
by solving the optimization model proposed in the next section, is depicted in
Figure 3 and Table 5. Figure 3 shows which SFCs are accepted and how they are
mapped to the substrate network and Table 5 illustrates the end-to-end delay
that the accepted SFCs tolerate. As it shown, to maximize the objective
function and to meet the SFC requirements, two SFCs are rejected.

Table 3: The settings of the SFCs in Figure 2

$r$ | $|N^{v}_{r}|$ | $t^{r}_{u}$ | $f_{r}$ | $rev_{r}$ | $d_{r}^{th}$
---|---|---|---|---|---
0 | 3 | 4,1,3 | 20 | 1050 | 0.3
1 | 3 | 1,2,3 | 30 | 1050 | 0.3
2 | 2 | 2,4 | 30 | 700 | 0.2
3 | 2 | 2,1 | 40 | 700 | 0.2
4 | 4 | 3,4,1,2 | 40 | 1400 | 0.4

Table 4: The settings of the VNF types in Figure 2

$t$ | $C_{t}$ | $CPU_{t}$ | $mem_{t}$ | $strg_{t}$ | $\mu_{t}$
---|---|---|---|---|---
1 | 100 | 100 | 150 | 300 | 100
2 | 150 | 100 | 150 | 300 | 100
3 | 120 | 100 | 150 | 300 | 100
4 | 140 | 100 | 150 | 300 | 100

Figure 3: The accepted SFCs and their mappings. Table 5: The components
(hypervisor, VNF instances, and propagation) of the end-to-end delay of the
accepted demands in the illustrated example of Figure 2

$r$ | $\sum{\bar{d}_{n}}$ | $\sum{\bar{d}_{i,t}}$ | $\sum{d_{(n,m)}}$
---|---|---|---
0 | 0.004547 | 0.053332 | 0.000001
2 | 0.004597 | 0.058333 | 0.000002
3 | 0.006578 | 0.057499 | 0.000002

###  3.3 Problem Formulation

In this section, the DCSM problem is formulated. At the begging, we introduce
the decision variables of the model, shown in table 6, and inter-dependencies
between them; then we discuss the constrains and objective function of the
model.

Table 6: Decision Variables and Corresponding Definitions

Variable |  Definition
---|---
$A_{r}\in{\\{{0,1}\\}}$ |  $A_{r}=1$ if and only if SFC $r\in G_{v}$ is accepted.
$s_{i,t}^{u,r}\in{\\{{0,1}\\}}$ |  $s_{i,t}^{u,r}=1$ if and only if VNF $u\in N_{r}^{v}$ from SFC $r\in G_{v}$ is mapped to the instance $i\in I_{t}$ of type $t\in T$.
$p_{n}^{i,t}\in{\\{{0,1}\\}}$ |  $p_{n}^{i,t}=1$ if and only if instance $i\in I_{t}$ of type $t\in T$ is mapped to the physical node $n\in N_{p}$.
$z_{n,i}^{u,r}\in{\\{{0,1}\\}}$ |  $z_{n,i}^{u,r}=1$ if and only if VNF $u\in N_{v}^{r}$, is mapped to instance $i\in I_{t_{u}}$ running on physical node $n\in N_{p}$.
$a_{n}^{r}\in{\\{{0,1}\\}}$ |  $a_{n}^{r}=1$ if and only if SFC $r\in G_{v}$ passes through physical node $n\in N_{p}$.
${\delta_{\left(n,m\right)}^{r,{\left(u,v\right)}}}\in R^{+}$ |  ${\delta_{\left(n,m\right)}^{r,{\left(u,v\right)}}}$ indicates the percentage of the traffic of the virtual link $\left(u,v\right)\in E_{v}^{r}$ that is mapped to physical link ${\left(n,m\right)}\in E_{p}$.
${y_{n}^{i,t}}\in R^{+}$ |  $y_{n}^{i,t}$ denotes the traffic of the hypervisor queue at node $n\in N_{p}$ which takes service from instance $i\in I_{t}$ of type $t\in T$.
${\bar{d_{n}}}\in R^{+}$ |  $\bar{d_{n}}$ denotes the average queuing and processing delays of the hypervisor in node $n\in N_{p}$.
${\bar{d_{i,t}}}\in R^{+}$ |  $\bar{d_{i,t}}$ denotes the average queuing and processing delays of instance $i\in I_{t}$ of type $t\in T$.
${d_{r}^{hyp}}\in R^{+}$ |  $d_{r}^{hyp}$ indicates the imposed delay to SFC $r\in G_{v}$ by all the hypervisors the SFC passes through them.
${d_{r}^{ins}}\in R^{+}$ |  $d_{r}^{ins}$ indicates the imposed delay to SFC $r\in G_{v}$ by all the instances servicing it.
${d_{r}^{link}}\in R^{+}$ |  $d_{r}^{link}$ indicates the imposed delay to SFC $r\in G_{v}$ by all the links forwarding its traffic.
${\lambda_{i,t}}\in R^{+}$ |  $\lambda_{i,t}$ denotes the traffic entering instance $i\in I_{t}$ of type $t\in T$.
${l_{n}^{r}}\in R^{+}$ |  $l_{n}^{r}$ indicates the delay that SFC $r\in G_{v}$ tolerates for passing through physical node $n\in N_{p}$.
${bw_{\left(n,m\right)}}\in R^{+}$ |  $bw_{\left(n,m\right)}$ indicates the allocated bandwidth of physical link $\left(n,m\right)\in E_{p}$ to the accepted chains crossing the link.
${q_{i,t}^{u,r}}\in R^{+}$ |  ${q_{i,t}^{u,r}}$ denotes the delay that SFC $r\in G_{v}$ tolerates since its VNF $u\in N_{v}^{r}$ is mapped to instance $i\in I_{t}$ of type $t\in T$.
${cost}\in R^{+}$ |  $cost$ denotes the total money payed by the service provider for bandwidth allocation and instance activation.
${rev}\in R^{+}$ |  $rev$ is the amount of money that the provider takes for the accepted SFCs
${gain}\in R$ |  $gain$ is the difference between total revenue and cost and indicates the provider’s profit.

####  3.3.1 Decision Variables

In this problem, there is a set of requested SFCs which the provider can
either accept or not. Binary variable $A_{r}$ is for call admission control
$\left(CAC\right)$ that denotes whether SFC $r$ is accepted, $A_{r}=1$. In
this paper, by assuming the instance sharing capability, we propose a novel
two-level-hierarchical mapping model for the DCSM problem. The first level is
the mapping of the VNFs to a set of instances, and the second level is the
mapping of the set of activated instances to the physical nodes. The binary
variable $s_{i,t}^{u,r}$ denotes whether or not VNF $u\in N_{v}^{r}$ from SFC
$r$ is mapped to the instance $i\in I_{t}$ of type $t\in T$. Similarly,
$p_{n}^{i,t}$ denotes whether the instance $i\in I_{t}$ of type $t\in T$ is
mapped to the physical node $n\in N_{p}$.

It is necessary to indicate if a VNF is mapped to a physical node which is
achieved in two steps. At first, binary variable $z_{n,i}^{u,r}$ is defined as
indicating whether VNF $u\in N_{v}^{r}$ of chain $r$ is mapped to instance
$i\in I_{t_{u}}$, of type $t_{u}$ running on physical node $n\in N_{p}$ or
not. This variable is obtained by the multiplication of $s_{i,t_{u}}^{u,r}$
and $p_{n}^{i,t_{u}}$:

$z_{n,i}^{u,r}=s_{i,t_{u}}^{u,r}.p_{n}^{i,t_{u}}{\ }{\ }{\ }\forall
r\in{G_{v}},\forall u\in N_{r}^{v},\forall i\in{I_{{t_{u}}}},\forall
n\in{N_{p}}$ (6)

The following constraints linearize (6).

$\displaystyle z_{n,i}^{u,r}\leq s_{i,{t_{u}}}^{u,r}{\ }{\ }{\ }$
$\displaystyle\forall r\in{G_{v}},\forall u\in N_{r}^{v},\forall
i\in{I_{t_{u}^{r}}},\forall n\in{N_{p}}$ (7) $\displaystyle z_{n,i}^{u,r}\leq
p_{n}^{i,{t_{u}}}{\ }{\ }{\ }$ $\displaystyle\forall r\in{G_{v}},\forall u\in
N_{r}^{v},\forall i\in{I_{t_{u}^{r}}},\forall n\in{N_{p}}$ (8) $\displaystyle
s_{i,{t_{u}}}^{u,r}+p_{n}^{i,{t_{u}}}-1\leq z_{n,i}^{u,r}{\ }{\ }{\ }$
$\displaystyle\forall r\in{G_{v}},\forall u\in N_{r}^{v},\forall
i\in{I_{t_{u}^{r}}},\forall n\in{N_{p}}$ (9)

At the second step, $x_{n}^{u,r}$ is defined as another binary variable by
taking summation of $z_{n,i}^{u,r}$ on $i$ that indicates whether VNF $u\in
N_{r}^{v}$ of SFC $r$ is embedded into the physical node $n\in N_{p}$ or not.

$\sum\limits_{i\in{I_{{t_{u}}}}}{z_{n,i}^{u,r}=x_{n}^{u,r}{\ }{\ }{\ }\forall
r\in{G_{v}},\forall u\in N_{r}^{v},\forall n\in{N_{p}}}$ (10)

For mapping virtual links, we use variable
$\delta_{\left(n,m\right)}^{r,\left(u,v\right)}$ which indicates the
percentage of the traffic of virtual link ${\left(u,v\right)}\in E_{r}^{v}$ of
SFC $r$ that is mapped to physical link ${\left(n,m\right)}\in E_{p}$ of the
substrate network.

${bw}_{\left(n,m\right)}$ is a real variable that indicates the amount of the
allocated bandwidth on physical link ${\left(n,m\right)}\in E_{p}$.
$\lambda_{i,t}$ is a real variable which denotes the traffic entering instance
$i$ of type $t$. Variable $y_{n}^{i,t}$ is the entering traffic to the
hypervisor queue at node $n\in N_{p}$ which should be forwarded to instance
$i\in I_{t}$ of type $t\in T$, so we have

$y_{n}^{i,t}=p_{n}^{i,t}.{\lambda_{i,t}}{\ }{\ }{\ }\forall t\in T,\forall
i\in{I_{t}},\forall n\in{N_{p}}$ (11)

This constraint is linearized as following where $M$ is a big value

$\displaystyle p_{n}^{i,t}.M\geq y_{n}^{i,t}{\ }{\ }{\ }$
$\displaystyle\forall t\in T,\forall i\in{I_{t}},\forall n\in{N_{p}}$ (12)
$\displaystyle{\lambda_{i,t}}-(1-p_{n}^{i,t}).M\leq y_{n}^{i,t}{\ }{\ }{\ }$
$\displaystyle\forall t\in T,\forall i\in{I_{t}},\forall n\in{N_{p}}$ (13)
$\displaystyle{\lambda_{i,t}}\geq y_{n}^{i,t}{\ }{\ }{\ }$
$\displaystyle\forall t\in T,\forall i\in{I_{t}},\forall n\in{N_{p}}$ (14)

The end-to-end delay of every accepted SFC is the summation of a) the delay in
the hypervisors that the SFC enters them which is denoted by $d_{r}^{hyp}$, b)
the delay of the instances that serve the VNFs of the chain which is denoted
by $d_{r}^{ins}$, and c) the propagation delay of the links forwarding the
traffic of the chain which is shown by $d^{link}_{r}$. Variable $l_{n}^{r}$
indicates the delay that SFC $r$ faces in passing through physical node $n\in
N_{p}$, it is obtained as

$l_{n}^{r}=a_{n}^{r}.{{\bar{d}}_{n}}{\ }{\ }{\ }\forall r\in{G_{v}},\forall
n\in{N_{p}}$ (15)

where $\alpha_{n}^{r}$ indicates whether or not SFC $r$ passes through
physical node $n\in N_{p}$. This nonlinear constraint is linearized in the
same way as $y^{i,t}_{n}$.

$q_{i,t}^{u,r}$ is another variable that denotes the delay of SFC $r$ since
its VNF $u\in N_{r}^{v}$ is mapped to instance $i$ of type $t$. It is obtained
as:

$q_{i,t}^{u,r}=s_{i,t}^{u,r}.{{\bar{d}}_{i,t}}{\ }{\ }{\ }\forall
r\in{G_{v}},\forall u\in N_{r}^{v},\forall i\in{I_{t_{u}^{r}}},\forall t\in T$
(16)

which is linearized as $y^{i,t}_{n}$.

The $cost$ variable is the total money payed by the service provider for
bandwidth allocation on physical links, turning on physical servers, and VNF
instances activation. $rev$ is the amount of money that the provider earns
from the accepted SFCs, and the $gain$ variable is the difference between
$rev$ and $cost$ that indicates the provider’s business profit.

####  3.3.2 Objective Function and Constrains

In this problem, the objective is to maximize the $gain$.

$\text{Minimize }gain$ (17)

which is computed by the constrains (18)-(20):

$\displaystyle gain=$ $\displaystyle\ rev-cost$ (18) $\displaystyle rev=$
$\displaystyle\sum\limits_{r\in{G_{r}}}{re{v_{r}}.{A_{r}}}$ (19)
$\displaystyle cost=$
$\displaystyle\sum\limits_{{n}\in{N_{p}}}{\sigma_{n}.{\alpha}^{r}_{n}}+\sum\limits_{t\in
T}\sum\limits_{i\in{I_{t}}}{C_{t}}.x_{t}^{i}+{\rho}.\sum\limits_{\left({m,n}\right)\in{E_{p}}}{b{w_{\left({m,n}\right)}}}$
(20)

As already eluded, a two-level mapping is conducted to deploy SFCs, at the
first level VNFs are mapped to instances and in the second level instances are
mapped to physical nodes. In the first level, if a SFC is accepted, all its
VNFs must be mapped to an instance, which is formulated as (21).

$\sum\limits_{i\in{I_{{t_{u}}}}}{s_{i,t}^{u,r}}={A_{r}}{\ }{\ }{\ }\forall
r\in{G_{v}},\forall u\in N_{r}^{v}$ (21)

In the second level, an instance must be mapped to a physical node if at least
a VNF is mapped to the instance, which is imposed by constraint (22).

$s_{i,t}^{u,r}\leq\sum\limits_{n\in{N_{p}}}{p_{n}^{i,t}}{\ }{\ }{\ }\forall
r\in{G_{v}},\forall u\in N_{r}^{v},\forall i\in{I_{t_{u}^{r}}}$ (22)

To map virtual links, under the assumption of flow-splitting, a set of paths
should be found in the physical network which is obtained by the flow
conservation constraint in (23); then the required bandwidth should be
allocated, which is formulated by (24), with subject to the capacity of
physical links in constraint (25).

$\displaystyle\sum\limits_{\left({n,m}\right)\in{E_{p}}}{\delta_{\left({n,m}\right)}^{r,\left({u,v}\right)}}-\sum\limits_{\left({m,n}\right)}{\delta_{\left({m,n}\right)}^{r,\left({u,v}\right)}=x_{n}^{u,r}-x_{n}^{v,r}}{\
}{\ }{\ }$ $\displaystyle\forall r\in{G_{v}},\forall\left({u,v}\right)\in
E_{r}^{v},\forall n\in{N_{p}}$ (23)
$\displaystyle\sum\limits_{r\in{G_{v}}}{\sum\limits_{\left({k,l}\right)\in
E_{r}^{v}}{w_{\left({k,l}\right)}^{r}}}.\delta_{\left({m,n}\right)}^{r,\left({u,v}\right)}=b{w_{\left({n,m}\right)}}{\
}{\ }{\ }$ $\displaystyle\forall\left({n,m}\right)\in{E_{p}}$ (24)
$\displaystyle b{w_{\left({n,m}\right)}}\leq{\theta_{\left({n,m}\right)}}{\
}{\ }{\ }$ $\displaystyle\forall\left({n,m}\right)\in{E_{p}}$ (25)

The CPU, storage, and memory capacity limitations in physical nodes are
respectively imposed by constraints (26), (27), and (28).

$\displaystyle\sum\limits_{t\in
T}{\sum\limits_{i\in{I_{t}}}{CP{U_{t}}}}.p_{n}^{i,t}\leq\theta_{n}^{CPU}{\ }{\
}{\ }$ $\displaystyle\forall n\in{N_{p}}$ (26) $\displaystyle\sum\limits_{t\in
T}{\sum\limits_{i\in{I_{t}}}{str{g_{t}}}}.p_{n}^{i,t}\leq\theta_{n}^{strg}{\
}{\ }{\ }$ $\displaystyle\forall n\in{N_{p}}$ (27)
$\displaystyle\sum\limits_{t\in
T}{\sum\limits_{i\in{I_{t}}}{me{m_{t}}}}.p_{n}^{i,t}\leq\theta_{n}^{mem}{\ }{\
}{\ }$ $\displaystyle\forall n\in{N_{p}}$ (28)

In order to compute the processing and queuing delays, the input traffic rate
for each instance $i\in I_{t}$ and each physical node $n\in N_{p}$ are
respectively calculated by (29) and (30).

$\displaystyle\sum\limits_{r\in{G_{v}}}{\sum\limits_{u\in
N_{v}^{r}}{{f_{r}}}}.s_{i,t}^{u,r}={\lambda_{i,t}}{\ }{\ }{\ }$
$\displaystyle\forall t\in T,\forall i\in{I_{t}}$ (29)
$\displaystyle\sum\limits_{t\in
T}{\sum\limits_{i\in{I_{t}}}{y_{n}^{i,t}}}={\lambda_{n}}{\ }{\ }{\ }$
$\displaystyle\forall n\in{N_{p}}$ (30)

Using the variables $\lambda_{n}$ and $\lambda_{i,t}$ and the given parameters
$u_{n}$ and $u_{t}$, the queuing and processing delays in the physical nodes
and the VNF instances will be as (31) and (32), respectively.

$\displaystyle\log\left({{{\bar{d}}_{n}}}\right)+\log\left({{\mu_{n}}-{\lambda_{n}}}\right)\geq
0{\ }{\ }{\ }$ $\displaystyle\forall n\in{N_{p}}$ (31)
$\displaystyle\log\left({{{\bar{d}}_{l,t}}}\right)+\log\left({{\mu_{t}}-{\lambda_{i,t}}}\right)\geq
0{\ }{\ }{\ }$ $\displaystyle\forall t\in T,i\in{I_{t}}$ (32)

It should be noted that these constraints are convex constraint.

Constraints (33), (34), and (35) calculate $d_{r}^{hyp}$, $d_{r}^{ins}$, and
$d_{r}^{link}$ for each SFC $r$ as the imposed average delay from hypervisors,
instances, and links respectively. To guarantee the end-to-end delay, the
summation of the delays should be less than the given threshold which is
imposed by (36).

$\displaystyle\sum\limits_{n\in{N_{p}}}{l_{n}^{r}=d_{r}^{hyp}}{\ }{\ }{\ }$
$\displaystyle\forall r\in{G_{v}}$ (33) $\displaystyle\sum\limits_{u\in
N_{r}^{v}}{\sum\limits_{i\in{I_{t_{u}^{r}}}}{q_{i,t_{u}^{r}}^{u,r}}}=d_{r}^{ins}{\
}{\ }{\ }$ $\displaystyle\forall r\in{G_{v}}$ (34)
$\displaystyle\sum\limits_{\left({n,m}\right)\in{E_{p}}}{\sum\limits_{\left({v,u}\right)\in
E_{v}^{r}}{{d_{\left({n,m}\right)}}.\delta_{\left({n,m}\right)}^{r,\left({u,v}\right)}}}=d_{r}^{link}{\
}{\ }{\ }$ $\displaystyle\forall r\in{G_{v}}$ (35) $\displaystyle
d_{r}^{hyp}+d_{r}^{ins}+d_{r}^{link}\leq d_{r}^{th}{\ }{\ }{\ }\forall
r\in{G_{v}}$ (36)

Finally, the values of variables $\alpha_{n}^{r}$ and $x_{n}^{u,r}$ need to be
determined in order to compute the $cost$, which are obtained by (30)-(32).

$\displaystyle x_{n}^{u,r}\leq\alpha_{n}^{r}{\ }{\ }{\ }$
$\displaystyle\forall r\in{G_{v}},\forall u\in N_{v}^{r},\forall n\in{N_{p}}$
(37) $\displaystyle\alpha_{n}^{r}\leq\sum\limits_{u\in
N_{v}^{r}}{x_{n}^{u,r}}{\ }{\ }{\ }$ $\displaystyle\forall r\in{G_{v}},\forall
n\in{N_{p}}$ (38) $\displaystyle s_{i,t}^{u,r}\leq x_{t}^{i}{\ }{\ }{\ }$
$\displaystyle\forall r\in{G_{v}},\forall u\in N_{v}^{r},\forall
i\in{I_{t}},\forall t\in T$ (39)

By putting the objective function and the constraints altogether, we have the
formulation of the DCSM as following

Model: | DCSM
---|---
Objective: | (17)
Constraints: | (6)-(16), (18)-(38)

This model is a mixed integer convex optimization problem. Unfortunately, it
cannot be used as a practical solution of the DCSM problem since the problem
is an NP-hard [11, 12, 13]. In the following section, by decomposing this
complex model, we develop an efficient solution for this problem.

##  4 Proposed Solution

This section describes the proposed solution, named MLDG (Multi-Level Delay-
Guaranteed) mapping, for the DCSM problem. In the following, we first explain
the main ideas and the overall procedure of the solution, then discuss the
details of the steps.

Inspecting the problem identified two sources of complexity. The first one is
the mapping of the instances on physical nodes, which is formulated by
decision variable $p_{n}^{i,t}$ in the optimization model, and the second
source is the mapping of the virtual functions to the instances, denoted by
$s_{i,t}^{u,r}$. Combinations of different values of these variables yield to
the exponential growth of the model solution space, and consequently cause
intractability of the model even in small instances.

Based on this observation, the main idea to approach the problem is to
decompose it into two subproblems. In the first subproblem, the candidate
instances of each function type are determined and placed in the physical
network. In the second subproblem, instead of considering all SFCs in a large
MINLP model, the service chains are deployed one-by-one using an iterative
algorithm. This decomposition eliminates the coupling between $p_{n}^{i,t}$
and $s_{i,t}^{u,r}$ that makes that problem solvable in a polynomial time. The
overall procedure of the proposed solution is depicted in 4; and the details
are discussed in the following subsections.

Figure 4: The overall procedure of the proposed solution

###  4.1 Subproblem 1: Instance Mapping

The main objective of the first subproblem is to determine the value of the
decision variables $p_{n}^{i,t}\ \forall t\in T$,$\forall i\in I_{t}$,$\forall
n\in N_{p}$, which is the first source of the complexity of the problem. For
this purpose, the instances should be placed in the physical network that
needs to answer two questions: 1) what is the required number of instances of
each type? and 2) where is the suitable location for the instances in the
physical network?

In answering the first question, we should not underestimate the number of
instances otherwise it causes rejection of demands in the second subproblem.
Therefore, by considering the case where all SFCs are accepted and according
to the assumption of instance sharing among VNFs, the estimated number of the
instances of the type $t$ is

${\eta^{t}}=\left\lceil{\frac{{\sum\limits_{\forall
r\in{G_{v}}}{\left({\sum\limits_{\forall u\in
N_{v}^{r}|type(u)=t}{{f_{r}}}}\right)}}}{{\theta.{\mu_{t}}}}}\right\rceil{\
}{\ }{\ }\forall t\in T$ (40)

where $0<\theta<1$ is a parameter to scale down the capacity of the instances.
This scaling is needed since in practice, as VNFs cannot be split among
multiple instances, it is not possible to utilize the fully capacity,
$\mu_{t}$, of the instances. This is the first step of the instance mapping
sub-problem in figure 4.

To answer the second question, we develop an algorithm based on a key
observation. As explain, three factors contribute to the end-to-end delay that
are the propagation delay of physical links, the operating system and
hypervisor delay in physical servers, and the queuing and processing delay in
instances. The key point is that if two successive VNFs of a chain are mapped
to the instances which are located in the same physical node, then the virtual
link connecting these two VNFs resides inside the physical node and
consequently the first and second delay factors are eliminated. Moreover, this
approach eliminates the cost of bandwidth allocation on physical links.
Therefore, in the instance mapping stage, we should seek to find a cluster of
instances which are mostly connected to each other and place the cluster on a
single physical server.

To select the first member of a cluster, we define the placement priorities
per type $t$ as following

${\pi^{t}}={\tilde{\eta}^{t}}.{\Lambda^{t}}{\ }{\ }{\ }\forall t\in T$ (41)

where ${\Lambda^{t}}$ is the total number of virtual links $\left(u,v\right)$
in all chains that either $u$ or $v$ is of type $t$, and ${\tilde{\eta}^{t}}$
is the number of instances of type $t$ which have not been placed yet. To
initialize the priorities, ${\tilde{\eta}^{t}}={\eta^{t}}$.

After selecting the first instance of a cluster, subsequent instances are
selected according to the number of connections (virtual links) between them
and the members of the cluster. More precisely, we define belonginess of type
$t$ to cluster $\kappa$ as

$\beta_{\kappa}^{t}=\Big{|}{\left\\{{\left({u,v}\right),\left({v,u}\right)\in
E_{r}^{v}{\ }{\ }\forall r\in{G_{v}}\text{ s.t. }u\in\kappa\text{ and
}type(v)=t}\right\\}}\Big{|}$ (42)

At each step, an instance of a type $t$ with the largest $\beta_{\kappa}^{t}$
is selected as a member of cluster if it does not violate the capacity of the
physical server. When it is not possible to add a new member to the cluster,
this procedure is repeated for a new physical server and its corresponding new
cluster. The details of the procedure are explained in algorithm 1.

INPUT:${\ }G_{p},\eta^{t}$
OUTPUT:${\ }p^{i,t}_{n}$

1: $\pi^{t}=\eta^{t}\Lambda^{t}{\ }\forall t\in T$

2: $n\leftarrow 0$

3: while ${\ }\exists t\in T{\ }\text{s.t.}{\ }\pi^{t}\neq 0$ do

4: $\tilde{t}\leftarrow\textbf{argmax}_{t\in T}\\{\pi^{t}\\}$

5: $\eta^{t}\leftarrow\eta^{t}-1$

6: $\kappa\leftarrow\\{i{\ }\text{s.t.}{\ }type\left(i\right)=t\\}$

7: $n\leftarrow n+1$

8: $p^{i,t}_{n}\leftarrow 1$

9: repeat

10: $\tilde{t}\leftarrow\textbf{argmax}_{t\in T}\\{\beta^{t}_{k}\\}$

11: if physical server $n$ has enough resources and $\eta^{t}\neq 0$ then

12: $\eta^{t}\leftarrow\eta^{t}-1$

13: $\kappa\leftarrow\\{i{\ }\text{s.t.}{\ }type\left(i\right)=t\\}\cup\kappa$

14: $p^{i,t}_{n}\leftarrow 1{\ }$

15: end if

16: until ${\ }\exists t\in T{\ }\text{s.t.}{\ }\pi^{t}\neq 0$ and server $n$
has sufficient capacity

17: $\pi^{t}=\eta^{t}\Lambda^{t}{\ }\forall t\in T$

18: end while

Algorithm 1 Most Connected Cluster Placement

In this algorithm, the placement priorities are initialized in line 1, the
first member of a cluster is found and placed in lines 4-8, similarly in lines
10-14 the most connected instance is added to the cluster, and finally in line
17 the priorities are updated.

###  4.2 Subproblem 2: SFC Mapping

The main steps of the second subproblem are depicted in Figure 4. In this
subproblem, by substituting the values of decision variables of $p_{n}^{i,t}$,
obtained from the first subproblem, in the MIP model and relaxing the binary
variables of it, we obtain the convex problem named SP2-CV. While the solution
of the convex model is not necessarily a feasible solution of the DCSM, it can
be post-processed by rounding techniques to obtain integer solution. Here, we
focus on the least fractional VNF mapping variable, $s_{i,t}^{u,r}$, and
deploy the chains in two nested loops. The outer loop, in each iteration,
finds the chain with the minimum fractional VNF mapping, and the inner loop
processes the VNFs of the chain. In each iteration of the loop, the minimum
fractional $s_{i,t}^{u,r}$ is selected, and rounded to 1. After fixing the
variable, the SP2-CV model is solved to update the remaining variables. This
procedure continues until either all VNFs of the chain is mapped, or the chain
is rejected due to infeasibility of the model. The subsequent chains are
deployed in the same way. The details of these steps are explained in
algorithm 2.

INPUT:$G_{p},G_{v},p^{i,t}_{n},T$
OUTPUT:$A_{r},s^{u,r}_{i,t},p^{i,t}_{n}$

1: repeat

2: $s^{u,r}_{i,t}\leftarrow\text{solve }SP2-CV$

3: ${\theta}_{r}\leftarrow\sum\limits_{u\in{N_{r}^{v}}}\textbf{max}_{i\in
I_{t_{u}}}\left(\\{s^{u,r}_{i,t}\\}/|N^{v}_{r}|\right)$

4: $\tilde{r}\leftarrow\textbf{argmax}_{u\in
N^{v}_{\tilde{r}}}\\{\theta_{r}\\}$

5: $A_{\tilde{r}}\leftarrow 1$

6: while ${\ }\exists u\in N^{v}_{\tilde{r}}{\ }\textbf{s.t.}{\
}s^{u,\tilde{r}}_{i,t}\neq 1$ do

7: $\tilde{u}\leftarrow\textbf{argmax}_{u\in
N^{v}_{\tilde{r}}}\\{s^{u,\tilde{r}}_{i,t}\\}$

8: $s^{\tilde{u},\tilde{r}}_{i,t}\leftarrow 1$

9: $\text{Substitute}{\ }s^{\tilde{u},\tilde{r}}_{i,t}{\ }\text{in}{\ }SP2-CV$

10: $\bar{s}^{u,r}_{i,t}\leftarrow\text{solve}{\ }SP2-CV$

11: if $\bar{s}^{u,r}_{i,t}{\ }\text{is infeasible}$ then

12: $s^{u,\tilde{r}}_{i,t}\leftarrow 0{\ }\forall u\in N^{v}_{\tilde{r}}$

13: $A_{\tilde{r}}\leftarrow 0$

14: break

15: else

16: $s^{u,r}_{i,t}\leftarrow\bar{s}^{u,r}_{i,t}$

17: end if

18: end while

19: until $\exists r\in G_{v}$

Algorithm 2 SFC Mapping

In line 2, the SP2-CV model, wherein the $s_{i,t}^{u,r}$ variables are not
necessarily binary, is solved. In line 3, the least fractional $s_{i,t}^{u,r}$
is found regarding to length of its corresponding SFC, and in line 4 the
mentioned SFC, which is denoted by $\tilde{r}$, is identified. It is assumed
that this chain will be accepted at line 5, and in the inner loop, the VNFs of
the chain are investigated. At each iteration, the $u\in N_{\tilde{r}}^{v}$
with least fractional value $s_{i,t}^{u,\tilde{r}}$ is identified in line 7.
It is rounded to 1 in line 8. After substituting this value in the model, it
is solved in line 10. If it is an infeasible model, this SFC is rejected in
lines 11-14, otherwise, $s_{i,t}^{u,r}$ values are update and the loops
continues to map the remaining VNFs of SFC $\tilde{r}$. The outer loop
continues until all SFCs are either accepted or rejected.

###  4.3 Complexity Analysis

The computational complexity of the proposed solution is analyzed in this
section. In the first subproblem, the complexity of computing $\eta^{t}$ is
$O\left(\left|T\right|\left|G_{v}\right|N^{*}\right)$ where $N^{*}$=max
$\left|N_{v}^{r}\right|$. Initializing $\pi^{t}$ takes $O\left(T\right)$ time.
Placement of instances on physical server, the two nested loops in lines 3-17
of algorithm 1, is performed in $O\left(H\right)$ iterations where
$H=\sum\eta^{t}$. Operations in lines 3-17 are $O\left(1\right)$ except the
argmax operation and updating $\pi^{t}$ which take $O\left(T\right)$.
Therefor, the complexity of the first subproblem is

$O(\text{subprobelm-1})=O(|T||G_{v}|N^{*})+O(T)+O(HT)=O(|T||G_{v}|N^{*})+O(HT)$

In the second subproblem, the nested loops and solving the SP2-CV model are
the main contributors of the complexity. The complexity of the outer loop is

$O(\text{subproblem-2})=O(|G_{v}|(CV)+R^{*}+N^{*}O(\text{inner}))$

Where $O(CV)$ and $O(\text{inner})$ are respectively the complexity of convex
programming and the complexity of lines 6-15 of algorithm 2. There are
efficient algorithms for convex programming [24]. The complexity of lines 6-15
is

$O(\text{inner})=O(N^{*}+O(LP)+N^{*})$

So, we have

$O(\text{subproblem-2})=O(|G_{r}|N^{*}O(CV))$

By putting these analyses together, the complexity of the proposed method is

$O(|G_{r}|N^{*}O(CV))+O(|T||G_{v}|N^{*})+(HT)$

which is polynomial in terms of the size of substrate network, the number of
function types, the number of SFCs and their sizes.

##  5 Simulation Results

In this section, at first, the simulation settings are discussed in detail,
then comparisons between the proposed solution and the optimal solution, and
the algorithm proposed in [7] are presented; and finally, the effects of the
parameters of the proposed algorithm are analyzed.

###  5.1 Simulation Settings

The system used for the simulations has a Core $i7$ Intel processor with 2.7
GHz frequency, 16 GB of RAM, and 512 GB of SSD hard disk. The simulation
environment is implemented by Python, and ANACONDA Package [25] is used to
configure the SCIP solver [26]. Since the problem studied in [7] is the most
similar one to our problem, we implemented its proposed algorithm, named
Annealing Based Simulation Approach (ABSA), and compared its performance to
the proposed solution. It should be noted that the problems are not exactly
the same, so, we modified them in such a way to make a fair comparison between
two solutions. The changes are discussed in the next sections.

In this paper, two topologies are used as the substrate network. Figure 5
shows the small topology, used for the of proposed solution against to the
optimal solution. In this topology, the bandwidth of all the links equal 1000
MB. The CPU capacity of all the nodes are randomly chosen in [220, 260] cores.
Storage capacity of all nodes is equal to 4000 GB and memory capacity is 1000
GB. Table 7 and Table 8 show the details of input SFCs and VNF types which are
used in the topology shown in Figure 5.

Figure 5: The Small Topology Used for Comparison with The Optimal Solution.
Table 7: The Setting of the SFCs Used for Comparison with the Optimal Solution
in Topology of Fig. 5.

Parameter | Value
---|---
VNF types $\left(t^{r}_{u}\right)$ |  Randomly in [1, 2, 3, 4]
VNF Number per SFC $(|N^{v}_{r}|)$ | 3 VNFs
Bandwidth $(f_{r})$ | 30 MB
Revenue $\left({rev}_{r}\right)$ | 9000
End-to-end delay threshold $\left(d^{th}_{r}\right)$ |  1 $\mu$s

Table 8: The Settings of the VNF Types Used for Comparison with the Optimal
Solution in Topology of Fig. 5.

Parameter | Value per Type
---|---
$t$ | 1 | 2 | 3 | 4
${cpu}_{t}$ (cores) | 80 | 50 | 50 | 60
${strg}_{t}$ (GB) | 200 | 250 | 250 | 300
${mem}_{t}$ (GB) | 160 | 100 | 100 | 120
${\mu}_{t}$ (MBps) | 100 | 100 | 100 | 100
$C_{t}$ | 500 | 600 | 700 | 500

Table 9: NFVI Setting in BtEurope Topology Used for Comparison with ABSA.

Parameter | Value
---|---
$\theta^{CPU}_{n}$ | 24 cores
$\theta^{strg}_{n}$ | 10000 GB
$\theta^{mem}_{n}$ | 256 GB
$\theta_{\left(n,m\right)}$ | 10000 MB
$\rho$ | 10
$\sigma_{n}$ | 1000
$\mu_{n}$ | 2000 MB_ps
$d_{\left(n,m\right)}$ |  0.5 $\mu$s
$d_{n}$ |  3 $\mu$s

Comparisons to the proposed algorithm in [7] were conducted in the BtEurope
topology, from The Internet Topology Zoo, available at [27]. The settings are
summarized in Table 9. The input SFCs and the VNF types used for these
comparisons are respectively shown in Table 10 and Table 11.

Table 10: The Setting of the SFCs Used for Comparison with ABSA in BtEurope.

Parameter | Value
---|---
VNF Types $\left(t^{r}_{u}\right)$ |  Randomly in [1, 2, 3, 4]
VNF Number per SFC $\left(|N^{v}_{r}|\right)$ | 4 VNFs
Bandwidth $(f_{r})$ | 100 MB
Revenue $\left({rev}_{r}\right)$ | $3000|N^{v}_{r}|+15f_{r}(|N^{v}_{r}|-1)$
End-to-end delay threshold $\left(d^{th}_{r}\right)$ |  3${\mu}s$

Table 11: The Settings of the VNF Types Used for Comparison with ABSA in
BtEurope.

Parameter | Value per Type
---|---
$t$ | 1 | 2 | 3 | 4
${CPU}_{t}$ (cores) | 4 | 7 | 6 | 5
${strg}_{t}$ (GB) | 90 | 90 | 120 | 100
${mem}_{t}$ (GB) | 16 | 24 | 32 | 24
${\mu}_{t}$ (MBps) | 450 | 500 | 400 | 450
$C_{t}$ | 2000 | 2200 | 1800 | 2500

In these simulations, in addition to the $gain$ which is the main objective of
DCSM, we also evaluate the results in terms of acceptance rate. Since the
problem is NP-Hard, it is extremely time consuming to reach the exact optimal
solution using a solver; hence, we set the optimality gap threshold equals to
5%.

###  5.2 Comparison with Optimal Solution

In this section, the efficiency of MLDG is evaluated by comparing it against
the solver’s 5% sub-optimal solution with respect to the number of requested
SFCs and the length of SFCs. These simulations were conducted in Figure 5
topology using the configurations presented in the previous subsection. The
results are shown in Figures 6$-$9. Figures 6 and 7 show the evaluation
results with respect to the number of SFCs; the effect of the length of SFC is
evaluated in Figures 8 and 9.

Figure 6: The Average Gain of the Solver and MLDG with Respect to the Number
of SFCs. Figure 7: The Average Acceptance Rate of the Solver and MLDG with
Respect to the Number of SFCs. Figure 8: The Average Gain of the Solver and
MLDG with Respect to the SFC Length. Figure 9: The Average Acceptance Rate of
the Solver and MLDG with Respect to the SFC Length.

As it seen the gain increases by increasing the number of requested SFCs and
the length of SFC as in this case the algorithms have more opportunity to
accept demands and each accepted demand makes more profit. However, the
acceptance rate is not necessarily improved by increase the parameters because
the algorithms may decide to reject some demands in favor of maximizing the
gain.

These results show that the differences between MLDG and the solver solution
are negligible and in some cases, the MLDG solutions are even better than the
solver’s 5% sub-optimal ones. That implies MLDG provides near-optimal
solutions. To evaluate this algorithm in a more realistic topology setting, we
compare it against another practical algorithm proposed in [7].

###  5.3 Comparison to ABSA

To the best of our knowledge, the problem investigated in [7] is the most
similar one to this paper. Nevertheless, these two problems have some
differences which should be manipulated in such a way that makes a fair
comparison. Their most considerable differences and the way we handled them
are as follows:

  1. 1.

The objective function: the objective of paper [7] is cost minimization, while
the objective of DCSM is gain maximization. Based on equation (18), the gain
is calculated by subtracting the cost from the revenue. Hence, we defined a
revenue for each SFC and changed the objective of [7] from cost minimization
to gain maximization.

  2. 2.

Cost calculation: paper [7] does not consider the cost of instance activation
for each VNF, therefore, we changed the cost function to consider the cost of
activating an instance.

  3. 3.

End-to-end delay calculation: In [7] authors have considered a constant delay
for the nodes and links. However, in this paper, as illustrated in inequality
(36), queuing delay is also considered. We changed our delay model and
simplified it as [7].

As mentioned, ABSA is based on the Simulated Annealing approach, in these
simulations, the corresponding parameters are follows: temperature is 1000,
cooling rate is 0.05 and the $\lambda$ parameter is 3.

Figure 10 and Figure 11 show the average gain and the average acceptance of
the proposed solution and ABSA with respect to the number of requested SFCs.
Although the acceptance rate of the MLDG algorithm is a bit lower than ABSA,
it skillfully accepts a subset demands that make more gain that is justified
by the considerable gap between MLDG and ABSA in Figure 10.

By increasing the number of input SFCs the average gain of both algorithms
increase but with different rates. By the increase of the number of input
SFCs, the required instances capacity increases which leads to more instances
sharing possibility. In the proposed solution, by exploiting this possibility,
the instance cost breaks down among multiple chains, and consequently, the
average cost of each SFC decreases, and as a result, the average gain
increases. On the other hand, ABSA does not share the instances that causes a
high cost and the lower gain.

Figure 10: The Average Gain of MLDG and ABSA with Respect to the Number of
SFCs. Figure 11: The Average Acceptance Rate of MLDG and ABSA with Respect to
the Number of SFCs.

Figure 12 and Figure 13 depict the effect of the length of SFCs on the
performance of the algorithms. In these simulations, 10 SFCs are requested. As
it shown, SFCs length and gain are positively correlated. Since by increasing
the number of VNFs of each SFC, the profit of the accepted demands increases.
Moreover, in this case, more instances can be shared among chains that leads
to cost breakdown and gain increment. On the other hand, as depicted in figure
13, the acceptance rate and the SFCs length are negatively correlated. The
capacity of each physical node is limited, therefore, longer SFCs should be
split in several physical nodes. In this case, several physical nodes should
be connected to each other that incurs additional delay that goes beyond the
required end-to-end-delay threshold; and consequently the request is rejected.

Figure 12: The Average Gain of MLDG and ABSA with Respect to the SFCs Length.
Figure 13: The Average Acceptance Rate of MLDG and ABSA with Respect to the
SFCs Length.

Putting the results together, indicates that the proposed approach both
theoretically and practically is an efficient solution of the DCSM problem.

###  5.4 Design Parameter Impact Analysis

In this subsection, the impact of the parameter $\theta$ on the performance of
the algorithm is evaluated. The results are depicted in Figure 14 and Figure
15. According to these figures, there is an optimum value of this parameter,
which is 0.7 in our settings. This parameter has a twofold effect on the
acceptance rate and gain. When the value of the parameter is much less than
the optimum value, according to the (40), the number of instances is
overestimated that leads to high cost and consequently decrease in gain.
However, when the value of the parameter is much greater than the optimum
value, it causes over utilization of the instances that consequently increase
the queuing delay and as a result some demands are rejected due to the end-to-
end delay constraint. This decreases the acceptance rate as well as the gain.

Figure 14: The Average Gain with respect to $\theta$ Figure 15: The Average
Acceptance Rate with Respect to $\theta$

##  6 Conclusion

In this paper, the DCSM problem that aims to maximize the profit gain of the
service provider while satisfying the QoS requirement including the end-to-end
delay is investigated. We presented an accurate modeling of the end-to-end
delay that considers the queuing delay as well as propagation delay. The
problem is formulated as a mixed integer convex problem, which is used to
obtain a performance bound. To approach the problem, a two-level mapping
algorithm is proposed by decomposing the optimization problem. At the first
level, it maps functions to VNF instances by exploiting the instance sharing
potential. In the second level, the instances are deployed in the physical
network. The simulation results showed the solution is near optimal.

## References

  * [1] H. Hawilo, A. Shami, M. Mirahmadi, R. Asal, Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc), IEEE Network 28 (6) (2014) 18–26.
  * [2] B. Han, V. Gopalakrishnan, L. Ji, S. Lee, Network function virtualization: Challenges and opportunities for innovations, IEEE Communications Magazine 53 (2) (2015) 90–97.
  * [3] J. G. Herrera, J. F. Botero, Resource allocation in nfv: A comprehensive survey, IEEE Transactions on Network and Service Management 13 (3) (2016) 518–532.
  * [4] R. Yu, G. Xue, X. Zhang, Qos-aware and reliable traffic steering for service function chaining in mobile networks, IEEE Journal on Selected Areas in Communications 35 (11) (2017) 2522–2531.
  * [5] R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, R. Boutaba, Network function virtualization: State-of-the-art and research challenges, IEEE Communications surveys & tutorials 18 (1) (2015) 236–262.
  * [6] A. Xie, H. Huang, X. Wang, Z. Qian, S. Lu, Online vnf chain deployment on resource-limited edges by exploiting peer edge devices, Computer Networks 170 (2020) 107069.
  * [7] A. Fischer, D. Bhamare, A. Kassler, On the construction of optimal embedding problems for delay-sensitive service function chains, in: 2019 28th International Conference on Computer Communication and Networks (ICCCN), IEEE, 2019, pp. 1–10.
  * [8] L. Qu, C. Assi, K. Shaban, M. J. Khabbaz, A reliability-aware network service chain provisioning with delay guarantees in nfv-enabled enterprise datacenter networks, IEEE Transactions on Network and Service Management 14 (3) (2017) 554–568.
  * [9] B. Tahmasebi, M. A. Maddah-Ali, S. Parsaeefard, B. H. Khalaj, Optimum transmission delay for function computation in nfv-based networks: The role of network coding and redundant computing, IEEE Journal on Selected Areas in Communications 36 (10) (2018) 2233–2245.
  * [10] Y. T. Woldeyohannes, A. Mohammadkhan, K. Ramakrishnan, Y. Jiang, Cluspr: Balancing multiple objectives at scale for nfv resource allocation, IEEE Transactions on Network and Service Management 15 (4) (2018) 1307–1321.
  * [11] H. A. Alameddine, S. Sebbah, C. Assi, On the interplay between network function mapping and scheduling in vnf-based networks: A column generation approach, IEEE Transactions on Network and Service Management 14 (4) (2017) 860–874.
  * [12] D. Bhamare, M. Samaka, A. Erbad, R. Jain, L. Gupta, H. A. Chan, Optimal virtual network function placement in multi-cloud service function chaining architecture, Computer Communications 102 (2017) 1–16.
  * [13] X. Chen, W. Ni, I. B. Collings, X. Wang, S. Xu, Automated function placement and online optimization of network functions virtualization, IEEE Transactions on Communications 67 (2) (2018) 1225–1237.
  * [14] F. Yaghoubpour, B. Bakhshi, Optimal delay-aware service function chaining in nfv, in: 2019 27th Iranian Conference on Electrical Engineering (ICEE), IEEE, 2019, pp. 1961–1966.
  * [15] M. A. T. Nejad, S. Parsaeefard, M. A. Maddah-Ali, T. Mahmoodi, B. H. Khalaj, vspace: Vnf simultaneous placement, admission control and embedding, IEEE Journal on Selected Areas in Communications 36 (3) (2018) 542–557.
  * [16] N. Yuan, W. He, J. Shen, X. Qiu, S. Guo, W. Li, Delay-aware nfv resource allocation with deep reinforcement learning, in: NOMS 2020-2020 IEEE/IFIP Network Operations and Management Symposium, IEEE, 2020, pp. 1–7.
  * [17] R. Gouareb, V. Friderikos, A.-H. Aghvami, Virtual network functions routing and placement for edge cloud latency minimization, IEEE Journal on Selected Areas in Communications 36 (10) (2018) 2346–2357.
  * [18] N. Makariye, Towards shortest path computation using dijkstra algorithm, in: 2017 International Conference on IoT and Application (ICIOT), IEEE, 2017, pp. 1–3.
  * [19] B. Kar, E. H.-K. Wu, Y.-D. Lin, Energy cost optimization in dynamic placement of virtualized network function chains, IEEE Transactions on Network and Service Management 15 (1) (2017) 372–386.
  * [20] G. Bolch, S. Greiner, H. De Meer, K. S. Trivedi, Queueing networks and Markov chains: modeling and performance evaluation with computer science applications, John Wiley & Sons, 2006.
  * [21] B. Han, V. Sciancalepore, D. Feng, X. Costa-Perez, H. D. Schotten, A utility-driven multi-queue admission control solution for network slicing, in: IEEE INFOCOM 2019-IEEE Conference on Computer Communications, IEEE, 2019, pp. 55–63.
  * [22] M. Erel-Özçevik, B. Canberk, Take your cell a walk for ultra-low e2edeiay in software defined vehicular networks, in: 2018 IEEE Globecom Workshops (GC Wkshps), IEEE, 2018, pp. 1–6.
  * [23] J. Prados, P. Ameigeiras, J. J. Ramos-Munoz, J. Navarro-Ortiz, P. Andres-Maldonado, J. M. Lopez-Soler, Performance modeling of softwarized network services based on queuing theory with experimental validation, IEEE Transactions on Mobile Computing (2019).
  * [24] A. Nemirovski, Interior point polynomial time methods in convex programming, Lecture notes (2004).
  * [25] Anaconda software distribution (2020).
URL https://docs.anaconda.com/

  * [26] G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eifler, M. Gasse, P. Gemander, A. Gleixner, L. Gottwald, K. Halbig, G. Hendel, C. Hojny, T. Koch, P. Le Bodic, S. J. Maher, F. Matter, M. Miltenberger, E. Mühmer, B. Müller, M. E. Pfetsch, F. Schlösser, F. Serrano, Y. Shinano, C. Tawfik, S. Vigerske, F. Wegscheider, D. Weninger, J. Witzig, The SCIP Optimization Suite 7.0, Technical report, Optimization Online (March 2020).
URL http://www.optimization-online.org/DB_HTML/2020/03/7705.html

  * [27] S. Knight, H. Nguyen, N. Falkner, R. Bowden, M. Roughan, The internet topology zoo, Selected Areas in Communications, IEEE Journal on 29 (9) (2011) 1765 –1775.  doi:10.1109/JSAC.2011.111002.