A Novel Performance Metric for Virtual Network Embedding Combining Aspects of Blocking Probability and Embedding Cost

Abstract

Network Virtualization offers a solution for Future Internet and it is a key enabler for cloud computing applications. Virtual Network Embedding (VNE) problem deals with resource allocation of a physical infrastructure to Virtual Network Requests (VNRs). Several performance metrics are employed in order to evaluate the efficiency of specific VNE approaches. These existing metrics, mostly related to Infrastructure Provider profit, are computed at the end of the VNE process, after embedding many VNRs. This work proposes a novel performance metric, VNE-NP (VNE Normalized Profit) which combines aspects of the two metrics most used in the literature: Blocking Probability and Embedding Cost.

1 Introduction

Network architecture is critical for cloud computing applications, which require distributed datacenters interconnected through high data transfer and low delay networks [1]. Besides, a high level of virtualization in datacenters resources and networking devices are required for the provisioning of cloud services, which explains the increasing importance of technologies related to Network Virtualization [2].

The problem of optimally assigning resources of a physical network to Virtual Network Requests (VNRs) is usually named Virtual Network Embedding (VNE) problem and it is the main resource allocation challenge in Network Virtualization [3].

Several performance metrics have already been used to compute how optimal or efficient a specific VNE approach is. Surveys as [3, 4] present these metrics, which are computed at the end of a VNE process (a large amount of VNR mappings), and are related to Quality of Services (QoS) or profit issues.

In this work, we present an overview of the performance metrics that are used to evaluate profit-related aspects. Next, a new performance metric is proposed for the first time, named VNE Normalized Profit (VNE-NP), considering both aspects of efficiency in finding a possible mapping of a specific VNR as well as physical network resources utilization.

The rest of this work is organized as follows: Sect. 2 presents a VNE formulation and main performance metrics, while the performance metrics related to economical profit are discussed in Sect. 3. Section 4 proposes the novel VNE-NP metric and a VNE example shows its viability. Section 5 concludes this work.

2 Virtual Network Embedding (VNE) Problem

2.1 Physical Network

When considering a VNE problem, a physical network is modeled as an undirected graph $G^{\mathrm {P}}=(N^{\mathrm {P}}, L^{\mathrm {P}})$ where $N^{\mathrm {P}}$ is the set of physical nodes and $L^{\mathrm {P}}$ is the set of bi-directional physical links.

Each physical node $n^{\mathrm {P}}\in N^{\mathrm {P}}$ can be considered as connected to a datacenter whose available computing capacity is represented by a single parameter $c^n$, usually called computing resource capacity.

At the same time, the physical links $l^{\mathrm {P}} \in L^{\mathrm {P}}$ interconnect physical nodes. Each physical link is characterized by its available bandwidth indication, i.e. its capacity to support data traffic.

2.2 Virtual Network Requests

Each virtual network request (VNR) is also usually modeled as an undirected graph $G^{\mathrm {V}}=(N^{\mathrm {V}}, L^{\mathrm {V}})$ where $N^{\mathrm {V}}$ is the set of virtual nodes and $L^{\mathrm {V}}$ is the set of virtual links. The requirements of each virtual node and each virtual link are typically related with the same parameters that characterize physical nodes and links respectively, i.e. each virtual node requires a specific number of computing resource units, while each virtual link requires a specific bandwidth.

2.3 VNE Problem Formulation

A given VNE algorithm should process one VNR at a time, trying to efficiently allocate virtual nodes into physical nodes and virtual links into paths formed by physical links. Therefore, a VNR allocation process can be divided in two mapping functions:

• 1. Virtual Node Mapping (VNM), which assigns each virtual node $n^{\mathrm {V}}$ to a physical node $n^{\mathrm {P}}$:

  $$\begin{aligned} VNM :\,= f(n^{\mathrm {V}} \rightarrow n^{\mathrm {P}}) \end{aligned}$$

  (1)

• 2. Virtual Link Mapping (VLM), which assigns to each requirement of virtual link $l^{\mathrm {V}}$ a path of consecutive physical links:

  $$\begin{aligned} VLM :\,= f(l^{\mathrm {V}} \rightarrow p^{\mathrm {P}}) \end{aligned}$$

  (2)

  $p^{\mathrm {P}} \in P^{\mathrm {P}}$ where $P^{\mathrm {P}}$ is the set of all possible paths (or lightpaths in the case of a physical optical network) between a pair of physical nodes which host the corresponding pair of virtual nodes interconnected by $l^{\mathrm {V}}$.

A feasible solution must comply with specified restrictions, mostly related to the availability of physical resources to host virtual nodes or links, and the nature of the physical network.

