Formulation¶

System Model: Physical Network and Virtual Network
Basic Formulation for Cost Optimization
Extensions for Emerging Network Scenarios

An example of resource allocation problem in network function virtualization (source: `IJCAI'24 - FlagVNE<https://arxiv.org/abs/2404.12633>`_)

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 is a critical challenge in modern networking. It involves efficiently mapping service requests, modeled as Virtual Networks (VNs) composed of interconnected Virtual Network Functions (VNFs), onto a shared physical network (PN) infrastructure.

This process must satisfy various resource demands and constraints. NFV-RA is recognized as an NP-hard combinatorial optimization problem, necessitating sophisticated solution strategies.

This page details the formal problem definition used within Virne, starting with a basic cost optimization model and then discussing common extensions.

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:

\[\mathcal{G}_p = (\mathcal{N}_p, \mathcal{L}_p)\]

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:

\[\mathcal{G}_v = (\mathcal{N}_v, \mathcal{L}_v, \omega, \varpi)\]

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 Formulation for Cost Optimization¶

The core NFV-RA problem involves deciding how to embed incoming VNs onto the PN while optimizing certain objectives, typically related to resource efficiency.

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.

\[\sum_{n_{p}^{i} \in \mathcal{N}_p} x_{i}^{m} = 1, \quad \forall n_{v}^{m} \in \mathcal{N}_v \quad (3)\]

2. PN Node Capacity: Each physical node can host at most one virtual node from the same incoming VN request.

\[\sum_{n_{v}^{m} \in \mathcal{N}_v} x_{i}^{m} \le 1, \quad \forall n_{p}^{i} \in \mathcal{N}_p \quad (4)\]

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.

\[x_{i}^{m} C(n_{v}^{m}) \le C(n_{p}^{i}), \quad \forall n_{v}^{m} \in \mathcal{N}_v, n_{p}^{i} \in \mathcal{N}_p \quad (5)\]

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$.

\[\sum_{n_{p}^{j} \in \Omega(n_{p}^{k})} y_{k,j}^{m,w} - \sum_{n_{p}^{i} \in \Omega(n_{p}^{k})} y_{i,k}^{m,w} = x_{k}^{m} - x_{k}^{w}, \quad \forall l_{v}^{m,w} \in \mathcal{L}_v, n_{p}^{k} \in \mathcal{N}_p \quad (6)\]

5. Loop Prevention: Virtual links should be routed acyclically.

\[y_{i,j}^{m,w} + y_{j,w}^{m,w} \le 1, \quad \forall l_{m,w}^{v} \in \mathcal{L}_{v}, l_{i,j}^{p} \in \mathcal{L}_{p} \quad (7)\]

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.

\[\sum_{l_{v}^{m,w} \in \mathcal{L}_v} (y_{i,j}^{m,w} + y_{j,i}^{m,w}) B(l_{v}^{m,w}) \le B(l_{p}^{i,j}), \quad \forall l_{p}^{i,j} \in \mathcal{L}_p \quad (8)\]

Constraints (3), (4), and (5) cover node mapping, while (6), (7), and (8) 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):

\[\text{maximize} \quad R2C(S) = \frac{\chi \cdot REV(S)}{COST(S)} \quad (1)\]

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)|$ quantifies the length (e.g., number of hops) of the physical path $rho_p$ routing the virtual link $l_v$[cite: 58, 338].

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, memory amounts), the node resource constraint (5) must hold for each type of resource $C in mathcal{C}$.

Resource Heterogeneity

\[x_{i}^{m} C_k(n_{v}^{m}) \le C_k(n_{p}^{i}), \quad \forall n_{v}^{m} \in \mathcal{N}_v, n_{p}^{i} \in \mathcal{N}_p, \forall k \in \mathcal{C}_{\text{types}}\]

Latency-aware Edge Networks¶

For time-sensitive services (e.g., in edge computing, 5G), virtual links $l_v$ may have maximum tolerable latency $D(l_v)$. The cumulative propagation delay $D(rho_p)$ of the physical path $rho_p$ routing $l_v$ must not exceed this:

Latency Requirements

\[D(\rho_p) = \sum_{l_p \in \rho_p} D(l_p) \le D(l_v)\]

Energy Efficient Networks¶

In green networking, minimizing energy consumption is crucial. The energy consumed by a physical node $n_p$, denoted $E(n_p)$, can depend on its status (idle/active) and workload. The optimization objective can be modified to a multi-objective function, e.g.:

Energy Efficiency

\[\text{maximize} \quad -w_a \sum_{n_p \in \mathcal{N}_p} E(n_p) + w_b \cdot R2C(S)\]

where $w_a$ and $w_b$ are weights for the different 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.