# VNF Placement Optimization at the Edge and Cloud +
## 6 Results and Discussions
### Experiment 1: Tabu Search Evaluation  
In this experiment, we try to find the optimal configuration of the TS algorithm to provide solutions with low deployment cost. The default configuration of the TS components are set as follows: (i) random initial solution, (ii) neighborhood of one VNF, (iii) tabu list size of 10, and (iv) 1000 iterations as our termination criterion. In the following experiments, we use this default configuration and we only change the component under consideration.  
Figure 5 illustrates that the initial solution can impact the overall deployment cost. Specifically, the more sophisticated the initial solution, the better the results. For example, the Random initial solution provides the worst deployment cost, while the Joint approach (placing VNFs in neighboring servers and interconnect the VNFs) presents the best. By selecting the servers with the highest availability (Sorted), we can get a solution in between these two extremes. This reveals that providing as input to the local search mechanism an initial solution with a lower cost can help the TS algorithm to converge to a better overall solution. It is worth noting that, even though the Joint solution is the most computational intense approach, the execution-time overhead is relatively small since it is executed only once at the beginning of the algorithm.  
Regarding the neighborhood, as illustrated in Figure 6, for movements of one VNF at each iteration of the Local Search, we can have better results. As the neighborhood grows (for example, more VNFs), the results get worse. The reason is that moving only one VNF to a new server can help the TS algorithm to escape from local optima easier. In contrast, moving two VNFs or the whole SC at each iteration does not help the algorithm avoid a local optima, since we cannot efficiently explore the search space of available solutions. In order to perform a detailed exploration of the search space, a higher number of iterations would be needed, which would significantly increase the execution time. To this end, as our goal is to propose an algorithm that can reduce the execution time in comparison to MIP, we adopt the \"One VNF\" neighborhood approach.  
Figure 5: Impact of initial solution in Tabu Search.  
As a third step of the fine tuning of the TS algorithm, we evaluate the impact of the Tabu List size. Figure 7 shows that, with a Tabu List of size 10, we can achieve the highest cost reduction. For a small sized Tabu List, we do not efficiently restrict the TS to not cycle into previously explored solutions, which can affect the overall deployment cost. On the other hand, if we utilize a large sized Tabu List, we significantly eliminate the search space and the available neighborhood of each VNF. For example, if a neighbor solution of a current solution is the optimal one but we select a different one from the available neighborhood, then we eliminate the algorithm to not find it for at least 15 iterations.  
As a final performance tuning step, we evaluate the impact of the termination criterion to the overall solution. We evaluate how the cost evolves as we increase the total number of iterations from 200 to 2000 with a step of 200. As Figure 8 illustrates, as we increase the number of iterations, a more refined final solution can be extracted. However, after 1400 iterations, the algorithm converges to a local optimum and no further improvements can be achieved. To this end, in the following experiment, we configure the TS algorithm to use a Joint initial solution, with a single movement of a VNF as the neighbor solution, a Tabu List with size 10, and 1400 iterations for our termination criterion.  
Figure 6: Impact of the Neighborhood of Local Search in Tabu Search.  
Figure 7: Impact of the Tabu list size in Tabu Search.