Each VNR allocation may be chosen to optimize a single objective function, or multiple objective functions, in order to choose the most convenient solution among all feasible alternatives. In this sense, each VNR allocation can be considered as an optimization problem, with a discrete and finite number of solutions that satisfy specific restrictions.

If the VNE process succedded in finding a feasible (and ideally optimal) solution, then the VNR is embedded and the physical resources required are assigned to it. Otherwise, the VNR is blocked. There is not partial VNR allocation.

2.4 VNE Global Performance Metrics

The individual result in the allocation or blocking of a single VNR does not define the real efficiency of the whole VNE process. The VNE process comprises multiple VNR allocations and it is evaluated by global, long-term Performance Metrics, which can only be computed at the end of a whole VNE process, typically given by a period of working (or simulation) under a required load environment.

VNE performance metrics can be classified into those related to: (i) resources spending or economical profit, (ii) Quality of Service issues, and (iii) others metrics [3]. The main performance metrics, utilized in almost all VNE approaches, are those related to resource spending or economical profit. Therefore, they will be explained in detail in next section.

3 Resources Spending or Economical Profit Metrics

These type of metrics try to measure how efficient is the VNE method in the utilization of physical resources or to accept the maximum number of VNRs. In this context, the most referenciated/used performance metrics are:

• Accepted Ratio [5];

• Embedding Cost [6];

• Embedding Revenue [7]; and

• Revenue/Cost Relation [8].

3.1 Accepted Ratio

Accepted Ratio performance metric [5] measures the relation between the number of accepted (not blocked) VNRs ($VNR_{\mathrm {Acc}}$) over the total number of VNRs considered in the process ($VNR_{\mathrm {Tot}}$):

$$\begin{aligned} Accepted\,Ratio= \frac{\sum VNR_{\mathrm {Acc}}}{\sum VNR_{\mathrm {Tot}}} \end{aligned}$$

(3)

The values of Accepted Ratio is in the range [0,1] and higher values of this metric indicate better performance of a specific approach. For online problems, this metric is usually considered as its complement and called “Blocking Rate” or “Blocking Probability”:

$$\begin{aligned} Blocking\,Rate= \frac{\sum VNR_{\mathrm {Block}}}{\sum VNR_{\mathrm {Tot}}} \end{aligned}$$

(4)

where $\sum VNR_{Block}$ is the number of blocked VNRs, and therefore:

$$\begin{aligned} Blocking\,Rate= 1 - Accepted\,Ratio \end{aligned}$$

(5)

Accepted Ratio represents the efficiency in finding a solution for allocating a VNR. However, an approach specially designed to declive this metric, can accept all VNRs with fewer amount of required resources and with simpler topologies, while blocking more complex VNRs.

3.2 Embedding Cost

Embedding Cost [6] or Physical Resource utilization performance metric computes total cost of embedding, in terms of physical resources that were needed to embed accepted requests.

The embedding cost of an individual $VNR_i$ ($Cost^{\mathrm {VNR}}_i$) can be considered as proportional to physical resources needed to perform virtual node and virtual link mappings:

$$\begin{aligned} Cost^{\mathrm {VNR}}_i = (\gamma \sum _{N^\mathrm {P}}c_{n,i}^\mathrm {P} + \delta \sum _{L^\mathrm {P}}B_{l,i}^\mathrm {P}).HT_i \end{aligned}$$

(6)

where $c_{n,i}^\mathrm {P}$ represents physical node resources assigned to virtual nodes of $VNR_i$; $B_{l,i}^\mathrm {P}$ are physical link resources (bandwidth) assigned to virtual links of $VNR_i$; while $\gamma$ and $\delta$ are coefficients that relate real costs per time unit of node resources and bandwidth resources of physical paths. At the same time, $HT_i$ is the Holding Time (lifetime) of a single request $VNR_i$. If the problem is a static VNE, $HT_i$ can be considered as equal to 1, or it may not be considered at all.

The Embedding Cost performance metric can be defined as the sum of all the embedding costs corresponding to accepted (not blocked) VNRs:

$$\begin{aligned} Embedding\,Cost= \sum _{\mathrm {Acc}}Cost^{\mathrm {VNR}}_i \end{aligned}$$

(7)

The values of this metric are not normalized and the VNE strategy must try to minimize its value, looking for an efficient utilization of physical resources. However, this metric does not consider neither the number of blocked VNRs, nor the number of total resources successfully embedded, so it is also a partial view of VNE efficiency.

3.3 Embedding Revenue

Embedding Revenue considers that the revenue of a VNR is proportional to the number of total node and link resources requested by virtual networks [7, 9].

The potential revenue of a single $VNR_i$, or $Revenue^{\mathrm {VNR}}_i$ (which can be effective, once embedded) can be defined as:

$$\begin{aligned} Revenue^{\mathrm {VNR}}_i=(\alpha \sum _{N^\mathrm {V}}c_{n,i}^\mathrm {V} + \beta \sum _{L^\mathrm {V}}B_{l,i}^\mathrm {V}).HT_i \end{aligned}$$

(8)

where $\alpha$ and $\beta$ are coefficients related to real revenue per time unit, of each unit of computing capacity resources $c^\mathrm {V}_{n,i}$ required by a virtual node and amount of spectrum/wavelength $B_{l,i}^\mathrm {V}$ required by virtual links (network resources) of $VNR_i$.

The Embedding Revenue performance metric can be defined as the sum of all potential revenues corresponding to all accepted VNRs:

$$\begin{aligned} Embedding\,Revenue = \sum _{\mathrm {Acc}}Revenue^{\mathrm {VNR}}_i \end{aligned}$$

(9)

The Embedding Revenue is a metric that must be maximized, looking for better profit of the Infrastructure Provider or InP and, as the previous metric, their values are not normalized.

3.4 Revenue/Cost Relation

Revenue/Cost Relation performance metric indicates the ratio between Embedding Revenue and Embedding Cost [8, 10]:

$$\begin{aligned} Rev/Cost Relation = \frac{Embedding\,Revenue}{Embedding\,Cost} \end{aligned}$$

(10)

This VNE performance metric does not express global efficiency of a VNE approach, because it is focused, as Embedding Cost and Embedding Revenue metrics, only in accepted VNRs. A VNE strategy rejecting a lot of VNRs may be very efficient in physical resources utilization, and therefore with a good Revenue/Cost Relation, but with a high blocking probability.

Revenue/Cost Relation performance metric must be maximized, for a good profit of the InP. Furthermore, if the values of parameters $\alpha , \beta , \gamma ,$ and $\delta$ are taken equal to one, this metric can be considered as normalized, with its values varying between 0 (in the worst case) and 1 (for a perfect VNE process with all virtual links mapped to single physical links) [8].

4 A Novel Profit-Related Performance Metric: VNE-NP

As we have seen, the diversity in the topology of each VNR and the resources that requires, makes that none of the above mentioned performance metrics is able to reflect all the different aspects of the problem, failing in adequately comparing the efficiency of two or more different approaches.

The Accepted Ratio metric evaluates only how many VNRs were accepted, without taking into account neither the potential lost revenue when large VNRs were blocked nor the efficiency in the utilization of physical resources in the VNE process. In terms of InP profit, there can be a considerable difference in blocking a relative large VNR, than blocking a small one that only requires a small number of resources.

The Embedding Cost metric only evaluates how efficiently is the VNE approach in physical resources utilization, with no consideration about the number of blocked VNRs and their potential lost revenue.

On the other hand, the rest of the considered metrics: Embedding Revenue and Revenue/Cost Relation do consider the revenue generation of accepted requests but gives a partial evaluation since only consider the cost of accepted VNRs.

To mitigate this situation with the already published metrics, a novel profit-related performance metric is proposed in this work, named Virtual Network Embedding Normalized Profit (VNE-NP). First, Potential Revenue is defined as the Total Revenue of both accepted and blocked VNRs (not only accepted VNRs as in Embedding Revenue):

$$\begin{aligned} Potential\,Revenue = \sum _{\mathrm {Tot}}Revenue^{\mathrm {VNR}}_i \end{aligned}$$

(11)

The VNE-NP metric is defined by:

$$\begin{aligned} VNE-NP=\frac{Embed.Revenue-Embed.Cost}{Potential\,Revenue} \end{aligned}$$

(12)

It is important to notice that while Embedding Revenue, Embedding Cost and Revenue/Cost Relation are computed over only the accepted (not blocked) VNRs as can be seen in (7), (9) and (10), the Potential Revenue (11) considers both accepted and blocked VNRs.

The VNE-NP performance metric expresses Net Profit of a single successfully embedded VNR as the difference between its Revenue and Cost, which are normalized by the total Potential Revenue of all VNRs in the process (blocked and accepted VNRs).

An additional benefit of VNE-NP is its normalization over potential total revenue, which permits a better comparison among different instances of the problem.

This way, VNE-NP takes into account all important aspects of profit for a VNE process, including:

• 1. the ability of finding a feasible solution for any VNR and therefore to accept the larger possible potential source of profit (Potential Revenue);

• 2. the efficiency of a VNE algorithm in physical resources utilization in the embedding process; and

• 3. the ability in generating more revenue, accepting more complex requests.

The above advantages are shown in Table 1, which compares the five metrics in these three above mentioned aspects.

Table 1. A comparison among the five VNE performance metrics studied

In what follows, an example is presented to show the difference of using VNE-NP with respect to other known metrics and how it can represent a better figure of merit for InP profit for different situations.

