# A Hybrid Reliable Heuristic Mapping Method Based on Survivable Virtual Networks for Network Virtualization

Authors: Qiang Zhu; Hui-Qiang Wang; Guang-Sheng Feng; Hong-Wu Lv; Zhen-Dong Wang; Xiu-Xiu Wen; Wei Jiang
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

The reliable mapping of virtual networks is one of the hot issues in network virtualization researches. Unlike the traditional protection mechanisms based on redundancy and recovery mechanisms, we take the solution of the survivable virtual topology routing problem for reference to ensure that the rest of the mapped virtual networks keeps connected under a single node failure condition in the substrate network, which guarantees the completeness of the virtual network and continuity of services. In order to reduce the cost of the substrate network, a hybrid reliable heuristic mapping method based on survivable virtual networks (Hybrid-RHM-SVN) is proposed. In Hybrid-RHM-SVN, we formulate the reliable mapping problem as an integer linear program. Firstly, we calculate the primary-cut set of the virtual network subgraph where the failed node has been removed. Then, we use the ant colony optimization algorithm to achieve the approximate optimal mapping. The links in primary-cut set should select a substrate path that does not pass through the substrate node corresponding to the virtual node that has been removed first. The simulation results show that the acceptance rate of virtual networks, the average revenue of mapping, and the recovery rate of virtual networks are increased compared with the existing reliable mapping algorithms, respectively.


---

## Body

## 1. Introduction

Due to the “best effort” service model of the Internet, cloud computing is facing challenges in service diversity providing. Network virtualization is an effective technique to solve this problem [1–3]. Network virtualization allows multiple independent virtual networks cohabiting on a shared substrate network, which can quickly and cost-effectively carry out new types of business and technologies [4]. Virtual network requests consisting of virtual nodes and virtual links with resource constraints are generated by users. How to provide reasonable substrate network resources allocation for virtual network requests is called virtual network mapping, which has been proved to be a NP-hard problem [5, 6].Previous researches on the virtual network mapping problem are almost concerned with the acceptance rate, the resource utilization, and the average revenue of the substrate network with no fault, such as ViNEYard algorithm [7], RW-BFS algorithm [8], DVNMA algorithm [9], distributed virtual network mapping algorithm [10], subgraph isomorphism detection based mapping algorithm [11], path splitting and migration [12], and other heuristic algorithms [13–15], without considering with the reliability of the mapped virtual networks. However, the nodes and the links in substrate network are inevitably affected by internal and external influences in actual situation, undermining the continuity of virtual network services.To solve the reliable virtual network mapping problem, previous researches mainly use protection mechanisms [16]. Rahman and Boutaba [17] proposed a hybrid strategy heuristic algorithm by utilizing a prereserved quota for backing up on each substrate link. In order to reduce the redundant backup resources, Yu et al. [18] proposed a method that nodes and links are backed up in different areas for virtual networks, which requires virtual nodes to transmit the current states to the backup nodes and exacerbates substrate network resources consumption. Yeow et al. [19] proposed an optimizing redundancy pool to allocate backup resources to multiple virtual networks dynamically, which can reduce redundant resources consumption of the substrate network. The protection mechanisms preassign redundant substrate resources for virtual networks. The disadvantage of the protection mechanisms is that it will bring excessive consumption to the substrate network and impact acceptance rate of virtual networks and revenue of the substrate network in the long run. Unlike the protection mechanisms, Butt et al. [20] proposed a topology-awareness and reoptimization mechanism based on node migration and link remapping, which does not provide virtual networks with redundancies. If a node or link failure occurs, the affected virtual node migrates to normal substrate node and the virtual links are remapped in order to recover the virtual network. In addition, the literature [21] also uses a recovery mechanism to deal with the reliable virtual network mapping problem. The main problem of the recovery mechanisms is that the recovery rate will be low when there are few resources in the substrate network.Inspired by the survivable routing in wavelength division multiplexing WDM (wavelength division multiplexing) optical network in literature [22], we propose the concept of survivable virtual network, which is different from traditional protection mechanisms and recovery mechanisms. In WDM optical networks, substrate resources are allocated to different logical networks. Any failure in the substrate network will lead to service interruptions. Survivable routing in WDM optical network means when the substrate network failure occurs, the affected optical network maintains the maximizing degree of connectivity, which can maintain a tolerable level of service and the ability for quick recovery [23, 24]. In this paper, the survivable virtual network needs to consider not only the links mapping, but also the nodes mapping, which is more complex than the survivable routing in WDM optical networks. To make the virtual networks with survivability, the mapping of virtual network needs a survivable strategy. When the substrate network is under a node failure, the rest of the mapped virtual networks needs to remain connected to ensure the continuity of virtual network services and finally uses the node migration and link remapping to repair the affected virtual networks.In order to reduce the cost of the substrate network, a hybrid reliable heuristic mapping method based on survivable virtual networks is proposed. In Hybrid-RHM-SVN, we formulate the reliable mapping problem as an integer linear programming model. Firstly, we calculate the primary-cut set of the virtual network subgraph where the failed node has been removed. Then, we use ant colony optimization algorithm to achieve the approximate optimal mapping. The links in the primary-cut set should be selected from the substrate paths that do not pass through the substrate node corresponding to the virtual node that has been removed first.


## 2. Reliable Virtual Network Mapping Formulation

In this section, we provide a mathematical formulation for the reliable virtual network mapping problem. We map virtual networks with survivable strategy in the substrate network. The reliable virtual network mapping formulation is composed by the substrate network and virtual network requests modeling, virtual networks mapping problem modeling, and virtual network survivability analysis.


### 2.1. Substrate Network

Similar to the previous works in [7–21], the substrate network is modelled as an undirected graph by Gs=(Ns,Es,Ans,Aes), where Ns is the set of the substrate nodes and Es is the set of the substrate links. Ans is an attribute set of each substrate node ns∈Ns including available CPU computing capability cpu(ns) and location loc⁡(ns). Aes is an attribute set of each substrate link eijs∈Es between i and j. The attribute of the substrate links is available bandwidth capability b(es). Ans and Aes can be extended by adding other attributes such as memory capability and link delay. Ps is the set of loop-free paths in the substrate network, and Ps(i,j) is the set of the loop-free path between i and j.


### 2.2. Virtual Network Request

