# Optimizing Resource Allocation and VNF Embedding in RAN Slicing

Tu N. Nguyen, Kashyab J. Ambarani, and My T. Thai The short version of the
paper has been accepted to the 2021 IEEE Global Communications Conference.
Corresponding author: Tu N. NguyenTu N. Nguyen is with the Department of
Computer Science, Kennesaw State University, Marietta, GA 30060 USA (e-mail:
tu.nguyen@kennesaw.edu).K. J. Ambarani is with the Department of Computer
Science, Purdue University Fort Wayne, Fort Wayne, IN 46805, USA (e-mail:
ambakj01@pfw.edu).M. T. Thai is with the Computer and Information Science and
Engineering, University of Florida, Gainesville, FL 32612 USA (e-mail:
mythai@cise.ufl.edu).

###### Abstract

5G radio access network (RAN) with network slicing methodology plays a key
role in the development of the next-generation network system. RAN slicing
focuses on splitting the substrate’s resources into a set of self-contained
programmable RAN slices. Leveraged by network function virtualization (NFV), a
RAN slice is constituted by various virtual network functions (VNFs) and
virtual links that are embedded as instances on substrate nodes. In this work,
we focus on the following fundamental tasks: i) establishing the theoretical
foundation for constructing a VNF mapping plan for RAN slice recovery
optimization and ii) developing algorithms needed to map/embed VNFs
efficiently. In particular, we propose four efficient algorithms, including
Resource-based Algorithm (RBA), Connectivity-based Algorithm (CBA), Group-
based Algorithm (GBA), and Group-Connectivity-based Algorithm (GCBA) to solve
the resource allocation and VNF mapping problem. Extensive experiments are
also conducted to validate the robustness of RAN slicing via the proposed
algorithms.

###### Index Terms:

RAN slicing, VNF embedding, resource allocation.

##  I Introduction

A new network technology is critical to leverage high demands for diverse
vertical industry applications growing rapidly. In recent years, Radio Access
Network (RAN) slicing has become one of the most promising architectural
technologies for the forthcoming 5G era [1, 2]. RAN slicing completely
overturns the traditional model of a single ownership of all network resources
and brings a new vision where the physical infrastructure resources are shared
across many RAN slices. Each slice built on top of the underlying physical RAN
(substrate) is a separate logical mobile network, which delivers a set of
services with similar characteristics and is isolated from others [3, 4, 5].
Leveraged by network function virtualization (NFV), a RAN slice is constituted
by various virtual network functions (VNFs) and virtual links that are
embedded as instances on substrate nodes [6, 7]. RAN enforcement mechanisms
enable a highly efficient resource management service and maximizes the
resources configured [8]. Efficient resource allocation and VNF embedding
serve as one of the critical aspects in RAN slicing technologies [9, 10]. The
resource allocation and VNF embedding problem is considered under a variety of
constraints [8, 11].

Motivation. Due to the complexity of the RAN slicing, existing configuration
schemes111Some other works refer to them as RAN enforcement. in RAN slicing
just focus on resource allocation [12, 13, 14]. However, a RAN enforcement
problem, in fact, cannot be addressed by only considering the resource
allocation but also needs to consider the relation between the substrate
nodes. The relations between VNFs decide the ways in which the VNFs will be
mapped into the substrate nodes. In addition, because of the connection
between VNFs, then bandwidth requirement of the virtual links between VNFs
[15, 16] needs to be considered as well. None of existing work fully considers
above factors nor do they attempt to consider the interdependency property to
mitigate the impact of the configuration process on the entire network.

Figure 1: A high-level architecture for RAN slicing.

Contributions. In this work we propose a new RAN enforcement, namely RAN
slicing-configuration (RS-configuration) that overcomes the drawbacks of the
existing works to provide an optimal mapping plan for VNFs onto the substrate
network. In particular, the RS-configuration will provide an ordered set of
mappings of VNFs onto substrate nodes. The RS-configuration will consider not
only availability of substrate’s resources but also the interdependence
between all possible mappings. Specifically, this paper focuses on the
following aspects: i) we propose to develop the theoretical model for
constructing a RS-configuration for VNF mapping; ii) designing algorithms
needed for mapping VNFs efficiently; and iii) conducting extensive experiments
to validate the performance of the proposed model and algorithms.

Organization: We organize the paper as follows. In $\S$II, we introduce the
background of RAN Slicing. In $\S$III, the network model as well as the
research problem are presented. Details of the proposed resource allocation
algorithms are shown in $\S$IV. In $\S$VI, we discuss the experiment results.
Finally, we make key concluding remarks in $\S$VII.

##  II RAN Slicing and Current Challenges

In order to focus on discussing the involved algorithmic problems, we present
a generic architecture that is depicted in Fig. 1. The architecture in the
figure shows the interactions of one (or more) mobile network operator(s)
(MNOs) with multiple enterprises. The key aspect of RAN slicing is that the
role of the MNO is to coordinate and allocate resources of the substrate
network to ensure the harmonic coexistence of multiple RAN slices, while the
role of the enterprise is to place slice requests and then manage the provided
slices [17, 18, 19, 6]. In particular, to prepare for a new slice
initialization, the enterprise must first determine the required slice
functionality and resources needed for VNFs of the requested slice. It is
envisioned that slice templates will be available for the most common types of
services [20, 21, 22]. Thus, the enterprise may select the slice template that
fits its purpose and parameterize it according to its needs. More
specifically, a RAN slice that is independent from others consists of a set of
VNFs. Upon receiving requests from the enterprise, the MNO works with the “RS-
configuration” (RAN enforcement) to allocate the substrate network resources
(e.g., resource blocks in long-term evolution (LTE)) to VNFs and virtual links
between VNFs, and provide an appropriate mapping plan, according to the
proffered demand, RAN policy, connectivity, and available spectrum resources
of the substrate nodes, also called resource blocks (RBs).

There have been efforts to design algorithms for the RAN resource allocation
problem that tend to consider only the available resources of the substrate
network to design a mapping plan and disregard the VNF connectivity and
bandwidth requirements [23, 24, 25, 26]. Again, a mapping plan for VNFs will
not only hinge on substrate nodes resource allocation but also rely on the VNF
connectivity requirement and bandwidth requirements of the VNF links [15, 16,
27, 28] (see $\S$III-A for the details). In order to be able to support novel
services in a large-scale system, a more flexible and comprehensive RAN
configuration scheme is needed to embed VNFs in the substrate nodes.

Unfortunately, existing works [12, 13, 14, 29] consider constructing mapping
plans for VNFs by considering only available resources, and this may cause an
internal fragmentation in the available resources of the substrate network. In
other words, available resources are sufficient but not eligible for mapping
more VNFs onto the substrate nodes due to not meeting the bandwidth and
connectivity requirements [30, 31]. This step requires considerations of the
interdependency property in the RAN slicing and efficient algorithms for
mapping VNFs onto the substrate nodes. The algorithmic considerations of this
step are described in the following sections of this paper. Based on the
solution to this problem, the MNO can embed more VNFs in the substrate network
using SDN and NFV technology [6, 32].

##  III Network Model and Research Problem

In the following sections, the basic mathematical notations are initially
introduced and simple examples are used to present the key ideas behind the
proposed RS-configuration paradigm and illustrate its advantages over the
conventional resource allocation-based enforcement algorithm in $\S$III-A. We
then provide a general problem formulation and highlight the major objectives
of the proposed paradigm in $\S$III-B.

###  III-A Network Model: Basic Notations and Illustration

Given a substrate network $G^{S}=(N^{S},E^{S})$, let $N^{S}$ and $E^{S}$
denote the set of substrate nodes and links, respectively. Considering a node
$s\in N^{S}$, the total available resources at node $s$ is defined as
$\mathcal{R}_{s}$. Namely, any node $s$ in $N^{S}$ can allocate a maximum
amount $\mathcal{R}_{s}$ of resources to VNFs. A VNF in a specific slice is
not available and accessible by other network slices for the isolation purpose
[33, 34, 35].

Let $\mathcal{G}^{V}$ be the set of RAN slices running over the substrate
network $G^{S}$, where
$\mathcal{G}^{V}=\\{G^{V_{1}},G^{V_{2}},\ldots,G^{V_{\ell}}\\}$. For emphasis,
we will denote a single RAN slice as $G^{V_{i}}$ ($1\leq i\leq\ell$) and drop
$i$ when the context is clear. We define a RAN slice
$G^{V_{i}}=(N^{V_{i}},E^{V_{i}})\in\mathcal{G}^{V}$, where $N^{V_{i}}$ and
$E^{V_{i}}$ are the set of VNFs and the set of virtual links between VNFs,
respectively.

For any VNF $u\in N^{V}$, it needs an amount $\Re_{u}$ of available resources
at a substrate node to be embedded. For any virtual link $(u,v)\in E^{V}$, it
requires a bandwidth $b_{(u,v)}$ for data flows between VNF $u$ and VNF $v$.
Likewise, instead of making the entire substrate network $G^{S}$ available for
routing traffic of all data flows, we consider a more general case: we are
restricted to the substrate network $G^{S}$ with an available capacity
constraint matrix $\mathcal{C}$ for all substrate links $(s,t)\in E^{S}$,
which specifies the maximum bandwidth $\mathcal{C}_{(s,t)}$ that can be
allocated to all virtual links mapped onto $(s,t)$. We introduce a binary
mapping variable $\mathcal{M}^{u}_{s}$ to indicate the decision that the VNF
$u$ is mapped onto the substrate node $s$ when $\mathcal{M}^{u}_{s}=1$, and
$\mathcal{M}^{u}_{s}=0$ otherwise.

