# The Value of Simple Heuristics for Virtualized Network Function Placement
## 4 Modeling Environment and Results
### Results
We also collected the execution times for the 4 simpler heuristics for a 100 node network. Again, the results clearly show the superior performance of the simple shortest path heuristic. The time listed here (2.3 s) is the average time to process all arriving requests. With, on average, four requests arriving per 100 time units, and the simulations running for 20,000 time units, we process approximately 800 requests in 2.3 s, so each request individually takes slightly less than 3 ms. This indicates quite clearly that this heuristic scales well for larger networks, allowing processing arriving new flows in real time. Unlike more complex approaches, the execution time of our simple heuristic is related to the number of nodes in the shortest path, not the number of nodes in the network. Figure 6: Average number of accepted requests. The advantage of the simple shortest path heuristic is that it provides a total number of accepted requests close to the optimization model in a timely manner. The all-shortest path and FACE heuristic incur a pre-processing step to calculate all shortest paths for all possible source and destinations in the network. This is a one-time process and does not depend on the number of requests. We excluded this one time calculation of all shortest paths for all pairs of nodes from their execution time. However, in case of dynamic topologies, we may have to run these steps multiple times, potentially each time a new request arrives. Limiting the placement heuristic to a shortest path will not eliminate the optimal placement in most cases. Over 97 % of the requests are being placed along a shortest path by the optimization model. However, this focus on the shortest path(s) results in a huge decrease in the execution time of all heuristics compared to the optimization model. In terms of the average cost, as the number of accepted requests are similar for heuristics that use a shortest path for placement of the NFs, we end up with more or less the same BW costs. The only potential difference would be the impact of interference, which only the last three approaches explicitly consider during the placement process. However, at least for the results presented here, this impact made little difference overall. In the second scenario, we apply our 4 proposed heuristics to a 100 nodes network. We chose a network with 100 nodes in order to have more shortest paths available for each pair of nodes in comparison to smaller networks and be able to compare the performance of the all-shortest path and FACE with the one that only considers one shortest path. We vary the uniform distribution that the physical links' BW is chosen from to model increased bandwidth availability. The intervals are [300, 400], [500, 600], [700, 800], [900, 1000], [1000, 1100]. As can be seen from Figure 7, the average number of accepted requests increases as we increase the initially available links' BW. The x-axis is labeled by the beginning of each BW interval. We can observe that the average number of accepted requests remains similar for all heuristics (except for the random placement). High consumption of BW due to the presence of interference makes BW a bottleneck for NF placement in wireless multi-hop networks. Increasing the available BW will mitigate the impact of this bottleneck, and increased the number of accepted requests uniformly for all heuristics. As discussed above, for each simulation run, we have about 800 flow arrivals. If we increase the bandwidth sufficiently (to at least 900 units per link), essentially all flows can be accommodated, independent of the heuristic, as long as NFs are place on a shortest path between source and destination. Finally, in the last scenario, for a network of 100 nodes, we increase the nodal resource by increasing the uniform distribution that the nodal resource is chosen from. The intervals are [1000, 1100], [2000, 2500], and [3000, 3500]. Figure 8 shows the acceptance ratio, again the x-axis is labeled by the beginning of each nodal resource interval.