# The Value of Simple Heuristics for Virtualized Network Function Placement
## 2 Related Work
The results in [6] are not compared against a simpler version of the provided heuristic such as the one that starts from the first NF of the SG instead of sorting the NFs based on their number of candidates. Such a comparison would demonstrate how this step of the algorithm contribute to improving the results. The authors in [7] break the placement problem into placing NFs and connecting them. In the first step, the proposed heuristic in [7] places the NFs based on their resource demand. The heuristic in [7] gives priority to the NF with the highest demand and place it in the cheapest node of the network. The value of each node is obtained from a formula that considers the available resource capacity, the price for each resource unit, and the ability to connect to other nodes. The placed NFs then connect through the available shortest path. Although the proposed algorithm considers multiple factors in obtaining a node for placement of NFs it does not consider the whole chain of NFs in its placement and may end up taking a path much longer than the shortest path from source to destination. Ref. [8] proposes an algorithm that considers NF placement, routing, and the traffic changing affect of NFs. The proposed heuristic is based on the observation that some NFs can increase a flow's BW, e.g., by adding authentication headers, or decrease a flow's BW by compressing, filtering, etc. The Least-First-Graetest-Last (LFGL) algorithm proposed in [8] starts from the NFs that decrease the BW usage and uses the Dijkstra algorithm to identify the closest node to the source. The LFGL algorithm then places the NFs decreasing the traffic rate in the closest node to the source until there is no space and then advances to the second closest node and so on. The process of placement is the same for the increasing BW usage NFs, except it starts from the destination node and places the NFs increasing the BW usage closer to the destination. The endpoints of the first and the second stage of the placement are then connected through a shortest path. The LFGL heuristic assumes that we have the freedom to re-organize the order of NFs within a SG. This may not be realistic, as in most cases the order of NFs cannot be changed (once a flow is encrypted, for example, it would become difficult to filter it based on payload attributes). The results in [8] do not provide a comparison between LFGL and a simpler version of the proposed heuristic to show the effectiveness of the considered parameters. In designing a heuristic the challenge is to consider the parameters that can improve the performance of an algorithm and avoid the ones that only complicate the model. [9] proposes a solution called Simple Lazy Facility Location (SLFL) that optimizes the placement of VNF instances in response to on-demand workload. Upon new demand arrival, a combination of installation, migrations, and reassignments can be applied to optimize the placement [9]. In each case, the cost of migrating the already deployed VNF, installing the new VNF instance, or adding to the already deployed VNFs are being compared with each other and the one with the lowest cost will be considered. Although it is mentioned that SLFL runs in polynomial time, its execution time is not reported. A performance comparison between SLFL and a model that places the NFs randomly does not show the effect of the parameters considered in the heuristic on the number of accepted requests. The heuristic algorithm proposed in [10] works based on the centrality matrix. The centrality for each node in [10] is defined as the sum of the total size of flows which have their shortest path going through that node. They assume that the source and destination of all flows are known and determine the node that has the most total traffic volume passing through. The main goal of the algorithm in [10] is to activate fewer licenses of a certain type of NF.