In the first place of setting up the network, all VNFs must be mapped
(embedded) onto substrate nodes. To ensure that all VNFs will be embedded, the
value of the binary mapping variable can be obtained as follows:
$\sum\limits_{s\in N^{S}}{\mathcal{M}_{s}^{u}}=1$ for all
$u\in\bigcup\limits_{i=1}^{\ell}{N^{{{V}_{i}}}}$. However, due to the limited
capacity at substrate nodes (available resources) and links (maximum
bandwidth), a VNF $u$ can actually be mapped onto a substrate node $s$ if the
available resources at $s$ are sufficient ($\Re_{u}\leq\mathcal{R}_{s}$) and
meet bandwidth and connectivity conditions such that
$b_{(u,v)}\leq\mathcal{C}_{(s,t)}$, $(s,t)\in E^{S}$ for all $s,t\in N^{S}$,
$v\in\mathcal{N}_{u}$, and $\phi^{v}_{t}=1$, where $\mathcal{N}_{u}$ is the
set of VNF $u$’s neighbors. In addition, we use a variable
$\psi_{(s,t)}^{(u,v)}$ to represent a simultaneous mapping of two VNFs $u$ and
$v$ onto two substrate nodes $s$ and $t$, respectively. In particular,
$\mathcal{M}_{s}^{u}+\mathcal{M}_{t}^{v}-\psi_{(s,t)}^{(u,v)}\leq 1$222Such
relations help avoid the quadratic constraint..

Fig. 2 shows an example of VNFs embedded in substrate nodes of the RAN
slicing. The substrate network consists of five base stations (BSs). Each BS
provides four resource blocks (RBs) (two frequency units during two-time
slots) to RAN slices. In the figure, there are also two RAN slices, and each
consists of various VNFs. Both slices utilize the same substrate cellular
network resources. We consider the VNF’s resource requirement, as each needs a
certain amount of resources at a substrate node to be embedded, where
$R_{u_{1}}=2$ RBs, $R_{u_{1}}=R_{p_{2}}=R_{p_{3}}$ and $R_{p_{2}}=1$ RB (25%
resources of a substrate node). In other words, if a VNF requires 25% of the
spectrum resources, the substrate node should make 25% of the RBs to the VNF.
In the figure, the solid link between any two VNFs in a slice indicates that
they are neighbors (e.g., $(u_{1},u_{2}),(p_{1},p_{2}),(p_{1},p_{3})$ and
$(p_{2},p_{3})$). Such a relation as above implies that for any VNF
$u\in\bigcup\limits_{i=1}^{\ell}{N^{{{V}_{i}}}}$, the target substrate nodes
that the VNFs can be embedded in must be the substrate nodes OR one of the
neighbors of the substrate nodes on which the VNFs neighbors are embedded.
This connectivity constrain make the VNF $u_{1}$ cannot be embedded in the
substrate node $s_{1}$ even though there are sufficient available resources.

As illustrated by the simple example above, existing works [36, 37, 38] that
focus on mapping VNFs by considering only the available resource of substrate
nodes may fail to fully embed all VNFs. Moreover, they cannot leverage the
maximum number of VNFs embedded, resulting in malfunction in RAN slices.
Therefore, it is vital to come up with efficient algorithms to handle this
resources allocation and embedding processes. The resources allocation
algorithms will allow us to attain higher flexibility and embedding
performance simultaneously, without needing further resources. To illustrate
how resources allocation are handled in this case, consider again the simple
example in Fig. 2 with a mapping plan to embed VNFs following a strict order.
The result is that all VNFs are successfully embedded in the substrate
network. We remark that the embedding algorithm should guarantee that all
mapped VNFs meet the bandwidth and connectivity requirements.

Figure 2: Resources allocation and embedding VNFs in a RAN slicing with a) a
random mapping and b) RS-configuration algorithms (best viewed in color).

###  III-B RS-Configuration: Research Problem

Clearly embedding VNF strategy will not only hinge on substrate nodes resource
allocation but also rely on the substrate connection set $E^{S}$ of the
substrate network and the bandwidth requirement of the virtual links between
VNFs. This is a key research challenge we will tackle in this paper. In
particular, for an RS-configuration in a cellular network, we would like to
explicitly account for the mapping plan of VNFs, with the goal of providing a
high performance for RAN slicing-based applications in terms of resources
allocation for embedding VNFs in substrate node. A high performance in this
stage is reflected through the number of successfully embedded VNFs. This is
in contrast to many existing studies where no recoverable and stable
performance is assured under failures for RAN slicing-based applications, nor
is any attempt made to mitigate the impact of the RAN configuration process on
the entire network. We observe that, in general, the enhanced embedding
performance is achieved at the expense of increased configuration units (more
mappings) of the substrate network resources for all RAN slices.

INSTANCE: Suppose we are given a substrate network $G^{S}=(N^{S},E^{S})$ with
a set of substrate nodes and links, respectively. Each substrate node $s\in
N^{S}$ can allocate to VNFs an amount $\mathcal{R}_{s}$ of resources. We
consider a general case: we are restricted to the substrate network $G^{S}$
with an available capacity constraint matrix $\mathcal{C}$ for all $(s,t)\in
E^{S}$, which specifies the maximum bandwidth $\mathcal{C}_{(s,t)}$ that can
be allocated to all virtual links mapped onto $(s,t)$. Also, a set of RAN
slices $\mathcal{G}^{V}=\\{G^{V_{1}},G^{V_{2}},\ldots,G^{V_{\ell}}\\}$ is
running over the substrate network $G^{S}$. For any VNF, $u\in N^{V_{i}}$
requires an amount $\Re_{u}$ of available resources at a substrate node to be
embedded. For any virtual link $(u,v)\in E^{V_{i}}$, it requires a bandwidth
$b_{(u,v)}$ for data flows between two VNFs $u$ and $v$.

QUESTION: Does a mapping plan ($\mathcal{MP}$) for all VNFs exist in the RAN
slicing, such that the number of successfully embedded VNFs is not less than
$k$? Mathematically, we formulate the following RS-configuration optimization
problem:

$\underset{\mathcal{M}^{u}_{s}}{\mathop{\text{maximize}}}\,\sum\limits_{s\in
N^{S}}{\sum\limits_{u\in\bigcup\limits_{i}^{\ell}{N^{{{V}_{i}}}}}{\mathcal{M}_{s}^{u}}}$
(1)

Here, the set of variables $\mathcal{MP}=\\{\mathcal{M}^{u}_{s}\\}$ represents
one possible mapping/embedding plan solution for VNFs in the RAN slicing. The
objective function is to maximize the total number of mappings of VNFs, which
means that the number of VNFs embedded is maximized. In addition, to ensure
that one VNF can only be mapped onto at most one substrate node, they must
meet the mapping convergence constraint at the first end $s$,
$\sum\limits_{t}{\sum\limits_{v}{\psi_{(s,t)}^{(u,v)}}}=\mathcal{M}_{s}^{u}$,
at the other end $t$,
$\sum\limits_{s}{\sum\limits_{u}{\psi_{(s,t)}^{(u,v)}}}=\mathcal{M}_{t}^{v},$
and at both ends simultaneously,
$\mathcal{M}_{s}^{u}+\mathcal{M}_{t}^{v}-\psi_{(s,t)}^{(u,v)}\leq 1,$ for all
$s,t\in N^{S}$, $u,v\in{{N}^{{{V}_{i}}}}$, and $\mathcal{M}_{s}^{u},$
$\mathcal{M}_{t}^{v},$ $\psi_{(s,t)}^{(u,v)}\in\\{0,1\\}$.

Apart from enhancing the embedding performance, we believe that latency is
another key performance metric that must be accounted for in the design of the
mapping plan for the RS-configuration. For example, delayed packets can cause
the TCP timeout, resulting in unnecessary packet retransmissions, thus
reducing overall application throughput. We, therefore, desire to bound the
bandwidth variability333Bounded bandwidth and bandwidth variability would help
the end host at the network layer to reorder packets before passing to the
transport layer. in the mappings of VNFs as follows:
$\sum\limits_{u,v\in\mathcal{G}^{V}|\mathcal{M}_{s}^{u}=\mathcal{M}_{t}^{v}=1}{{{b}_{(u,v)}}}\leq{{\mathcal{C}}_{(s,t)}}$
for all $(s,t)\in E^{S}$. Namely, the total allocated bandwidth on a substrate
link does not exceed its link capacity. Likewise, the available resources at
any substrate node $s$ must be sufficient, that is,
$\sum\limits_{u\in\mathcal{G}^{V}|\mathcal{M}_{s}^{u}=1}{\Re_{u}\leq\mathcal{R}_{s}}$
for all $s\in N^{S}$. On the other hand, to conserve the virtual connection
between VNFs, the mapping must also meet the connectivity constraint in which
for any mapping of a VNF $u$ onto a substrate node $s$ and the other VNF $v$
onto the other substrate node $t$, for all $(u,v)\in E^{V},$ $s$ and $t$ must
be physically connected in the substrate network, that is, $(s,t)\in E^{S}$.
Thus, the mapping plan achieves the goal of providing a good embedding
performance for RAN slicing.

###  III-C The Hardness of the RS-configuration Problem

In this section, we show the hardness of the RS-configuration problem by first
showing that a sub-problem of the RS-configuration, referred to as the Reduced
RS-configuration (RRS-configuration) problem, is NP-hard. The RRS-
configuration is the RS-configuration with $\ell=1$ that is there is only one
network slice in the network, and $|N^{S}|=1$ that is there is only one
substrate node in the network. The problem is illustrated as follows:

