Topology Based Reliable Virtual Network Embedding from a QoE Perspective

Peiying Zhang, Sheng Wu, Miao Wang, Haipeng Yao,＊, Yunjie Liu

1 College of Computer & Communication Engineering, China University of Petroleum (East China), Qingdao 266580, China

2 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications,Beijing 100876, China

3 DFH Satellite Co., Ltd., Beijing 100094, China

Abstract: In the network virtualization environments, one of the most challenges is how to map the virtual networks (VNs) onto a shared substrate network managed by an infrastructure provider (InP), which is termed as virtual network embedding problem. Prior studies on this issue only emphasize on maximizing the revenue or minimizing the energy consumption while ignoring the reliability requirements of end-users. In our work, we incorporate the reliability probability into the virtual network embedding process with an aim to improve the QoS/QoE of end users from a new perspective.We devised two novel reliable virtual network embedding algorithms called RRW-MaxMatch and RDCC-VNE based on RW-MaxMatch and DCC-VNE, respectively. Extensive simulations demonstrated that the efficiency of our proposed algorithms is better than those of two primitive algorithms in terms of the reliability demands, the acceptance ratio of virtual networks and the long-term average revenue.

Keywords: virtual network embedding; reliability probability; node mapping procedure;link mapping procedure; node ranking metric

I. INTRODUCTION

The deployment and installation of new Internet services are increasingly being more and more difficult due to the Internet ossification.To satisfy the demand of increasing number of applications with various qualities of service or qualities of experience (QoS/QoE) requirements [1-6] including reliability, security or other aspects, virtual network embedding has been propounded as the building block for the future Internet architecture, and it exerts a tremendous fascination on many researchers.

In the virtual network environments, traditional Internet service provider (ISPs) are separated into infrastructure providers (InPs)and service providers (SPs). InPs are in the charge of maintaining the substrate network infrastructure, SPs will able to create heterogeneous virtual networks to offer customized end-to-end network services through aggregating distributed or centralized resources from multiple infrastructure providers (InPs). Virtual network embedding is a process of assigning the virtual network requests from service providers to the substrate network infrastructures with the constraints of CPU computing demand on nodes and bandwidth resource requirement on links.

The reliability of provisioning network services is essential to the virtual network embedding algorithm due to the fact that some users would pay expensive cost for the reliable or stable services. Therefore, the metric of reliability for virtual network embedding algorithm is vital to the stakeholders. Prior studies[1, 4, 5] mainly focused on the guaranteeing reliability by means of increasing the physical infrastructures to back up the critical nodes or links. The authors of [1] proposed a strategy to guarantee some levels of reliability by providing backup for virtual nodes and links simultaneous with the instantiation of each virtual infrastructures. The authors of [4] introduced a new reliability-aware VDC embedding algorithm RAVDC that embeds VDC onto the physical servers meanwhile guaranteeing the reliability requirement of the VDC, and the simulation results indicated that the proposed algorithm performs better than those of current VDC embedding algorithms. The authors in [5] proposed an approach with a maximum flow (MF) algorithm for an efficient topology reconfiguration in reconfigurable architectures.In their work, they converted the topology reconfiguration into a network flow problem through constructing a directed graph, and leveraged the MF algorithm to obtain the solution.

Inspired by the theory of Markov random walks (RW) to rank the node importance, we adopt the same theory to measure topology-aware reliability ranking of nodes called the comprehensive metric of node reliability(CMNR). The CMNR can reflect the reliability of node according to its reliability and its connected link reliability. In the node mapping stage, we not only consider the node available resource, but also take into account the comprehensive metric of node reliability (CMNR).Therefore, we can choose the most appropriate substrate node for each virtual node with an aim to offer a reliable virtual network service.In the link mapping stage, we adopt the shortest path algorithm to perform the link mapping process.

The main contribution of this paper can be summarized as follows.

1. We introduced the comprehensive metric of node reliability by means of node reliability and link reliability, and formulated a Markov random walk model to compute the topology-aware reliability ranking values for substrate nodes. To the best of our knowledge,this work is the first time attempting to apply random walks to ranking the node reliability aiming at improving the QoS/QoE of virtual network provisioning services.

