# 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
If a candidate is found the node is assigned and the sets of UPF locations (\(S_{u_{\text{L}}}\)), UPF service areas (\(S_{sa_{\text{L}}}\)), unassigned (R)AN nodes (\(S_{r}\)), candidate locations (\(N_{c}\)) and candidate near the access nodes \(N_{nc}\), are updated (lines: 11-13). Otherwise, the critic access node is added to the set of unassigned access nodes (\(S_{unassign_{ku}}\)) (lines: 14-15). In both cases, the candidate evaluation process is interrupted and restarted (line: 16). If Algorithm 2 was successfully executed, the candidate service area is inspected. If the service area is not empty, the candidate is evaluated and added to a list of valid candidates (\(S_{valid}\)) (lines: 18-20). The candidate evaluation is made by taking into account metrics such as utilization, worst delay and relocation avoidance for mobility considerations. If the candidate has no assigned access nodes, it is removed from the set of candidates (lines: 21-22). Once all the candidates are analyzed, the valid candidate with the best service area is selected (lines: 23-25). The best candidate is the one that has more access nodes assigned and avoids the greatest number of UPF relocations if m = 1. Each time that the best candidate is chosen, the sets \(S_{u_{ku}}\), \(S_{su_{ku}}\), \(S_{r}\), \(N_{c}\) and \(N_{nc_{r}}\) are updated (line: 25). In case no valid candidates, the remaining access nodes in \(S_{r}\) are added to the set of unassigned access nodes (lines: 26-27) and further analysis is required. These access nodes could be assigned to a UPF by relaxing the latency requirement or by deploying additional infrastructure. Notice, that these approaches imply either QoS degradation or the incurrence of additional costs. The candidate evaluation process (lines: 5-25) is repeated while there are unassigned access nodes. Algorithm 3 is executed (line: 28) after a level \(k_{u}\) of UPFs is placed. Its main objective is to reduce the number of UPFs and the relocation occurrence if mobility requirements are considered. Hence, Algorithm 3 first step is to determine the overall available capacity (\(C_{u_{available}}\)) in the UPFs of the level (line: 1). This capacity is compared with the UPF maximum capacity (line: 2). If the overall available capacity is higher than the UPF maximum capacity, the number of UPFs could be reduced (by removing some of them). To delete the lowest utilized UPFs, they are sorted and analyzed in descending order according to their available capacity (line: 3). For each UPF at level \(k_{u}\), it is checked whether all its assigned access nodes can be served by other UPFs (lines: 5-12). If an access node can be reassigned to other UPF, this is indicated by marking the access node (lines: 7-8). If all the access nodes in a UPF service area can be served by other UPFs, they are reassigned and the UPF is deleted from the set of UPFs (lines: 9-11). As a result of this process, the set of UPFs at level \(k_{u}\), their service areas, the available candidates and the candidate locations for each access node are updated (line: 12).