4.1 An Example of VNE-NP Application

In Fig. 1(a) it can be seen a physical network with five nodes ($n^\mathrm {P}_1$ to $n^\mathrm {P}_5$) and six links ($l^\mathrm {P}_1$ to $l^\mathrm {P}_6$). Each physical node has three available CPU units and each physical link has two bandwidth units (indicated in parenthesis).  Figure 1(a) also shows three VNRs (VNR 1, VNR 2 and VNR 3) which must be embedded in the physical network using a VNE approach. Each virtual link requires one bandwidth unit, and each virtual node requires one CPU unit, which are not indicated in the figure for simplicity.

We also consider three different VNE algorithms (VNE algorithms A, B and C) which offers three different embedding solutions showed at Figs. 1(b), (c) and (d) respectively.

Fig. 1.

(a) Initial situation; (b) Embedding of VNE Algorithm A; (c) Embedding of VNE Algorithm B; (d) Embedding of VNE Algorithm C.

As we can see in Fig. 1(b), VNE Algorithm A only was able to embed VNRs 1 and 2 while VNR 3 could not be allocated, because there were not enough physical link resources. On the other hand, in Fig. 1(c), Algorithm B succedded in embedding VNRs 2 and 3, but it could not embed VNR 1. However, Algorithm C was successfull in embedding the three VNRs, as it is showed in Fig. 1(d).

Notice that the three VNRs require different numbers of virtual nodes and virtual links and the total demand of resources are different, and that is why they represent different amount of profit for the InP.

Let us calculate and compare the values of the five performance metrics related to InP profit already defined: Accepted Ratio, Embedding Cost, Embedding Revenue, Revenue/Cost Relation and VNE-NP.

Taking $\alpha = \beta = 2$ (The revenue of embedding a virtual node or link gives to the InP an equivalent revenue of two physical units), and $\gamma = \delta = 1$ (CPU units cost the same as Bandwidth units), Table 2 shows the values of the five different performance metrics for the three VNE algorithms.

Table 2. Values of performance metrics for the studied VNE algorithms

4.2 A Discussion of the Results

An initial and important observation is that Algorithm C reaches best values for 4 out of 5 metrics: Accepted Ratio, Embedding Revenue, Revenue/Cost Relation and VNE-NP. That was an expected result, since Algorithm C succedded in embedding the three VNRs, reaching the best revenue and revenue/cost relation in the process. Only Embedding Cost found Algorithm A as the best. This indicates that this metric can be strongly influenced by the diversity of resource demands for different VNRs and can fail in performing a good evaluation.

Now, we can obviate Algorithm C and compare only results for Algorithms A and B for the four remaining performance metrics. We can notice some important aspects:

• Accepted Ratio shows the same results for both algorithms A and B (0,67). Although these algorithms embedded two VNRs and blocked one, the potential revenue of VNR 2 is larger than VNR 1 given that VNR 2 needs more resources. This important aspect is not considered when using Accepted Ratio performance metric.

• Revenue/Cost Relation found better results for Algorithm A, while the two remaining metrics: Embedding Revenue and VNE-NP coincide in finding Algorithm B better than Algorithm A. The difference in complexity between blocked VNRs indicates that this is the expected result. That suggests that Revenue/Cost Relation fails in adequatly compare these two algorithms.

This analysis indicates that for the above example, Embedding Revenue and VNE-NP best express the economical benefit of the InP and the ability in embedding more complex VNRs, with a clear advantage in using VNE-NP given that it is normalized while Embedding Revenue is not.

5 Conclusion

Virtual Network Embedding (VNE) problem leads with the efficient allocation of physical network resources to virtual network requests. A VNE approach is evaluated with global, long-term performance metrics, that are computed at the end of a VNE process (or simulation).

Most used VNE performance metrics are related to economical profit of Infrastructure Provider (InP), being “Embedding Cost” and “Accepted Ratio” the most cited in the literature. However, they can loose objectivity when the resources requested by virtual network requests (VNRs) are heterogeneous, as shown in Sect. 4.

In this work, we propose a novel performance metric, named Virtual Network Embedding-Normalized Profit (VNE-NP), presenting an example where the proposed metric proved to give a better figure of merit than any other metric. The proposed performance metric offers a good, normalized representation of the profit reached by an InP in the VNE process, and considers both the savings in physical resources utilization as well as the ability of finding feasible efficient solutions for a maximum number of VNRs.

In future works, the authors plan to implement VNE-NP to network simulators, in order to evaluate VNE instances jointly with other performance metrics. Besides, it would be interesting to study real economical values of physical network resources (nodes and links resources) in cloud applications, aiming a more real evaluation of VNE-NP metric.