2. We proposed two approaches of topology based reliable virtual network embedding algorithm called as RRW-MaxMatch and RDCC-VNE algorithms, respectively. Extensive experiments demonstrated that our proposed methods can improve the performance of embedding system in terms of reliability.

The remainder of this paper is organized as follows. In Section 2, we review the related works associated with the maximum revenue,minimum energy consumption, the reliability and the survivability. Section 3 introduces the network model and problem statement. In Section 4, we present the topology aware comprehensive metric of node reliability using the random walk model. Section 5 describes the reliable virtual network embedding algorithms including RRW-MaxMatch and RDCC-VNE.The proposed virtual network embedding algorithms are evaluated in Section 6. Section 7 concludes this paper.

We used the Markov random walk model to obtain the reliability of substrate nodes.

II. RELATED WORKS

Virtual network (VN) consists of virtual nodes and virtual links. Each virtual node owns some computing resource requirement such as CPU capacity, and each virtual link has some communication resource requirement such as bandwidth resource. The goal of virtual network embedding problem is to allocate the virtual network requests (VNRs) to a shared substrate infrastructure with some constraints such as CPU capacity on nodes and bandwidth resource on links.

The VNE problem is an NP-hard problem even when s single virtual network request is present or when each virtual network request consists of a single virtual node. The virtual network embedding algorithms have been studied in lots of literature [7-30]. Based on its different optimization objectives, the existing VNE algorithms fall under four categories: (1)maximize the revenue or minimize the cost;(2) minimize the energy consumption; (3) reliable virtual network embedding algorithms;and (4) survivable virtual network embedding algorithms.

2.1 Related works with maximum revenue or minimum cost objective

The conventional optimization objective of prior VNE algorithms is maximum revenue or minimum cost, such as the literature [9-13].In these studies, the authors strive to choose the substrate nodes that are close each other aiming at reducing the bandwidth resource consumption. The authors in [9] utilized the multi-commodity flow algorithm to perform the link mapping process with the aim of increasing the acceptance ratio of VN requests if substrate network supports splitting data transmit mechanism. In literature [10], the authors use the heuristic algorithm with less computation complexity to solve the solution. The authors of [11] incorporated topology attributes and network resource into the virtual network embedding process. The authors of [12] employed the Markov Random Walk (RW) model to measure embedding potential of a substrate node according to its resource and topological structure of substrate network. In literature[13], the authors proposed a unified enhanced PSO based virtual network embedding algorithm VNE-UEPSO, aiming at solve these two models regardless of the support for path splitting.

2.2 Related works with minimum energy consumption objective

The authors of [14] introduced a green energy-aware hybrid virtual network embedding approach, with the aim of achieving energy efficiency and resource consolidation. In their work, three different resource selection criteria including energy source, request priority, and request location are taken into consideration.The authors in [15] proposed the node energy model and link energy model with the purpose of minimizing the overall energy consumption. They formulated a mixed integer linear programming model for virtual network embedding, and utilized heuristic algorithm to solve this problem. An efficient algorithm for energy-aware virtual network embedding is proposed in [16]. In this work, there are three main contributions: (1) the proposed algorithm allows multiple virtual nodes to be mapped onto the same substrate node; (2) the proposed algorithm gives higher priority to those substrate nodes that already activated for hosting newly arrived virtual nodes; (3) the proposed method formulates both node energy consumption model and link energy consumption model. The authors of [17] utilized resource consolidation technique to save the energy consumption of substrate network, the aim of the proposed method is to assign the virtual network requests onto a reduced set of substrate network equipment. In their study, they proposed a mixed integer program model and used the ALEVIN framework to solve it for evaluating its performance against near-optimal cost-based heuristics.

2.3 Related works with reliability optimization objective

