# VNF Placement Optimization at the Edge and Cloud +
## 5 Experimentation Environment  
To model and evaluate our approach, we used and extended a discrete event java-based simulator called simulator for controlling virtual infrastructures (CVI-SIM) [50]. The particular simulator enables the evaluation of resource allocation approaches in the existence of single or multi-provider cloud infrastructures. CVI-SIM allows for modelling the physical infrastructure along with the control and management plane for more realistic scenarios. It further supports various probabilistic distributions to model the end-user requests.  
In order to model the VNF-PEC problem, we created three different infrastructures representing the cloud, edge, and transport networks. To create and interconnect these infrastructures, the JUNG library was used that facilitates the modelling of the various networks as graphs. The JUNG library generates random graphs using the erdos-renyi model, while the simulator guarantees the repeatability of the experimental set up by setting up a specific seed at the beginning of the execution.  
The SCs are also modeled as graphs using the JUNG library, while they belong under the IoT layer package of the CVI-SIM. In the same package, the IoT devices are also modeled including their requirements, their association with the IoT applications, their inter-arrival time, and their lifetime distribution.  
Another package of the CVI-SIM includes the VNF placement algorithms. In the above section, we have already presented the theoretical aspects of the VNF-PEC algorithms along with their mathematical formulation and pseudocode. However, in this part of the paper, we provide a more complete description of the proposed algorithms and optimization approaches, including their technical aspects and how they were executed in the CVI-SIM simulator.  
Regarding MIP approaches, they are characterized by an increased complexity. In addition, for the VNF Placement problem, the MIP approach is characterized as an Non-deterministic Polynomial-time (NP)-hard problem [51]. This makes the particular solution computational intractable for large scale experimentations and thus we can only use it as a benchmark approach or an offline solution. The main reason is that the particular algorithms, as the optimal ones, are exhaustive, meaning they are trying to go through every possible solution to extract the optimal one. Thus, appropriate solvers are needed to model and solve MIP problems.  
In this work, we utilized the IBM CPLEX 12.8 package to solve the MIP formulation [48]. In particular, we used the Cplex Java API to execute the MIP algorithm in our discrete event java-based simulator. Cplex library uses a generic branch and cut approach to extract the final solution. In the particular approach, the problem is decomposed in a number of continuous subproblems in a form of a tree. At the beginning, the problem is treated as a continuous relaxation of the integer constraint. If the solution contains one or more fractional variables, CPLEX will try to find cuts to remove areas of the search space that contain fractional solutions. Then, it branches to the cut (subproblem) with the more restrictive bounds until it finds an all-integer solution.  
In contrast to MIP, the TS algorithm is very simple and easy to implement by simply translating the pseudocode into a java class with a dozen lines of code. Specifically, it needs a total of \(O(max\_no\_of\_iterations*(K+3))\) operations, where \(max\_no\_of\_iterations\) is the number of iterations needed to evoke the termination criterion of the algorithm, while at each iteration we only perform four operations: (i) select a random neighbor solution, (ii) calculate the cost of the new solution, (iii) compare the new solution with the current best, and (iv) finally update the Tabu List. From these four operations, the cost calculation is only proportional to the number of VNFs \(K\) consisting of the SC.