Similar to the substrate network, a virtual network request is also modelled as an undirected graph byGv=(Nv,Ev,Cnv,Cev), where Nv is the set of virtual nodes and Ev is the set of virtual links. Cnv is the attributes set of virtual nodes including available CPU computing capability demand cpu(nv) and location demand loc⁡(nv). Cev is the attributes set of each virtual link consisting of available bandwidth capability demand b(ev).


### 2.3. Virtual Network Mapping Problem Modeling

The virtual network mapping problem is defined as mapping a virtual networkGv to Gs′, which is a subset of Gs. The CPU, location, and bandwidth constraints in Gv are all needed to be satisfied. The virtual network mapping can be naturally defined by fN:(Nv,Ev,Cnv,Cev)→(Ns′,Ps′), where Ns′⊂Ns and Ps′⊂Ps.


### 2.4. Virtual Network Survivability Analysis

In literature [22], Todimala and Ramamurthy have proved that the routing of virtual topology Gv over physical topology Gs is survivable if and only if Gv,i is the node set that the virtual node corresponding to the substrate node with failure has been removed and the primary-cut set PCSGv,iS,Nv,i∖S of the virtual topology exists at least one link not routed over any of the links passing through the substrate node with failure. Nv,i is the virtual node set of Nv-{i}. S,Nv,i∖S is a cut set of Gv without node i, which divides the set Nv,i into set S and set Nv,i∖S. The cut set CSGv,iS,Nv,i∖S=p,q∣p,q∈E∧p∈S∧q∈Nv,i∖S. It also classifies cuts of the graph into primary-cuts and secondary-cuts based on the connectedness of the partitions. A cut is called a primary-cut if and only if both of the induced subgraphs are connected components. For the primary-cut PCSGv,iS,Nv,i∖S, the subgraphs that formed by node sets S and Nv,i∖S are connected components. This conclusion provides inspiration for virtual network survivability in our reliable virtual network mapping method.


## 2.1. Substrate Network

Similar to the previous works in [7–21], the substrate network is modelled as an undirected graph by Gs=(Ns,Es,Ans,Aes), where Ns is the set of the substrate nodes and Es is the set of the substrate links. Ans is an attribute set of each substrate node ns∈Ns including available CPU computing capability cpu(ns) and location loc⁡(ns). Aes is an attribute set of each substrate link eijs∈Es between i and j. The attribute of the substrate links is available bandwidth capability b(es). Ans and Aes can be extended by adding other attributes such as memory capability and link delay. Ps is the set of loop-free paths in the substrate network, and Ps(i,j) is the set of the loop-free path between i and j.


## 2.2. Virtual Network Request

Similar to the substrate network, a virtual network request is also modelled as an undirected graph byGv=(Nv,Ev,Cnv,Cev), where Nv is the set of virtual nodes and Ev is the set of virtual links. Cnv is the attributes set of virtual nodes including available CPU computing capability demand cpu(nv) and location demand loc⁡(nv). Cev is the attributes set of each virtual link consisting of available bandwidth capability demand b(ev).


## 2.3. Virtual Network Mapping Problem Modeling

The virtual network mapping problem is defined as mapping a virtual networkGv to Gs′, which is a subset of Gs. The CPU, location, and bandwidth constraints in Gv are all needed to be satisfied. The virtual network mapping can be naturally defined by fN:(Nv,Ev,Cnv,Cev)→(Ns′,Ps′), where Ns′⊂Ns and Ps′⊂Ps.


## 2.4. Virtual Network Survivability Analysis

In literature [22], Todimala and Ramamurthy have proved that the routing of virtual topology Gv over physical topology Gs is survivable if and only if Gv,i is the node set that the virtual node corresponding to the substrate node with failure has been removed and the primary-cut set PCSGv,iS,Nv,i∖S of the virtual topology exists at least one link not routed over any of the links passing through the substrate node with failure. Nv,i is the virtual node set of Nv-{i}. S,Nv,i∖S is a cut set of Gv without node i, which divides the set Nv,i into set S and set Nv,i∖S. The cut set CSGv,iS,Nv,i∖S=p,q∣p,q∈E∧p∈S∧q∈Nv,i∖S. It also classifies cuts of the graph into primary-cuts and secondary-cuts based on the connectedness of the partitions. A cut is called a primary-cut if and only if both of the induced subgraphs are connected components. For the primary-cut PCSGv,iS,Nv,i∖S, the subgraphs that formed by node sets S and Nv,i∖S are connected components. This conclusion provides inspiration for virtual network survivability in our reliable virtual network mapping method.


## 3. Integer Linear Programming Formulation

In this paper, we formulate the reliable heuristic mapping problem as an integer linear program in the following manner with the objective function of minimizing the cost of the substrate network.


### 3.1. Variable Description

(1)ηim, a binary variable, denotes the mapping relationship between virtual nodes and substrate nodes. If the virtual node m is mapped to the substrate node i, ηim=1, and ηim=0 otherwise.(2)φijmn, a binary variable, denotes the mapping relationship between virtual links and substrate links. If the virtual node m is mapped to the substrate node i, φijmn=1, and φijmn=0 otherwise.


### 3.2. Objective Function

Consider(1)min⁡⁡∑(i,j)∈Aes∑(m,n)∈Cevφijmnbemn.


### 3.3. Constraints

#### 3.3.1. Node Constraints

Consider(2)∀i∈Ns,∀m∈Nv,ηimcpum≤cpui,(3)∀i∈Ns,∀m∈Nv,ηimloc⁡m-loc⁡i≤Dm,(4)∀i∈Ns,∑m∈Nvηim≤1,(5)∀m∈Nv,∑i∈Nsηim=1.


#### 3.3.2. Link Constraints

Consider(6)∀i,j∈Ns,∀m,n∈Nv,φijmnbemn≤beij,(7)∀i∈Ns,∀m,n∈Ev,∑(i,j)∈Esφijmn-∑(j,i)∈Esφjimn=1ifηim=1-1ifηin=10otherwise.


#### 3.3.3. Survivability Constraints