In case of substrate network suffers from attack or equipment failure, it will affect the already mapped virtual networks, such as service interruption, lower user experience and economic loss of service providers (SPs) and so on. To address these issues, we should take into consideration of the reliability of virtual network embedding, aiming at improving the ability of substrate network to cope with facility failure. Facing different substrate network environments, there are different methods to deal with the reliability of virtual network embedding. In the static substrate network environments, we mainly take into consideration of the network connectivity and load balancing with the purpose of improving the reliability.The most representatives of these algorithms are [18-19]. The authors in [18] presented a reliable virtual network embedding algorithm aiming at dealing with the issue of a single node failure condition, which ensures that the completeness of the virtual network and continuity of services. In the dynamic substrate network environments, we primarily employ the backup resource migration or re-mapping invalidation resources to address the issue of mapping reliability. The authors of [19] introduced a virtual network reliable mapping scheme based on topology impact degree and backtracking migration aiming at facing the dynamic network topology environment.

Different from the aforementioned studies,we investigate the reliable virtual network embedding algorithm on top of limited substrate resources, which selected reliable substrate nodes for mapping virtual nodes with an aim to increase the probability of instable network services. In this manner, we can improve the quality of experiences (QoE) for end-users in a new perspective.

2.4 Related works with survivable optimization objective

Some survivable virtual network embedding algorithms are studied in literature [20-23].The aim of [20] is to strive for making up for substrate facility failures through increasing extra substrate resources. The major contribution of [20] is to formulate the survivable virtual network embedding with an aim to address single substrate link failure for the first time. The single substrate link failure is a frequent event, while the multiple substrate link failure is a low probability event. Therefore, it is a hot research issue in the network virtualization. The authors of [21] investigated the 1+1-Protected virtual network embedding issue. They proposed a dedicated protection mechanism called DRONE to perform virtual network embedding process. DRONE includes an integer linear programming formulation for optimal solution (OPT-DRONE) and a heuristic (FAST-DRONE) to deal with the long running time problem. Experimental results indicated that the FAST-DRONE can accept four times more VN requests on average compared to the state-of-the-art solution for provisioning dedicated protection to VNs. To address the survivable virtual network embedding problem, the authors in [22] proposed survivability in multi-path link embedding, which guarantees VN survivability against single link failure while incurring minimal resource redundancy using path diversity. A recent study by Xiao A. et al. [23] reported a topology-aware VN embedding method striving to address the problem of multiple node failures.

The major difference between these studies and our work is that our proposed methods do not occupy extra substrate resources for guaranteeing reliable virtual network provisioning services. The trend of differentiated services would lead to more revenue for InPs using our proposed reliable virtual network embedding algorithms. In addition, our proposed methods could improve the users’ QoS/QoE of provisioning network services from SPs.

III. NETWORK MODEL AND VIRTUAL NETWORK EMBEDDING DESCRIPTION

3.1 Substrate network infrastructure

We model a substrate network infrastructure as a weighted undirected graph and denote it by Gs=(Vs,Es) , where Vsand Esrepresent the set of substrate nodes and substrate links,respectively. Each substrate node vs∈Vsis associated with some constraints such as CPU capacity CPU(vs) and geographic locationloc(vs). Each substrate link es=(i,j)∈Esbetween two substrate nodes i and j is associated with the communication capacity such as BW(es) denoting the total amount of available bandwidth resource. We define the set of all substrate paths by Ps, and the set of substrate paths from source node s to destination node t by Ps(s,t ).

The left part of figure 1 illustrates a substrate network, where the numbers over the links represent the available bandwidth resource and the residual bandwidth resource separating by a vertical line, the numbers aside the nodes represent the available CPU capaci-ty in the first rectangular box and the residual CPU capacity in the second rectangular box.

3.2 Virtual network request

Similarly, a virtual network request is modelled as an undirected weighted graph Gv=(Vv,Ev), where Vvand Evrepresent the set of virtual nodes and virtual links, respectively. For a virtual node nv∈Vv, its demanded CPU capacity can be defined as CPU(nv). For a virtual link lv(i,j)∈Ev, where i and j represent the two end nodes of lv, and its required bandwidth resource can be defined as BW(lv). A virtual network request consists of three virtual nodes and three virtual links is depicted in the right part of figure 1. The numbers in rectangular boxes aside the nodes denote their required CPU capacity, and the numbers over the links denote their required bandwidth resource.