INSTANCE: Given a substrate node $s$ that can allocate to VNFs an amount
$\mathcal{R}_{s}$ of resources. Also, a RAN slice $\\{G^{V_{i}}$ is running
over the substrate node $s$. For any VNF, $u\in N^{V_{i}}$ requires an amount
$\Re_{u}$ of available resources at a substrate node to be embedded.

QUESTION: Does a mapping plan ($\mathcal{MP}$) for all VNFs exist in the RAN
slicing, such that the number of successfully embedded VNFs is not less than
$k$?

Lemma 1 is used to show that the RRS-configuration problem is NP-hard. We
first use the knapsack problem [39] to show the hardness of the RRS-
configuration problem. Then, the hardness of the RS-configuration problem is
provided in Theorem 1. The knapsack problem is illustrated as follows:

INSTANCE: Given a set $n$ items; each item $i$ ($i=1,\ldots,n$) has a value
$c_{i}>0$ and a weight $a_{i}>0$, and a knapsack with capacity $b$.

QUESTION: Does the knapsack can be filled with items so as to maximize the
total value of the items included in the knapsack?

###### Lemma 1

The RRS-configuration problem is NP-hard.

###### Proof:

In the knapsack problem, each item $i$ can be treated as a VNF $u\in
N^{V_{i}}$; the value $c_{i}$ can be considered as the value $\Re$ of each
VNF; the knapsack with a capacity $b$ is treated as the substrate node $s$
with the capacity $\mathcal{R}_{s}$ in the network; and if we consider each
item $i$ has a weight $a_{i}=1$, the knapsack problem is also a RRS-
configuration problem. We have that the knapsack problem is a sub-problem of
the RRS-configuration problem. Because the knapsack problem is NP-hard [39],
the RRS-configuration is also NP-hard. This completes the proof. ∎

###### Theorem 1

The RS-configuration problem is NP-complete.

###### Proof:

By Lemma 1, because the RRS-configuration problem, which is a sub-problem of
the RS-configuration problem, is NP-hard, the RS-configuration problem is,
therefore, NP-hard. In addition, it is clear that the RS-configuration problem
belongs to the NP class. We therefore have that the RS-configuration problem
is NP-complete. ∎

##  IV Resource Allocation Algorithms

Equation 1 lays out the RS-configuration optimization problem thereby giving a
better understanding of the design of the resource allocation algorithms which
achieve the given optimization. Since the RS-configuration optimization
problem is NP-complete (shown in section III-C), we propose two heuristic
frameworks to solve the investigated problem: 1) we focus on leveraging a good
embedding efficiency while maintaining the lowest possible time complexity,
and 2) we consider the embedding efficiency as the vital requirement, and then
try to maximize the number of embedded VNFs regardless the time complexity. In
the following sections, the first two algorithms (i.e. the Resource-based
Algorithm (RBA) and Connectivity-based Algorithm (CBA)) follow the first
heuristic class given above. On the other hand, the Group-Connectivity-based
Algorithm (GCBA) and Group-based Algorithm (GBA) seek to maximize the
embedding performance without being subject to a specific time constraint
function, thereby falling into the category of the second class of heuristic
approaches. As part of each algorithm subsection, an overview and pseudocode
are provided, along with a detailed description of the key idea behind the
designed algorithms for the orderings and metrics involved.

###  IV-A Resource-based Algorithm (RBA)

Given a substrate network $G^{S}=(N^{S},E^{S})$, the major challenge becomes
how to select available resources and allocate them to suitable VNFs to
achieve the highest number of embedded VNFs. In this section, we propose the
Resource-based Algorithm (RBA), which addresses the RS-configuration
optimization problem (equation 1) using a heuristic approach. The main idea is
to generate a mapping plan $\mathcal{MP}$ which provides good embedding
efficiency while achieving low computational complexity. RBA achieves the
heuristic by taking a greedy approach and prioritizing the embedding of VNF
$u$ based on resources (from highest to lowest) $\Re_{u}$ $\forall\ u\in
N^{V_{i}}$, to the substrate node with the highest available resources
$\mathcal{R}_{t}\ |\ \mathcal{R}_{t}\geq\Re_{u}\ \forall\ t\in N^{S}$. The key
idea behind this approach is to iteratively select the most demanding VNF (in
terms of resources) and find the substrate node which can host it.

Algorithm 1 Resource-Based Algorithm

Input: $G^{S},\mathcal{G}^{V}$
Output: $\mathcal{MP}$

1:Initializing an empty set of mappings: $\mathcal{MP}=\emptyset$.

2:Constructing a descending-order set $\mathcal{L}^{S}$ of substrate nodes
based on the available resource value
$\mathcal{R}_{t^{\prime}}\,\forall\,t^{\prime}\in N^{S}$.

3:Constructing a descending-order set $\mathcal{L}^{V}$ of VNFs on the basis
of Resources $\Re_{u^{\prime}}\ \forall\ u^{\prime}\in N^{V_{i}}$.

4:while $\mathcal{L}^{V}\neq\emptyset$ do

5: Let $u$ be an element in $\mathcal{L}^{V}$ with highest value $\Re_{u}$

6: EmbeddingVNF($u$, $\mathcal{L}^{S}$, $\mathcal{MP}$)

7: $\mathcal{L}^{V}=\mathcal{L}^{V}-\\{u\\}$

8:end while

9:return $\mathcal{MP}$

Given the substrate network $G^{S}$ and a set of RAN slices $\mathcal{G}^{V}$,
we follow the RBA with three main steps for generating the mapping plan
$\mathcal{MP}$ as follows:

  1. 1.

We first construct the prioritized set of VNFs $\mathcal{L}^{V}$ based on the
required resources (from highest to lowest).

  2. 2.

We then construct the descending-order set of substrate nodes
$\mathcal{L}^{S}$ based on available resources.

  3. 3.

We finally generate the mapping plan $\mathcal{MP}$ for embedding all VNFs in
$\mathcal{L}^{V}$ to the substrate nodes in $\mathcal{L}^{S}$.

As indicated in the algorithm 1, we first initialize the $\mathcal{MP}$ set,
the prioritized set of VNFs $\mathcal{L}^{V}$, and construct the descending-
order set of substrate nodes $\mathcal{L}^{S}$ in the first three lines of the
pseudocode. The procedure EmbeddingVNF handles step 3 i.e. the embedding
process, and is described in detail from lines 3–16. For a VNF $u$ and a
substrate node $t$ such that $u\in\mathcal{L}^{V}$ and $t\in\mathcal{L}^{S}$,
the embedding process is separated into two cases, 1) VNF $u$ has no neighbor
which is currently embedded onto a substrate node (lines 3–7), and 2) VNF $u$
has at least one neighbor which is currently embedded onto a substrate node
(lines 8–14).

The motivation behind the separation of the embedding process into different
cases is due to the different embedding constraints imposed upon a VNF in both
cases. In the case one, the VNF $u$ is only subject to the resource constraint
$\mathcal{R}_{t}\geq\Re_{u}$. This is because there are no existing neighbors
embedded onto the substrate network for the VNF $u$ to ensure connectivity and
bandwidth constraints for. Upon checking for the satisfaction of the resource
constraint in line 4, the embedding process is completed and the mapping
variable $\mathcal{M}^{u}_{t}$ is added to the mapping plan set $\mathcal{MP}$
(lines 5–6). In case two i.e. when $u$ has at least one neighbor embedded
onto a substrate node, the connectivity and bandwidth constraints need to also
be satisfied to embed a VNF onto a substrate node. Firstly, the connectivity
is achieved by constructing the descending-order set
$\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$, containing the substrate nodes onto
which the neighbors of $u$ ($\mathcal{N}_{u}$), and the common neighbors of
nodes in $\mathcal{N}_{u}$ are hosted (line 9). The representation of the set
$\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$ is expressed by the following
mathematical relation:

$\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}=\\{s_{i},\ldots,s_{j}\\}\bigcup\\{\mathcal{N}_{s_{i}}\bigcap\ldots\bigcap\mathcal{N}_{s_{j}}\\}\
|\ \mathcal{M}^{u_{p}}_{s_{q}}=1\ $ (2)

where $\mathcal{R}_{s_{i}}\geq\mathcal{R}_{s_{j}}$ for all
$u_{p}\in\mathcal{N}_{u}$ and $s_{q}\in\\{s_{i},\ldots,s_{j}\\}$. Once the set
$\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$ has been constructed, we select the
first substrate node $t_{i}$ in $\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$, which
satisfies the resource and bandwidth constraint to host the VNF $u$ (line 10).
If the substrate node $t_{i}$ exists, VNF $u$ is embedded onto $t_{i}$ and
$\mathcal{M}^{u}_{t_{i}}$ is added to $\mathcal{MP}$ (lines 11–13). Hence,
VNFs within RAN slices are embedded onto the substrate network and the mapping
plan $\mathcal{MP}$ is determined.

###  IV-B Connectivity-based Algorithm (CBA)

Algorithm 2 Connectivity-Based Algorithm

Input: $G^{S},\mathcal{G}^{V}$
Output: $\mathcal{MP}$

1:Initializing an empty set of mappings: $\mathcal{MP}=\emptyset$.

2:Constructing a descending-order set $\mathcal{L}^{S}$ of substrate nodes
based on the available resource value
$\mathcal{R}_{t^{\prime}}\,\forall\,t^{\prime}\in N^{S}$.

3:Constructing a descending-order set $\mathcal{L}^{V}$ of VNFs on the basis
of degree $|\mathcal{N}_{u^{\prime}}|\ \forall\ u^{\prime}\in N^{V_{i}}$.

4:while $\mathcal{L}^{V}\neq\emptyset$ do

