# The Value of Simple Heuristics for Virtualized Network Function Placement
## 2 Related Work
At each iteration, the algorithm compares the cost of activating a new NF in the node with the highest centrality with the cost of the flow traversing through already placed NFs and only activates a new one if it decreases the placement cost. Ref. [11] propose different heuristics and compares their performance in terms of the maximum number of requests that can be placed in a network. Between the proposed heuristics in [11] only one, named heuristic-A, is not combined with a proposed mathematical model. Heuristic-A places requests one by one along the shortest path between source and destination. The other heuristics, heuristic-B, B+, B+COR, and C are all being combined with the mathematical model to reduce their execution time. As the proposed mathematical model in [11] aims at solving the placement problem for all flows at once, the flows are divided into the groups. These heuristics start from the first group and solve the optimization problem for this group. Based on the solution, the problem is updated again and being solved for the next group. Heuristic B randomly groups the requests, heuristic C is the same as B but also consider minimizing the number of used cores in the network. Heuristic B+COR sorts nodes in ascending order based on the number of flows passing through them. Less crowded nodes are selected first to distribute the load away from bottleneck nodes. It is stated that B+COR can place more requests in the network in comparison to other proposed heuristics. However, [11] did not compare the execution time of the models and only considered the maximum number of the flows that each heuristic can place in the same network. As we will show later in our results, the more complex heuristics combined with a mathematical model may bring better results in terms of the number of accepted requests but suffer from high execution time and therefore are not applicable to large scale networks. Another attempt in simplifying the problem of VNF placement is to reduce the complexity of the mathematical model by reducing the size of the search space. One example is the heuristic proposed in [12]. A sampling-based Markov approximation (MA) approach is proposed in [12] to solve the NP-hard problem which requires a long convergence time. The method begins with a random feasible solution and iterates the process of transformation from the current solution to another feasible solution until the steady-state distribution of the Markov chain appears. To reduce the execution time, the solution space is reduced to a subset of randomly chosen nodes that satisfy the resource demands of a request. It is been stated that the problem can be solved in polynomial time but the execution time of the algorithm is not being reported or compared with other proposed heuristics with similar time complexity. Additionally, the subset of nodes could be chosen based on more sophisticated parameters to reach a near optimal solution faster. Another example is [13], where the proposed heuristic narrows the target search space of VNF placement by introducing a smaller accessible scope to which the possible locations of VNFs are confined. The requests are categorized based on their source and destination. The nodes with lowest sum of distance from source and destination are in the accessible scope of the request. The size of each accessible scope for each set of requests is proportional to the total traffic volume of those requests. It is shown in [13] that the size of the accessible scope will impact the time efficiency and performance of the NF placement. Considering all nodes to be in the accessible scope will not reduce the execution time but will provide the acceptance ratio of the optimization model. On the other hand, a very small accessible scope will decrease the execution time but also the acceptance ratio. This approach considers the whole SG and its source and destination. Unlike previous heuristics it does not choose the reduced search space randomly.