3.3 Virtual network embedding problem description

The process of virtual network embedding can be expressed by a mapping function M :→, from Gvto a subset of Gs, whereand. The mapping process can be generally decomposed into two mapping steps: (i) node mapping:mapping the virtual nodes to heterogeneous substrate nodes meanwhile satisfying the CPU computing resource constraints on nodes; (ii)link mapping: mapping the virtual links onto a loop-free substrate link meanwhile satisfying the bandwidth resource constraints on links.

Fig. 1. The illustration of virtual network and substrate network.

Fig.1 demonstrates a solution of virtual network embedding for virtual network request which is depicted in the right part of figure 1. The mapping solution can be represented by node mapping result{a→E,b→F,c→C} and link mapping result {(a,b)→Ps(E,F),(b,c)→Ps(F,C),(a,c)→Ps(E,B,C)}.

3.4 Objectives

In substrate network, substrate nodes refer to concrete servers or facilities. Due to the reasons such as wear and aging and so on, some servers or facilities broke down over time.The main objective of our work is to enhance the degree of reliability to make the solution of virtual network embedding more reliable,i.e., to make the allocated substrate network infrastructure including substrate nodes and substrate links owning high reliability.

Similar to the literature [12], [25], the revenue of accommodating a VNR at time t can be defined as:

where CPU(nv) denotes the CPU capacity requirement for virtual node nv, BW(lv) denotes the bandwidth resource requirement for virtual link lv.

The cost of hosting a VNR at time t can be defined as the sum of the CPU capacity resource and bandwidth resource that allocated to the VNR:

The acceptance ratio of VN requests can be defined as:

where acceptance represents the acceptance ratio of VN requests, VNRaccrepresents the number of the accepted VNRs, and VNRarrrepresents the number of the arrived VNRs.

For the InPs, the goal of VN embedding algorithm is to maximize the revenue of InPs and increase the resource utilization of the substrate network in the long run.

IV. TOPOLOGY-BASED NODE RELIABILITY RANKING

The process of virtual network embedding contains node mapping stage and link mapping stage. In node mapping stage, we prefer the substrate nodes with sufficient CPU capacity and high reliability for virtual nodes from VNRs. In link mapping stage, we give embedding priority to the reliable substrate links with sufficient bandwidth resource. Specifically, we take a different perspective by incorporating topology attributes during the node mapping process, with the aim of leveraging available resources and node/link reliability probability to improve the virtual network embedding algorithm. The aim of our work is to strive to find a solution that can enhance the mapping reliability without sacrificing too much revenue or acceptance ratio, the reason is that once some substrate nodes are broken down, the cost of reconfiguration or remapping VN requests should also be taken into consideration.

4.1 Motivation

A motivation example is illustrated in figure 2. In the figure 2, the number in the rectangular box next to node represents the metric of node reliability (MNR), the number over link represents the metric of link reliability (MLR).Node A and E seem to have the same metric of reliability if they are considered alone.However, the node E is a more “reliable” node because its directly connected links are more reliable than that of node A.

We define the notion of node reliability metric with the aim of measuring the reliability of a substrate node. Intuitively, the reliability of a substrate node nsis affected by its node reliability, but the fact is that the reliability of a substrate node is not only determined by its node reliability, but also determined by the link reliability of its directly connected links.Here we assume that the reliability of nodes and links are independent.

The comprehensive metric of reliability for a substrate node nscan be defined as follows:

where Rnsdenotes the comprehensive metric of node reliability (CMNR), rnsdenotes the metric of node reliability (MNR) for substrate node, nbr(ns) denotes the set of substrate links that are directly connected to substrate node ns, rlsdenotes the metric of link reliability (MLR).

4.2 A example to illustrate the motivation

The comprehensive metric of node reliability for substrate node A is computed as:

The comprehensive metric of node reliability for substrate node E is computed as:

Therefore, mapping a virtual node onto substrate node E has a higher opportunity to achieve a reliable virtual network mapping than mapping it onto substrate node A.

4.3 The metric of node reliability

Fig. 2. A motivation example.