5: Let $u$ be an element in $\mathcal{L}^{V}$ with highest value
$|\mathcal{N}_{u}|$

6: EmbeddingVNF($u$, $\mathcal{L}^{S}$, $\mathcal{MP}$)

7: $\mathcal{L}^{V}=\mathcal{L}^{V}-\\{u\\}$

8:end while

9:return $\mathcal{MP}$

While the set $\mathcal{MP}$ is obtained by RBA, we consider a second
algorithm, Connectivity-based Algorithm (CBA) that can be done with the same
computational complexity as well as can provide a better embedding
performance. The essential idea behind CBA is to consider the set of VNF
$\mathcal{L}^{V}$ based on the degree value $|\mathcal{N}_{v}|$ of all VNF
$v\in N^{V_{i}}$. This allows the VNF $v^{\prime}$ with the highest degree
value $|\mathcal{N}_{v^{\prime}}|$ to be embedded onto the substrate node $s$
which has the highest available resources $\mathcal{R}_{s}$ $\forall s\in
N^{S}$. The newly ordered set $\mathcal{L}^{V}$ would increase the possibility
of VNFs in the set $\mathcal{N}_{v^{\prime}}$ to be embedded onto the
substrate node set $\mathcal{N}_{s^{+}}$, where $\mathcal{N}_{s^{+}}$ denotes
the set of substrate node $s$ and its neighbors $\mathcal{N}_{s}$ such that
$\mathcal{N}_{s^{+}}=s\bigcup\mathcal{N}_{s}$

1:procedure EmbeddingVNF($u$, $\mathcal{L}^{S}$ $\mathcal{MP}$)

2: Let $t$ be an element in $\mathcal{L}^{S}$ with highest value
$\mathcal{R}_{t}$

3: if $\mathcal{M}^{v}_{s}=0\ \forall\ v\in\mathcal{N}_{u},s\in N^{S}$ then

4: if $\mathcal{R}_{t}\geq\Re_{u}$ then

5: $\mathcal{R}_{t}=\mathcal{R}_{t}-\Re_{u}$

6: $\mathcal{MP}=\mathcal{MP}\bigcup\\{\mathcal{M}^{u}_{t}\\}$

7: end if

8: else

9: Constructing $\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$, representing the
descending-order set of substrate nodes and their common neighbors, based on
the available resource value, onto which the substrate nodes are hosting $v$
$\forall\ v\in\mathcal{N}_{u}$

10: Let $t_{i}$ be the first element in $\mathcal{L}^{N_{u}}_{S^{+}}\ |\
b_{(u,u^{\prime})}\leq\mathcal{C}_{(t_{i},t_{j})}$ and
$\Re_{u}\leq\mathcal{R}_{t_{i}},\forall\ u^{\prime}\in\mathcal{N}_{u},\
t_{j}\in\mathcal{N}_{t^{+}_{i}}$, where $\mathcal{N}_{t^{+}_{i}}$ denotes the
set of $t_{i}$’s neighbors and itself.

11: if $\exists\ t_{i}$ then

12: $\mathcal{R}_{t_{i}}=\mathcal{R}_{t_{i}}-\Re_{u}$

13: $\mathcal{MP}=\mathcal{MP}\bigcup\\{\mathcal{M}^{u}_{t_{i}}\\}$

14: end if

15: end if

16: return $\mathcal{MP}$

17:end procedure

In algorithm 2, to obtain the mapping plan $\mathcal{MP}$ the process is still
hinged on the three main steps we presented in the previous section. However,
we try to improve the performance of the matching of the VNFs and substrate
nodes by using a different metric. Specifically, we construct the descending-
order set $\mathcal{L}^{V}$ based on the degree value $|\mathcal{N}_{v}|$ of
every VNF $v\in N^{V_{i}}$ rather than the resource value $\Re_{v}$ (line 3 in
the pseudocode of the algorithm 2). The following steps are similar to the
algorithm 1, the construction of the descending-order set of substrate nodes
$\mathcal{L}^{S}$ is executed in line 2 while the procedure EmbeddingVNF
determines the mapping plan set $\mathcal{MP}$.

###  IV-C Group-Connectivity-based Algorithm (GCBA)

In the later section ($\S$VI) we test the performance of all proposed
algorithms and it will be verified that the algorithm 1 and algorithm 2
provide a good embedding efficiency within a fair time complexity. However,
the RS-configuration’s objective function is not completely optimized due to
the heuristic for the RBA and CBA being subject to the constraint of a low
computational complexity. In this section we propose a high performance
algorithm, referred to as Group-Connectivity-based Algorithm (GCBA) to attain
the highest number of embedded VNFs, without being subject to the
computational complexity constraint. GCBA achieves a good performance by
considering VNFs in a specific list of clusters, namely $\mathcal{L}^{V}$. We
then find the best matching substrate group for a cluster set
$\mathcal{N}_{u_{i}^{+}}$ (refer to $\S$IV-B) $\forall\
\mathcal{N}_{u_{i}^{+}}\in\mathcal{L}^{V}$

Algorithm 3 Group-Connectivity-Based Algorithm

Input: $G^{S},\mathcal{G}^{V}$
Output: $\mathcal{MP}$

1:Initializing an empty set of mappings: $\mathcal{MP}=\emptyset$.

2:Constructing a descending-order (based on the size of each set) list of
clusters $\mathcal{L}^{V}$, where
$\mathcal{L}^{V}=\\{\mathcal{N}_{u_{i}^{+}},\ldots,\mathcal{N}_{u_{j}^{+}}\\}$
such that $\mathcal{N}_{u_{i}^{+}}\bigcap\mathcal{N}_{u_{j}^{+}}=\emptyset$.

3:while $\mathcal{L}^{V}\neq\emptyset$ do

4: Let $\mathcal{N}_{u_{i}^{+}}$ be the first element in $\mathcal{L}^{V}$

5: for $u\in\mathcal{N}_{u_{i}^{+}}$ do

6: EmbeddingGroup$(u,\mathcal{MP})$

7: end for

8: $\mathcal{L}^{V}=\mathcal{L}^{V}-\\{\mathcal{N}_{u_{i}^{+}}\\}$

9:end while

10:return $\mathcal{MP}$;

To embed the VNFs in a given cluster set ($\mathcal{N}_{u_{i}^{+}}$) onto the
appropriate substrate node, GCBA performs the three step $\mathcal{MP}$ set
generation process as follows:

  1. 1.

Firstly, we construct the descending-order list of VNF cluster sets
$\mathcal{L}^{V}$ based on the size of each cluster set.

  2. 2.

We then construct the ordered-set of substrate nodes $\mathcal{L}^{S}$ per VNF
$u$ such that $\mathcal{R}_{t}\geq\Re_{u}\ \forall\ t\in\mathcal{L}^{S}$ and
$u\in\mathcal{L}^{V}$.

  3. 3.

Finally, we embed the mutually exclusive cluster sets in $\mathcal{L}^{V}$ to
the substrate network.

As specified in algorithm 3, we construct the list of VNF cluster sets in line
2. This process is carried out by the iterative addition of the VNF cluster
head $v$ followed by its respective neighbor set $\mathcal{N}_{v}$. The
representation of the set $\mathcal{L}^{V}$ is expressed by the following
mathematical relation:

$\mathcal{L}^{V}=[\\{v_{i}\bigcup v^{\prime}_{i}\\},\\{v_{j}\bigcup
v^{\prime}_{j}\\},\ldots,\\{v_{k}\bigcup v^{\prime}_{k}\\}]\ $ (3)

where
$|\mathcal{N}_{v_{i}}|\geq|\mathcal{N}_{v_{j}}|\geq|\mathcal{N}_{v_{k}}|\
\forall\
v^{\prime}_{i}\in\mathcal{N}_{v_{i}},v^{\prime}_{j}\in\mathcal{N}_{v_{j}},$
and $v^{\prime}_{k}\in\mathcal{N}_{v+k}$ We construct the set of substrate
nodes $\mathcal{L}^{S}$, containing the substrate nodes which satisfy the
resource constraint $\mathcal{R}_{t}\geq\Re_{u}\ \forall\ t\in N^{S}$ and
$u\in\mathcal{L}^{V}$. To optimize the embedding performance, we define the
neighborhood resource cumulative property $x(T)$ for all VNFs and substrate
nodes in order to improve the selection process of the best possible substrate
node. Given a VNF $v$ and a substrate node $s\ \forall\ v\in\mathcal{L}^{V}$
and $s\in\mathcal{L}^{S}$, the $x(T)$ property for $v$ and $s$ is computed as
follows:

$\begin{gathered}v(T_{\Re})=\Re_{v}+\sum\limits_{v^{\prime}\in\mathcal{N}_{v}}{\Re_{v^{\prime}}},\\\
s(T_{\mathcal{R}})=\mathcal{R}_{s}+\sum\limits_{s^{\prime}\in\mathcal{N}_{s}}{\mathcal{R}_{s^{\prime}}}\end{gathered}$
(4)

In equation 4, the replacement of $x$ in $x(T)$ with $v$ and $s$ along with
addition of $\Re$ and $\mathcal{R}$ as subscripts to $T$, allows for greater
clarity while determining which element the $x(T)$ property is being computed
for. In procedure EmbeddingGroup, we evaluate the $x(T)$ property (lines 3–4)
after the embedding process is separated into two cases. For each case, the
substrate node is picked based on $x(T)$.