Consider(8)∀i∈Ns,∀Nv,i∈Nv,∑(m,n∈CS(PCSS,Gv,i∖S))φijmn+φjimn<PCSS,Nv,i∖S.Remarks. (1) The objective function (1) is to minimize the cost of the link mapping. For a specific virtual network request, the resources allocated to the virtual nodes are identical. However, the resources assigned to the virtual links depend on the length of the substrate links. For this reason, we use the bandwidth usage of the substrate links to measure the cost of mapping.(2) Constraint (2) means that the rest available CPU resources of substrate nodes should meet the demand constraints of virtual nodes. Constraint (3) means the locations of the substrate node loc⁡(i) and the virtual node loc⁡(m) should be at a distance within the range of D(m). loc⁡(m)-loc⁡i denotes the distance between m and i.(3) Constraints (4) and (5) enforcing each virtual node in a virtual network request can only be assigned to one substrate node. Any two virtual nodes cannot be assigned to the same substrate node. Virtual nodes from different virtual networks can be assigned to the same substrate node.(4) Constraint (6) indicates that the virtual link can be mapped to the substrate link which needs to satisfy the condition that the rest available bandwidth resource of the substrate link should meet the demand constraints of the virtual link.(5) Constraint (7) represents link connectivity constraints. If virtual nodes m and n are mapped to the substrate nodes i and j, the virtual link (m,n) is mapped to the substrate link p∈Ps(i,j) between i and j. If the node i is the source node, m is mapped to i and ηim=1. The inflow of the source node is 0 and the outflow is 1. If the node i is the destination node, n is mapped to i and ηin=1. The inflow of the destination node is 1 and the outflow is 0. For other nodes, the inflow and outflow are both 0. In brief, the link connectivity constraint equations above can be expressed as (7).(6) Constraint (8) represents the survivability constraints of virtual networks. Let PCSS,Nv,i∖S denote the number of virtual links in the primary-cut set PCS(S,Nv,i∖S). For the virtual network with the removal of node i, the number of virtual links in primary-cut set that mapped to the same substrate link should be less than the number of virtual links in the primary-cut set, which means the virtual links in the same primary-cut set should not be mapped to the same substrate link. If the virtual links in the same primary-cut set are mapped to the same substrate link, substrate node failures will lead to the failures of links that pass through the substrate node. It means that if we remove all the links in the primary-cut set, the figure will no longer keep its connectivity.


## 3.1. Variable Description

(1)ηim, a binary variable, denotes the mapping relationship between virtual nodes and substrate nodes. If the virtual node m is mapped to the substrate node i, ηim=1, and ηim=0 otherwise.(2)φijmn, a binary variable, denotes the mapping relationship between virtual links and substrate links. If the virtual node m is mapped to the substrate node i, φijmn=1, and φijmn=0 otherwise.


## 3.2. Objective Function

Consider(1)min⁡⁡∑(i,j)∈Aes∑(m,n)∈Cevφijmnbemn.


## 3.3. Constraints

### 3.3.1. Node Constraints

Consider(2)∀i∈Ns,∀m∈Nv,ηimcpum≤cpui,(3)∀i∈Ns,∀m∈Nv,ηimloc⁡m-loc⁡i≤Dm,(4)∀i∈Ns,∑m∈Nvηim≤1,(5)∀m∈Nv,∑i∈Nsηim=1.


### 3.3.2. Link Constraints

Consider(6)∀i,j∈Ns,∀m,n∈Nv,φijmnbemn≤beij,(7)∀i∈Ns,∀m,n∈Ev,∑(i,j)∈Esφijmn-∑(j,i)∈Esφjimn=1ifηim=1-1ifηin=10otherwise.


### 3.3.3. Survivability Constraints

Consider(8)∀i∈Ns,∀Nv,i∈Nv,∑(m,n∈CS(PCSS,Gv,i∖S))φijmn+φjimn<PCSS,Nv,i∖S.Remarks. (1) The objective function (1) is to minimize the cost of the link mapping. For a specific virtual network request, the resources allocated to the virtual nodes are identical. However, the resources assigned to the virtual links depend on the length of the substrate links. For this reason, we use the bandwidth usage of the substrate links to measure the cost of mapping.(2) Constraint (2) means that the rest available CPU resources of substrate nodes should meet the demand constraints of virtual nodes. Constraint (3) means the locations of the substrate node loc⁡(i) and the virtual node loc⁡(m) should be at a distance within the range of D(m). loc⁡(m)-loc⁡i denotes the distance between m and i.(3) Constraints (4) and (5) enforcing each virtual node in a virtual network request can only be assigned to one substrate node. Any two virtual nodes cannot be assigned to the same substrate node. Virtual nodes from different virtual networks can be assigned to the same substrate node.(4) Constraint (6) indicates that the virtual link can be mapped to the substrate link which needs to satisfy the condition that the rest available bandwidth resource of the substrate link should meet the demand constraints of the virtual link.(5) Constraint (7) represents link connectivity constraints. If virtual nodes m and n are mapped to the substrate nodes i and j, the virtual link (m,n) is mapped to the substrate link p∈Ps(i,j) between i and j. If the node i is the source node, m is mapped to i and ηim=1. The inflow of the source node is 0 and the outflow is 1. If the node i is the destination node, n is mapped to i and ηin=1. The inflow of the destination node is 1 and the outflow is 0. For other nodes, the inflow and outflow are both 0. In brief, the link connectivity constraint equations above can be expressed as (7).(6) Constraint (8) represents the survivability constraints of virtual networks. Let PCSS,Nv,i∖S denote the number of virtual links in the primary-cut set PCS(S,Nv,i∖S). For the virtual network with the removal of node i, the number of virtual links in primary-cut set that mapped to the same substrate link should be less than the number of virtual links in the primary-cut set, which means the virtual links in the same primary-cut set should not be mapped to the same substrate link. If the virtual links in the same primary-cut set are mapped to the same substrate link, substrate node failures will lead to the failures of links that pass through the substrate node. It means that if we remove all the links in the primary-cut set, the figure will no longer keep its connectivity.


## 3.3.1. Node Constraints

Consider(2)∀i∈Ns,∀m∈Nv,ηimcpum≤cpui,(3)∀i∈Ns,∀m∈Nv,ηimloc⁡m-loc⁡i≤Dm,(4)∀i∈Ns,∑m∈Nvηim≤1,(5)∀m∈Nv,∑i∈Nsηim=1.


## 3.3.2. Link Constraints

Consider(6)∀i,j∈Ns,∀m,n∈Nv,φijmnbemn≤beij,(7)∀i∈Ns,∀m,n∈Ev,∑(i,j)∈Esφijmn-∑(j,i)∈Esφjimn=1ifηim=1-1ifηin=10otherwise.


## 3.3.3. Survivability Constraints

