# 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  
The OUP model for non-mobility considerations is a variant of two well known NP-hard problems, the Resilient Controller Placement Problem [30; 31] and the Hierarchical Capacitated Facility Location Problems [32; 33], whereas its form for mobility requirements can be seen as a combination of the previous problems and the Location Area Planning problem [5; 34] which is also NP-hard. Therefore, the OUP model, in either variant, is NP-hard. Hence, the OUP approach is not feasible for ultra-dense networking scenarios where the number of access nodes and candidate locations is quite large. In these scenarios, the number of possible combinations is extremely high and finding the optimal solution for the UPFP may require excessive computation time and resources or lead to impractical solutions. To deal with this limitation, the NOUP algorithm has been developed. The pseudocode of the NOUP solution is shown in Algorithm 1. ```
Input:\(N_{r}\), \(N_{c}\), \(N_{nr_{c}}\), \(N_{nc_{r}}\), \(C_{n_{max}}\), Access node demands (\(D_{r}\)), \(H_{ij}\), m, \(K_{u}\) Output: Set of total UPFs (\(S_{u_{T}}\)), Set of UPFs service areas (\(S_{sat_{T}}\)), Set of unassigned access nodes (\(S_{unassign_{T}}\))
1 Initialize the output variables: \(S_{u_{T}}\), \(S_{sat_{T}}\), \(S_{unassign_{T}}\);
2 while there is an unplaced level of UPFs (\(K_{u}\
eq 0\)) and \(N_{c}\) is not emptydo
3 Initialize: \(S_{u_{R}}\), \(S_{sat_{T}}\), \(S_{unassign_{R}}\) ;
4 Select the set of access nodes to be assigned to a UPF at level \(k_{u}\) (\(S_{r}\));
5 while\(S_{r}\) is no emptydo
6 forall\(n_{c}\) in \(N_{c}\)do
7 Select the unassigned access nodes near \(n_{c}\) (\(N_{nr_{c}}[n_{c}]\)) ;
8 Form a service area for \(n_{c}\)\(\leftarrow\)Algorithm 1 ;
9 ifthe service area was not successfully createdthen
10 Search for a candidate for the critic access node ;
11 ifa candidate was foundthen
12 Assign the critic access node to the candidate;
13 Update \(S_{u_{R}}\), \(S_{u_{R}}\), \(S_{r}\), \(N_{c}\), \(N_{nc_{r}}\)
14 else
15 Add the critic access node to \(S_{unassign_{R}}\)
16 break
17 else
18 ifthe candidate service area is not emptythen
19 Evaluate \(n_{c}\)
20 Add \(n_{c}\) to a set of valid candidates (\(S_{valid}\))
21 else
22 Remove \(n_{c}\) from the set of candidates (\(N_{c}\))
23 if\(S_{valid}\) is no emptythen
24 Select the valid candidate with the best service area (\(n_{c_{max}}\));
25 Update \(S_{u_{R}}\), \(S_{u_{R}}\), \(S_{r}\), \(N_{c}\), \(N_{nc_{r}}\)
26 else
27 Add the access nodes in \(S_{r}\) to \(S_{unassign_{R}}\)
28
29\(S_{u_{R}}\), \(S_{sat_{R}}\), \(N_{c}\), \(N_{nc_{r}}\)\(\leftarrow\)Algorithm 2 ;
30 Update \(S_{u_{T}}\), \(S_{sat_{T}}\), \(S_{unassign_{T}}\), \(K_{u}\)
```  
**Algorithm 1**NOUP  
The NOUP algorithm aims at finding the best locations and number of UPFs to serve a given set of access nodes at different resilience levels. The levels of UPFs are placed according to their role, starting with the main level and ending with the last level of backup. For each level, all the available candidates are evaluated and the best ones are selected. This approach guarantees that the best locations are selected and that these locations belong to UPFs with a higher role. Executing this algorithm outputs the location of the UPFs (\(S_{u_{T}}\)), their service area (\(S_{sat_{T}}\)) and the unassigned access nodes (\(S_{unassign_{T}}\)), in case there are any. The NOUP starts by initializing the output variables (line: 1). Afterwards, it proceeds to determine the UPF placement for the \(K_{u}\) required levels (lines: 2-29). The first step when placing a level of UPF is to create the empty sets for the output variables in the corresponding level (i.e., \(S_{u_{R}}\), \(S_{sat_{R}}\) and \(S_{unassign_{R}}\)) (line: 3). Next, the access nodes to be assigned to a level \(k_{u}\) of UPFs are selected (line: 4). To determine the best location for the UPFs each available candidate is analyzed by establishing its potential service area (lines: 6-22).