# 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
```
1 Calculate the overall capacity available (\(C_{u_{available}}\)) in UPFs of level \(k_{u}\) (\(S_{u_{ku}}\)) if\(C_{u_{available}}\geq C_{u_{un}}\)then
2 Sort the UPFs (\(n_{u}\)) based on their available capacity in descending order
3 forall\(n_{u}\) in \(S_{u_{lu}}\)do
4 forall access node (\(n_{r}\)) in \(n_{u}\) service area (\(S_{su_{u}}\))do
5 Find a UPF to which \(n_{r}\) can be reassigned (\(n_{u_{target}}\)) if\(a\)\(n_{u_{target}}\) was foundthen
6 Mark that \(n_{r}\) can be reassigned
7 ifall\(n_{r}\) in \(S_{su_{u}}\) can be reassignedthen
8 Reassign all \(n_{r}\) in \(S_{su_{u}}\) Remove \(n_{u}\) from \(S_{u_{lu}}\) Update \(S_{u_{lu}}\), \(S_{su_{lu}}\), \(N_{c}\), \(N_{nc}\),
9
10 if\(k_{u}\) is a level of main UPFs and \(m\)=1 then
11 forall\(n_{r}\) in \(S_{r}\)do
12 Find a UPF to which \(n_{r}\) can be migrated to improve UPFs overall relocations (\(n_{u_{target}}\)) if\(a\)\(n_{u_{target}}\) was foundthen
13 Reassign \(n_{r}\) Update UPFs service areas (\(S_{su_{lu}}\))
14
15 end if
16



55 Return \(n_{u_{target}}\)
56 end for
57
58 end for
594
595 end for
507
508 end for
5096
510 end for
525 Return \(n_{u_{target}}\)
526 end for
53 Return \(n_{u_{target}}\)
54 end for



65 Return \(n_{u_{target}}\)





Moreover, for a level of main UPFs with mobility requirements, Algorithm 3 tries to reduce the occurrence of relocations (lines: 13-18). For each access node that has been assigned during this level, it searches for whether there is a better UPF (lines: 15). If a better UPF in terms of relocations avoidance is found, the access node is reassigned and the UPF service areas are updated (lines: 16-18). At the end of this algorithm, two additional steps can be included to ensure that each access node is assigned to its nearest UPF and to reduce the load imbalance. Finally, in Algorithm 1, the output sets are updated and the level indicator is decremented (line: 29). Steps 2-29 are repeated while there are available candidates and levels of UPFs pending for placement. ## 5 Evaluation and Results

A territory of interest with a size of 10,000 km\({}^{2}\) was used, where an arbitrary set of TGs was randomly deployed mimicking a fairly realistic demand distribution, with high density urban areas and lower traffic density in rural ecosystems. The TGs represent fixed and radio access nodes with traffic demands between 0 and 1 Tb/s. In the urban scenarios, the radio access nodes are centralized Baseband Units (BBUs) with a maximum coverage area of 3 km whereas in the rural area they are distributed BBUs with radii of 10 and 20 km. To generate the TG traffic demands, six services with different requirements of bandwidth, reliability and latency were considered [35; 36]. Table 3 shows the selected use cases and their requirements. ### ENS Placement Results

For the ENPP solution, the latency constraints were translated into Euclidean distances considering the propagation times of a direct link between any TG-EN pair. Namely, for ultra-low latency requirements, a lower bound was fixed in 2 km while the upper bound was set to 6 km (considering an approximate propagation time of 5 \(\upmu\)s/km [19]), for ultra-low latency requirements under 1 ms and low latency requirements around 5 ms. The results for the conducted experiments are shown in Figure 4a,b. Both the Evolutionary Algorithm (EA) and the HSA were tested for an arbitrary range of TGs varying between 200 and 400 (considering a representative number of nodes for envisioned 5G networks in mid to large city deployments). The hardware used to run the experiments has a 3.30 GHz CPU, x64 architecture (with 10 physical cores and 2 threads per core) and 64 GB RAM. The set of input parameters used for each algorithm is presented in Tables 4 and 5.