# The Value of Simple Heuristics for Virtualized Network Function Placement
## 5 Conclusions  
One main challenge in the use of NFVs is to optimally map the SG requests to the physical network. As optimal placement methods are NP-hard and cannot be applied to large networks, we have to design a heuristic with lower complexity that is scalable and can reach near optimal results. Although there exists a wide range of heuristics proposed for VNF placement, none has focused on design a _simple_ heuristic that is time efficient and hence scalable. We explored four heuristics, ranging from very simple to more complex, involving backtracking, in order to identify the simplest possible method that can place a high number of requests in the network in a timely manner.  
We compared the performance of our four heuristics with a mathematical model and a popular heuristic proposed in the literature. Our results show that randomly placing NFs, as expected, produces poor results (low acceptance rate, high costs). So some effort is warranted in placing NFs. However, and somewhat unexpected, the simple shortest path heuristic can reach similar results as more complex heuristics. Additional steps, added to the all shortest paths and the FACE heuristic, do not increase the number of accepted requests. Even more complex heuristics such as the accessible scope heuristic [13] do not improve the acceptance rate. In fact, as shown in Figure 6, all these approaches provide, statistically speaking, the same performance as an optimization model. However, as shown in Table 2, the simpler the heuristic, the faster its execution time. The simplest shortest path heuristic can process a newly arriving flow in a few milliseconds in a network of 100 nodes, arguing for its scalability and suitability for real-time admission control.  
We explored the effect of increasing BW and nodal resources on the performance of each heuristic. However, we kept the request arrival rate and network density constant. Going forward, we will more thoroughly evaluate and compare the performance of the various heuristics as we vary these parameters as well, resulting in networks that are more lightly or highly loaded.  
We also plan to explore possible ways to improve the performance of the shortest path heuristic. Baed on the results presented here, improving the heuristic in a scenario where we process flow arrivals one at a time by more selectively placing NFs among candidate nodes will be of limited benefit. However, in [5] we already showed that considering already placed flows jointly with a new flow arrival (placement request) may result in more accepted requests overall. While that work used small networks and the optimization model, we plan to extend this to the heuristic approaches as well. The added complexity of such an approach is that such an approach potentially moves some of the already placed NFs. We therefore would need to consider which NFs can be moved and at what cost. This \"reconfiguration costs\" needs to be considered in a complete solution. Jointly considering multiple requests will also increase the heuristic's execution time, potentially limiting its scalability.  
Conceptualization, T.K.; investigation, Z.J.; methodology, T.K.; project administration, T.K.; software, Z.J.; writing--original draft, Z.J.; writing--review & editing, T.K. All authors have read and agreed to the published version of the manuscript. This research was funded by the Natural Sciences and Engineering Research Council of Canada (NSERC), under a Discovery Grant on \"SDN-Enabling Multihop Wireless Networks\". The authors declare no conflict of interest.