Consider(8)∀i∈Ns,∀Nv,i∈Nv,∑(m,n∈CS(PCSS,Gv,i∖S))φijmn+φjimn<PCSS,Nv,i∖S.Remarks. (1) The objective function (1) is to minimize the cost of the link mapping. For a specific virtual network request, the resources allocated to the virtual nodes are identical. However, the resources assigned to the virtual links depend on the length of the substrate links. For this reason, we use the bandwidth usage of the substrate links to measure the cost of mapping.(2) Constraint (2) means that the rest available CPU resources of substrate nodes should meet the demand constraints of virtual nodes. Constraint (3) means the locations of the substrate node loc⁡(i) and the virtual node loc⁡(m) should be at a distance within the range of D(m). loc⁡(m)-loc⁡i denotes the distance between m and i.(3) Constraints (4) and (5) enforcing each virtual node in a virtual network request can only be assigned to one substrate node. Any two virtual nodes cannot be assigned to the same substrate node. Virtual nodes from different virtual networks can be assigned to the same substrate node.(4) Constraint (6) indicates that the virtual link can be mapped to the substrate link which needs to satisfy the condition that the rest available bandwidth resource of the substrate link should meet the demand constraints of the virtual link.(5) Constraint (7) represents link connectivity constraints. If virtual nodes m and n are mapped to the substrate nodes i and j, the virtual link (m,n) is mapped to the substrate link p∈Ps(i,j) between i and j. If the node i is the source node, m is mapped to i and ηim=1. The inflow of the source node is 0 and the outflow is 1. If the node i is the destination node, n is mapped to i and ηin=1. The inflow of the destination node is 1 and the outflow is 0. For other nodes, the inflow and outflow are both 0. In brief, the link connectivity constraint equations above can be expressed as (7).(6) Constraint (8) represents the survivability constraints of virtual networks. Let PCSS,Nv,i∖S denote the number of virtual links in the primary-cut set PCS(S,Nv,i∖S). For the virtual network with the removal of node i, the number of virtual links in primary-cut set that mapped to the same substrate link should be less than the number of virtual links in the primary-cut set, which means the virtual links in the same primary-cut set should not be mapped to the same substrate link. If the virtual links in the same primary-cut set are mapped to the same substrate link, substrate node failures will lead to the failures of links that pass through the substrate node. It means that if we remove all the links in the primary-cut set, the figure will no longer keep its connectivity.


## 4. A Hybrid Reliable Heuristic Mapping Method Based on Survivable Virtual Networks

For the integer linear programming of the reliable virtual networks mapping problem, we can quickly calculate the optimal solution when solution space is small. With the increase of the solution space, it is exponentially difficult to evaluate the optimal solution [25, 26]. In order to solve this problem, we propose a reliable heuristic virtual network mapping method called Hybrid-RHM-SVN using the ant colony algorithm proposed by Dorigo et al. [27], which has global optimization capability to calculate the approximate optimal solution. Hybrid-RHM-SVN consists of two steps: firstly, we use the enumeration strategy proposed by Tsukiyama, which has a linear time complexity, to calculate the cut sets of the virtual network that removes each node when a virtual network request arrives [28]. We find the primary-cut based on the approach proposed by literature [22]. Secondly, we use the ant colony optimization algorithm to achieve the approximate optimal mapping solution with the purpose of reducing the cost of the substrate network. In detail, when a virtual node is mapped to the substrate network, for the subgraph with the removal of the node, the edge in the primary-cut set should select the substrate path that does not pass through the substrate node corresponding to the virtual node that has been removed. When the node failure occurs, we can ensure the virtual network survivability and minimize the links failure caused by the node failure.


### 4.1. Nodes and Links Allocation Strategy

#### 4.1.1. Nodes Allocation Strategy

Step 1.
According to the location constraint of the virtual nodem, we get the set θ(m), in which substrate nodes can be assigned to m, and θm=i∈Ns∣loc⁡m-loc⁡i⩽Dm. θ(m) is a substrate node set in the circle with loc⁡(m) as the center and D(m) as the radius.Step 2.
There is no substrate node that can meet the location constraint ofm when Ω(m)=θ(m)∩i∈Ns∣ηim=1 is an empty set, which means the virtual network request is rejected; otherwise turn to Step 3.Step 3.
Obtain the value ofHi′ for the substrate node i′ that can meet the node constraints in Ω(m),
(9)Hi′=ω1cpui′+ω2∑j∈Ω(m)bPi′j,
where Pi′j is the path between i′ and its adjacent node j. ω1 and ω2 are the weights of the available CPU and bandwidth.Step 4.
Allocate the substrate nodes inθ(m) for the virtual node with the value of H(i′) decreasing.


#### 4.1.2. Links Allocation Strategy

Step 1.
If the virtual nodem is assigned to the substrate node i, calculate the primary-cut set PCSGv,mS,Nv,m∖S of the virtual network with removal of m.Step 2.
For the virtual link(p,q) in the primary-cut set, suppose that p and q are assigned to the substrate nodes p′ and q′, respectively. Find the substrate link in the loop-free path set Ps(p′,q′) for (p,q). If there is a link p∈Ps(p′,q′) not passing through the node i and satisfies the link constraints (6)~(8), we assign links for (p,q). If the links in the primary-cut set do not satisfy not passing through the node i, the virtual network does not have the survivability. We assign the link p′ for (p,q) and p′ should satisfy the link constraints (6) and (7).


### 4.2. Nodes and Links Mapping Based on Ant Colony Optimization

The ant colony optimization algorithm is a random search optimization algorithm that simulates ants foraging by iterations [29]. In the ant colony optimization algorithm, ants can release pheromone information when looking for food on the path. The pheromone has a certain scope to cause the attention of other ants. If the food is in a short distance, the ants in the path may be back and forth many times and leave more pheromone. The more pheromone is left, the higher probability of this path can be chosen. We use the ant colony optimization algorithm to solve the mapping problem, and the fitness function, transition probability, and pheromone trail update need to be redefined as follows.Definition 1 (fitness function).
The fitness function of the ant colony optimization algorithmfit is related to the objective function, which is the cost of mapping:
(10)fit=∑(m,n)∈Aes∑(i,j)∈Cevφijmnb(emn).Definition 2 (transition probability).
The transition probability is the probability that the virtual nodem can be mapped to the substrate node i. The ant’s transition probability at time t is related to the pheromone trail:
(11)pmi=τmi(t)∑x∈Nsτmx(t).Definition 3 (pheromone trail update).
In each iteration, the pheromone trail of virtual nodem is mapped to the substrate node i updates as follows:
(12)τmit+1=1-ρτmit+Δτmibest,Δτmi=Qfsbest,
where ρ is the evaporation of trail, 0<ρ<1. sbest is the optimal solution of the current iteration, and Q is a positive constant.
During the execution of mapping, the rest of available CPU resources and location of the substrate nodes should meet the demand constraints of the virtual nodes in (2)~(5). The virtual links can be mapped to the substrate links needing to satisfy the condition that the rest available bandwidth resources of the substrate links should meet the demand constraints of virtual links in (6) and (7). The details of the Hybrid-RHM-SVN algorithm are described as follows.Step 1.
Initialize the population size of antSN and the total number of iterations N.Step 2.
Update the transition probability according to the pheromone trail, maps virtual nodes and links in accordance with nodes and links allocation strategy in Section4.2, respectively.Step 3.
Obtain the fitness valuefit for each artificial ant. If the fitness value in the current iteration is lower, the new mapping solution is better than the original. Use the new mapping solution instead of the original optimal solution sbest.Step 4.
Get the current optimal solution and update pheromone trail. If the current iteration is less thanN, turn to Step 2; otherwise end the Hybrid-RHM-SVN algorithm.


