# A Novel Strategy for VNF Placement in Edge Computing Environments
## 5 A Novel Smart VNF Placement Algorithm  
The proposed heuristic-based algorithm for VNF placement determines to which VNF instance, hosted by an edge node, the VNFs associated with a user SFC Request should be mapped and which link between the nodes that host such VNFs should be used. Finding a solution for the VNF placement problem by considering all SFCs that arrived within a time window in the decision increases the complexity of the problem due to the variety ofcombinations of possible placement plans. Thus, adopting an optimal approach, such as that based on ILP, is unfeasible due to the time taken to find the placement plan. Once the SFC to be placed is chosen, the heuristic needs to select the chain of VNF instances that will be considered to meet the SFC request. Then, following the VNF order in the SFC, the heuristic either reuses a VNF instance that is already running in an edge node or creates a new one. In other words, the heuristic algorithm has two phases: phase 1, which exploits already-placed VNF instances, and phase 2, which places new VNF instances. Figure 1 illustrates an overview of each step of the proposed heuristic. Both phases rely on an evaluation metric to sort a list of \"candidate entities\" with which the current VNF will associate. These \"candidate entities\" are defined according to the execution phase of the smart VNF placement algorithm. In _Phase 1_, a candidate entity is an existing VNF instance that has not exceeded the maximum share. In _Phase 2_, a candidate entity is an edge node that the NFVO has verified as feasible to place the requested VNF. The evaluation metric proposed in this paper is a convex combination of the following attributes of the entity \(e\): latency delay (\(L_{e}\)), resource capacity availability (\(R_{e}\)), and energy availability (\(E_{e}\)), as defined in Equation (14), where \(w_{1}+w_{2}+w_{3}=1\) and \(w_{i}\geq 0\) with \(i=1,2,3\). Note that the weights are assigned by the network administrator to set up the heuristic to prioritize one attribute over the others. Alternatively, this setup can be performed by an autonomous agent, but it is out of the scope of this article. \[Eval(e)=w_{1}\times E_{e}+w_{2}\times R_{e}+w_{3}\times L_{e} \tag{14}\]  
The novel VNF placement algorithm allows resource sharing among multiple VNF instances by exploiting already-placed VNF instances before creating new ones. This resource sharing among VNFs can reduce the computational resource usage since the request uses the resource allocated to the instance serving it. Furthermore, this novel aspect can optimize the use of well-positioned nodes by concentrating several requests in the same node. Figure 2 depicts a scenario composed by users \(u_{1}\), \(u_{2}\), and \(u_{3}\), requesting SFCs \(s_{1}\) and \(s_{2}\). The placement plan for request \((u_{1},s_{1})\) has decided to create new VNF instances  
Figure 1: Smart VNF placement algorithm. of VNFs \(\circ\) and \(\triangle\) in node \(h_{1}\), and VNF \(\square\) in node \(h_{3}\). The instance of VNF \(\square\) is reused in the placement plan for request \((u_{2},s_{2})\), since it can be shared by two requests at most, while VNF \(\circ\) is created in node \(h_{2}\). Once the instance of VNF \(\square\) in node \(h_{3}\) reaches its maximum share, the placement plan for request \((u_{3},s_{2})\) has to create a new instance of VNF \(\square\) in node \(h_{4}\). The proposed algorithm also targets a different application QoS while decreasing the cost for the infrastructure provider. To this end, the algorithm is aware of latency, computational resource capacity, and energy consumption. Therefore, it selects the edge nodes for placing VNF requests by verifying those characteristics in the candidate edge nodes. Each SFC has a list in our model that defines the priority order considering latency, capacity, and energy. Thus, the algorithm searches for candidate nodes according to the highest priority requirement (among energy consumption, latency, and resource consumption) for each SFC request.