In the substrate network, the node reliabili-ty is not only affected by its comprehensive metric of node reliability, but also affected by the comprehensive metric of its neighborhood node reliability. The neighborhood nodes of node u can be defined as the node set that can be reached from node u. We classify the neighborhood nodes into two groups, one is refers to the node set that have at least one link connected to it, the other one is refers to the node set that can be reached from it via multiple hops.

The initial CMNR value for node nscan be calculated as follows:

Suppose that u,v∈nsbe two different nodes.

+=×6 Algorithm 1. CMNR Computation Algorithm.1 Initialize the matrix CMNR(0) using formula (7).2 Calculate the Markov Transition matrix T.3 Initialize the variable ε,0←i.4 repeat 5 CMNRTCMNR(1)()i i δ←−CMNRCMNR(1)()i+i 7 i++8 until δ＜ε

For a node v∈V, the following formula is used to iterate with the aim of obtaining the final CMNR value for a node v.

where α+β=1,α＞0,β＞0, and t=0,1,2,....The parameters α and β are tuning factors aiming to balance the two parts.

For a substrate network with n nodes, its node set, letand denote bythe vector of node ranking at iteration t, where t=0,1,2,.... Thus,

where T is a one-step transition matrix of the Markov chain and it can be defined as:

Note that the maximum eigenvalue of matrix T equals to one, T is a stable matrix. This can guarantee the convergence of Markov chain. Here we use the classical iteration algorithm to compute the CMNR.

4.4 The metric of node ranking

In this section, we modified two existing algorithms including RW-MaxMatch [12] and DCC-VNE [25]. On the foundation of these two algorithms, we modified their node ranking methods by multiplying the comprehensive metric of node reliability CMNR(ni). The two metrics of node ranking are defined as follow:

where HRRW(ni) and HRDCC(ni) represent the two modified node ranking values based on the RW-MaxMatch and DCC-VNE algorithms.

OK, Listen, please! There were 10 birds rested at the tree branches, one boy used a stone to hit one bird down, the question is how many birds are left in the tree? I asked.

V. RELIABLE VIRTUAL NETWORK EMBEDDING ALGORITHM

Taking advantage of the topology-aware comprehensive metric of node reliability, we devise two novel VN embedding algorithms called RRW-MaxMatch and RDCC-VNE respectively. In this section, we will detail the two algorithms.

5.1 The RRW-MaxMatch algorithm

In this section, we will describe the details of RRW-MaxMatch algorithm. The algorithm is composed of two procedures including node mapping and link mapping. The node mapping algorithm for RRW-MaxMatch is illustrated in algorithm 2.

The link mapping algorithm for RRW-Max-Match is illustrated in algorithm 3.

5.2 The RDCC-VNE algorithm

In this section, we will describe the details of RDCC-MaxMatch algorithm. The algorithm is composed of two procedures including node mapping and link mapping. The node mapping algorithm for RDCC-VNE is illustrated in algorithm 4.

The link mapping algorithm for RDCC-VNE is illustrated in algorithm 5.

VI. SIMULATION RESULTS AND ANALYSIS

In this section, we will describe our simulation experimental setting and discuss the simulation results.

?

?

?

Fig. 3. The acceptance ratio of virtual networks.

Fig. 4. The long-term average revenue.

?

6.1 Simulation experimental setting

In this section, we give our simulation experimental setting. The topology of substrate network consists of 100 nodes and 570 links.The CPU capacity of substrate nodes and the bandwidth resource of substrate links are uniformly distributed in U[50, 100]. The reliable probability of substrate nodes and substrate links are uniformly distributed in U[0.8, 1.0].The process of VNR’s arrival can be viewed as a Poisson process, and its average arrival rate is set to 5 VNRs per 100 time units. The number of virtual nodes in VNRs is uniformly distributed in U[2, 10]. The connectivity probability of every two virtual nodes is set to 0.5.The demanded CPU capacity of virtual nodes and the required bandwidth resource are uniformly distributed in U[0, 50]. We carried out five experiments and took their average value as the final results.

6.2 Experimental results and analysis