### 4.3. Failed Nodes and Links Recovery Strategy

If the failure of the substrate nodei occurs, all the virtual nodes mi, i∈{1,2,…,N}, mapped on node i are affected. For mi in the virtual network with survivability, the rest of the mapped virtual networks remain connected. We just need to repair the node mi and links connected to this node. We reselect the substrate node for node mi according to Step 4 of nodes allocation strategy and substrate links for virtual links connected to the node mi according to the Step 2 of links allocation strategy. If the nodes and links do not satisfy the constraints of the failed virtual network nodes and links, the recovery fails and moves the virtual network to the end of the queue waiting for the next round of repairing. If the virtual networks do not have survivability, we use topology-awareness and reoptimization mechanism for virtual network embedding in literature [20] to remap the nodes and links. In links allocation strategy, if the node and links do not satisfy the constraints of the failed virtual network node and links, the virtual network is also moved to the end of the queue waiting for the next round of repairing.


## 4.1. Nodes and Links Allocation Strategy

### 4.1.1. Nodes Allocation Strategy

Step 1.
According to the location constraint of the virtual nodem, we get the set θ(m), in which substrate nodes can be assigned to m, and θm=i∈Ns∣loc⁡m-loc⁡i⩽Dm. θ(m) is a substrate node set in the circle with loc⁡(m) as the center and D(m) as the radius.Step 2.
There is no substrate node that can meet the location constraint ofm when Ω(m)=θ(m)∩i∈Ns∣ηim=1 is an empty set, which means the virtual network request is rejected; otherwise turn to Step 3.Step 3.
Obtain the value ofHi′ for the substrate node i′ that can meet the node constraints in Ω(m),
(9)Hi′=ω1cpui′+ω2∑j∈Ω(m)bPi′j,
where Pi′j is the path between i′ and its adjacent node j. ω1 and ω2 are the weights of the available CPU and bandwidth.Step 4.
Allocate the substrate nodes inθ(m) for the virtual node with the value of H(i′) decreasing.


### 4.1.2. Links Allocation Strategy

Step 1.
If the virtual nodem is assigned to the substrate node i, calculate the primary-cut set PCSGv,mS,Nv,m∖S of the virtual network with removal of m.Step 2.
For the virtual link(p,q) in the primary-cut set, suppose that p and q are assigned to the substrate nodes p′ and q′, respectively. Find the substrate link in the loop-free path set Ps(p′,q′) for (p,q). If there is a link p∈Ps(p′,q′) not passing through the node i and satisfies the link constraints (6)~(8), we assign links for (p,q). If the links in the primary-cut set do not satisfy not passing through the node i, the virtual network does not have the survivability. We assign the link p′ for (p,q) and p′ should satisfy the link constraints (6) and (7).


## 4.1.1. Nodes Allocation Strategy

Step 1.
According to the location constraint of the virtual nodem, we get the set θ(m), in which substrate nodes can be assigned to m, and θm=i∈Ns∣loc⁡m-loc⁡i⩽Dm. θ(m) is a substrate node set in the circle with loc⁡(m) as the center and D(m) as the radius.Step 2.
There is no substrate node that can meet the location constraint ofm when Ω(m)=θ(m)∩i∈Ns∣ηim=1 is an empty set, which means the virtual network request is rejected; otherwise turn to Step 3.Step 3.
Obtain the value ofHi′ for the substrate node i′ that can meet the node constraints in Ω(m),
(9)Hi′=ω1cpui′+ω2∑j∈Ω(m)bPi′j,
where Pi′j is the path between i′ and its adjacent node j. ω1 and ω2 are the weights of the available CPU and bandwidth.Step 4.
Allocate the substrate nodes inθ(m) for the virtual node with the value of H(i′) decreasing.


## 4.1.2. Links Allocation Strategy

Step 1.
If the virtual nodem is assigned to the substrate node i, calculate the primary-cut set PCSGv,mS,Nv,m∖S of the virtual network with removal of m.Step 2.
For the virtual link(p,q) in the primary-cut set, suppose that p and q are assigned to the substrate nodes p′ and q′, respectively. Find the substrate link in the loop-free path set Ps(p′,q′) for (p,q). If there is a link p∈Ps(p′,q′) not passing through the node i and satisfies the link constraints (6)~(8), we assign links for (p,q). If the links in the primary-cut set do not satisfy not passing through the node i, the virtual network does not have the survivability. We assign the link p′ for (p,q) and p′ should satisfy the link constraints (6) and (7).


## 4.2. Nodes and Links Mapping Based on Ant Colony Optimization

