# The Value of Simple Heuristics for Virtualized Network Function Placement
## 2 Related Work  
NFEP can be solved via using mathematical methods or by designing a heuristic algorithm. Although mathematical models provide an optimal solution, they are complex and proven to be NP-hard [2]. The alternative is to design a heuristic that can provide near-optimal solutions with less computational demand and near optimal performance. Although there is (potentially) some performance loss (in our case the acceptance rate of new requests) between the heuristic algorithms and direct solving method, heuristic algorithms have advantage in computational complexity when solving large-scale network optimization problems [3]. There exists a wide range of heuristics proposed for VNF placement. The proposed methods are designed based on the objectives of their authors. Our goal here is to design a heuristic that can place (ideally) as many requests as the mathematical model while reducing the resource consumption by SGs. Here we review recently proposed heuristics that provide novel methods for mapping SGs' NFs to a physical network and compare them in terms of their complexity and performance. The heuristic proposed by the authors of [4] breaks a SG into the NFs and the links connecting them. The proposed multi-stage algorithm finds all possible options for each NF and defines a cost for each option based on the cost of traveling from previously placed NFs to the current NF according to the path it should take. The algorithm runs in \(\theta(n^{2}m)\) where \(n\) is the number of nodes in the physical network and \(m\) is the number of NFs per SG. The use of a multi-stage algorithm may make it easier to find a solution for placing each NF but the solution does not minimize the cost for the whole SG. The results are not compared against a simple version of the proposed solution to demonstrate how breaking the problem into sub-problems and the other considered parameters contributes to the reported results. In another example, the authors of [5] used Dynamic Programming (DP) to organize the problem into smaller interdependent sub-problems of placing each VNF and the virtual link connected to it towards the next VNF. The solutions for the sub-problems are then aggregated to compose the overall chain placement. Similar to [4; 5] breaks the problem of SG placement into the placement of each NF and the virtual link connected to it. However, providing a solution that \begin{table}
\begin{tabular}{c c} \hline
**Acronym** & **Description** \\ \hline BW & Bandwidth \\ \hline CI & Confidence Interval \\ \hline CAPEX & Capital Expenditure \\ \hline DP & Dynamic Programming \\ \hline FACE & Fast and Cost-Efficient \\ \hline ILP & Integer Linear Programming \\ \hline LFGL & the Least-First-Greatest-Last \\ \hline LP & Linear Programming \\ \hline MA & Markov Approximation \\ \hline NF & Network Function \\ \hline NFEP & Network Function Embedding Problem \\ \hline NFV & Network Function Virtualization \\ \hline OPEX & Operational Expenditure \\ \hline SG & Service Graph \\ \hline SLFL & Simple Lazy Facility Location \\ \hline VNF & Virtualized Network Function \\ \hline \end{tabular}
\end{table} 
Table 1: List of acronyms. minimizes the resource consumption by a NF and the link connected to it does not ensure that the final solution minimizes the cost of the whole SG placement. In [5] there is a lack of evaluations against very simple placement approaches. Finally, in another similar approach we have a three step placement algorithm proposed in [6]. The proposed algorithm in [6] first computes the list of physical node candidates for each VNF, then sorts them based on the number of physical node candidates for placement in increasing order. In the last step, the heuristic computes the placement cost of that VNF and its virtual link to the physical network and chooses the one with the lowest cost. The same problem arises here as the placement focuses on placement of each NF instead of the whole SGs.