Formulation¶
System Model: Physical Network and Virtual Network
Basic Embedding Formulation
Extensions for Emerging Network Scenarios
Note
Figure: An example of a resource allocation problem in network function virtualization. It illustrates the mapping process of virtual network requests onto physical network resources. (Source: IJCAI’24 - FlagVNE)
NFV-RA maps service requests, modeled as Virtual Networks (VNs), onto a shared Physical Network (PN). This page defines the graph model, feasibility constraints, and resource-efficiency objective used by Virne. It then gives several illustrative extensions for emerging network scenarios.
System Model¶
Both the physical infrastructure and the virtual service requests are modeled as attributed graphs.
Physical Network (PN)
The Physical Network, \(\mathcal{G}_p\), represents the underlying infrastructure and is modeled as an undirected graph:
where:
\(\mathcal{N}_p\) is the set of physical nodes (e.g., servers).
\(\mathcal{L}_p\) is the set of physical links interconnecting these nodes.
Each physical node \(n_p \in \mathcal{N}_p\) is associated with available computing resources, denoted as \(C(n_p)\) (e.g., CPU, RAM). Each physical link \(l_p \in \mathcal{L}_p\) has an available bandwidth capacity, \(B(l_p)\).
Virtual Network (VN)
A service request, or Virtual Network \(\mathcal{G}_v\), is also modeled as an undirected graph:
where:
\(\mathcal{N}_v\) is the set of virtual nodes, representing VNFs or service components.
\(\mathcal{L}_v\) is the set of virtual links, representing the required connectivity and traffic flow between virtual nodes.
\(\omega\) is the arrival time of the VN request.
\(\varpi\) is the requested lifetime (duration) of the VN.
Each virtual node \(n_v \in \mathcal{N}_v\) has specific computing resource demands, \(C(n_v)\). Each virtual link \(l_v \in \mathcal{L}_v\) has a required bandwidth demand, \(B(l_v)\).
An NFV-RA problem instance \(I\) is defined by the pair \(I = (\mathcal{G}_v, \mathcal{G}_p)\), representing a VN request arriving at a snapshot of the PN. Virne aims to find an efficient mapping for these instances.
Note
Figure 1 in our research paper provides a visual illustration of this NFV-RA problem model.
Basic Embedding Formulation¶
The core problem is to find a feasible embedding while using physical resources efficiently.
Embedding Process
Mapping a VN \(\mathcal{G}_v\) onto a sub-portion of the PN, \(\mathcal{G}_{p'}\), is represented by a mapping function \(f_{\mathcal{G}}: \mathcal{G}_v \rightarrow \mathcal{G}_{p'}\). This consists of two sub-processes:
Node Mapping (:math:`f_N`): Assigning each virtual node \(n_v \in \mathcal{N}_v\) to a suitable physical node \(n_p = f_N(n_v) \in \mathcal{N}_p\).
Link Mapping (:math:`f_L`): Routing each virtual link \(l_v \in \mathcal{L}_v\) over a physical path \(\rho_p = f_L(l_v)\) in \(\mathcal{L}_p\) that connects the physical nodes hosting the endpoints of \(l_v\).
Boolean Variables for Mapping Decisions
To formalize the constraints and objectives, we use boolean variables:
\(x_{i}^{m} = 1\) if virtual node \(n_{v}^{m}\) is placed on physical node \(n_{p}^{i}\), and \(0\) otherwise.
\(y_{i,j}^{m,w} = 1\) if virtual link \(l_{v}^{m,w}\) (connecting \(n_{v}^{m}\) and \(n_{v}^{w}\)) traverses physical link \(l_{p}^{i,j}\) (connecting \(n_{p}^{i}\) and \(n_{p}^{j}\)), and \(0\) otherwise.
Here, \(m, w\) are identifiers for virtual nodes, and \(i, j, k\) are identifiers for physical nodes.
Embedding Constraints¶
A VN request is successfully embedded if a feasible mapping solution is found that satisfies the following constraints:
Node Constraints
1. VN Node Assignment: Each virtual node must be mapped to exactly one physical node.
2. PN Node Capacity: Each physical node can host at most one virtual node from the same incoming VN request.
3. Node Resource Availability: The computing resources available at a physical node must meet or exceed the demands of the virtual node mapped to it.
Link Constraints
4. Flow Conservation: For each virtual link, a valid path must be established in the PN between the physical nodes hosting its endpoints. Let \(\Omega(n_p^k)\) be the set of neighbors of physical node \(n_p^k\).
5. Opposite-direction Exclusion: A virtual link cannot use both orientations of the same physical link. Virne’s path-based routing constructs simple physical paths.
Resource Constraints
6. Link Bandwidth Availability: The sum of bandwidth demands of virtual links routed over a physical link must not exceed its available bandwidth.
Equations (1), (2), and (3) cover node mapping. Equations (4), (5), and (6) cover link mapping.
Optimization Objective¶
Revenue-to-Cost Ratio (R2C)
The primary objective in NFV-RA, especially for online service requests, is often to maximize the overall resource utilization, which facilitates long-term resource profit and request acceptance. A widely used metric to assess solution quality (\(S\)) for an instance \(I\) is the Revenue-to-Cost Ratio (R2C):
where:
\(\chi\) is a binary variable indicating solution feasibility: \(\chi=1\) if solution \(S\) satisfies all constraints, and \(\chi=0\) otherwise.
\(REV(S)\) is the revenue generated by embedding the VN \(\mathcal{G}_v\). If \(\chi=1\), it’s calculated as the sum of resources requested by the VN:
\[REV(S) = \sum_{n_v \in \mathcal{N}_v} C(n_v) + \sum_{l_v \in \mathcal{L}_v} B(l_v)\]\(COST(S)\) is the resource consumption in the PN due to embedding \(\mathcal{G}_v\). If \(\chi=1\), it’s calculated as:
\[COST(S) = \sum_{n_v \in \mathcal{N}_v} C(n_v) + \sum_{l_v \in \mathcal{L}_v} (|f_{\mathcal{L}}(l_v)| \times B(l_v))\]Here, \(|f_{\mathcal{L}}(l_v)|\) is the length, usually measured in hops, of the physical path \(\rho_p\) that carries virtual link \(l_v\). This definition follows Appendix A.1 of the Virne benchmark paper.
Extensions for Emerging Network Scenarios¶
The basic NFV-RA model can be extended to address unique challenges in emerging network scenarios. Virne supports such extensions. Key examples include:
Representative Scenarios¶
Heterogeneous Resourcing Networks¶
In networks with diverse physical node capabilities (e.g., different types of CPUs, GPUs, and memory), the node resource constraint (3) must hold for each resource type \(C \in \mathcal{C}\).
Resource Heterogeneity
Latency-aware Edge Networks¶
For time-sensitive services (e.g., in edge computing and 5G), a virtual link \(l_v\) may have a maximum tolerable latency \(D(l_v)\). The cumulative propagation delay \(D(\rho_p)\) of its physical path \(\rho_p\) must not exceed this limit:
Latency Requirements
Energy Efficient Networks¶
In green networking, the energy consumed by a physical node \(n_p\), denoted \(E(n_p)\), can depend on its status and workload. The optimization objective can incorporate both resource utilization and energy consumption, for example:
Energy Efficiency
where \(w_a\) and \(w_b\) weight the two objectives.
Note
These are illustrative extensions. The flexible design of Virne allows for the incorporation of various other constraints and objectives relevant to specific NFV-RA research problems. Refer to Appendix A.2 of our research paper for further discussion on these extensions.