The ant colony optimization algorithm is a random search optimization algorithm that simulates ants foraging by iterations [29]. In the ant colony optimization algorithm, ants can release pheromone information when looking for food on the path. The pheromone has a certain scope to cause the attention of other ants. If the food is in a short distance, the ants in the path may be back and forth many times and leave more pheromone. The more pheromone is left, the higher probability of this path can be chosen. We use the ant colony optimization algorithm to solve the mapping problem, and the fitness function, transition probability, and pheromone trail update need to be redefined as follows.Definition 1 (fitness function).
The fitness function of the ant colony optimization algorithmfit is related to the objective function, which is the cost of mapping:
(10)fit=∑(m,n)∈Aes∑(i,j)∈Cevφijmnb(emn).Definition 2 (transition probability).
The transition probability is the probability that the virtual nodem can be mapped to the substrate node i. The ant’s transition probability at time t is related to the pheromone trail:
(11)pmi=τmi(t)∑x∈Nsτmx(t).Definition 3 (pheromone trail update).
In each iteration, the pheromone trail of virtual nodem is mapped to the substrate node i updates as follows:
(12)τmit+1=1-ρτmit+Δτmibest,Δτmi=Qfsbest,
where ρ is the evaporation of trail, 0<ρ<1. sbest is the optimal solution of the current iteration, and Q is a positive constant.
During the execution of mapping, the rest of available CPU resources and location of the substrate nodes should meet the demand constraints of the virtual nodes in (2)~(5). The virtual links can be mapped to the substrate links needing to satisfy the condition that the rest available bandwidth resources of the substrate links should meet the demand constraints of virtual links in (6) and (7). The details of the Hybrid-RHM-SVN algorithm are described as follows.Step 1.
Initialize the population size of antSN and the total number of iterations N.Step 2.
Update the transition probability according to the pheromone trail, maps virtual nodes and links in accordance with nodes and links allocation strategy in Section4.2, respectively.Step 3.
Obtain the fitness valuefit for each artificial ant. If the fitness value in the current iteration is lower, the new mapping solution is better than the original. Use the new mapping solution instead of the original optimal solution sbest.Step 4.
Get the current optimal solution and update pheromone trail. If the current iteration is less thanN, turn to Step 2; otherwise end the Hybrid-RHM-SVN algorithm.


## 4.3. Failed Nodes and Links Recovery Strategy

If the failure of the substrate nodei occurs, all the virtual nodes mi, i∈{1,2,…,N}, mapped on node i are affected. For mi in the virtual network with survivability, the rest of the mapped virtual networks remain connected. We just need to repair the node mi and links connected to this node. We reselect the substrate node for node mi according to Step 4 of nodes allocation strategy and substrate links for virtual links connected to the node mi according to the Step 2 of links allocation strategy. If the nodes and links do not satisfy the constraints of the failed virtual network nodes and links, the recovery fails and moves the virtual network to the end of the queue waiting for the next round of repairing. If the virtual networks do not have survivability, we use topology-awareness and reoptimization mechanism for virtual network embedding in literature [20] to remap the nodes and links. In links allocation strategy, if the node and links do not satisfy the constraints of the failed virtual network node and links, the virtual network is also moved to the end of the queue waiting for the next round of repairing.


## 5. Performance Evaluation

### 5.1. Simulation Environment

As specified in [7–21], we use the following standard setup for all our simulations. The graphs for the substrate network and virtual network requests are generated by using the GT-ITM topology generator tool [30], which is widely used for generating network topologies. The substrate network has 200 nodes and each pair of the nodes is randomly connected with a probability of 0.5, corresponding to a medium sized Internet service provider. The available CPU and bandwidth resources of the substrate nodes are real numbers uniformly distributed between 50 and 100. Virtual network requests arrive in a Poisson process with an average rate of 4 virtual network requests per 100 time units, and each request has an exponentially distributed lifetime with an average of 1000 time units. The number of the nodes in each virtual network request is determined by a uniform distribution between 4 and 10. Each pair of virtual nodes is also randomly connected with a probability of 0.5. The bandwidth requirement of the virtual link is a real number uniformly distributed between 0 and 40. A single node failure arrives in a Poisson process with an average rate of 2 per 100 time units. The horizontal ordinate and vertical ordinate of the node location are uniformly distributed between 0 and 100. Radius D is uniformly distributed between 50 and 100. Both the CPU resources weight α and bandwidth resources weight β are 1. The value of ω1 and ω2 is 1. The population size of artificial ant SN is 50 and the total number of iterations N is 100. Pheromone trail τmi is 5. ρ and Q are 0.8 and 10000, respectively.Our simulation experiments evaluate three algorithms listed in Table1. SVNE-ORP is based on the protection mechanism and SVNE-TAP is based on the recovery mechanism.Table 1
Comparisons.
Notation
Algorithm description
Hybrid-RHM-SVN
Hybrid reliable heuristic mapping method based on survivable virtual networks
SVNE-ORP [19]
Reliable mapping method based on optimization sharing redundancy mechanism
SVNE-TAP [20]
Reliable mapping method based on topology-awareness and reoptimization mechanism


### 5.2. Evaluation Metrics

We define the reliable virtual network mapping evaluation metrics as follows.


#### 5.2.1. Acceptance Rate of Virtual Network Requests

The acceptance ratio measures the percentage of virtual network requests accepted by the mapping algorithm over a period of time. Similar to the previous works, the acceptance rate of virtual network requestsηacc can be formulated by
(13)ηacc=lim⁡T→∞∑t=0TVNRacc∑t=0TVNR+ε1,
where VNRacc is the virtual network requests that has been mapped successfully. VNR is the virtual network requests that arrived. ε1 is a positive number close to zero infinitely.


#### 5.2.2. Average Revenue of Mapping Virtual Networks

The revenue gives us a clear insight into how much infrastructure providers will gain when accepting a single virtual network request. The average revenue of mapping virtual networksηrev denotes how much infrastructure providers will gain in the long run:
(14)RGv,i=α∑nv∈Nvcpunv+β∑ev∈Evbev,ηrev=lim⁡T→∞∑t=0TR(Gv,i)T+ε2,
where R(Gv,i) is the revenue of mapping one virtual network successfully. α and β are weights of CPU and bandwidth capability. ε2 is a positive number close to zero infinitely.


#### 5.2.3. Recovery Rate of Virtual Networks

The recovery rate of virtual networks, which is the ratio of the number of virtual networks that has been successfully recovered to the number of virtual networks that is affected by the substrate failure, is an important evaluation of reliable virtual network mapping. The recovery rate of virtual networksηsuc can be formulated by
(15)ηsuc=lim⁡T→∞∑t=0F(T)κ′(ti)∑t=0F(T)κ(ti)+ε3,
where F(T) is the failure occuring in the substrate network between 0 and T. κ(ti) is the number of virtual networks that is affected by the substrate failure at ti∈(0,1,…,F(T)). κ′(ti) is the number of virtual networks that has been recovered successfully. ε3 is a positive number close to zero infinitely.


### 5.3. Evaluation Results

