Assigning user plane functions (UPFs) within a 5G core network
Systems and methods are provided for placement of User Plane Functions (UPFs) on one or more nodes and assigning Distributed Units (DUs) to the UPF-hosting nodes of a 5G network slice. A method, according to one implementation, includes the step of obtaining a network topology map portraying a network that includes at least a plurality of components of a Radio Access Network (RAN) and a plurality of eligible nodes capable of connecting the components to the Internet. The method also includes the step of creating a tree graph from the network topology map. The tree graph includes a plurality of branches, where each branch represents the lowest cost path between a respective eligible node and a selected one of the plurality of components. In addition, the method includes selecting a group of the eligible nodes that collectively are capable of connecting the plurality of components to the Internet.
1 . A non-transitory computer-readable medium configured to store computer logic having instructions that, when executed, cause one or more processing devices to perform steps of:
obtaining a network topology map portraying a network that includes at least a plurality of components of a Radio Access Network (RAN) and a plurality of eligible nodes capable of connecting the plurality of components to the Internet;
creating a tree graph from the network topology map, the tree graph including a plurality of branches, wherein each branch represents a lowest cost path between a respective eligible node and a selected one of the plurality of components; and
selecting a group of the eligible nodes that collectively are capable of connecting the plurality of components to the Internet, wherein selecting the group includes filtering candidate nodes based on sufficient processing and storage capacity to host a User Plane Function (UPF), computing a compute cost for each candidate node, translating the compute cost into a compute latency, and summing the compute latency with link-path costs to obtain cumulative path costs for tree construction and selection.
2 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include
determining which candidate nodes of the plurality of nodes are eligible to host a UPF based on combined processing capacity, storage capacity, and latency requirements.
3 . The non-transitory computer-readable medium of claim 2 , wherein the steps further include
analyzing both processing availability and storage availability of each candidate node and filtering out ineligible nodes for UPF placement while retaining them for path traversal.
4 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include
determining link costs of each of a plurality of communication links in the network topology from the network topology map.
5 . The non-transitory computer-readable medium of claim 4 , wherein the steps further include
summing the link costs for each path between each eligible node and selected component to obtain path costs from which the lowest cost paths are derived.
6 . The non-transitory computer-readable medium of claim 4 , wherein the steps further include
calculating a compute cost of each eligible node;
translating the compute cost into a compute time latency; and
summing the link costs and compute time latency to obtain path costs from which the lowest cost paths are derived, wherein the compute time latency represents additional delay incurred by instantiating a UPF at the eligible node.
7 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include
pruning one or more of the plurality of branches of the tree graph that violate a rule associated with a predetermined maximum path cost, such that branches are removed when cumulative compute latency and link costs exceed a threshold or when node capacity would be exceeded.
8 . The non-transitory computer-readable medium of claim 1 , wherein the step of creating the tree graph includes the steps of
creating a first set of sub-branches from the eligible nodes to one or more Centralized Units (CUs) of the RAN;
creating a second set of sub-branches from the one or more CUs to a plurality of Distributed Units (DUs) of the RAN; and
combining the first and second sets of sub-branches to obtain the plurality of branches to be introduced in the tree graph, thereby generating a hierarchical assignment structure distinguishing CU-to-DU and UPF-to-CU sub-paths.
9 . The non-transitory computer-readable medium of claim 1 , wherein the step of selecting the group of the eligible nodes that collectively are capable of connecting the plurality of components to the Internet includes one or more of a minimum set cover technique and a probabilistic heuristic technique.
10 . The non-transitory computer-readable medium of claim 9 , wherein the one or more of the minimum set cover technique and probabilistic heuristic technique are configured to return a fewest possible number of eligible nodes, while ensuring that load distribution and latency requirements are satisfied.
11 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include
assigning each component of the RAN to a node selected from the group of eligible nodes, such that each DU is assigned to a UPF-hosting node that satisfies capacity and latency constraints.
12 . The non-transitory computer-readable medium of claim 11 , wherein the step of assigning each component to a node is configured to distribute a substantially equal load on each node of the group of eligible nodes.
13 . The non-transitory computer-readable medium of claim 11 , wherein the step of assigning each component to a node is configured to minimize a total cost in the network without overloading any node, where total cost includes both link costs and compute time latencies.
14 . The non-transitory computer-readable medium of claim 1 , wherein the eligible nodes are part of a 5G core network, and the components of the RAN include at least a Centralized Unit (CUs) and one or more Distributed Units (DUs).
15 . The non-transitory computer-readable medium of claim 1 , wherein each of one or more of the lowest cost paths represent a shortest path between the respective eligible node and the selected one of the plurality of components.
16 . A method comprising steps of:
obtaining a network topology map portraying a network that includes at least a plurality of components of a Radio Access Network (RAN) and a plurality of eligible nodes capable of connecting the plurality of components to the Internet;
creating a tree graph from the network topology map, the tree graph including a plurality of branches, wherein each branch represents a lowest cost path between a respective eligible node and a selected one of the plurality of components; and
selecting a group of the eligible nodes that collectively are capable of connecting the plurality of components to the Internet, wherein selecting includes computing compute costs, translating compute costs to compute latencies, summing the latencies with link costs to obtain cumulative path costs, and pruning branches exceeding latency or capacity thresholds.
17 . The method of claim 16 , wherein the steps further include
determining link costs of each of a plurality of communication links in the network topology; and
summing the link costs together with compute time latencies of candidate UPF-hosting nodes for each path between each eligible node and the selected component to obtain path costs from which the lowest cost paths are derived.
18 . The method of claim 16 , wherein the steps further include
pruning one or more of the plurality of branches of the tree graph that violate a rule associated with a predetermined maximum path cost; and
assigning each component of the RAN to a node selected from the group of eligible nodes, such that assignment minimizes cumulative cost or balances load while preventing overload of any node.
19 . A processing device comprising:
one or more processors and memory storing instructions that, when executed, cause the one or more processors to
obtain a network topology map portraying a network that includes at least a plurality of components of a Radio Access Network (RAN) and a plurality of eligible nodes capable of connecting the plurality of components to the Internet,
create a tree graph from the network topology map, the tree graph including a plurality of branches, wherein each branch represents a lowest cost path between a respective eligible node and a selected one of the plurality of components, and
select a group of the eligible nodes that collectively are capable of connecting the plurality of components to the Internet, wherein selection includes computing compute latencies for candidate nodes, summing compute latencies with link costs to obtain cumulative path costs, and assigning RAN components to elected nodes to minimize cost or balance load subject to capacity constraints.
20 . The processing device of claim 19 , wherein the instructions that, when executed, further cause the one or more processors to
determine link costs of each of a plurality of communication links in the network topology, and
sum the link costs and compute latencies for each path between each eligible node and the selected component to obtain path costs from which the lowest cost paths are derived.