Specifically, we first compute the difference $s(T_{\mathcal{R}})-v(T_{\Re})$
(lines 6 and 11), after that the substrate node $s$, with the positive
difference value closest to $0$ is selected. In the case of only negative
differences, the substrate node with the smallest negative difference is
selected for embedding. The idea behind this metric (computing the difference)
is to find the substrate node $s$ with the highest probability of supporting
the VNF $u$ as well as the neighbor set $\mathcal{N}_{u}$. We select the
substrate node with the difference value closest to $0$ to minimize the
possibility of the available resources being wasted. In addition, prioritizing
the positive difference ensures maximum embedding (based on the resource
constraint) of all the VNFs $u^{\prime}$ in $\mathcal{N}_{u^{+}}$, for all
$\mathcal{N}_{u^{+}}\in\mathcal{L}^{V}$. Finally, if $\mathcal{L}^{V}$
consists of substrate nodes producing solely negative differences, the
substrate node with the smallest difference is chosen so as to increase the
probability of the maximum number of VNFs being embedded. The three steps to
obtain the optimal $\mathcal{MP}$ set are therefore completed, thereby
determining $\mathcal{MP}$.

###  IV-D Group-based Algorithm (GBA)

Similar to the algorithm 2’s improvement in the embedding efficiency as
compared to the algorithm 1, can we achieve a greater optimization over the
objective function in the RS-configuration (equation 1) in comparision to the
algorithm 3? We propose the Group-based Algorithm (GBA) to further enhance the
optimization. To achieve the enhanced optimization, we chance the basis of
ordering the set of VNFs $\mathcal{L}^{V}$. Instead of ordering the VNF
cluster sets based on the basis of the degree of cluster heads, descending-
order cluster sets are constructed, based on the the neighborhood resource
cumulative value ($x(T)$) of the cluster heads. In doing so, the cluster sets
with the greatest isolation of resources are embedded onto the substrate layer
first.

Algorithm 4 Group-Based Algorithm

Input: $G^{S},\mathcal{G}^{V}$
Output: $\mathcal{MP}$

1:Initializing an empty set of mappings: $\mathcal{MP}=\emptyset$.

2:Evaluate the value $v(T_{\Re})$ for all VNFs $v$ in $N^{V_{i}}$

3:Constructing a descending-order (based on the value of $v(T_{\Re})$) list of
clusters $\mathcal{L}^{V}$, where
$\mathcal{L}^{V}=\\{\mathcal{N}_{u_{i}^{+}},\ldots,\mathcal{N}_{u_{j}^{+}}\\}$
such that $\mathcal{N}_{u_{i}^{+}}\bigcap\mathcal{N}_{u_{j}^{+}}=\emptyset$.

4:while $\mathcal{L}^{V}\neq\emptyset$ do

5: Let $\mathcal{N}_{u_{i}^{+}}$ be the first element in $\mathcal{L}^{V}$

6: for $u\in\mathcal{N}_{u_{i}^{+}}$ do

7: EmbeddingGroup$(u,\mathcal{MP})$

8: end for

9: $\mathcal{L}^{V}=\mathcal{L}^{V}-\\{\mathcal{N}_{u_{i}^{+}}\\}$

10:end while

11:return $\mathcal{MP}$;

As shown in the algorithm 4, the step one (line 2) shows the improvement of
GBA comparing to GCBA. Steps two and three, similar to the algorithm 3, are
carried out with the help of the procedure EmbeddingGroup. The following steps
are strictly followed the three steps of the embedding process we discussed in
the earlier section. Hence, the $\mathcal{MP}$ set is obtained.

1:procedure EmbeddingGroup($u$, $\mathcal{MP}$)

2: Constructing a set $\mathcal{L}^{S}$ of substrate nodes such that
$\mathcal{R}_{t^{\prime}}\geq\Re_{u}\,\forall\,t^{\prime}\in N^{S}$.

3: Evaluate the value $s(T_{\mathcal{R}})$ for all substrate nodes $s$ in
$\mathcal{L}^{S}$

4: Evaluate the value $u(T_{\Re})$

5: if $\mathcal{M}^{v^{\prime}}_{t^{\prime}}=0\ \forall\
v^{\prime}\in\mathcal{N}_{u},t^{\prime}\in N^{S}$ then

6: Let $t$ be a substrate node in $\mathcal{L}^{S}$ with the minimum
difference $s(T_{\mathcal{R}})-u(T_{\Re})\ \forall\ s\in\mathcal{L}^{S}$

7: $\mathcal{R}_{t}=\mathcal{R}_{t}-\Re_{u}$

8: $\mathcal{MP}=\mathcal{MP}\bigcup\\{\mathcal{M}^{u}_{t}\\}$

9: else

10: Constructing $\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$, representing the set
of substrate nodes in $\mathcal{L}^{S}$ and their common neighbors, onto which
the substrate nodes are hosting $v^{\prime}$ $\forall\
v^{\prime}\in\mathcal{N}_{u}$

11: Let $t_{i}$ be a substrate node in $\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$
with the minimum difference $s^{\prime\prime}(T_{\mathcal{R}})-v(T_{\Re})$ and
$b_{(u,v^{\prime})}\leq\mathcal{C}_{(t_{i},t_{j})}\ \forall\
s^{\prime\prime}\in\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}},v\in\mathcal{N}_{u^{+}},v^{\prime}\in\mathcal{N}_{u},\
t_{j}\in\mathcal{N}_{t^{+}_{i}}$, where $\mathcal{N}_{t^{+}_{i}}$ denotes the
set of $t_{i}$’s neighbors and itself.

12: if $\exists\ t_{i}$ then

13: $\mathcal{R}_{t_{i}}=\mathcal{R}_{t_{i}}-\Re_{u}$

14: $\mathcal{MP}=\mathcal{MP}\bigcup\\{\mathcal{M}^{u}_{t_{i}}\\}$

15: end if

16: end if

17: return $\mathcal{MP}$;

18:end procedure

##  V Time Complexity

###### Theorem 2

The time complexity of the procedure EmbeddingVNF is bounded in
$O(|N^{V_{i}}|\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)$

###### Proof:

In the procedure EmbeddingVNF, the maximum number of VNF $u$’s neighbors is
$|N^{V_{i}}|-1$, so that it requires $O(|N^{V_{i}}|)$ to determine if the VNF
$u$ has a neighbor already embedded onto a substrate node. If the VNF $u$ has
at least one already embedded neighbor, the maximum number of substrate nodes
we have to check for satisfaction of the connectivity constraint is $|N^{S}|$.
Therefore, obtaining the substrate nodes in the set
$\mathcal{L}^{\mathcal{N}_{u}}_{S+}$ requires
$O(|N^{V_{i}}|^{2}\times|N^{S}|)$, since we consider each of the neighbors of
the VNF $u$ ($|N^{V_{i}}|-1$), the links between the VNF $u$ and the neighbors
of $u$ ($|N^{V_{i}}|-1$), and the substrate nodes which satisfy the
connectivity constraint for the VNF $u$ and it’s neighbors ($|N^{S}|$). To
achieve the descending-order sorting of the set
$\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$, we utilize the MergeSort mechanism
that requires $O(|N^{S}|\times\log{|N^{S}|})$ (best-worst case) to construct
the set $\mathcal{L}^{\mathcal{N}_{u}}_{S^{+}}$. Likewise, it requires
$O(|E^{V_{i}}|\times|E^{S}|)$ for checking the satisfaction of the bandwidth
constraint. Finally, for determining the substrate node which satisfies the
resource requirement, $O(|N^{S}|)$ is required. Hence the time complexity of
the procedure is given as
$O(|N^{V_{i}}|^{2}\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)$. ∎

###### Theorem 3

The time complexity of the RBA is bounded in
$O(|N^{V_{i}}|\times((|N^{V_{i}}|\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)))$

###### Proof:

In the RBA, the descending-order sorting of the set of substrate nodes
$\mathcal{L}^{S}$ requires $O(|N^{S}|\times\log{|N^{S}|})$. Similarly, to
construct the descending-order set of VNFs $\mathcal{L}^{V}$, requires
$O(|N^{V_{i}}|\times\log{|N^{V_{i}}|})$. Finally, the while loop iterates over
the VNFs in $\mathcal{L}^{V}$, and for each iteration, the procedure
EmbeddingVNF is executed. Considering that the number of VNFs in
$\mathcal{L}^{V}$ is $|N^{V_{i}}|$, the while loop requires
$O(|N^{V_{i}}|\times((|N^{V_{i}}|\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)))$
to determine the mapping plan. Hence, the time complexity of the RBA is given
as
$O(|N^{V_{i}}|\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.

∎

###### Theorem 4

The time complexity of the CBA is bounded in
$O(|N^{V_{i}}|\times((|N^{V_{i}}|\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)))$.

###### Proof:

In comparison to the theorem 3, the distinct preliminary step within the CBA
is the metric, based on which the set of VNFs $\mathcal{L}^{V}$ are sorted.
Regardless of the different metric, $O(|N^{V_{i}}|\times\log{|N^{V_{i}}|})$ is
still required to construct the set $\mathcal{L}^{V}$. The set of substrate
nodes $\mathcal{L}^{S}$ also requires $O(|N^{S}|\times\log{|N^{S}|})$ to be
constructed. Finally, the while loop (similar to the theorem 3) requires
$O(|N^{V_{i}}|\times((|N^{V_{i}}|\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)))$.
Therefore, the time complexity of the CBA is given as
$O(|N^{V_{i}}|\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.
∎

###### Theorem 5

The time complexity of the procedure EmbeddingGroup is bounded in
$O(|N^{V_{i}}|^{2}\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)$.

###### Proof:

In the procedure EmbeddingGroup, we first construct the set of substrate nodes
$\mathcal{L}^{S}$ which satisfy the resource constraint, requiring
$O(|N^{S}|)$. To evaluate the $s(T_{\mathcal{R}})$ property, we require to
traverse through a maximum of $|N^{S}|$ substrate nodes, and for each
substrate node the cumulative of $|N^{S}|$ substrate nodes (at maximum)
requires to be computed. Therefore, we require $O(|N^{S}|^{2})$ to compute the
$s(T_{\mathcal{R}})$ property for each substrate node in $\mathcal{L}^{S}$.
Likewise, to evaluate the $u(T_{\Re})$ property for the VNF $u$, we require
$O(N^{V_{i}})$. As shown in theorem 2, we require $O(|N^{V_{i}}|$ to determine
whether the VNF $u$ has a neighbor already embedded. Computing the differences
of the $x(T)$ property’s of the substrate nodes in $\mathcal{L}^{S}$ and the
VNF $u$ along with finding the substrate node $t$ with the minimum difference
would require $O(|N^{S}|)$. To construct the set
$\mathcal{L}^{\mathcal{N}_{u}}_{S+}$, $O(|N^{V_{i}}|^{2}*|N^{S}|)$ would be
required (similar to 2). Lastly, we consider the substrate node $t_{i}$ in
$\mathcal{L}^{\mathcal{N}_{u}}_{S+}$, with the minimum difference of the
$x(T)$ property’s of the substrate nodes (in
$\mathcal{L}^{\mathcal{N}_{u}}_{S+}$) and the VNF $u$, and satisfies the
bandwidth constraint. To obtain the substrate node $t_{i}$, we require
$O(|E^{V_{i}}|\times|E^{S}|)+O(|N^{S}|)$. Hence the time complexity of the
procedure is given as
$O(|N^{V_{i}}|^{2}\times|N^{S}|)+O(|E^{V_{i}}|\times|E^{S}|)$. ∎

###### Theorem 6

The time complexity of the GCBA is bounded in
$O(|N^{V_{i}}|^{2}\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.

###### Proof:

In the GCBA, to construct the set of VNF cluster sets $\mathcal{L}^{V}$,
requires $O(|N^{V_{i}}|\times\log{|N^{V_{i}}|})+O(|N^{V_{i}}|^{2})$. The while
loop iterates over the VNF cluster sets in $\mathcal{L}^{V}$, and each
iteration executes the for loop which iterates through the cluster sets
$N_{u_{i}^{+}}$. The procedure EmbeddingGroup is called within each iteration
of the for loop, thereby resulting in the requirement of
$O(|N^{V_{i}}|^{2}\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.
Therefore, the time complexity of the GCBA is given as
$O(|N^{V_{i}}|^{2}\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.
∎

###### Theorem 7

The time complexity of the GBA is bounded in
$O(|N^{V_{i}}|^{2}\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.

###### Proof:

In comparison to the theorem 6, GBA performs the sorting of the VNF cluster
sets based on the $x(T)$ property of the cluster heads. Even with the change
in the metric of sorting, the requirement
$O(|N^{V_{i}}|\times\log{|N^{V_{i}}|})+O(|N^{V_{i}}|^{2})$ remains. The nested
loop structure in the GBA requires
$O(|N^{V_{i}}|^{2}\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.
Therefore, the time complexity of the GBA is given as
$O(|N^{V_{i}}|^{2}\times((|N^{V_{i}}|^{2}\times|N^{S}|)+(|E^{V_{i}}|\times|E^{S}|)))$.
∎

##  VI Performance Evaluation

In this section, we present simulations to demonstrate our approaches’
efficiency by firstly implementing the proposed algorithms for constructing a
embedding plan for RS-configuration through simulations. It is expected that
the advantage of the algorithms will be manifested when the number of
successfully embedded VNFs is significant high.

We consider the RAN slicing consisting of one substrate network and a variety
of network slices. The number of network slices and the number of VNFs on each
slice are randomly generated depending on the test case (we will present the
details of setting in the following sections). The substrate network is
composed of a random number of substrate nodes representing the number of data
centers. Each is initialized with an amount of resources. It is feasible to
create different embedding scenarios in the simulations and validate the
simulation results. The first case is to test the feasibility of the proposed
algorithms under the normal network condition that can provide reasonable
resources for embedding VNFs into the substrate network, referred to as the
normal case. In this case, we generate the number of substrate nodes from the
interval $[60,100]$, each is initialized with an amount of resources selected
from the interval $[4,8]$. In terms of the network slice, the number of
network slices is randomly generated from the interval $[2,10]$ and the number
of VNFs on each slice is also randomly chosen based on the number of network
slices from the interval $[10,100]$.

In the second case, we generate the network topology with limited resources
that can test the performance of the proposed algorithms under the resource
shortage condition, referred to as the shortage case. In this case, network
resources are strictly controlled as follows: for the number of substrate
nodes, from the interval $[60,100]$; for the number of resources for each
substrate node, from the interval $[2,4]$; for the number of network slices,
from the interval $[2,10]$; and for the number of VNFs on each slice, from the
interval $[1,10]$. In the following sections, Fig. 3 and Fig. 5 show the
results in the “normal case” test, and Fig. 4 and Fig. 6 show the results in
the “shortage case” test.

###  VI-A Embedding Performance

Figure 3: Normal Case: total number of embedded VNFs when a) the number of
substrate nodes ranging from 60 to 140, b) number of VNFs ranging from 160 to
240, c) $k$-connected substrate network with degree ($k$) ranging from 2 to 10
per substrate node, and d) $k^{\prime}$-connected RAN slice with degree
($k^{\prime}$) ranging from 2 to 10 per VNF.

Figure 4: Shortage Case: total number of embedded VNFs when a) the number of
substrate nodes ranging from 60 to 140, b) number of VNFs ranging from 160 to
240, c) $k$-connected substrate network with degree ($k$) ranging from 2 to 10
per substrate node, and d) $k^{\prime}$-connected RAN slice with degree
($k^{\prime}$) ranging from 2 to 10 per VNF.

We first test the embedding performance of the proposed algorithms by
comparing the results in both normal and shortage case. Fig. 3 and Fig. 4 show
the performance of the proposed algorithms in terms of number of embedded VNFs
in the normal and shortage case, respectively.

Fig. 3 shows comparisons of the number of embedded VNFs when the number of
substrate nodes ranges from $60$ to $140$. In the figure, GBA and GCBA provide
the best performance with a higher total number of embedded VNFs. During the
embedding process, GBA and GCBA consider not only the required resources of a
single VNF but also we take into account of the required resources of a
cluster of VNFs. In addition, in the GCBA, we also consider the degree of VNFs
(number of neighbors) when determining the mapping plan. The concept of
cluster (interdependency) makes the GBA and GCBA to be the best in performing
embedding VNFs. The differences are reflected through the neighborhood
resource cumulative property $x(T)$ considered in both GBA and GCBA.

In Fig. 3 we test the performance of the proposed algorithms when the number
of VNFs ranging from $160$ to $240$. The results are similar to the Fig. 3 as
GBA and GCBA still demonstrate a better performance than the CBA and RBA in
terms of the total number of embedded VNFs. We realize that the higher the
VNFs in the substrate network, the higher the number of VNFs is successfully
embedded into the substrate network. It indicates that the algorithms perform
more efficiently when having more resources in the network (higher number of
VNFs).

Fig. 3 shows comparisons of the test performance of the algorithms proposed
for $k$, where $k$ denotes the degree of every substrate node in the substrate
network, which ranges from $2$ to $10$. In the figure, GBA and GCBA
demonstrate a better performance with a higher total number of embedded VNFs
when comparing to CBA and RBA. We also observe that the higher the degree of
substrate nodes, the higher the number of VNFs embedded in the substrate
network. In addition, there is higher efficiency in performance when the
degree of substrate nodes is increased.

In the Fig. 3 we analyze comparisons of the capability of the proposed
algorithms with different $k^{{}^{\prime}}$, in which $k^{{}^{\prime}}$
denotes the degree of VNFs in RAN slices ranging from 2 to 10. GBA and GCBA
continue to perform better when comparing CBA and RBA with the total embedded
VNFs. We can evaluate that the lower the degree of VNFs in a RAN slice, the
higher the number of VNFs successfully embedded in the substrate network. If
the VNFs have a higher degree of VNFs, they demonstrate a lower embedding
performance. In summary, the results in Fig. 3 show the performance of all
algorithms in the “normal case” test. We test the proposed algorithms using
different metrics, including varying the number of substrate nodes, changing
the number of VNFs, adjusting the degree of substrate nodes ($k$) and the
degree of VNF ($k^{\prime}$).

In Fig. 4 we test the performance of the proposed algorithms in the “shortage
case” test to see how the shortage resource condition impacts to the number of
VNF embedded in the network. Specifically, in Fig. 4 we compare the embedding
performance of the proposed algorithms to that the number of substrate nodes
ranging from $60$ to $140$. As shown in the figure, GBA and GCBA have the best
efficiency performance with a higher total number of embedded VNFs. As
mentioned in the previous analysis, both GBA and GCBA consider the
neighborhood resource cumulative property $x(T)$. In addition, in GBA we
evaluate the $x(T)$ for both virtual networks and substrate network while only
the substrate network is evaluated with the $x(T)$ in GCBA. These metrics make
GBA and GCBA perform better than CBA and RBA. In contrast, using CBA and RBA,
the embedding performance is lower with a lower number of embedded VNFs. Note
that for CBA and RBA, all VNFs are scheduled to be embedded by considering
only the embedding status of the individual VNFs resource or connectivity
constraint.