In this section, we conduct three experiments with the aim of evaluating the performance of our proposed algorithms against other algorithms. These three experiments are using the failure probability of 0.85, 0.90, and 0.95 respectively. The threshold of failure probability means that the facility will fail if the reliability probability of nodes and links are lesser than the threshold value.

Experiment 1:The threshold value of failure probability is set to 0.85. The acceptance ratio of virtual networks and the long-term average revenue of InP are illustrated in figure 3 and figure 4.

Result Analysis:From the figure 3 and figure 4, we can see that the performance of RRW-MaxMatch and RDCC-VNE is better than those of RW-MaxMatch and DCC-VNE.The reason is that our proposed two algorithms take into consideration of the reliability of substrate nodes and links. This will lead to reliable virtual network embedding. In case of some substrate resources lose efficacy, the available substrate network resource can still host the majority of virtual network requests.

Experiment 2:The threshold value of failure probability is set to 0.90. The acceptance ratio of virtual networks and the long-term average revenue of InP are illustrated in figure 5 and figure 6.

Result Analysis:From the figure 5 and figure 6, we can see that the overall performance of our proposed two algorithms is better than those of original algorithms. In the initial running time, the acceptance ratios of virtual networks for these four algorithms are crossing each other, the reason is that the substrate network resource is abundant in this phrase, the different metrics of node ranking for substrate nodes have little influence on the acceptance ratio of virtual networks. However, the overall trends of these four algorithms are stable,which can validate our proposed algorithms.

Experiment 3:The threshold value of failure probability is set to 0.95. The acceptance ratio of virtual networks and the long-term average revenue of InP are illustrated in figure 7 and figure 8.

Result Analysis:From the figure 7 and figure 8, we can see that the overall performance of our proposed two algorithms is better than those of original two algorithms.The improved performance of our proposed algorithms are not obvious, when the threshold value of reliability probability is higher.The reason is that when the threshold value is higher than 0.9, the majority of substrate nodes and links are reliable which can deteriorate the performance of our proposed algorithms.

VII. CONCLUSION AND FUTURE WORK

Virtual network embedding is a promising technique to overcome the ossification of current network architecture. In this paper, we proposed two reliable approaches for virtual network embedding with an aim to increase the revenue or improve the users’ QoS/QoE of provisioning network services. Specifically,we used the Markov random walk model to obtain the reliability of substrate nodes. Extensive simulation experiments demonstrated that the proposed algorithm can greatly improve the performance of virtual network embedding in terms of reliability, the acceptance ratio of virtual networks and the long-term average revenue.

Fig. 5. The acceptance ratio of virtual networks.

Fig. 6. The long-term average revenue.

Fig. 7. The acceptance ratio of virtual networks.

Fig. 8. The long-term average revenue.

The aim of our work is to incorporate reliability probability of substrate nodes/links into virtual network embedding process, and improve the QoS/QoE of end users from a reliable perspective using the same substrate resources. This research may provide an alternative to the virtual network embedding problem from the point of view of reliability. In case of facility failures, the conventional VNE algorithms must re-embed the virtual network requests or migrate substrate nodes/links in order to offer stable network services. This process would incur some costs due to re-embedding or migration. However, our proposed methods choosing reliable substrate nodes/links for provisioning virtual network services could improve the QoS/QoE of end users. The limitation of our work is lacking of sufficient experimental comparison with the recent research literature [26-29]. In our future work,we intend to carry out more experiments with an aim to validate our proposed methods.

ACKNOWLEDGMENTS

This work is supported by “the Fundamental Research Funds for the Central Universities” of China University of Petroleum(East China) (Grant No. 18CX02139A), the Shandong Provincial Natural Science Foundation, China (Grant No. ZR2014FQ018),the National Natural Science Foundation of China (Grant No. 61471056), the National Basic Research Program (973) of China(Grant No. 2012CB315801), the Research on coordinated management and control technology of network and satellite multi-domain network resources (Grant No. 17-H863-01-ZT-001-001-02) and the China research project on key technology strategy of infrastructure security for information network development. The authors also gratefully acknowledge the helpful comments and suggestions of the reviewers, which have improved the presentation.