# The Value of Simple Heuristics for Virtualized Network Function Placement
## 1 Introduction  
The use of Network Function Virtualization (NFV) can bring advantages and challenges at the same time. One of the main challenges is the optimized placement of the virtualized functions based on the characteristics and available resources of the network [1]. In most cases, Virtualized Network Functions (VNF) form a chain of Network Functions (NF) with predefined parameters that are referred to as a Service Graph (SG) [1]. The placement of all NFs in a SG is a Network Function Embedding Problem (NFEP). NFEP is defined as mapping the Virtual Network Functions (VNF) and the links between them to the physical network. NFEP can be solved by modeling it as an optimization problem that can be solved using different Linear Programming (LP) solvers/tools [1]. Such optimization models are proven to be NP-hard and are not scalable. The alternative solution is to design a heuristic that can provide near-optimal solutions with lower complexity. While there have been numerous proposed heuristics for NFEP in wired and wireless networks, the focus has mostly been on providingresults close to an optimal solution. Consequently, the proposed heuristics became quite complex and highly time-consuming for larger networks, limiting their scalability. In contrast, in this paper, we explore _simple_ heuristics and their benefits/drawbacks. We aim to design a heuristic that is as simple as possible, allowing it to be time-efficient/scalable and therefore applicable to larger networks. We are particularly interested in the case of multi-hop wireless networks, with their more severe bandwidth-constraints, but believe that the insights from this work could also apply to other networks where NFs have to be placed, such as data centre networks, wired access networks, or the next generation of cellular networks. To design a simple heuristic we break our design process into four heuristics that each include one more parameter than the previous heuristic. The following briefly summarizes the four heuristics. * Random placement: The first heuristic places NFs randomly in the network and connects the source and destination of the request to the NFs based on their order in the SG via a shortest path. This heuristic can be used as a benchmark to show the worst result that can be expected, placing NFs randomly. * Shortest path placement: The second heuristic considers the shortage of BW in wireless multi-hop networks due to the presence of interference. This heuristic first finds a shortest path between source and destination of a request by using the Dijkstra algorithm and places NFs along the shortest path based on their order in the service graph. * All shortest path placement: The third heuristic considers the probability of having more than one shortest path and chooses the one with more nodal resources along the path. The main idea here is to increase the chance of placing the current request successfully. In this heuristic, we rank the shortest paths based on their available nodal resources and select the one ranked first. NFs will be placed along the chosen shortest path based on their order in the SG. * Fast and Cost-Efficient (FACE) placement: The fourth and last heuristic is named FACE. FACE uses the same method as the all shortest path heuristic to choose a shortest path but places NFs differently. In placing the NFs, FACE gives priority to the one that has fewer options for placement. We compare the results gathered from the four mentioned heuristics, an optimization model, and an alternative heuristic. The collected results show that the optimization model has highest execution time in comparison to all explored heuristics. However, it can reach the best results in terms of number of accepted requests. Our comparison between heuristics shows that the shortest path heuristic can place as many requests as the more complex ones with comparable cost.