Fig. 4 shows the impact of the number of embedded VNFs with respect to the
number of VNFs ranging from $160$ to $240$. The total number of VNFs embedded
in the substrate network is higher in GBA and GCBA. Therefore, the efficiency
of RBA and CBA is lower as the total number of embedded VNFs is lower in the
substrate network. As the algorithms demonstrate a greater efficiency
performance when number of VNFs is increased. In the Fig. 4 we analyze
comparisons of the algorithms of number of embedded VNFs capability to $k$,
where $k$ denotes the degree of each substrate node, which ranges from $2$ to
$10$. GBA and GCBA exhibits a greater efficiency performance with a higher
total number of VNFs embedded in the substrate network whereas, RBA and CBA
have a lower total number of VNFs embedded in the substrate network. We
observe that the greater the degree of substrate nodes, the better the number
of VNFs embedded in the substrate network. It indicates that there is a
greater efficiency performance when the degree of substrate nodes is greater.
Fig. 4 shows comparisons of the total number of embedded VNFs to each
($k^{{}^{\prime}}$). The number of VNFs connected per RAN slice is denoted by
$k^{{}^{\prime}}$, ranging from $2$ to $10$. GBA and GCBA show a higher total
number of embedded VNFs in the substrate network. In contrast, RBA and CBA
have a fewer total number of embedded VNFs as they have a lower embedding
efficiency. In addition, the proposed algorithms demonstrate a lower embedding
performance when the degree of VNF is higher.

###  VI-B Resource Utilization Efficiency

Figure 5: Normal Case: total amount of available resources in the substrate
network when a) the number of substrate nodes ranging from 60 to 140, b)
number of VNFs ranging from 160 to 240, c) $k$-connected substrate network
with degree ($k$) ranging from 2 to 10 per substrate node, and d)
$k^{{}^{\prime}}$-connected RAN slice with degree ($k^{{}^{\prime}}$) ranging
from 2 to 10 per VNF.

Figure 6: Shortage Case: total amount of available resources in the substrate
network when a) the number of substrate nodes ranging from 60 to 140, b)
number of VNFs ranging from 160 to 240, c) $k$-connected substrate network
with degree ($k$) ranging from 2 to 10 per substrate node, and d)
$k^{\prime}$-connected RAN slice with degree ($k^{\prime}$) ranging from 2 to
10 per VNF.

In this section we conduct simulations to evaluate the algorithms in terms of
the resource utilization efficiency in both scenarios (normal case in Fig. 5
and shortage case in Fig. 6). Fig. 5 shows comparisons of the amount of
remaining resources of the substrate network ($G^{S}$) after finishing the
embedding process when the number of substrate nodes increasing from $60$ to
$140$. The figure illustrates that RBA and CBA have a lower amount of
remaining resources while committing a higher embedding performance as
demonstrated in Fig. 3. As explained in the Fig. 3 and Fig. 4, both RBA and
CBA consider the cluster of VNFs and substrate nodes during the embedding
process that helps leverage of not only embedding performance but also
resource utilization performance. In addition, CBA and RBA provide a fair
performance in terms of resource utilization with a lower time complexity.

Fig. 5 shows the impact of remaining resources of the substrate node ($G^{s}$)
with respect to the number of VNFs ranging from $160$ to $240$. As expected,
GBA and GCBA continue to show better embedding performance as seen in Fig. 3
while still consuming minimal amount of resources. In contrast to, CBA and
RBA, which have a slight decrease in the embedding efficiency even though,
both algorithms utilize high resources to embed VNFs to the substrate network.

Fig. 5 shows comparison of the remaining resources of the substrate node
($G^{S}$) with respect to $k$ where $k$ denotes the degree of each substrate
node in the substrate network, ranging between $2$ to $10$. In the figure, GBA
and GCBA still show superior performance invariably compare to CBA and RBA.
Moreover, Fig. 5 illustrates that as the degree of substrate node increases,
the number of embedded VNFs increases in the algorithms GBA and GCBA, with
still having a high amount of resources remaining, on the other hand RBA and
CBA consume high amount of resources, but still result in lower performance
efficiently.

Fig. 5 we analyze the comparisons of the proposed algorithms with different
$k^{{}^{\prime}}$ with respect to the remaining resources of each substrate
node , which $k^{{}^{\prime}}$ denotes the degree of VNFs in RAN slices
ranging from 2 to 10. GBA and GCBA continue to perform better when comparing
with CBA and RBA. As shown in Fig. 5 when the degree per substrate node is $2$
GBA and GCBA embed VNFs with as lower as $204$ remaining resources, but this
not the case with RBA and CBA as both algorithms even after having to consume
$254$ total resources still embed VNFs at a lower efficiently with comparison
to GBA and GCBA.

Fig. 5 shows comparisons of the amount of remaining resources of the substrate
network ($G^{S}$) after finishing the embedding process when the number of
substrate nodes increasing from $60$ to $140$. The figure illustrates that GBA
and GCBA have a higher amount of remaining resources while committing a higher
embedding performance as demonstrated in Fig. 3. As explained in the Fig. 3
and Fig. 4, both GBA and GCBA consider the cluster of VNFs and substrate nodes
during the embedding process that helps leverage of not only embedding
performance but also resource utilization performance. In addition, CBA and
RBA provide a fair performance in terms of resource utilization with a lower
time complexity.

Fig. 6 illustrates comparisons of the amount of remaining resources of the
substrate network ($G^{S}$) after completing the embedding process when the
number of substrate nodes are increased from $60$ to $140$. The figure
demonstrates that GBA and GCBA have a higher amount of remaining resources
while committing a higher embedding performance efficiency as shown in Fig. 6.
As described in the Fig. 3 and Fig. 4, both GBA and GCBA during the embedding
process consider not only the required resources of a single VNF but also take
into consideration of the required resources of a cluster of VNFs. GBA and
GCBA, therefore, provide a better performance in terms of resource utilization
with a fair time complexity.

In the Fig. 6 we analyze comparisons of the algorithms capability in terms of
the remaining resources in the substrate node ($G^{S}$) with respect to the
number of VNFs ranging from $160$ to $240$. As expected both GBA and GCBA
still continue to show better performance efficiency while embedding the VNFs
with high remaining resources. In contrast to CBA and RBA performing slightly
towards the lower end in terms of the embedded VNFs, on the other hand
consuming high resources to embed the VNFs.

Fig. 6 shows the performance of the proposed algorithms when varying the
amount of remaining resources in the substrate nodes ($G^{S}$) with respect to
$K$ which denotes the degree of the substrate node in the substrate network
from $60$ to $140$. The performance of GBA and GCBA still shows a higher
result, when compare to both CBA and RBA having a lower performance
efficiency. Moreover, we can see that the higher the amount of remaining
resources in the substrate network, higher is the embedding performance of GBA
and GCBA while having the amount of remaining resources high.

Fig. 6 shows comparisons of the remaining resources in the substrate network
($G^{S}$) with respect to $k^{{}^{\prime}}$, which denotes the degree of VNFs
in an RAN slice, ranging from $2$ to $10$. GBA and GCBA show a higher total
number of embedded VNFs in the substrate network. In contrast, RBA and CBA
have a lower number of total embedded VNFs. As expected by this mechanism, GBA
and GCBA embed more VNFs with still having high remaining resources, on the
other hand CBA and RBA while taking more resources to embed have a lower
embedding efficiency. In summary, Fig. 6 evaluations show that the comparisons
of shortage case in Fig. 6 – Fig. 6 in terms of amount of remaining resources
in the substrate network($G^{S}$) when varying the substrate nodes, VNFs, $k$,
and $k^{{}^{\prime}}$. GBA and GCBA consistently provide a better performance
in terms of amount of resource utilization than RBA and CBA.

##  VII Conclusion

In this paper we have established the theoretical foundation for using RS-
configuration to construct a VNF embedding plan for the RAN slicing. We have
formulated the efficient resource allocation as an essential problem with the
objective to maximize the total number of embedded VNFs. To solve the RS-
configuration problem, we have introduced four efficient algorithms (RBA, CBA,
GCBA and GBA) and show theoretical analyses to demonstrate the efficacy of the
algorithms. Extensive simulation results have been provided to evaluate the
performance of the proposed algorithms using different metrics in terms of the
embedding performance and resource utilization performance. We have created
different scenarios to test the algorithms, including considering the network
under the normal condition (normal case) and under the resource shortage
condition (shortage case). Through the results of the simulations, GBA and
GCBA consistently demonstrate a better performance for both embedding VNFs and
utilizing the network’s resources when comparing to RBA and CBA. However, in
terms of the time complexity RBA and CBA demonstrate as faster algorithms with
lower time complexity while remaining fair embedding VNFs and resource
utilization performances.

## ACKNOWLEDGEMENT

This research was supported in part by the US NSF grant CNS-2103405.

