# The Value of Simple Heuristics for Virtualized Network Function Placement
## 4 Modeling Environment and Results
### Results  
In order to evaluate the relative performance of our heuristics and to determine the time it takes to solve the placement problem, we designed three scenarios. * In a first scenario, we applied our heuristic models to wireless multi-hop networks of increasing size to evaluate their performance in terms of the time it takes to solve the placement problem and their success in placing the requests. To benchmark our results, we applied the Integer Linear Programming (ILP) model for wireless multi-hop networks introduced in [1] to the same topologies and the same set of requests as our heuristic models. We compared our results with the accessible scope heuristic proposed in [13] that we reviewed earlier. * In a second scenario, we focus on the first four proposed heuristics and apply them to a larger size network of 100 nodes to compare their performance in terms of the number of accepted requests, average cost, and execution time. In this scenario, we maintain the number of nodes and increase the available links' BW. * In a third scenario, similar to the second scenario, we compare the performance of our proposed heuristics as resource availability changes. Here we increase the nodal resource of the nodes while keeping the number of nodes constant at 100. In this scenario, in addition to comparing the relative performance of the proposed heuristics, we can also identify the impact of increasing nodal resources on the number of accepted requests. Figure 6 shows the average number of accepted requests and their 95 % Confidence Intervals (CI) for a simulated network lifetime of 20,000 s. We applied our 4 heuristics, the accessible scope heuristic, and the ILP model to the same physical networks and the same set of requests. We increased the number of nodes from 20 to 30 and 40 nodes. For each network size, we repeated the experiment 10 times with different network topologies, averaged the number of accepted requests and calculated the corresponding 95 % CI. The most surprising part of the results is that the average number of accepted requests is almost the same for all heuristics, except for the random placement strategy. The differences in the average acceptance rates, as indicated by the 95 % confidence intervals, are not statistically significant. It may seems counter-intuitive that, for a 30 node network, the ILP has a slightly lower average acceptance rate than the accessible scope heuristic. However, as we have shown in [1], accommodating placement requests one at a time (as we did here) will impact future placement requests. In this case, ILP successfully placed a request along nodes on a non-shortest path. This reduced available resources, preventing the placement of subsequent requests. The shortest path  
heuristics would have failed to place such a request, resulting in more resources remaining available to place future requests. While the four heuristics are quite different in terms of their level of complexity, the shortest path heuristic can place the same number of requests as the complicated accessible scope heuristic or even FACE. All the steps added to our heuristic after the focusing on (a randomly determined) shortest path do not improve the number of accepted requests. However, these steps add complexity and as we can see in Table 2 increases the execution time. For a 40 node network, applying an optimization model takes almost 10 times as long as the accessible scope heuristic, 100 times longer than FACE, and almost 1000 times longer than the simple shortest path heuristic. Randomly placing network functions in the network actually takes longer (in our implementation), as we repeatedly need to discover shortest paths between consecutively placed NFs. In a network where such information is readily available, for example in the centralized controller of an SDN architecture, randomly placing NFs and placing them in a best-effort manner along the shortest path between source and destination would have approximately the same, minimal, time complexity.