related-works.tex

In this section, we review the works that have been done on service chain deployment and resource assignment in NFV, and mainly focus on the works that consider management requirements of chains.

\subsection{Resource Allocation in NFV}
The service chain deployment problem specially for virtual mobile core network functions has recently received substantial attention in the literature \cite{GilHerrera2016}\cite{Laghrissi2019}\cite{Bhamare2016}.
This problem is composed of two main steps: allocating computing and memory resources for virtual machines to run the chains' virtual network functions and assigning network resources to the chains' virtual links \cite{Laghrissi2019}. 
Various versions of this problem with different objective functions and considering wide range of constraints have been investigated in the literature \cite{Laghrissi2019}.
Placement problem has many variations and we concentrate on VNF Placement with VNF Chain Placement. There are many different objectives
like minimizing the deployment cost, increasing profit, minimizing the resource usage and etc. \cite{Laghrissi2019}\cite{Bhamare2016}
Also there are many other variations to Chain Placement Problem such as online, dynamic, schedule and etc. \cite{1608.00095}

From the objective function standpoint, deployment of service chains can be optimized for different goals.
One of the most common category is the approaches that utilize SFC deployment as a tool to maximize the business profit of the infrastructure provider \cite{Eramo2016}\cite{Eramo2017}\cite{TahmasbiNejad2018}\cite{Huang2019}.
In these approaches, the objective is to maximize the revenue gained by accepting SFC requests while minimizing the cost of physical servers and links \cite{Bouet2015}\cite{Pham2020}\cite{Huang2019}, the cost of VNF images and licenses \cite{Bouet2015}.
Energy-awareness is another objective that has been considered in SFC deployment problem \cite{Eramo2017}\cite{Eramo20172}\cite{Farkiani2019},
wherein, it is aimed to minimize the power footprint of the infrastructure provider by turning off the unused servers and links via green networking techniques, e.g., traffic consolidation \cite{Zheng2020}.
While QoS requirements are typically considered as the constraints of the SFC deployment problem, some work have optimized QoS metrics, e.g., delay and congestion, as the objective function of the problem  \cite{Huang2019}\cite{Yu2017}\cite{Chen2017}.
Finally, it is worth to note that there are plenty of work in the literature that aimed to optimize multiple objectives simultaneously, e.g., load balancing and reconfiguration overheads \cite{Qu2020}, ...

The constraints of the SFC deployment problem are the second differentiating factor of the existing work on this problem.
The required computing resources for virtual functions and bandwidth for virtual links of chains as well as the limited capacity of the infrastructure network resources are the most basic constraints in the SFC problem \cite{TahmasbiNejad2018}\cite{Eramo2016}\cite{Huang2019}.
In addition to these basic constraints, some more realistic assumptions as well as QoS requirements of chains have also been considered.
While VNFs are software images, their processing capacity is typically limited by software implementation issues and license beside the underlying hardware capacity;
these limitations was considered in \cite{Luo2020}.
Authors also took into account different QoS requirements of service chains, for example end-to-end delay \cite{Yu2017}\cite{Yaghoubpour2019} and reliability \cite{Yu2017}\cite{Torkamandi2019}\cite{Khezri2019}.
Finally, it should be noted that management requirements of service chains are another important category of constraints, which have received a little attention yet \cite{AbuLebdeh2017}\cite{AbuLebdeh20172}\cite{Chiang2019}.
We will elaborate it in the following subsection.

Several solution methods have been utilized to approach the SFC deployment problem.
Mainly, the problem is formulated as a Mixed Integer Linear Programming (MILP) model; and since it is NP-Hard \cite{Eramo2016}\cite{Ma2017}, various approaches have been proposed to tackle its complexity.
Optimization theory techniques like decomposition methods and Lagrangian relaxation methods were proposed \cite{Liu2017}\cite{Farkiani2019}\cite{1709.04772}.
Another category is the solutions based on meta-heuristic algorithms, e.g., Tabu search, genetic algorithm, and ... \cite{AbuLebdeh2017}.
The problem specific heuristic algorithms are also very common \cite{Ghaznavi2017}\cite{Bari2015}\cite{Eramo2016}.
Available information about demands is another important issue in solution approaches.
In off-line approaches, it is assumed that whole demands are known at the beginning, while in on-line solutions, demands arrive one-by-one \cite{Alhussein2020}.

Until now, we briefly reviewed the work on general SFC deployment problem; interested readers can refer to \cite{Laghrissi2019} for more details.
In comparison to previous works, here, we consider profit maximization as the objective function, formulate the problem as MILP model, and use Tabu search to solve it.
However, in addition to computation and bandwidth requirements, we consider the management requirement which have not investigated in the literature except very few studies that are discussed in the following. 

\subsection{Management Resources in NFV}
As already mentioned, this work considers management requirements in SFC deployment. To the best of our knowledge, work \cite{AbuLebdeh2017}, its next work \cite{AbuLebdeh20172}, and reference \cite{Chiang2019} are the only ones that consider VNFM and other management resources in SFC deployment.

In \cite{AbuLebdeh2017}, the authors studied the problem of VNFM placement in a distributed NFV infrastructure under the assumption that chains have already been deployed and consequently, the location of VNFs are known.
The objective function of the VNFM placement problem is to minimize the operational costs which is composed of life cycle management cost, compute resources cost, migration cost, and reassignment cost. Delay constraint on management links is also considered. The authors used Tabu search algorithm 
to find a polynomial solution. They start from a feasible placement, and in each step, they improve VNFM placement by doing reassignment, relocation, bulk reassignment, and deactivation. While this is the first work that investigated the management resource assignment in NFV, it does not \textit{jointly} deploy SFCs and VNFMs. 

In \cite{AbuLebdeh20172}, authors extended their previous work \cite{AbuLebdeh2017}, and solve the VNFO placement problem.
Authors consider the same system model as \cite{AbuLebdeh2017}, but here they aim to place VNFO and VNFM jointly to  minimize operational cost as defined in \cite{AbuLebdeh2017}. They propose a two step placement algorithm that first place VNFOs and then place VNFMs, which use Tabu search method. That paper also assumes that SFCs have already been deployed.

In \cite{Chiang2019}, authors consider autonomy for VNFMs, so they select their managed VNFs dynamically. The authors use game theory to achieve a distributed solution to the VNFM Placement Problem as described in \cite{AbuLebdeh2017}. In that paper, again it is assumed that the location of VNFs are given and VNFM placement is the only problem.

To conclude, as discussed, the previous work on management resource in NFV, are based on the system model of \cite{AbuLebdeh2017} wherein it is assumed that service chains are deployed beforehand. But, here, we aim to \textit{jointly} optimize SFC deployment and SFC placement. Moreover, we consider license cost for VNFM instances and in our model, each physical node has its specific list of nodes that can run its VNFM that provides a great flexibility for implementing management policies.