# 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
At first glance, it can be observed that OUP_M1 and NOUP_M1 provide better results in comparison to OUP_M0 and NOUP_M0, even though they all have the same number of UPFs. Specifically, OUP and NOUP for mobility considerations achieve a reduction of the UPF relocations rate of up to 55% and 32%, respectively, in comparison to UPF placement without mobility (see Figure 11). For services with low requirements, this difference is higher, reaching values up to 72% and 57%, respectively. These results are expected as in OUP_M1 and NOUP_M1 the main objective is not only to minimize the number of UPFs but also the relocation occurrence. It can be noticed that most of the time NOUP_M1 provides similar results to OUP_M1. The difference among solutions with and

Figure 11: UPF Relocation Rate vs. capacity for services with high requirements. Figure 12: UPF Relocation Rate vs. capacity for services without low requirements. Figure 10: UPF Utilization vs. capacity for services with low requirements. without mobility considerations is more remarkable for the second group of services where the rate of relocations is much higher. This is because in this category there are more services with mobility requirements and therefore the effects of this parameter are more pronounced. Overall, a reduction of UPF relocations with the increase of the capacity can be observed. This is more noticeable for the first group of services in City_2 region where relocations are completely reduced for \(C_{u}=2.5\) Tb/s. In this case, the occurrence of relocations is zero because all the access nodes are served by the same UPF, see Figure 11b. However, it must be highlighted that a lower number of UPFs does not necessarily imply lower relocations, but it is also mandatory to take into account users mobility patterns. #### 5.2.4 Complexity Analysis and Execution Time

Finally, the four solutions are compared in terms of their complexity and execution time. The computational complexity of a mathematical model is given by the size of the problem which is expressed in terms of the number of variables (n) and constraints (m). However, formulating a function that relates both terms is hardly possible since this is an open issue [40]. In the worst-case, the computational complexity of the simplex algorithm was shown to be exponential in the size of the problem whereas in practice it has been found to be \(nxm\)[41]. Please note that there is a substantial difference between both approaches. Hence, the problem complexity will be formulated based on the number of variable and constraints separately and non-fixed expression will be given to establish their relationship. Table 7 characterizes the complexity of OUP for mobility and non-mobility considerations. From this table, it can be observed that the complexity of OUP_M0 and OUP_M1 in terms of their variables or constraints are O(\(|N_{r}|*|N_{c}|\)) and O(\(|N_{r}|^{2}*|N_{c}|\)), respectively. Therefore, the complexity of OUP_M0 model is asymptotically smaller than that of OUP_M1. Regarding the computational complexity of NOUP, it is determined by the main loop of Algorithm 1. This while loop will be executed \(K_{u}\) times, being \(K_{u}\) the levels of UPFs that must be placed. The complexity associated with the iterative processes inside this loop is given by the number of access nodes that must be assigned (\(S_{r}\)) and the number of candidate locations (\(N_{c}\)) which are evaluated in the innermost loop of Algorithm 1. A significant time-consuming part related to the candidate evaluation process is the execution of Algorithm 2. The time complexity of Algorithm 2 is linked to its while loop which can be specified as O(\(|\) A\(|\) ), where A denotes the maximum number of access nodes that can be assigned to a candidate. Please note that A cannot be found beforehand since it depends on several factors such as the number of access nodes near a candidate (\(N_{nrc}[nc]\)), the UPF capacity and access node demands. Hence, the overall NOUP algorithm complexity is formulated based on it.