# A Framework for the Joint Placement of Edge Service Infrastructure and User Plane Functions for 5G
## 4 Framework Proposal
### UPF Placement Stages
#### 4.2.2 Near-Optimal UPF Placement
Considering the worst time-consuming scenario where only one access node is assigned to a candidate in each iteration and assuming that all the access nodes must be assigned (\(S_{r}=N_{r}\)) to \(K_{u}\) levels of UPFs, the complexity of NOUP can be defined as O(\(|K_{u}|*|N_{r}|*|N_{c}|*|A|\)) where \(A<<N_{r}\). By comparing this complexity function with any of the OUP complexity expressions, that jointly embrace variables and constraints terms, it can be concluded that NOUP complexity is smaller. The computation time of the proposed solutions is summarized in Figure 7.0 The first observation made from Table 8 is that the OUP_M1 model has the worst performance with running times in the order of thousands of seconds. This higher timescale makes it unfeasible for online placement. On the contrary, the running time of the other solutions is much lower, with typical values around 1s. Concretely, the average time of NOUP in urban and rural scenarios are 0.15 s and 0.33 s, respectively, \begin{table}
\begin{tabular}{l c c} \hline \hline
**Model** & \multicolumn{2}{c}{**Time Complexity**} \\  & **Variables** & **Constraints** \\ \hline OUP\_M0 & \(2*|N_{r}|*|N_{c}|+2*|N_{c}|\) & \(5*|N_{r}|*|N_{c}|+3*|N_{c}|+2*|N_{r}|\) \\ OUP\_M1 & \(|N_{r}|^{2}*|N_{c}|+2*|N_{r}|*|N_{c}|+2*|N_{c}|\) & \(|N_{r}|^{2}*|N_{c}|+5*|N_{r}|*|N_{c}|+3*|N_{c}|+2*|N_{r}|\) \\ \hline \hline \end{tabular}
\end{table} 
Table 7: OUP Complexity Analysis. whereas OUP_M0 requires 0.95 s in the cities and 0.52 s in the rural area. Thus, our heuristic provides a running time reduction of around 85% and 35% in urban and rural areas respectively, with respect OUP_M0. These results verify that NOUP outperforms the optimal solution. Regarding the effects of mobility consideration on the heuristics execution time, there is no significant difference, being this parameter always below 0.6 s with a maximum variation of 0.25 s.

## 6 Conclusions

In this paper, we provided a framework to optimize the UPFs placement based on a previous optimal location of the edge service infrastructure (i.e., ENs). The main goal was to determine the optimal number and location of ENs and UPFs to meet 5G stringent requirements in a cost-effective manner. A thorough evaluation of the proposed placement solutions was presented. To optimize the EN placement, two strategies were proposed considering their proven use in similar problems. Overall, HSA outperformed the evolutionary method tested achieving cost savings over 20% due to its adaptability to the problem and its better exploration of the solution space. These approaches enhance the UPF placement results by reducing their deployment costs and improving QoS since the UPF candidate locations (i.e., ENs) are optimally determined according to users' traffic demands. Regarding the UPFs placement, the devised solutions allow minimizing not only the deployment costs (measured in terms of the number of UPFs) but also the operational costs related to UPF relocations. Concretely, regarding user mobility, the UPF solutions regarding user mobility allowed reductions in the UPF relocation rate of up to 55% and 70% for services with high and low requirements, respectively, at the same deployment cost. Moreover, the proposed heuristic for UPF placement with mobility considerations provided significant run-time improvements, while keeping similar cost values when compared to the optimal. The obtained results demonstrate the assertiveness of the proposed approaches in attaining their objectives. Thus, this framework is a valuable tool for 5G network operators to efficiently plan and deploy their resources. Future research should focus on the simultaneous and online solution of both optimization problems (i.e., ENPP, UPFPP), comparing sequential and simultaneous approaches on 5G emulated scenarios or testbeds.