Figure1 depicts the comparisons of virtual network request acceptance rates between our Hybrid-RHM-SVN algorithm and the existing algorithms. Due to the searching optimization capability of the ant colony optimization algorithm, Hybrid-RHM-SVN achieves substantially higher virtual network requests acceptance rate compared with those of the other algorithms in the long run. The Hybrid-RHM-SVN’s acceptance rate is steady at 0.72 which is higher than SVNE-TAP. SVNE-ORP needs to provide redundant resources for virtual nodes and links, which will make excessive consumption of resources in substrate network. It is difficult to deal with the continuous arrival of virtual network requests.Figure 1
Acceptance rate of virtual network requests.Figure2 depicts the average revenue between our Hybrid-RHM-SVN and other algorithms. It shows that Hybrid-RHM-SVN can achieve the highest average revenue in a reasonable number of iterations. Due to the highest virtual network requests acceptance rate, Hybrid-RHM-SVN algorithm can successfully map the largest number of virtual networks per unit time and the average revenue will be increased and steady at 25. In order to ensure the recovery rate of virtual networks, SVNE-ORP needs to provide many redundant resources for virtual network resources, leading to the lowest average revenue of mapping.Figure 2
Average revenue of mapping virtual networks.Figure3 shows the recovery rates of virtual networks that are affected by single substrate node failure. Our experiments show that SVNE-ORP obtains the highest recovery rate followed by Hybrid-RHM-SVN in the time units from 0 to 16500. Hybrid-RHM-SVN obtains the highest recovery rate in the rest time. In the time units from 0 to 16500, the number of virtual networks needing to be mapped is less. There are enough available resources for SVNE-ORP to provide redundant resources for virtual nodes and links. Therefore, SVNE-ORP algorithm has a higher recovery rate in the early period. For Hybrid-RHM-SVN, not all the virtual networks have survivability. Virtual networks with survivability can be quickly recovered. Virtual networks without survivability need to be remapped by node migration and links remapping. In node migration and links remapping stage, the capacity constraints of nodes and links can be easily satisfied. But the location constraint loc⁡(i) limits the number of substrate nodes that can be selected, which make the recovery rate of Hybrid-RHM-SVN lower than SVNE-ORP. With the substrate network resources occupied continually, there are fewer and fewer redundant resources that can be provided to virtual networks. The recovery rate of the SVNE-ORP algorithm will decrease rapidly. Although with the decrease of available resources in the substrate network, the recovery rate of Hybrid-RHM-SVN reduces slower than other algorithms due to the virtual network with survivability. The recovery rate is kept steady at 0.80, better than the other two algorithms in the long run.Figure 3
Recovery rate of virtual networks.Figure4 shows the runtime of mapping single virtual network of the three comparisons. As shown in Figure 4, with the increasing of virtual nodes, the runtime of mapping single virtual network increases. SVNE-TAP consumes the most running time while Hybrid-RHM-SVN consumes the least running time. In Hybrid-RHM-SVN, calculating the primary-cut set will take a certain amount of time. But Hybrid-RHM-SVN handles virtual network requests in second class like the other two algorithms. Hybrid-RHM-SVN can increase the acceptance rate of virtual networks, the average revenue of mapping, and recovery rate of virtual network, which can meet the demands of infrastructure providers to deal with the virtual network requests.Figure 4
Runtime of mapping single virtual network.


## 5.1. Simulation Environment

As specified in [7–21], we use the following standard setup for all our simulations. The graphs for the substrate network and virtual network requests are generated by using the GT-ITM topology generator tool [30], which is widely used for generating network topologies. The substrate network has 200 nodes and each pair of the nodes is randomly connected with a probability of 0.5, corresponding to a medium sized Internet service provider. The available CPU and bandwidth resources of the substrate nodes are real numbers uniformly distributed between 50 and 100. Virtual network requests arrive in a Poisson process with an average rate of 4 virtual network requests per 100 time units, and each request has an exponentially distributed lifetime with an average of 1000 time units. The number of the nodes in each virtual network request is determined by a uniform distribution between 4 and 10. Each pair of virtual nodes is also randomly connected with a probability of 0.5. The bandwidth requirement of the virtual link is a real number uniformly distributed between 0 and 40. A single node failure arrives in a Poisson process with an average rate of 2 per 100 time units. The horizontal ordinate and vertical ordinate of the node location are uniformly distributed between 0 and 100. Radius D is uniformly distributed between 50 and 100. Both the CPU resources weight α and bandwidth resources weight β are 1. The value of ω1 and ω2 is 1. The population size of artificial ant SN is 50 and the total number of iterations N is 100. Pheromone trail τmi is 5. ρ and Q are 0.8 and 10000, respectively.Our simulation experiments evaluate three algorithms listed in Table1. SVNE-ORP is based on the protection mechanism and SVNE-TAP is based on the recovery mechanism.Table 1
Comparisons.
Notation
Algorithm description
Hybrid-RHM-SVN
Hybrid reliable heuristic mapping method based on survivable virtual networks
SVNE-ORP [19]
Reliable mapping method based on optimization sharing redundancy mechanism
SVNE-TAP [20]
Reliable mapping method based on topology-awareness and reoptimization mechanism


## 5.2. Evaluation Metrics

We define the reliable virtual network mapping evaluation metrics as follows.


### 5.2.1. Acceptance Rate of Virtual Network Requests

The acceptance ratio measures the percentage of virtual network requests accepted by the mapping algorithm over a period of time. Similar to the previous works, the acceptance rate of virtual network requestsηacc can be formulated by
(13)ηacc=lim⁡T→∞∑t=0TVNRacc∑t=0TVNR+ε1,
where VNRacc is the virtual network requests that has been mapped successfully. VNR is the virtual network requests that arrived. ε1 is a positive number close to zero infinitely.


### 5.2.2. Average Revenue of Mapping Virtual Networks

The revenue gives us a clear insight into how much infrastructure providers will gain when accepting a single virtual network request. The average revenue of mapping virtual networksηrev denotes how much infrastructure providers will gain in the long run:
(14)RGv,i=α∑nv∈Nvcpunv+β∑ev∈Evbev,ηrev=lim⁡T→∞∑t=0TR(Gv,i)T+ε2,
where R(Gv,i) is the revenue of mapping one virtual network successfully. α and β are weights of CPU and bandwidth capability. ε2 is a positive number close to zero infinitely.


### 5.2.3. Recovery Rate of Virtual Networks

The recovery rate of virtual networks, which is the ratio of the number of virtual networks that has been successfully recovered to the number of virtual networks that is affected by the substrate failure, is an important evaluation of reliable virtual network mapping. The recovery rate of virtual networksηsuc can be formulated by
(15)ηsuc=lim⁡T→∞∑t=0F(T)κ′(ti)∑t=0F(T)κ(ti)+ε3,
where F(T) is the failure occuring in the substrate network between 0 and T. κ(ti) is the number of virtual networks that is affected by the substrate failure at ti∈(0,1,…,F(T)). κ′(ti) is the number of virtual networks that has been recovered successfully. ε3 is a positive number close to zero infinitely.


