# VNF Placement Optimization at the Edge and Cloud +
## 4 Algorithm Design
### Tabu Search Algorithm  
Even though MIP formulations can provide the optimal solution, they are characterized by an increased complexity that can lead to computational intractability, especially for large scale experimentation. To this end, we adopt the Tabu Search (TS) algorithm to model the VNF-PEC problem. TS is a meta-heuristic approach that applies local search to provide solutions very close to optimality [49]. In contrast with other heuristics and meta-heuristics, TS can avoid being trapped in a local optimum by incorporating a short-term memory, called Tabu List. In general, the TS algorithm is comprised of five components: (i) the Initial Solution; (ii) the Neighbor Solution; (iii) the Tabu List; (iv) the Aspiration Criterion; and (v) the Termination Criterion. These components are appropriately adapted for our problem and are described in detailed as follows, while the pseudocode for our TS implementation is provided in Algorithm 1:  
* Generate Initial Solution: The initial solution is the starting point for the TS algorithm. In this work, three different initial solutions are examined. First, a random initial solution \(F_{0}\) is applied. For each VNF in the SC \(s_{k}^{i}\in S^{i}\), a random server \(n\in N\) is selected. In the second solution, we sort the available Edge and Cloud servers according to their capacity. Finally, in the third solution, we select the server with the highest capacity. If we cannot place the whole SC, we place the rest of the VNFs to neighboring servers, with the goal to jointly place the VNFs of the SC and interconnect them to minimize the propagation delay. In all cases, the selected server needs to satisfy both the resource capacity requirements and location constraints. For the interconnection of VNFs possibly residing on different servers, a shortest path algorithm is used. In the following, we set this initial solution as our best solution \(F^{*}:=F_{0}\) and current solution \(F:=F_{0}\) (lines 1-2 of Algorithm 1). * Neighborhood Solution: This component actually defines the movement from a current solution \(F\) to a new solution \(F^{{}^{\prime}}\) in the neighborhood of \(F\), \(P(F)\) (lines 5-6 of Algorithm 1). It is essentially a local search mechanism for finding local improvements of the solution. In this particular work, we define three different neighborhoods. In the first case, a neighbor solution is a simple type of movement of one random VNF of the SC \(s_{k}^{i}\) to a new server \(n^{\prime}\in N\), while in the second case the neighbor solution is provided by moving jointly two consecutive VNFs of an SC to a new server \(n^{\prime}\in N\). In the third case, we randomly reallocate all the VNFs of the SC. It should be noted that we do not restrict to move only to feasible solutions, since it is sometimes desirable to explore all parts of the search space [49]. * Tabu List: The Tabu List \(J\) is actually a short-term memory of the local search and contains the few last transformations performed on the current solution. Before applying a local search improvement, TS algorithm checks the Tabu List in order to avoid using a solution that has been recently selected. This way: (i) it prevents the algorithm for cycling into previous explored solutions; (ii) it facilitates the algorithm to move from local optima and explore other parts of the search space. In our implementation, for every VNF \(s_{k}^{i}\), we explore the impact of the length of the tabu list \(J_{k}\) in the final solution by taking into consideration the last five, ten, or fifteen movementsof the VNFs on different servers (lines 10-13). If the \(J_{k}\) list is full, the first element of the list is removed (e.g., the oldest value in the list) (line 12). * Aspiration Criterion: The aspiration criterion revokes a tabu, when a tabu move does not necessarily lead to cycling or to a restriction of the search space. Thus, in our implementation, the aspiration criterion is to allow a tabu move only if the new solution provides a lower cost than the current best solution.