## References

  * [1] C. Marquez, M. Gramaglia, M. Fiore, A. Banchs, and X. Costa-Perez, “How should i slice my network? a multi-service empirical evaluation of resource sharing efficiency,” in _Proceedings of the 24th Annual International Conference on Mobile Computing and Networking_ , ser. MobiCom ’18, 2018, p. 191–206.
  * [2] X. Foukas, M. K. Marina, and K. Kontovasilis, “Orion: Ran slicing for a flexible and cost-effective multi-service mobile network architecture,” in _Proceedings of the 23rd Annual International Conference on Mobile Computing and Networking_ , ser. MobiCom ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 127–140. [Online]. Available: https://doi.org/10.1145/3117811.3117831
  * [3] X. Foukas, G. Patounas, A. Elmokashfi, and M. K. Marina, “Network slicing in 5g: Survey and challenges,” _IEEE Communications Magazine_ , vol. 55, no. 5, pp. 94–100, 2017.
  * [4] T. Taleb, B. Mada, M. Corici, A. Nakao, and H. Flinck, “Permit: Network slicing for personalized 5g mobile telecommunications,” _IEEE Communications Magazine_ , vol. 55, no. 5, pp. 88–93, 2017.
  * [5] P. L. Vo, M. N. H. Nguyen, T. A. Le, and N. H. Tran, “Slicing the edge: Resource allocation for ran network slicing,” _IEEE Wireless Communications Letters_ , vol. 7, no. 6, pp. 970–973, 2018.
  * [6] H. Zhang, N. Liu, X. Chu, K. Long, A. Aghvami, and V. C. M. Leung, “Network slicing based 5g and future mobile networks: Mobility, resource management, and challenges,” _IEEE Communications Magazine_ , vol. 55, no. 8, pp. 138–145, 2017.
  * [7] C. Sun, J. Bi, Z. Zheng, H. Yu, and H. Hu, “Nfp: Enabling network function parallelism in nfv,” in _Proceedings of the Conference of the ACM Special Interest Group on Data Communication_ , ser. SIGCOMM ’17, 2017, p. 43–56.
  * [8] D. Mascarenas, E. Flynn, C. Farrar, G. Park, and M. Todd, “A mobile host approach for wireless powering and interrogation of structural health monitoring sensor networks,” _IEEE Sensors Journal_ , vol. 9, no. 12, pp. 1719–1726, Dec 2009.
  * [9] W.-C. Ke, B.-H. Liu, and M.-J. Tsai, “Efficient algorithm for constructing minimum size wireless sensor networks to fully cover critical square grids,” _IEEE Transactions on Wireless Communications_ , vol. 10, no. 4, pp. 1154–1164, April 2011.
  * [10] S.-R. Qi, “The solution of problem about fermat point in application of the modern pipeline design,” _Electronic and Mechanical Engineering and Information Technology (EMEIT), 2011 International Conference on_ , vol. 7, pp. 3785–3788, Aug 2011.
  * [11] R. Mittal and M. P. S. Bhatia, “Wireless sensor networks for monitoring the environmental activities,” _Computational Intelligence and Computing Research (ICCIC), 2010 IEEE International Conference on_ , pp. 1–5, Dec 2010.
  * [12] H. Halabian, “Optimal distributed resource allocation in 5g virtualized networks,” in _2019 IFIP/IEEE Symposium on Integrated Network and Service Management (IM)_ , 2019, pp. 28–35.
  * [13] A. Ksentini and N. Nikaein, “Toward enforcing network slicing on ran: Flexibility and resources abstraction,” _IEEE Communications Magazine_ , vol. 55, no. 6, pp. 102–108, 2017.
  * [14] M. R. Rahman and R. Boutaba, “Svne: Survivable virtual network embedding algorithms for network virtualization,” _IEEE Transactions on Network and Service Management_ , vol. 10, no. 2, pp. 105–118, 2013.
  * [15] T. Kuo, B. Liou, K. C. Lin, and M. Tsai, “Deploying chains of virtual network functions: On the relation between link and server usage,” in _IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications_ , 2016, pp. 1–9.
  * [16] Fangxin Wang, Ruilin Ling, J. Zhu, and D. Li, “Bandwidth guaranteed virtual network function placement and scaling in datacenter networks,” in _2015 IEEE 34th International Performance Computing and Communications Conference (IPCCC)_ , 2015, pp. 1–8.
  * [17] P. Rost, C. Mannweiler, D. S. Michalopoulos, C. Sartori, V. Sciancalepore, N. Sastry, O. Holland, S. Tayade, B. Han, D. Bega, D. Aziz, and H. Bakker, “Network slicing to enable scalability and flexibility in 5g mobile networks,” _IEEE Communications Magazine_ , vol. 55, no. 5, pp. 72–79, 2017.
  * [18] S. Vassilaras, L. Gkatzikis, N. Liakopoulos, I. N. Stiakogiannakis, M. Qi, L. Shi, L. Liu, M. Debbah, and G. S. Paschos, “The algorithmic aspects of network slicing,” _IEEE Communications Magazine_ , vol. 55, no. 8, pp. 112–119, 2017.
  * [19] V. Sciancalepore, K. Samdanis, X. Costa-Perez, D. Bega, M. Gramaglia, and A. Banchs, “Mobile traffic forecasting for maximizing 5g network slicing resource utilization,” in _IEEE INFOCOM 2017 - IEEE Conference on Computer Communications_ , 2017, pp. 1–9.
  * [20] N. Nikaein, E. Schiller, R. Favraud, K. Katsalis, D. Stavropoulos, I. Alyafawi, Z. Zhao, T. Braun, and T. Korakis, “Network store: Exploring slicing in future 5g networks,” in _Proceedings of the 10th International Workshop on Mobility in the Evolving Internet Architecture_ , ser. MobiArch ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 8–13. [Online]. Available: https://doi.org/10.1145/2795381.2795390
  * [21] X. Zhou, R. Li, T. Chen, and H. Zhang, “Network slicing as a service: enabling enterprises’ own software-defined cellular networks,” _IEEE Communications Magazine_ , vol. 54, no. 7, pp. 146–153, 2016.
  * [22] B. Chatras, U. S. Tsang Kwong, and N. Bihannic, “Nfv enabling network slicing for 5g,” in _2017 20th Conference on Innovations in Clouds, Internet and Networks (ICIN)_ , 2017, pp. 219–225.
  * [23] S. D’Oro, F. Restuccia, and T. Melodia, “Toward operator-to-waveform 5g radio access network slicing,” _IEEE Communications Magazine_ , vol. 58, no. 4, pp. 18–23, 2020.
  * [24] M. Richart, J. Baliosian, J. Serrat, and J. Gorricho, “Resource slicing in virtual wireless networks: A survey,” _IEEE Transactions on Network and Service Management_ , vol. 13, no. 3, pp. 462–476, 2016.
  * [25] R. Trivisonno, R. Guerzoni, I. Vaishnavi, and A. Frimpong, “Network resource management and qos in sdn-enabled 5g systems,” in _2015 IEEE Global Communications Conference (GLOBECOM)_ , 2015, pp. 1–7.
  * [26] Y. Jia, H. Tian, S. Fan, P. Zhao, and K. Zhao, “Bankruptcy game based resource allocation algorithm for 5g cloud-ran slicing,” in _2018 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2018, pp. 1–6.
  * [27] S. Schneider, M. Peuster, and H. Karl, “A generic emulation framework for reusing and evaluating vnf placement algorithms,” in _2018 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN)_ , 2018, pp. 1–6.
  * [28] W. Fang, M. Zeng, X. Liu, W. Lu, and Z. Zhu, “Joint spectrum and it resource allocation for efficient vnf service chaining in inter-datacenter elastic optical networks,” _IEEE Communications Letters_ , vol. 20, no. 8, pp. 1539–1542, 2016.
  * [29] S. D’Oro, F. Restuccia, A. Talamonti, and T. Melodia, “The slice is served: Enforcing radio access network slicing in virtualized 5g systems,” _Proc. of IEEE Conference on Computer Communications (INFOCOM)_ , 2019.
  * [30] H. Hawilo, A. Shami, M. Mirahmadi, and R. Asal, “Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc),” _IEEE Network_ , vol. 28, no. 6, pp. 18–26, 2014.
  * [31] P. T. A. Quang, A. Bradai, K. D. Singh, G. Picard, and R. Riggio, “Single and multi-domain adaptive allocation algorithms for vnf forwarding graph embedding,” _IEEE Transactions on Network and Service Management_ , vol. 16, no. 1, pp. 98–112, 2019.
  * [32] K. Katsalis, N. Nikaein, E. Schiller, A. Ksentini, and T. Braun, “Network slices toward 5g communications: Slicing the lte network,” _IEEE Communications Magazine_ , vol. 55, no. 8, pp. 146–154, 2017.
  * [33] G. I. Team, “5g white paper,” _NGMN Alliance, Frankfurt, Germany, White Paper Version 1.0_ , p. 1–125, 2015.
  * [34] A. I. Swapna, R. V. Rosa, C. E. Rothenberg, I. Sakellariou, L. Mamatas, and P. Papadimitriou, “Towards a marketplace for multi-domain cloud network slicing: Use cases,” in _2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS)_ , 2019, pp. 1–4.
  * [35] N. Omnes, M. Bouillon, G. Fromentoux, and O. L. Grand, “A programmable and virtualized network it infrastructure for the internet of things: How can nfv sdn help for facing the upcoming challenges,” in _2015 18th International Conference on Intelligence in Next Generation Networks_ , 2015, pp. 64–69.
  * [36] R. Wen, G. Feng, J. Tang, T. Q. S. Quek, G. Wang, W. Tan, and S. Qin, “On robustness of network slicing for next-generation mobile networks,” _IEEE Transactions on Communications_ , vol. 67, no. 1, pp. 430–444, 2019.
  * [37] A. Baumgartner, T. Bauschert, A. M. C. A. Koster, and V. S. Reddy, “Optimisation models for robust and survivable network slice design: A comparative analysis,” in _GLOBECOM 2017 - 2017 IEEE Global Communications Conference_ , Dec 2017, pp. 1–7.
  * [38] R. Wen, J. Tang, T. Q. S. Quek, G. Feng, G. Wang, and W. Tan, “Robust network slicing in software-defined 5g networks,” in _GLOBECOM 2017 - 2017 IEEE Global Communications Conference_ , 2017, pp. 1–6.
  * [39] D. Pisinger, “Where are the hard knapsack problems?” _Computers & Operations Research_, vol. 32, no. 9, pp. 2271–2284, 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S030505480400036X