## 5.2.1. Acceptance Rate of Virtual Network Requests

The acceptance ratio measures the percentage of virtual network requests accepted by the mapping algorithm over a period of time. Similar to the previous works, the acceptance rate of virtual network requestsηacc can be formulated by
(13)ηacc=lim⁡T→∞∑t=0TVNRacc∑t=0TVNR+ε1,
where VNRacc is the virtual network requests that has been mapped successfully. VNR is the virtual network requests that arrived. ε1 is a positive number close to zero infinitely.


## 5.2.2. Average Revenue of Mapping Virtual Networks

The revenue gives us a clear insight into how much infrastructure providers will gain when accepting a single virtual network request. The average revenue of mapping virtual networksηrev denotes how much infrastructure providers will gain in the long run:
(14)RGv,i=α∑nv∈Nvcpunv+β∑ev∈Evbev,ηrev=lim⁡T→∞∑t=0TR(Gv,i)T+ε2,
where R(Gv,i) is the revenue of mapping one virtual network successfully. α and β are weights of CPU and bandwidth capability. ε2 is a positive number close to zero infinitely.


## 5.2.3. Recovery Rate of Virtual Networks

The recovery rate of virtual networks, which is the ratio of the number of virtual networks that has been successfully recovered to the number of virtual networks that is affected by the substrate failure, is an important evaluation of reliable virtual network mapping. The recovery rate of virtual networksηsuc can be formulated by
(15)ηsuc=lim⁡T→∞∑t=0F(T)κ′(ti)∑t=0F(T)κ(ti)+ε3,
where F(T) is the failure occuring in the substrate network between 0 and T. κ(ti) is the number of virtual networks that is affected by the substrate failure at ti∈(0,1,…,F(T)). κ′(ti) is the number of virtual networks that has been recovered successfully. ε3 is a positive number close to zero infinitely.


## 5.3. Evaluation Results

Figure1 depicts the comparisons of virtual network request acceptance rates between our Hybrid-RHM-SVN algorithm and the existing algorithms. Due to the searching optimization capability of the ant colony optimization algorithm, Hybrid-RHM-SVN achieves substantially higher virtual network requests acceptance rate compared with those of the other algorithms in the long run. The Hybrid-RHM-SVN’s acceptance rate is steady at 0.72 which is higher than SVNE-TAP. SVNE-ORP needs to provide redundant resources for virtual nodes and links, which will make excessive consumption of resources in substrate network. It is difficult to deal with the continuous arrival of virtual network requests.Figure 1
Acceptance rate of virtual network requests.Figure2 depicts the average revenue between our Hybrid-RHM-SVN and other algorithms. It shows that Hybrid-RHM-SVN can achieve the highest average revenue in a reasonable number of iterations. Due to the highest virtual network requests acceptance rate, Hybrid-RHM-SVN algorithm can successfully map the largest number of virtual networks per unit time and the average revenue will be increased and steady at 25. In order to ensure the recovery rate of virtual networks, SVNE-ORP needs to provide many redundant resources for virtual network resources, leading to the lowest average revenue of mapping.Figure 2
Average revenue of mapping virtual networks.Figure3 shows the recovery rates of virtual networks that are affected by single substrate node failure. Our experiments show that SVNE-ORP obtains the highest recovery rate followed by Hybrid-RHM-SVN in the time units from 0 to 16500. Hybrid-RHM-SVN obtains the highest recovery rate in the rest time. In the time units from 0 to 16500, the number of virtual networks needing to be mapped is less. There are enough available resources for SVNE-ORP to provide redundant resources for virtual nodes and links. Therefore, SVNE-ORP algorithm has a higher recovery rate in the early period. For Hybrid-RHM-SVN, not all the virtual networks have survivability. Virtual networks with survivability can be quickly recovered. Virtual networks without survivability need to be remapped by node migration and links remapping. In node migration and links remapping stage, the capacity constraints of nodes and links can be easily satisfied. But the location constraint loc⁡(i) limits the number of substrate nodes that can be selected, which make the recovery rate of Hybrid-RHM-SVN lower than SVNE-ORP. With the substrate network resources occupied continually, there are fewer and fewer redundant resources that can be provided to virtual networks. The recovery rate of the SVNE-ORP algorithm will decrease rapidly. Although with the decrease of available resources in the substrate network, the recovery rate of Hybrid-RHM-SVN reduces slower than other algorithms due to the virtual network with survivability. The recovery rate is kept steady at 0.80, better than the other two algorithms in the long run.Figure 3
Recovery rate of virtual networks.Figure4 shows the runtime of mapping single virtual network of the three comparisons. As shown in Figure 4, with the increasing of virtual nodes, the runtime of mapping single virtual network increases. SVNE-TAP consumes the most running time while Hybrid-RHM-SVN consumes the least running time. In Hybrid-RHM-SVN, calculating the primary-cut set will take a certain amount of time. But Hybrid-RHM-SVN handles virtual network requests in second class like the other two algorithms. Hybrid-RHM-SVN can increase the acceptance rate of virtual networks, the average revenue of mapping, and recovery rate of virtual network, which can meet the demands of infrastructure providers to deal with the virtual network requests.Figure 4
Runtime of mapping single virtual network.


## 6. Conclusion

The reliable virtual network mapping is one of the major problems in network virtualization researches. An efficient reliable mapping algorithm plays an important role in accepting more virtual network requests and generating more revenues for infrastructure providers. Different from the traditional protection mechanisms and recovery mechanisms, we proposed a hybrid reliable heuristic mapping method based on the survivable virtual network concepts inspired by survivable routing in wavelength division multiplexing WDM optical network. We formulate the reliable mapping problem as an integer linear program and propose a virtual networks survivable strategy. We propose a node allocation strategy, link allocation strategy, failed node, and link recovery strategy and use the ant colony optimization algorithm to achieve the approximate optimal mapping solution. The simulation results show that the survivable virtual network is a better idea of dealing with reliable mapping problem and our algorithm outperforms the previous approaches in the acceptance rate of virtual networks, the average revenue of mapping, and the recovery rate. In the future work, we will focus on how to optimize nodes and links allocation strategies to reduce the time usage of mapping.



---

*Source: 316801-2015-02-04.xml*