Heuristic Solutions of Virtual Network Embedding: A Survey

Haotong Cao, Han Hu, Zhicheng Qu, Longxiang Yang,＊

1 College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

2 College of Internet of Things, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

3 Jiangsu Key Laboratory of Wireless Communications, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

* The corresponding author, email:yanglx@njupt.edu.cn

I. INTRODUCTION

THE worldwide promotion of the Internet over the past three decades is mainly dependent on different infrastructure technologies so as to run protocols and distributed applications. However, the diversification of the Internet has also become a serious impediment to the development of Internet in terms of the underlying technologies and offered network services. The impediment is therefore known as ossi fication of the Internet [1]. Owing to the fact that the Internet architecture is owned by a large number of different Internet Service Providers (ISPs), it is hardly possible to adopt a new network architecture to totally take the place of the Internet, without the agreement of many stakeholders. Unless the consensus is reached, any initiative to remove the ossi fication will be dif ficult and limited in scope for the future Internet.

On the basis of the above background, network virtualization [2],[3],[4],[5],[6] is widely recognized as one of the most promising technology for the future Internet. Promoted as an effective method to evaluate new protocols and services[7], network virtualization has been developed in several research testbeds and projects successfully, such as the CABO[8], 4WARD [9],[10] and G-Lab [11]. Network virtualization is therefore promoted as an effective tool to overcome the resistance of current Internet to the fundamental change. In the literature, network virtualization has been widely accepted as an inherent component of the future network architecture. Even today,network virtualization is also applied in the area of telecommunication. Examples figured out here are the SINET [12],[13] and the OpenFlow [14].

In the context of network virtualization,the future network architecture is based on the Infrastructure as a Service (IaaS) [15]business model to decouple the infrastructure of the traditional ISPs. The decoupling result is only two new roles: Service Provider (SP)and Infrastructure Provider (InP). In this business model, the InPs are responsible for maintaining and allocating part of their sliceable resources to different SPs. The InPs are allowed to manage and allocate their physical resources independently while SPs deploy network protocols and offer customized network services (e.g. online gaming, IPTV, online broadcasting) to end users. In the literature,some papers [9],[10] further separate the management and business roles of the SP into three other roles: Virtual Network Provider(VNP), Virtual Network Operator (VNO) and Service Provider (SP). In order to analyze the representative heuristic VNE algorithms and categorize the heuristics, the IaaS business model is adopted in this survey.

The primary entity in NV is the virtual network (VN). The virtual network in network virtualization is used to designate several network technologies such as Virtual Private Networks (VPN), overlay networks and active or programmable networks. The model of a virtual network is commonly represented by a set of network elements (nodes and links)that are on top of a substrate network (SN).All virtual nodes of the virtual network are interconnected through a number of virtual links, along with resource requirements,such as node capacity, node location, link bandwidth and link propagation delay. Thus forming a professional noun called virtual network request (VNR). Multiple virtual network requests with varying characteristics are allowed to coexist on the shared substrate network. The assignment method of mapping /embedding VNs on a substrate network is one of the main challenges in network virtualization [16] and is known as the Virtual Network Embedding (VNE) algorithm. Virtual Network Embedding aims to deal with the allocation of virtual resources both in nodes and links. In the literature, there have been a lot of VNE algorithms proposed for solving the VNE problem. Until now, a consensus has been reached that the benefit earned from the existing SN can be maximized through dynamic mapping of virtual requests onto the substrate resource.The optimal dynamic resource allocation, with regard to different objectives (e.g. long term economical profit, QoS, QoE, survivability),will be necessary to provide guaranteed customized service to end users.

This paper presents a survey of current heuristic algorithms in VNE area.

However, the VNE problem is NP-hard and has been regarded as the multi-way separator problem[17]. Even in offline situations,VNE is reduced to the unsplittable flow problem[18],[19] and still NP-hard. To get a feasible mapping solution in the polynomial time,algorithms / solutions of the virtual network embedding in the literature compromise for the global optimality. Algorithms proposed by both industry and academia are mostly heuristic.

Previous VNE surveys [20],[21] have provided a description of the VNE problem and the categorization method of VNE algorithms.A recent survey by Haotong Cao et al.[22]presents the exact solution survey of VNE. On the basis of previous contributions, this survey focuses on the heuristic solution of VNE. A normal and generic mathematical formulation of the heuristic solution is also presented in this survey. Several representative heuristic algorithms are presented and analyzed according to the classi fication strategy, derived from the previous research [21]. The merging research directions of the heuristics are highlighted and emphasized at the end of this survey.

The remainder of this survey is organized as follows: Section II presents the VNE problem, the formulation of VNE heuristic solution included. In Section III, several representative VNE heuristic algorithms of different catego-ries are analyzed in detail. A number of VNE heuristic algorithms are selected and grouped by tables in Section IV. While in Section V,emerging research directions of VNE are suggested and highlighted. Finally, Section VI concludes this survey.

II. VIRTUAL NETWORK EMBEDDING

Previous VNE papers in the literature have provided particular descriptions of VNE problem and designated heuristic formulations for solving VNE problem. In this section, a concise VNE problem description and a general VNE heuristic formulation are presented. A taxonomy method of the heuristics, derived from the survey [21], is promoted and aims to help readers to easily identify each variant of the heuristics in the future VNE research.

2.1 Virtual network embedding problem description

Fig. 1. Two virtual networks and one substrate network

In network virtualization, virtual networks with customized protocols and service demands, proposed by end users, are allowed to coexist on the shared substrate / physical network. Each virtual network is composed of a subset of resources of the underlying substrate network. The substrate network needs to effectively and efficiently allocate substrate resources to fulfill the demands of proposed virtual networks. This kind of network resource assignment problem can be modeled by referring to the theory of mathematical model.

Substrate network: The substrate network is also called as the physical network in VNE research area. In general, each substrate network is managed and operated by an InP. The InP is able to earn pro fits by leasing substrate network resources to SPs or end users. The substrate network consists of substrate nodes(routers or switches) connected by substrate links (coaxial cable or optical fiber) that form the substrate topology. Different InPs own their substrate networks with different topologies and resource characteristics.

Derived from the theory of the mathematical model, the substrate network can be modeled as a weighted undirected graph GS=(NS,LS), where NSis the set of substrate nodes and LSrepresents all substrate links. Fig. 1 shows a VNE network scenario where two virtual networks are to be embedded on the shared substrate network. In the substrate network,each substrate nodem∈NScan be characterized by its specific substrate resources, such as the node capacity,, and the node location, loc(m). With respect to substrate links,each substrate linkmnhas its corresponding resources such as a finite bandwidthand a link propagation delay. Other substrate resources (e.g. memory size and storage capacity) must be considered in real implementation. For simplicity, these resources can be neglected in VNE study.

The right part of Fig. 1 is the model of a substrate network in VNE. The numbers over the links are available bandwidth and numbers in rectangles are available node capacity. For simplicity, the location of each substrate node and link propagation delay are omitted in this figure.

Virtual network: Generally, the virtual network is proposed by end users and is operated and maintained by the SP. The SP is able to allocate network resources, leased from InP, to end users according to one selected VNE algorithm / mapping strategy. Each virtual network also consists of a set of virtual nodes (e.g.routers) connected by virtual links that form the virtual network topology, same to the substrate network. Different end users put forward different topologies owing to their particular service requests, such as self-broadcasting service and IPTV service.

In the view of mathematical model, a virtual network also can be modeled as a weighted undirected graph GV=(NV, LV), where NVis the set of all virtual nodes of the VNR and LVis the set of all virtual links per VNR. Each virtual nodeMcan be characterized by the required sources, such as the required node capacity, CVM, and the required virtual node location, Loc(M). The allowed maximum derivation of the virtual nodeMis set to be LR(M) respectively. The derivation relationship between virtual nodeMand any selected substrate nodemis usually represented by the Euclidean Distance. The derivation must be within the required radius LR(M). With respect to the virtual links, each virtual linkMNhas a required bandwidthand the allowed maximum link propagation delay

The left part of Fig. 1 shows two virtual networks with different topologies. The numbers over the links are required link bandwidth and the numbers in rectangles are node capacity demands of virtual nodes. For simplicity,the location of each virtual node and allowed maximum link propagation delay are omitted in Fig. 1.

Virtual Network Embedding: With modeling substrate network and virtual network in network virtualization, it is of great importance to effectively and efficiently map virtual networks onto the substrate network. The method of mapping virtual networks, with elements’ demands, is virtual network embedding(VNE), performed by Service Provider (SP)and Infrastructure Provider (InP). The goal of VNE is to optimally allocate node and link resources. The simplest scenario of VNE, proposed in the early stage of VNE research [23],is the scenario where only the VN topology is considered without any other requirements such as node capacity for virtual nodes and link bandwidth for virtual links. The VNE research has developed a lot over the past few years. Therefore, the VNE scenario is totally different the previous topology scenario. In network virtualization, the VNE is also different from the resource allocation in other networking paradigms, such as the virtual private networks (VPN) [6], virtual circuit routing.Four main differences are presented: (1) the topology of a VN maybe arbitrary or speci fied while others just are a number of connections between multiple nodes; (2) the load balancing of substrate nodes and links must be considered in VNE; (3) VNE deals with the resource allocation of a VN in the form of a graph, not simply a connection between two nodes in the network; (4) to get the optimal resource allocation, the embedding of a VN, along with virtual nodes and links requirements, must be conducted and ful filled at the same time.

Generally speaking, the embedding of a virtual network can be divided into two prima-ry components: one component that deals with the assignment of virtual nodes, and the other component aims to ensure the mapping of virtual links. Notations used for expressing both two components are listed in Table I.

Table I. VNE notations

1) Virtual Node Embedding: Each virtual node of the same VN must be assigned to a different substrate node of the substrate network. This does bene fit to the flexibility, manageability, stability and load balancing of substrate network. The assignment of all virtual nodes can be determined by a node-mapping functionMN() : NV→ NS.

subject to

Where only node capacity requirement is listed in expression (1). For simplicity, expressions of other requirements (e.g. Location constraint) are not presented here.

2) Virtual Link Embedding: Each virtual link of the same VNR can be mapped onto a single substrate path (unsplittable flow) in this section between the corresponding substrate nodes that host the end virtual nodes of mapped virtual link. Different paths do not interfere with each other. This is a key characteristic in link embedding. The link embedding is implemented according to the link-mapping functionML() : LV→ PSfor all virtual links per VNR.

subject to

Where only the constraint of virtual link bandwidth is considered and is expression (2)in this example.

With fulfilling both two different components of resource allocation in VNE, it is easy to draw the conclusion that VNE problem is rather complex in nature. In the literature, the VNE problem can be reduced to the multiway separator problem[17] and NP-hard even when all proposed VNs are known in advance.Even in of fline situations, VNE is regarded as an of fline load balancing problem and reduced to the unsplittable flow problem[18],[19] that is still NP-hard. Based on these backgrounds,the VNE has attracted a lot of attention and most algorithms proposed in the literature are heuristic. Heuristic solutions are able to solve the VNE problem in polynomial time. Thus being developed in the academia and the industry.

2.2 Formulation of VNE heuristic algorithms

Up modeling the substrate and virtual networks of VNE successfully in the above subsection, it is of great importance to put forward the proper solution model to deal with the VNE problem. Heuristic solution plays an important role in VNE. This subsection talks about the general formulation of VNE heuristic solution.

The formulation of VNE heuristic solution varies each other and can be categorized into two main classes whether referring to the mathematical method or not. One is the pure heuristic formulation while the other is based on mathematical formulation. Through relaxing values of variables of the latter, a feasible solution can be worked out in polynomial time.

1) Based on Pure Heuristic Formulation

In the early stage of VNE study, researchers attempt to find an acceptable and feasible solution. Pure heuristic methods are adopted and proposed to deal with the VNE problem. The execution time should be minimized and is crucial in that period. Most heuristic methods originate from the area of computer science,such as the greedy approach[24], k-shortest path method[25], multi-commodity solution[26] and the subgraph isomorphism detection method[27]. Through setting variables and programming, the pure heuristic solution of a network scenario can be easily found out.

However, an apparent flaw of the pure heuristic solutions exists along with its existence in VNE area. It is the flaw that the pure heuristic solution compromises for short execution time and only aims to find a feasible solution.With regard to one speci fic metric, optimal or sub-optimal resource allocation cannot be realized. For instance, with the goal of mapping as many virtual networks as possible, using the greedy method to cope with the virtual node mapping and k-shortest path to deal with the virtual link mapping ensure the proposed virtual network to be mapped. This algorithm can cope with the coming virtual networks and performs well when the substrate resources are abundant. In real environment and simulation, the substrate resources are limited. With further batch processing and former virtual networks’ expiring, the resource fragmentation exists. Thus resulting in the degenerating of processing and not accepting more proposed virtual networks. Therefore, pure heuristic solution needs to be modi fied and further developed from the scratch, especially for the formulation. The pure heuristic solution is not based on the mathematical theory. The assignment solved by the pure heuristic is only feasible and sub-optimal in most network scenarios. In addition, the pure heuristic solution is not effective and efficient enough to deal with the VNE problem in the long term.

2) Based on Mathematical Formulation

With the VNE research extending and VNE exact formulation being proposed[22], the heuristic algorithm has been fully developed.Mathematical methods have been applied to cope with the VNE problem and aim to find a more acceptable solution within allowed convergence range. This is totally different from the pure heuristic solution without any search direction in the allowed solution space.

For readers to grasp the general mathematical formulation of VNE heuristic solution,the formulation of a representative heuristic solution[28], [29], cited by researchers more than one hundred times in the IEEE Xplore, is presented to be analyzed below. The formulation is labeled as VNE-MIP in this section.

The VNE-MIP is formulated based on the mixed integer programming (MIP) of optimization theory. Notations used in VNE-MIP are same to what are de fined in Table I. Next, the mathematical formulation of VNE heuristic solution VNE-MIP is presented as shown below.

Two kinds of variables are de fined at first.xMmis a binary variable which has the value “1”when virtual nodeMis mapped onto substrate nodeis the allocated amount of flow on the substrate linkmnfor theith virtual link.The object is to coordinate the substrate mapping cost in order to accept more proposed virtual networks and to achieve the substrate load balancing at the same time.

The formulation is presented as follows:

subject to

Node Constraints:

Flow Constraints:

Source nodes:

Sink nodes:

Intermediate nodes:

Capacity Constraints:

Domain Constraints:

Remarks:

(1) Expression 3 is the objective function and tries to minimize the cost of embedding a virtual network as well as balance the load.α and β are wight parameters, commonly referred in formulation, to control the importance of load balancing. γ and δ are small positive constants to avoiding by zero in computing the objective function.

(2) Expression 4 and 5 are related to the relationship between every virtual nodeMand substrate nodem. In each virtual network of VNE, each virtual node is mapped onto a substrate node and different virtual nodes must not be mapped onto the same substrate node.While to each substrate node of the SN, it can accommodate no more than one virtual node.

(3) Expression 6, 7 and 8 all refer to the flow conservation conditions and play a very important role in formulating the VNE-MIP.These three expressions show that the net flow to a node is zero, except for the source node and the sink node.

(4) Expression 9 and 10 contain the substrate link bandwidth and node capacity bounds. For instance, summing up the flow in 9 aims to ensure that the sum of substrate linkmnis within its available bandwidth.

(5) Expression 11 and 12 denote the real and binary constraints on the variablesandxMm, respectively.

Based on the above description and explanation, an initial and typical mathematical formulation of VNE heuristic solution is easy to be grasped by readers. However, due to the scale of simulation and nature of MIP, it is computationally intractable [30] in real implementation. Thus demanding relaxing the constraints to obtain another linear programming(LP) model. Then it is useful to develop a feasible and heuristic solution in reasonable time and achieve optimal mapping solution in several cases. Software tools, used to solve the LP model in each VNE scenario, are GLPK [31]and CPLEX [32], commonly used in solving LP problems.

Different from the pure heuristic formulation, the mathematical heuristic formulation outperforms in many aspects. It lies to the nature of mathematical programming. Through sacri ficing part performance of the execution time, several metrics, such as VNR acceptance ratio, are greatly improved [29]. By setting the variables properly and controlling the scale of network simulation, the heuristic solution can be changed into the VNE exact solution[33],[34],[35],[36][136] and solved in reasonable time. In other words, exact solution and heuristic solution can transform mutually in several cases [37],[38].

2.3 A category scheme of VNE heuristic algorithms

Derived from previous surveys and algorithms of VNE [21],[22], different VNE algorithms have various characteristics. Therefore, it is of great use to categorize all VNE algorithms proposed in the literature. All VNE heuristic algorithms also can be categorized according to different variants of the underlying VNE problem. Six variants, selected from these characteristics, are Static or Dynamic, Centralized or Distributed, and Concise or Redundant. These six concepts will be described in this subsection one by one. These concepts will be used in Section III and IV for analyzing and classifying VNE heuristic solutions in the literature.

(1)StaticorDynamic: In the real network environments, the VNE problem ought to be online. Virtual networks are not known in advance and ought to be mapped onto the substrate network immediately virtual networks arrive. However, VNE researches in the academia deal with the VNE problem in the way that VNs stay in the network queue for an arbitrary amount of time and are mapped one by one. Thus, the VNE problem can be categorized into two classes: static and dynamic.Each class has its own advantage and disadvantage. For the static, the optimal mapping can be computed in small-scaled network,with regard to one concrete object. The best feasible solution can also be worked out in allowed convergence. While to the disadvantage of the static VNE solutions, the fragmentation of substrate resources will exist and the VN request acceptance ratio will diminishes in the long term. Dynamic VNE solutions try to reconfigure the mapped virtual networks and reorganize the substrate resources. However,the complexity will increase in dynamic VNE solutions. Changes of the virtual networks and substrate network will further make the VNE problem more complicated. The optimal embedding will be harder to be found out in polynomial time.

(2)CentralizedorDistributed: The VNE problem can also be classi fied according to the number of substrate networks that are responsible for allocating substrate resources to proposed virtual networks. Both two classes are called as Centralized and Distributed. They are fundamentally different, each having its own advantages and disadvantages.

(a)Centralized: In the centralized problem,there is only one substrate network responsible for performing the embedding. This does bene fit to finding out the optimal solution of VNE problem in a small-scaled network. At first,it is rather convenient to formulate the VNE problem. Then optimal solutions, with regard to different objects, can be calculated through a dedicated machine computing. When in a large network and allowed convergence range,the heuristic solution can also be computed.However, if a single network element of the centralized substrate network fails, the entire mapping will fail. Moreover, the scalability problem in large-scaled network exists. A single substrate network will be overwhelmed by a large number of virtual networks are required to be handled.

(b)Distributed: Contrary to the centralized VNE problem, the distributed utilizes multiple substrate networks (at least two) for computing the embedding assignment. The advantage of such an algorithm lies in the better scalability, comparing with the centralized. Since loads are distributed among several nodes,each substrate node is able to further deal with the embedding, with different kinds of requirements. However, several disadvantages exist. At first, it is that how the proposed virtual network can be separated and distributed among different substrate networks. Then the VNE solution space is extended and larger than before and efficient solution is hard to be computed in large networks. The computation will be very large. There is also increased overhead. A trade-off between the feasibility and optimality needs to be achieved.

(3)ConciseorRedundant: In VNE, the failure of a single substrate entity will affect all virtual networks that are mapped onto the substrate network. Therefore, in the real network environments where fault-sensitive applications are deployed inside the virtual network, it is advisable and necessary to set up backup resources in case the corresponding primary resources fail. While in VNE research,the embedding solution is referred to be ‘concise’ if no resources are spared for node / link failures. On the contrary, the ‘redundant’ refers to the fact that resilient resources are leased from the substrate network for occasional substrate node and/or link failures.

(a)Concise: The ‘concise’ heuristic solutions only use as many substrate resources as necessary to fulfill the demands of the proposed virtual networks. There is no additional resources reserved for any failure. This also means that there is no guarantee that the virtual network can recover from the occasional failure, though more substrate resources can be reserved for embedding further virtual networks. In the VNE research area, many algorithms are proposed on the basis of the assumption that the substrate network is operational all times. Most VNE algorithms proposed in the literature are therefore concise.

(b)Redundant: The redundant VNE heuristic approaches reserve additional resources for virtual networks in case some substrate elements may fail at run-time. This class of approaches enable to improve the reliability of mapped virtual networks. However, a tradeoff between the reliability of the heuristic solution and its embedding cost must be made:higher the degree of reliability, more substrate resources are consumed and less virtual networks are to be embedded. Anyhow, the redundant VNE algorithms are more popular than the concise in real network implementations. In case an element (substrate node or substrate link) of virtual networks fails, a fallback mechanism is able to switch from the primary element to one of its backup elements and reactivate the element. In recent years,redundant VNE heuristic solutions have been proposed[39],[40],[41],[42] in several journals.

As presented in above contexts, the characteristics are mutually independent. Therefore,any selected VNE heuristic algorithm may be,for example, static, centralized, concise at the same time. Based on this, a notation is derived to determine the class of the speci fic algorithm which it belongs to. The selected heuristic algorithms throughout this survey are described with the following syntax:

S|D / C|D / C|R

The first character denotes that whether the algorithm is Static or Dynamic. Next, the second character denotes that whether the algorithm is Centralized or Distributed. Finally,the third character aims to denote that whether the algorithm is Concise or Redundant. For instance, a VNE heuristic algorithm denoted as S/C/C represents that the heuristic algorithm is a static, centralized and concise algorithm.This categorization method allows for quick classification of any algorithm and proper comparison with similar VNE solutions.

III. ANALYSIS OF TYPICAL VNE HEURISTIC SOLUTIONS

Until now, a large number of VNE heuristic algorithms have been proposed for allocating substrate resources to proposed virtual networks. This section analyzes several heuristic algorithms in detail. Derived from the category method introduced in Section II, each heuristic algorithm can be categorized according to several mutual characteristics. Each category has its own representative heuristic algorithms. For a better understanding of each taxonomy, multiple VNE heuristic algorithms are selected to be analyzed, description or formulation included. In addition, one selected heuristic solution may belong to more than one category and is therefore analyzed in different subsections of this section.

3.1 Static / Centralized / Concise Heuristic solutions

This subsection is to detail typical heuristic algorithms that belong to the S/C/C scheme. In the VNE research, the S/C/C scheme is easy to be modeled and solved, comparing with the other seven categories. Main contributions and highlights of the VNE study lie in the S/C/C scheme and deserve to be carefully analyzed.

One of the earliest works in VNE and the S/C/C category is [23]. Two network entities,substrate network and virtual networks, are considered in this paper. The goals are to map virtual networks onto the substrate network effectively and to achieve low load on both substrate nodes and substrate links. While in [23], only the topology of virtual network is considered as a constraint. Constraints on virtual nodes (e.g. node capacity) and virtual links (such as link bandwidth) both are not included. Substrate resources are assumed to be in finite in this paper. That is to say, metrics called node stress and link stress are associated to each substrate node and substrate link respectively. Node stress is equal to the number of virtual nodes assigned to each substrate node; link stress measures the number of virtual links going through the substrate link. An algorithm in [23] called VNE-I performs the VN assignment without recon figuration in the substrate network. No extra resources are reserved for occasional failures. Thus the algorithm VNE-I belonging to the S/C/C category.To achieve low node stress and link stress, a subset of substrate nodes, called a cluster, are de fined and consists of three procedures. The first procedure is to determine the cluster center localization. Then to ful fill the node selection. At last, it is to select the substrate path.For conducting the node selection, a metric called node potential is de fined to reduce the node stress. For the link mapping, the shortest substrate path is used with mapping all virtual nodes. What’s more, a VN is proposed to subdivided into smaller star topologies to make the VN mapping easy. An adaptive optimization strategy is also proposed to perform the VN mapping. Simulation results reveal that the VNE-I outperforms the basic algorithm that maps virtual nodes and links based on pure stress levels. The bene fits of subdividing the VN are more signi ficant when the topology is sparse. Last but not least, the VNE-I can ef-fectively avoid hot spots and congestion in the substrate network, such as transit-stub links.

One typical heuristic algorithm of S/C/C category is [24], commonly cited in VNE research nowadays. An effective heuristic algorithm BA (Basic Algorithm) is proposed in [24] which includes path splitting and path migration. Different from former research,five main properties of VNE problem are identified in this paper: (1) finite substrate node and link resources; (2) VN admission control strategy; (3) the unpredictable nature of coming virtual networks; (4) the diversity of VN topologies; (5) node and link constraints (e.g.node capacity, link bandwidth). With these five properties, the VNE problem aims to optimize node and link mapping at the same time and is NP-hard [17] in nature. The objects are to map proposed VNs as many as possible and maximize the long-term average revenue of service provider. Thus virtual networks with higher revenue are assigned with higher priority. Algorithm BA consists of two main steps.First of all, the BA uses a greedy method to map virtual nodes. It sorts and prioritizes VNs based on VNs’ revenues and VNs in the order of priority. For each virtual node, candidate substrate nodes are determined on the basis of available resources and requirements. The substrate node with “maximum available resources” is selected and accommodates the virtual node. Lastly, it is to the virtual link mapping of BA. Virtual networks are sorted,prioritized and processed in the same way. For each virtual link, the method of k-shortest path is adopted. Upon setting the value k,k-shortest paths are computed and bandwidth requirements are considered. If fulfilled, the virtual link is mapped. If none of theses paths are able to satisfy the bandwidth requirement,the VN will be put in a queue for future processing. Mapping each virtual link exclusively to a single substrate path may lead to inefficient bandwidth usage and will not do bene fit to accommodating more proposed VNs in the future. An enhanced BA is also developed in this paper and allows flexible virtual link splitting over multiple substrate paths. The link mapping can be viewed as a multi-commodity flow problem [26]. The splitting ratio of each virtual link can be adjusted and facilitates a more flexible and manageable link assignment. Path migration is not formulated and illustrated in [24], just brie fly mentioned.

Another representative heuristic algorithm of the S/C/C is [28]. Most notably, the authors of [28] make the first attempt to solve the VNE problem through formulating one Mixed Integer Linear Programming(MIP) model.The method of adopting mathematical model is totally different from the previous heuristics. It enables to extend the solution space and outperforms the pure heuristics. However,the pure MIP model in [28] cannot be solved in polynomial time [44] when the substrate network is medium-sized. A relaxed version of Linear Programming (LP) where the objective function is a weighted sum of node and link mapping is developed from the previous MIP model. The object is to coordinate the VN assignment so as to increase VN request ratio and revenue and to decrease mapping cost.Another main contribution of [28] is the promotion of meta-node, one per virtual node,each connected to a cluster of candidate substrate nodes obeying node constraints (see Fig.2). Each time a virtual network is proposed,the substrate network is augmented with meta-nodes. These meta-nodes are connected to all substrate nodes within a given distance from the requested location of the corresponding virtual node. Then the augmented substrate network is used to solve a simple k-shortest path [25] or multi-commodity flow problem[26] to connect meta-nodes according to the virtual network topology. Owing to the fact that authors of [28] also fight for load balancing of substrate network elements, splittable link mapping is considered here. Two main algorithms are proposed: deterministic node mapping with multi-commodity flow method(D-ViNE) and randomized node mapping with multi-commodity flow (R-ViNE). D-ViNE is based on the deterministic virtual node mapping (the substrate node corresponding to the highest value of a given metric is selected).R-ViNE is based on the randomized virtual node mapping (the substrate node is selected on the basis of selection probability). Main simulation results reveal that: (1) mathematical programming, though variables relaxed,contributes to the performance of higher VN request acceptance ratio and revenue; (2)splittable link and multi-commodity flow method does bene fit to substrate load balancing; (3) randomization behaves better than the deterministic rounding approach in the node mapping period. Based on the conference work done in [28], [29] further develops the heuristic algorithm and proposes a generalized window algorithm for batching processing proposed VNs online. The window algorithm further enriches the contribution of [28].While in reference [33], the authors propose an exact VNE solution and use the pure MIP model [28] to solve VNE problem in smallscaled substrate network. Generally speaking,[28] is a quite representative paper in VNE research and affects a lot to the following heuristic solutions of the S/C/C category.

Fig. 2. Construction of an augmented substrate network with meta-nodes for a VN request ([28]).

Derived from the Subgraph Isomorphism Detection (SID) problem of the graph [43][44], another heuristic solution of the S/C/C category is proposed and presented in [27]. To the substrate network, it is treated as the graph G. Every proposed virtual network is viewed as a graph H. The isomorphism between both two graphs is a bijection f: V(G)→V(H), such that any two virtual nodes m and n of G are adjacent in G if and only if f(m) and f(n) are adjacent in H. The SID problem is NP-hard in nature and particular cases of this problem can be solved in polynomial time. In [27], a backtracking search approach based on SID is proposed to assign virtual nodes and links at the same time. If bad assignment exists, it can be revised by backtracking to a previous valid assignment in the SID algorithm [27]. Though conducting all network elements of the VN in one stage, [27] must have a full knowledge of the substrate network and proposes virtual networks ahead. The SID algorithm cannot be promoted to be on-line. Thus not useful in real network implementation.

Different from simply measuring the product of node resource and its adjacent link resources [24] to determine the VNE node mapping stage, the authors of [45] propose a novel S/C/C VNE method for mapping virtual nodes and ranking substrate nodes. As known to all, the node’s position inside the topology is one of the most important parameters in networking. Topology attributes of a node(substrate or virtual) have a direct effect on the effectiveness and efficiency of the embedding.A node ranking solution, inspired by the PageRank algorithm [46] used in Google’s search engine, is proposed to measure the topology incidence of a node when taking topology attributes into account. The algorithm proposed in [45] is labeled as RW-MaxMatch.The RW-MaxMatch is a two-stage mapping algorithm. During the first period, it computes the NodeRank values for each virtual and substrate nodes. Then it sorts virtual nodes in decreasing order according to the calculated NodeRank values. It does the same to substrate nodes. Next, virtual nodes with decreasing order are mapped to the substrate nodes in decreasing order. While in the second phase,the RW-MaxMatch is to assign virtual links to substrate paths with end nodes fulfilling resources demanding. Similar to the strategies in [24] and [28], find the just- fit shortest path by searching the k-shortest paths using binary search on values of k, until a path that satis fies the bandwidth demand of the virtual link is found. This is the case where substrate network does not support path splitting. When the substrate network supports path splitting,the multi-commodity flow approach is used to embed virtual links to the substrate links.A number of numerical results reveal that the RW-MaxMatch is a better resource measure and increases the long-term average revenue and VN request acceptance ratio, comparing to the algorithms in [24]. Another algorithm RWBFS, a backtracking algorithm based on the PageRank algorithm and breadth- first search,is proposed in [45] and is able to dynamically embed virtual networks during one mapping stage. It belongs to the D/C/C category that is detailed in the following subsection.

In [47], the authors develop one S/C/C heuristic algorithm on the basis of particle swarm optimization (PSO) method [48]. In general,VNE problem can also be treated as another combinatorial optimization problem. Through setting the number of iterations and convergence range, a sub-optimal solution will be found. In [47], it firstly makes a brief description of the VNE problem and presents an exact formulation based on ILP model, derived from the reference [28]. However, the ILP model is not used to resolve the problem. Then it constructs the VNE with discrete PSO. In the following section, it conducts a comparison with[49], another PSO approach, for performance evaluation. The simulation environment is to randomly generate a network scenario which consists of a substrate network and a virtual network, only with node capacity and link bandwidth requirements considered. The number of iterations is set to 50. The object is to evaluate the convergence performance. Simulation results show that the proposed DPSO outperforms [49] in terms of the convergence performance. Execution time and average value of objective function are calculated to prove the convergence true.

Due to the conclusion drawn from [28]that pure MIP model cannot be used to solve medium-sized and large-scaled VNE problem in polynomial time, authors of reference [50],belonging to the S/C/C category, resolve the VNE problem by using the method of column/ path generation [51]. In [50], the authors present the path-based MIP model for the VNE problem. The object is to minimize the overall cost of link bandwidth. The node consumption is excluded in the objective function since consumed node resources are fixed. In the first step, the authors relax the flow variables and shrink the solution space. The previous of MIP model is therefore edited to be an ILP model. Solve the ILP model and a feasible solution can be found. In the second step, construct the dual program of relaxed ILP model.Solve the dual model and add new paths to the previous ILP model. Upon calculating negative reduced cost, stop adding paths. The last step is to calculate the overall link bandwidth cost. Select the minimum value. Thus getting the optimal assignment in the restricted solution space. Similar to [50], [35] and [38] both apply column generation to VNE. Jarry et al.apply the column generation approach to oneshot VNE by assuming that the embedding of VNs can be delayed by storing coming virtual networks and be processed in batches using an auctioning mechanism. [35] can therefore be considered to be an of fline one. Mijumbi et al. [38] formulate a one-shot path-based VNE where the substrate network does not support path splitting. The formulated ILP model is then relaxed so as to apply column generation.The object of [38] is to ensure execution time low with VN request acceptance ratio high.Thus conducting relaxing variables of ILP.Then [38] constructs the dual program of ILP and applies column generation to fulfill the virtual link mapping. At last, a restricted VNE problem is solved to obtain a final solution. In additional, one proof of directly solving pathbased ILP model without any relaxation is[34]. [34] is an exact solution in nature. The formulation and simulation results are therefore not detailed in this survey.

In [37], Su et al. present two energy-ware VNE algorithms based on heuristics, proposed in [45] and [49]. The conference version of[37] is [52]. As energy cost is more than half of the operating cost of the substrate network,minimizing energy cost is critical for SP and InP. An energy cost model is presented in[37]. Host and router nodes are introduced and included in the model for the first time in VNE research. Different from the previous work [33] of the same topic, the energy cost model proposed does not violate the fact that virtual nodes per VN cannot map onto the same substrate node in VNE. Owing to the NP-hardness of solving the energy cost model,the authors propose two heuristic VNE algorithms for solving the VNE problem: a noderanking-based algorithm [45] and another particle-swarm-optimization algorithm [49].Through running extensive simulations, both two heuristic algorithms are able to save the energy cost up to 50%, comparing with the heuristic [28], deterministic node mapping &shortest path link mapping. Some other heuristic algorithms are not included in the simulation part.

3.2 Static / Centralized / Redundant Heuristic solutions

Comparing with the S/C/C category, the S/C/R scheme is a bit different and can be described as the “Survivable” VNE. The S/C/C heuristic solutions for VNE problem are proposed assuming that the shared substrate network remains operational at all times.However, arbitrary substrate node or link failures are part of everyday operation in today’s substrate network, such as multi-protocol label switched (MPLS) networks [53] and real time systems [54]. The S/C/R heuristic solution,striving for VN survivability and sparing extra resources for making up for substrate failures,is therefore a hot research issue and has been addressed in network virtualization. This subsection analyzes several representative algorithms of the S/C/R category.

The first typical work to consider redundant resources in virtual network embedding is [39]. Its conference version is [55]. In [39],the objects are to maximize the VN revenue and minimize the substrate penalty caused by single link failure. One main contribution of [39] is to formulate the survivable VNE(SVNE) to incorporate single substrate link failure for the first time. Since multiple link failures is a low probability event, one single link failure is considered. Besides of this, node failures are not explicitly dealt with. It is due to the fact that any node failure VNE depends on tolerating adjacent link failures. As a result,single link failure is addressed before coping with node failures. In addition, three heuristic SVNE algorithms for dealing with single substrate link are proposed in [39] due to the NP-hard nature of the MIP formulation of SVNE problem. In [39], node and link embedding are separated. The shared substrate network supports path splitting. For the node mapping phase, existing heuristics [24],[28] are conducted by the authors. To the link mapping stage, the first heuristic algorithm is a baseline policy heuristic. Thus labeling as BPH.Whenever a substrate link fails, the BPH simply recomputes a new link embedding for each VN affected by the substrate link failure.Though the BPH seems rather simple, it has a high recovery complexity and recon figuration cost. When to the second heuristic approach,it is a proactive heuristic and is labeled as PH.In the link mapping stage, for each virtual link per VN, a primary flow and a secondary flow, meeting the virtual link bandwidth requirement, are both prepared ahead by PH. To protect against the single substrate link failure,PH ensures that the primary and secondary flows are edge disjoint. The remaining heuristic proposed in [39] is a hybrid policy heuristic (HPH). Different the BPH and the PH, the HPH has a set of candidate backup detours for each substrate link. A path selection algorithm,such as k-shortest path algorithm, column generation [51], is conducted for computing these backup detours. In case any substrate link fails, the backup substrate link is invoked immediately. Evaluation results show that the PH and the HPH for SVNE outperform the BPH in terms of long term VN revenue, VN request acceptance ratio and link bandwidth efficiency. Several special topologies like hub-and-spoke and mesh VN topologies are also used in the simulation.

The authors in [56] propose to leave “backup resources” so as to offer guaranteed reliability and redundancy VN mapping. Firstly,the concept of “virtual infrastructures” is introduced and additional resources are collected from the substrate network. Then the “opportunistic redundancy pooling mechanism” is proposed whereby a set of redundant resources are shared by several virtual elements. Different from the work done in [39], this proposal focuses on node failures, especially on critical node backups. A virtual network is claimed to be reliable for a particular failure situation if it has redundant resources to recover from that situation. That level of reliability is limited by a number of failed resources. If the number exceeds the number of redundant resources,resources are said to be not recoverable.

In [57], a survivable S/C/R heuristic VN algorithm with the topology awareness is proposed to solve multiple substrate node failures. Previous survivable or redundant VNE algorithms, such as [56], [58], [59] and [60],aim to provide the survivability against single substrate node failure in a cost-effective way.Objects of [57] are to increase the long term revenue to the substrate network by ensuring a certain VN request acceptance ratio and to reduce the penalty incurred due to substrate node failures. The authors of [57] construct the Candidate Node Set of each virtual node at first. To each virtual node, the speci fic node,having the highest probability among the nodes in the Candidate Node Set, is selected to replace the former substrate node that has mapped onto the virtual node in case the former substrate node fails. Primary and backup node resources are also de fined in [57]. A recoverability-based VNE algorithm (R-VNE),adding a higher recoverability in the objective function of MIP formulation [28], is presented to map virtual networks in the first stage.When substrate node failures exist, a profit-driven VNE algorithm(PD-VNE) is adopted to ful fill the node mapping. Simulation results reveal that R-VNE and PD-VNE outperform the coordinated algorithm[28] in terms of long term business revenue, with the primary resource usage percentage up to 70% and VN request acceptance ratio equal.

Another special case where single facility(or host) node failure exists in real network scenario is illustrated in [61]. Similar to the network scenario in [37], authors of [61] present a SVNE algorithm, based on the bipartite graph matching problem of the graph theory,to deal with single facility node failure, with advanced switching (or router) nodes operational all the time. In [61], VN mapping consists of two components: one is to conduct the working and backup node mapping, the other is to ful fill the working and backup link mapping. In the node mapping stage, the first procedure is to map the working switching nodes to corresponding virtual switching nodes. Switching nodes with more available resources are selected in the first place. The criterion is same to [24]. The next procedure is to map working facility nodes to virtual facility nodes. Backup facilities are selected at the same time. While to the link mapping, working and backup link mappings are designed to minimize the bandwidth consumption. Two scenarios, anycast and multicast-based, are analyzed apart. Simulation results show that the proposed SVNE algorithm performs better than [40] in terms of blocking probability and time-average revenue.

In [62], M. Khan et al. propose another survivable VNE algorithm (SiMPLE) to deal with the single substrate link failure under the assumption that path splitting is allowed in the embedding. Its former conference version is [63]. The authors firstly present the background that link failures are more frequent than node failures [64][65]. In addition, the study in [65] shows that at most 5% of the substrate failures occur in presence of anther substrate link failure. Node failures can also be modeled as multiple link failures [66]. Based on these backgrounds, it is of great essence to study the single link failure in SVNE. To deal with the small or medium-scaled substrate network problem (e.g. 50 nodes), an integer linear program (ILP) of SiMPLE is constructed and is able to solve the SVNE problem. However,with the size of substrate network increasing to 100 nodes, it is hardly possible to solve the SVNE problem in polynomial time. Two heuristic algorithms of SiMPLE is therefore proposed: one is proactive solution, SiMPLE-PR,embeds VN and backups resources at the same time; the other is reactive recovery mechanism, SiMPLE-RE, performs on the substrate link failure as it arrives. As the path splitting is considered, backup resources is only 1/k times of the virtual link bandwidth demand, where k is the average number of splits in embedding a virtual link. Thus saving more resources for accommodating more proposed VNs. Numerical simulations reveal that SiMPLE outperforms full backup and shared backup schemes for SVNE [39].

3.3 Dynamic / Centralized / Concise Heuristic solutions

With new virtual network requests being proposed, the overall con figuration may become very bad. This situation will affect the operation of already mapped VNs and prevent new VN from being mapped. Solution to this situation is to recon figure the resource allocation.This recon figuration approach can be referred to as dynamic, as opposed to the static approach without any reconfiguration. There is only one shared substrate network and the SN is assumed to be operational all time. The notation D/C/C is used to represent this category.The heuristic algorithms of this category may require the costly migration of virtual nodes and links resulting in long service disruption times that be unacceptable for real-time and critical application. Comparing with the S/C/C scheme, fewer heuristic algorithms of D/C/C scheme are proposed in the literature.

The first attempt of recon figuration is [23].In [23], the authors propose two algorithms.One is VNA-I which has described in above subsection, the other is the VNE-II with reconfiguration. VNE-II is based on: (1) a periodic global marketing process to identify critical virtual networks (highly stressed nodes and links); (2) recon figuration using the basic algorithm VNE-I. Simulation results show that recon figuring only a subset of critical VNs can achieve most of the benefits of dynamic recon figuration while keeping the cost low.

While in [24], the authors propose node remapping and path migration approaches for recon figuration, on the basis of BA. Node remapping does not change the resource deployment when the virtual networks are running. A customized node remapping approach is presented for hub-and-spoke topologies. Nodes with the most available resources are selected as hub nodes. The spoke nodes are mapped on substrate nodes based on the shortest path method. Path migration is considered as a method of improving substrate link bandwidth utilization. The path migration can be performed for VNs with a long duration so as to accept more virtual networks. Different from the path splitting, path migration may incur significant computation overhead. However,the path migration in resource con figuration is not carefully presented and illustrated in [24].A brief introduction is mentioned instead.

In [67], the authors propose a service migration to improve Quality of Service (QoS)for mobile applications. It considers geographically sparse services worldwide. One highlight is that Quality of Experience (QoE)is promoted to end users. The objects of [67]are to minimize access cost to end users and to minimize network cost of InP. There is an assumption that all players in the model support service migration while the service is changing geographical location. Service delay is considered as the main parameter of access cost. Link bandwidth consumption is therefore considered as the main parameter of substrate cost. Each service is located in each server. Owing to the migration and tradeoffs of cost to revenue, the SP tries to find the optimal assignment in the solution space. For instance, gaming applications are very useful in this kind of service migration. Two kinds of nodes, access nodes and service nodes, make up of a virtual network. Only of fline situation is talked in this survey. The of fline algorithm migrates the server to a node which minimizes overall cost. Migration cost is the sum of available bandwidth, transit cost and required node capacity.

Another study on the D/C/C category is[68]. The corresponding journal version is[69]. The authors of [68] consider the mobility awareness of the VNE problem. The effect of VN mobility is an important issue in developing a VNE algorithm for mobile / dynamical networks. In this paper, a mobile core network is viewed as the available physical network.It is used for accommodating different VNs.In the first step, VN prioritization is proposed.Then a greedy heuristic algorithm is proposed.The main contribution is that [68] reveals the interaction of substrate network topology and traffic tunnelling at the mobility anchors on the efficient construction of virtual networks.

Due to the nature of on-line characteristic and complex computation, dynamic heuristic solutions are more challenging than the static scheme. The dynamical publications are therefore fewer than the static scheme. In addition,one shared substrate network restricts the solution space and is easy to achieve successful VN mappings when comparing with multiple substrate networks. In a word, the D/C/C category has fewer heuristic publications in the literature, when comparing with the the S/C/C category.

3.4 Static / Distributed / Concise Heuristic solutions

As presented in above three subsections, previous VNE heuristic algorithms all consider the VNE in one substrate network owned by an InP. However, in realistic settings, various VNs must be mapped on top of multiple substrate networks owned by different InPs. Each substrate network is able to embed parts of virtual network and connect them using the external links among SNs. figure 3 shows a VN and its assignment to a set of substrate networks managed by different InPs. This subsection presents and analyzes several typical heuristic algorithms, belonging to the S/D/C category, in recent years.

The first proposal of the S/D/C scheme is[70]. Its further extension work is journal version [71]. In [70], the main goal is to map virtual networks on multiple substrate networks(at least two) efficiently while minimizing the cost. Different from the previous centralized heuristic algorithms [23][24], the heuristic algorithm of [70] is distributed among multiple substrates. What’s more, four main problems arise: (1) it is hard to reduce mapping cost without a centralized substrate network; (2)parallel high-speed processing of multiple VNs must be allowed; (3) partial failures must be dealt with through automatic and runtime repairs; (4) robustness is to be ensured by avoiding single node failure. To deal with these issues and simplify the VNE problem,two assumptions are made. One is that the substrate resources are in finite throughout the mapping process. The other is that all VNs are known in advance. In addition, each VN is decomposed into smaller hub-and-spoke clusters. The splitting algorithm is easier to be proposed to deal with these smaller huband-spoke networks. In each smaller hub-andspoke network, virtual nodes with higher node capacity demand are elected as hubs and others are regarded as spokes. After conducting the splitting algorithm, another algorithm is to map each hub-and-spoke virtual network on top of corresponding substrate network. The corresponding strategy is that VN with large demand is assigned to SN with redundant resources. For each hub-and-spoke (sub-VN),the substrate node with the largest capacity is selected as the root node and the bub node is mapped onto it. Spoke nodes are then assigned by root substrate nodes on the basis of the shortest path. After all of the nodes and links in each hub-and-spoke are assigned, they are removed from the substrate network. The process is then repeated for remaining huband-spoke virtual networks. Extension work in[71] further proposes a Capacity Node Sorting algorithm (CNS) to sort the capacity ability of substrate nodes. A Shortest-Path-Tree algorithm (SPT) is also presented to construct shortest paths of end nodes. Results reveal that the CNS and SPT contribute to the efficient substrate resource usage comparing with the heuristic solution proposed in conference version[68].

Fig. 3. Embed one VN request among three SNs owned by different InPs[21].

In [72], a policy-based distributed inter-domain embedding algorithm PolyViNE is proposed. The PolyViNE also belongs to the S/D/C category. At first, the authors address the conflict between service providers (SPs)and infrastructure providers (InPs) in VNE.Each InP aims to release more resources in his managed substrate network by mapping more VNs. This will lead to earning more profits.While to each SP, it is to minimize the consumed resources with satisfying VN requests.To deal with this issue, PolyViNE defines a distributed protocol that coordinates participant InPs during the embedding process and ensures competitive embedding pricing for the SPs. For every virtual network, PolyViNE assigns priorities based on geographic location of each InP. When a SP is to establish a VN,he advertises the VN to a number of InPs. Responses will indicate the ability of each InP to embed the requested virtual network and the overall cost. The SP then picks the lowest cost proposal. InPs are therefore allowed to communicate with each other during the matching process. If one InP does not have enough resources (e.g. node capacity, link bandwidth),he can relay the VN to other InPs. In some cases, InPs can jointly participate in the bidding process, and jointly provide various resources for the embedding of a single virtual network. Comparing with the proposal in [70],PolyViNE presents a feasible VNE assignment on the basis of limited substrate network.This is practical in real network implementation. However, an apparent flaw of PolyViNE cannot be ignored and PolyViNE assigns each virtual network to one substrate network in the embedding process. Splitting a VN is not included. This situation therefore be reviewed as a special case in distributed VNE.

Another static, distributed and concise VNE heuristic algorithm is proposed in [73], along with fault-tolerant ability. This algorithm is aware of resource failures and performance degradation. The assignment per VN is separated two stages: initial and adaptive stage.The initial VN mapping consists of four procedures: (1) resource description and advertisement; (2) resource discovery and matching; (3)assignment of the VN; (4) VN binding. This scheme is same to [71]. The adaptive stage is made up of two main steps: (1) VN expansion;(2) deal with failure or any other abrupt situation.

Though mapping one VN across multiple SNs is an essential technology in VNE heuristic study and relieve substrate load, an assumption that all owners of substrate networks must reveal or exchange their private information each other is made. Several previous heuristic algorithms [70][72][75][76][77]have been proposed based on this assumption.These algorithms are unacceptable to owners of SNs. The resource information disclosure of SNs allows their competitors to estimate their future bidding pieces. So published heuristic algorithms are not applied in practice.An improved heuristic algorithm is proposed in [74] with limited information disclosure of multiple substrate networks. One S/D/C VNE heuristic framework is proposed. The framework is composed of four steps. The first step is the Resource Information Disclosure.The disclosure part per substrate network consists of three characteristics: (1) location and footprint; (2) the associated cost of each offered virtual node that is to be mapped onto the substrate nodes; (3) the bandwidth cost of the links between the peering nodes. All disclosed information is collected and registered by the SP who is be responsible for mapping and ranging the deployment of each VN. The second step is Resource Matching. According to the information disclosed by multiple SNs, the SP identifies a set of candidate resources for fulling the requirements of each requested virtual elements (e.g. virtual node capacity). Next, it is to the third step and it is the VN Partitioning. Different from former partitioning method [70] (e.g. max- flow mincut algorithm), an ILP model is proposed to split each VN request. The object is a cost minimization. All disclosed resource costs are taken into consideration. The VN partitioning solver generates multiple sub-VNs. At last,it is the fourth step: VN Segment Mapping.Upon splitting each VN request, each SN map assigned VN segments while satisfying certain virtual node and virtual link requirements. A MIP model, derived from [28], is constructed to deal with the mapping problem. To investigate the framework, a comparison with a“best-case” approach [70] is made. Simulation results show that the heuristic algorithm with limited information disclosure behaves well and proves to be a feasible approach to map a VNR across multiple SNs.

When it is to the proposal [78], T. Mano et al., present another S/D/C VNE heuristic solution, based on secure multi-party computation (MPC) [79], to efficiently map virtual networks across multiple substrate networks without revealing any private information of substrate networks. The previous version is [80]. Comparing with previous heuristic algorithms of revealing all or limited private information, [80] is the first attempt that is acceptable for all owners of SNs to implement in practice. The MPC has been applied to various problems, including polynomial optimization problems [81][82] and simple decision problems [83][84], but has not been successfully applied to VNE problem. The algorithm of[78] is labeled as VNE-MPC in this survey.In [78], three main steps make up the VNEMPC: (1) according to an MPC sort algorithm, the authors split every proposed virtual network into pieces and calculate the price order of all pieces; (2) the authors then select an optimal set of pieces to cover the proposed VN; (3) different substrate networks enumerate the minimum necessary pieces based on Pareto optimal set [78]. Different from the conference version [80], [78] can achieve a feasible solution in few minutes. One VN can be processed each time. The VNE-MPC is therefore an online VNE heuristic algorithm as well.

3.5 Remaining four categorizes

As talked in the former subsections, four remaining categories of VNE heuristic algorithms, S/D/R, D/D/C, D/ D/R and D/C/R,demand to be analyzed.

However, few publications have been proposed so far in the literature. This status results from two main reasons as follows:

(1) NP-hardness of VNE problem: At the early stage of VNE study, VNE has been proven NP-hard [17]. It is difficult to achieve an exact mapping assignment in polynomial time(a substrate network of 50 nodes, each VN consisting of 10 nodes and 0.5 link probability). It is therefore impossible to promote VNE to the realistic implementation. The heuristic algorithms are therefore developed to find a feasible solution, with regard to each concrete network scenario. Pure heuristic method and relaxed mathematical model are adopted in the heuristic research. Previous surveys [21][22]have vividly indicated the fact that it is hardly possible to solve the VNE problem, with any two characteristics of dynamical remapping or multiple SNs or resilience, in minutes of time,even for moderately sized networks (a SN of 40 nodes, a VN of 5 nodes and 0.5 link probability) [22]. Thus leading fewer publications of the remaining four categories in the literature.

(2) Extension work of the S/C/C category: The S/C/C category has been considered as a basic scheme in the VNE heuristic research[21]. Most proposals concentrate on this cate-gory. On the basis of the S/C/C, any particular scheme, which selects any characteristic of the distributed, dynamic and resilience, is considered as a variant of the S/C/C category. Fewer publications are proposed comparing with the S/C/C category. If selecting two characteristics a time, it is more dif ficult to propose any heuristic algorithm to solve corresponding VNE problem. To this end, the remaining four categories has fewer publications in the literature, even comparing with the schemes that only change one characteristic.

IV. A CLASSIFICATION OF CURRENT HEURISTIC ALGORITHMS

While in this section, the taxonomy approach proposed in Section II-C is adopted to group a number of VNE heuristic algorithms. Table II and Table III group a large number of heuristic solutions in the literature. In addition,each heuristic solution is further characterized,considering the mapping stages of VNE, as derived from Section II-A. Node-link constraints are figured out in both two tables. Link constraints are usually link bandwidth and link propagation delay. Node constraints are usually node location and node capacity. In many other VNE heuristic algorithms, node capacity is usually called as CPU, representing node’s ability of calculation. For the sake of generality, node capacity, representing the node’s ability of calculating or processing a computation task, is adopted throughout this survey. Goals of each heuristic algorithm are described, followed by the node-link constraints. Individual contribution of each heuristic solution is also presented in the last column. Heuristic solutions belonging to more than one category are also marked with an asterisk (*). This marking method happens when an algorithm is implemented in two opposite ways (e.g. either centralized or distributed).

The VNE heuristic algorithms belonging to the S/C/C category are grouped in the first part of Table II. This category of heuristic solutions can perform the resource con figuration of proposed virtual networks in a centralized manner, knowing full knowledge of VNs in advance, and leaving no extra resources for mapping VNs. An assumption that the shared substrate network is operational throughout the whole VN mapping process. The S/C/C category is the straightforward solution in VNE, with a large number of algorithms in the literature proposed.

The D/C/C category groups a set of solutions that are able to implement the dynamic recon figuration of mapped virtual networks as soon as a new virtual network arrives. Other aspects, such as centralized behavior and concise manner, are both considered. Dynamic heuristic solutions are more challenging than the static owing to their on-line characteristic and complex computation. Thus leading to fewer publications than the S/C/C category.These heuristic solutions are listed in the second part of Table II.

A large number of VNE heuristic solutions are static and centralized and also consider the redundancy. Thus belonging to the S/C/R category. An example described here is the VN mapping assignment that spares extra node or link resources in advance. This method not only does bene fit to the VN survivability, but also contributes to the realistic network application. In case any substrate element (link or node) fails, the SP can use the spared resources to fulfill the reconfiguration of the failed substrate link or node. The first part of Table III presents the algorithms of this category.

While to the second part of Table III, it is S/D/C scheme and groups some algorithms that perform the configuration of proposed VNs across multiple substrate networks. Though conducted in a distributed network environment, several heuristic algorithms are proposed owing to the demand of implementing VNE problem for application.

The remaining four categories, S/D/R, D/D/C, D/D/R and D/C/R, have stimulated little interest both from academia and industry so far. This contributes to the situation that the distributed algorithms are significantly hard to implement comparing with the centralized.Foremost, it is rather dif ficult to split the pro-posed virtual network. In addition, even in small-scaled network scenario, it is hard to reach near-optimal solutions in distributed networks, with regard to different objects. Solutions in these categories are grouped in lower parts of Table II and Table III.

?

Table III. Classi fication of vne heuristic algorithms

?

Based on above two tables, it is easy to draw the conclusion that the present VNE heuristic study focuses on the centralized category in the academia. There are also many approaches belonging to the static category.This tendency will continue in the foreseeable future. Research on the distributed aspect also requires to be done in order to enrich the VNE study.

Considering Section III and Section IV,a overall comparison of all heuristic algorithms can be made. Three main conclusions can be drawn. Firstly, the S/C/C category is the fundamental category of VNE heuristic algorithms. Many VNE heuristic algorithms,proposed in the literature, belong to the S/C/C category. Two factors contribute to this phenomenon in VNE heuristic research area.One factor is that the S/C/C category covers the simplest VNE network scenario (batch processing VNs in a time window or know VNs in advance + only one shared substrate network + all operational network elements throughout the VNE process) in VNE study[21]. Therefore, conducting the research of the S/C/C category is much easier than the other seven categories. The other factor is that other categories are on the basis of the S/C/C category. Therefore, it is important and essential to research the S/C/C category in the first place. Secondly, there exists some heuristic proposals belonging to these categories, such as the S/C/R category, in the literature. For these categories, only one attribute is changed,comparing with the S/C/C category. The S/C/R category is selected to be described. The S/C/R category aims to make mapped VNs still run in case that any substrate node / link fails.Though the problem is more complicated than the S/C/C category, a feasible VN embedding still can be found. One common and direct heuristic solution is to remap the affected VN again. Finally, there have been few studies belonging to these categories, changing no less than two attributes of the S/C/C category, so far in the literature. The network scenarios of these categories are rather complex and hard to be analyzed. For instance, the S/D/R category aims to optimize the VN embedding among multiple SNs. The failure of any substrate element (node or link) is also considered. Thus the complexity is higher than the usual S/D/C category, not to mention S/C/C category.Any corresponding heuristic algorithm is very hard to be proposed. However, these categories, changing no less than two attributes of the S/C/C category, are suitable for the VN embedding in realistic networking application.Therefore, more exploration is required in the future study of VNE heuristic solutions.

V. FUTURE RESEARCH DIRECTIONS

This section aims to highlight and emphasize the future directions of VNE heuristic solution. Three main fields are pointed out in order to propel the VNE research in the future: VNE heuristic algorithms covering the categories of distributed or dynamic approaches, VNE algorithms striving for the optimization of particular aspects and the application of VNE in wireless network environment. In general,these three main fields are independent and isolated from each other. However, these three main fields may intertwine each other when dealing with one concrete VN embedding problem. For instance, one heuristic algorithm,belonging to the D/D/C category, is proposed to embed a unpredictable VN among multiple SNs. The goal of this heuristic algorithm is to minimize the total energy consumption of all active network elements (switches and links)among SNs. The VN embedding is also conducted in wireless network environment, not the usual wired network. In addition, these three main fields are all plotted in a figure. The figure 4 is plotted, with the goal of helping readers to grasp the mainline of this section easily.

5.1 Distributed and dynamic VNE Heuristic

Although the representative formulations of VNE exact solution, such as ILP formulation[34] and MIP formulation [28][29], have been proposed for embedding virtual networks,finding an optimal embedding assignment is computationally complex and is still limited in a small or medium-scaled substrate network(at most 50 nodes and 0.5 link probability).To solve a larger instances and promote VNE to future realistic network scenarios, heuristic approaches, such as greedy method and relaxing the variables of original MIP, are adopted and developed. VNE heuristic algorithms have been warmly developed over the past years.Several optimization techniques, such as column / path generation [35][38][50] method,also have been used to achieve near-optimal assignment in moderate sized VNE. However,these achievements are mostly realized in a centralized substrate network, with no reconfiguration. Virtual networks are encouraged to be distributed to multiple substrate networks.Reconfiguration of any mapped VN is also allowed to realize a better assignment as soon as a new VN comes. Under both two circumstances, substrate load maybe spread and more VNs are to be accepted. Both two kinds of mapping strategies are more suitable to the application in the future network environment.Table II and III vividly show that, currently, there is a lack of distributed and dynamic solutions for the VNE heuristic study. However, the characteristic of distributed is more important than the dynamic attribute [21][22].Thus the distributed attribute having the priority in this subsection.

Fig. 4. Future directions of VNE heuristic solution

The earliest work of the distributed VNE heuristic in the literature is [70]. Although [70]enriches the VNE research area and removes the weakness of the centralized algorithms,several problems still come into appearance.The fundamental problem is the sub-optimal embedding solution calculated by [70]. It is hard to find the proper convergence direction in multiple substrate networks. To deal with this problem, using clustering techniques will confirm the embedding tasks to a limited subset of the substrate networks, thereby achieving the near-optimal assignment within allowed convergence error. In addition, private information of multiple SNs must be known in advance. This is another issue in distributed VNE heuristic research. It is not practical in realistic implementation owing to the fact that InPs will not share the private information of their substrate networks to remain competitive in their fields.

The recent work of the typical distributed VNE heuristic is [78]. Comparing with the work done in [70], [78] improve a lot in many aspects. [78] aims to solve the issue of whether to share the private information or not. The authors propose a novel approach that can achieve the near-optimal VN assignment over multiple substrate networks without revealing any private information of substrate network.The approach employs secure multi-party computation only for masking sensitive values. This can optimize virtual networks under limited information without applying any time-consuming techniques, based on the theory of optimization. The algorithm of [78],VNE-MPC, is therefore accused of finding reasonably near-optimal VN assignments. This work can be implemented in practice for deploying virtual networks across multiple SNs manged by different InPs. However, dynamic mapping of VNs is not presented in [78].

Up to now, there is still a lack of distributed VNE heuristic algorithms, especially along with the dynamic characteristic. The main interest of the academia has focused on static VN embedding in a distributed network virtualization environment. The substrate resource recon figuration among multiple substrate networks (distributed NV environment) is very meaningful and has a large potential for the real implementation of network virtualization.However, the complex computation is an obstacle to the development of the distributed VNE heuristic algorithms with resource reconfiguration (dynamical VN mapping). Not only the optimal mapping is hard to be achieved in small-scaled SNs, but also the heuristic solution is calculated for large SNs [22].

5.2 Particular VNE aspects

At present, several fields have been acquired in the VNE heuristic study. Two particular fields are selected here: Survivability and Energy-awareness.

1) VNE Survivability: Previous research on VNE heuristic algorithms is based on an assumption that the substrate network is operational at all times. However, occasional substrate failures are common in the realistic networks. There is a demand of developing survivability in VNE. Survivability has been investigated in nonvirtualized networks in the past [108][109][110]. In [108], network survivability in Optical and Multi-protocol Label Switched (MPLS) networks is considered. When to the Cloud Computing, a trend towards designing survivable resource allocation schemes is also developed [109][110].Xu et al. [111] propose a resource allocation scheme for provisioning virtual data centers with backup virtual machines and links. However, the survivability of physical machines and links are not taken into account in their proposal.

In network virtualization, if the goal of VNE changes to secure the mapped VNs running and unaffected by the substrate failures(substrate node or link), the substrate network must provide backup substrate nodes and links rather than remapping affected VNs. For instance, due to different reactive schemes of substrate failures, the best approach to minimize the effect of single substrate link is to backup every substrate link in advance [39].

In the literature, the first journal paper relating to VNE survivability is [39]. The authors of [39] remove the assumption of operational network elements all time and propose the solution model of SVNE based on the MIP model [29]. This proposal aims to deal with one substrate link failure. The object of [39]is to minimize the consumed cost of mapped VNs, including the backup resources. Due to the complex computation of MIP model, a proactive and hybrid heuristic algorithms are presented to deal with SVNE problem instead.To the proactive, it is to backup all mapped substrate paths in advance. In case where any substrate link fails, the corresponding backup path can replace the previous path immediately. To the hybrid, it is based on a fast re-routing strategy and utilizes a preserved quota for backup on each substrate link. The proposal also concludes that the hybrid and proactive schemes outperform the coordinated algorithm[28] in terms of long term profit and VN request acceptance ratio.

The up-to-date study on SVNE is [62]. At first, the authors point out that link failures are more frequent than node failures in SVNE[64][65]. Node failures can be modeled as link failures in network research [66]. Therefore,link failures of SVNE deserve more and deep research. By exploiting the path diversity of the substrate network, the authors propose a survivability in multi-path link embedding(SiMPLE) to against substrate link failures while incurring minimal resource redundancy.In case of multiple arbitrary link failures, SiMPLE provides maximal survivability to the virtual networks. A greedy proactive solution is developed to solve the large-scaled network scenarios in case of any single link failure. In the presence of more than one substrate link failure, a greedy reactive algorithm is proposed as a extension of the single link failure.Simulation results show that two heuristics of the SiMPLE run smoothly for solving occasional link failures.

Future study of the VNE survivabilty aspect may concentrate on both two directions: (1)previous SVNE is proposed in a shared substrate network. Survivability in multiple substrate networks, still at its early stage, can raise further challenges since it involves both intra and inter substrate link failures. The solution space is therefore extended; (2) the relationship between substrate node failure and link failure requires further research in VNE. This does bene fit to the coordination of nodes and links in SVNE [66]. If possible, it is necessary to propose a expression to quantify describe their quanti fied relationships in SVNE.

2) VNE Energy-awareness: To save energy consumption in future shared substrate networks, resource consolidation (rearrange the allocated resources) is considered as an enabler [112][113]. For instance, in the literature,a set of green strategies to allocate resources in Cloud Computing environments have been proposed. In [114], the authors propose a Green Power Management (GPM) to migrate the virtual machine in Cloud environment owing to a dynamic resource allocation that seeks the ideal load balancing among all virtual machines.

In the network virtualization environment,the substrate networks need to dynamically dimension themselves for current link traffic requirements rather than for peak traf fic if the goal of VN assignment is to minimize the energy consumption. Owing to the fact in [115]that power consumption of current network equipment is insensitive to its traffic load,the best solution of minimizing the energy consumption is to switch off or hibernate as many networking elements (nodes and links)as possible without compromising the network performance.

The energy-ware VNE should be performed during low traffic demands when several nodes can be switched off by rerouting the traf fic to a smaller set of consolidated network equipment. This scheme may result in long substrate path between end nodes because of finite substrate resources (link and node). The substrate consumption of mapping a VN is therefore increasing. So, a trade-off between different objects, such as substrate cost, energy consumption, must be achieved in energy-aware VNE.

The fist journal algorithm proposed in the energy-aware area is [33] and labeled as VNE-EA. The goal of [33] is to minimize the switched nodes and links of each mapped virtual network. The simulation reveals that as VN traffic load increases, the VNE-EA saves energy but at the cost of high substrate cost, with VNR acceptance ratio high. However, a flaw in the formulation of VNE-EA is that more than one virtual nodes of a VN are allowed to coexist on a substrate node. This breaks the relationship of virtual and substrate nodes in VNE. In addition, networking elements (substrate nodes and substrate links) are assumed to be homogeneous with regard to their energy consumption. This assumption is not true in real network environment.

The recent typical work of energy-awareness is [37] and two heuristic algorithms are proposed. The authors try to minimize the number of active substrate nodes and links with ensuring VN request acceptance ratio high. An exact formulation based on ILP model is also constructed in [37]. The flaw in[33] is removed in the formulation of [37] and virtual nodes per VN is not allowed to coexist on the same substrate node. Energy cost of the complex substrate network is modeled, too.For instance, the authors classify substrate nodes into host nodes, which need to execute some computational tasks, and router nodes,which forward packets to and from host nodes.Therefore, energy consumption of different nodes differ each other. Through referring to[116][117][118], models of host and router node energy cost are constructed. This modeling method has the potential of being promoted to the real VNE application in the future.

Future research of energy-awareness could concentrate on two points: (1) further develop heuristic algorithms to find near-optimal solutions in reasonable time; (2) perfect the formulation of VNE energy-aware problem. Topology is an important aspect in energy consumption. In addition. It is necessary to study the relationship between the energy efficiency and VNR acceptance ratio [37]. In other words, it is important to avoid rejecting proposed VNs when shifting to more energy efficient VN assignments. At last, another issue that energy cost is dependent on the load can be another future direction in VNE energy-awareness area.

5.3 VNE in wireless environments

When it is to the maturity of network virtualization, it is to be applied in the realistic network environment. Several specific network environments are included. For achieving this motivation, VNE heuristic algorithms are migrating from theoretical to real scenarios trying to deal with particular constraints of each network environment. VNE in wireless environments is selected in this subsection.

VNE in wireless environments can be described as Wireless virtual network embedding(WVNE) in the literature. Though wireless networks have been playing an important role in accessing the core network and virtualization in wireless networks is an emerging area,little attention has been attracted over the past ten years. Several significant research challenges remain to be solved before widespread deployment of wireless networks. Two main challenges are presented in this survey. Firstly, unlike previous VNE heuristic algorithms in wired networks, where substrate resources are unchanged and resource allocation can be done with certain, radio resource abstraction and isolation in wireless environments are not straightforward. It is due to the inherent broadcast nature of wireless communications and stochastic fluctuation of wireless channel quality [119]. Therefore, how to virtualize links is a distinctive challenge in WVNE. The other challenge presented is the mobility of substrate nodes. Such the mobility [120] can change the connectivity of the substrate nodes and corresponding substrate paths are made insuf ficient or invalid in WVNE.

Based on the challenges in wireless environments, several solutions have been proposed to deal with WVNE. Commonly, several assumptions, such as removing mobility of end users [121], ignoring nodes and links constraints [122], are made to restrict solution space and find a feasible solution. Several accessing or multiplexing methods (e.g. FDM[123][124], TDM [125][126][127], space division multiplexing [128][129]) are adopted in WVNE research.

As can be drawn from the literature and referring to the related survey [130][131], future heuristic solutions of wireless VNE will concentrate on two characteristics below:

(1) Mobility: the mobility of each end user is one important attribute in wireless environments. Former works [69][132] start to consider nodes’ mobility as a trigger for resource con figuration in wireless VNE.

(2) Isolation: a set of parties own and manage wireless resources. They are characterized by a lack of the centralized environment which can contribute to a universal VN assignment[133] and management in WVNE. A general mechanism is therefore in need to be developed. More interest for developing the mechanism will be extended in the future study.

VI. CONCLUSION

Network virtualization provides a promising tool to remove the rigidity of current Internet.Virtual Network Embedding is considered as a key issue requiring to be solved in network virtualization. Optimizing the embedding of several heterogeneous virtual networks onto shared substrate networks is NP-hard in nature. Exact VNE solutions can be achieved for deploying small-sized network scenarios.VNE algorithms proposed in the literature are mostly heuristic, with the goal of solving the feasible VN assignment in polynomial time.

This paper presents a survey of current heuristic algorithms in VNE area. A concise description of the VNE problem and formulation of the heuristic solution are provided in Section II. Based on the category derived from former researches, multiple typical heuristic algorithms of each category are analyzed.Next, a large number of VNE heuristic solutions are summarized and categorized in tables of Section IV.

There are a lot of works remaining to be done in the area of VNE heuristic solution.For instance, VN mapping among multiple substrate networks still calls for the improvement of VNR acceptance ratio, with the assignment enabling to be solved in reasonable time. Moreover, survivable VNE needs to be further extended and takes network elements’migration (node or link) into account. There are some other novel directions, such as energy-awareness, which has also been largely neglected in the VNE research. Last but not least, the research in wireless environment is still at its early stage and deserves more attention both from the industry and the academia[140][141][142].

ACKNOWLEDGMENT

This work was supported by the National Natural Science Foundation of China under Grants 61372124 and 61401225, the National Science Foundation of Jiangsu Province under Grant BK20140894, the Postgraduate Research & Practice Innovation Program of Jiangsu Province under Grant KYCX17_0784.

[1] J. S. Turner and D.E. Taylor, “Diversifying the internet,” in Proc. IEEE GLOBECOM’05, St. Louis,MO, USA, 2005.

[2] N. M. M. K. Chowdhury, “Network virtualization:State of the art and research challenges,” IEEE Communications Magazine, vol. 47, no. 7, pp.20-26, Jul. 2009.

[3] A. Berl, A. Fischer, and H. De Meer, “Virtualisierung im future internet- virtualisierungsmethoden und anwendungen,” Informatik-Spektrum,vol. 33, no. 2, pp. 186-194, Apr. 2010.

[4] K. Tutschku, T. Zinner, A. Nakao, and P. Tran-Gia,“Network virtualization: Implementation steps towards the future internet,” in Proc. Of the Workshop on Overlay and Network Virtualization at KiVS, Kassel, Germany, Mar 2009.

[5] A. Berl, A. Fischer, and H. De Meer, “Using system virtualization to create virtualized networks,” in Workshops der Wissenschaftlichen Konferenz Kommunikation in Verterlten Systemen (WowKIVS2009), Kassel, Germany, Mar 2009.

[6] N. Chowdhury and R. Boutaba, “A Survey of network virtualization,” Computer Networks(Elsevier), vol. 54, no. 5, pp. 862-876, 2010.

[7] L. Peterson, S. Shenker, J. Turner et al., “Overcoming the internet impasse through virtualization,” IEEE Computer, vol. 38, no. 4, pp. 34-41,Apr. 2015.

[8] N. Feamster, L. Gao and J. Rexford, “How to lease the internet in your spare time,” ACM SIGCOMM Computer Communication Review, vol.37, no. 1, pp. 61-64, 2007.

[9] J. Carapinha and J. Jimenez, “Network virtualization: a view from the bottom,” in Proceedings of the 1stACM workshop on Virtualized infrastructure systems and architectures, ser. VISA ’09.New York, NY, USA: ACM, 2009, pp. 73-80.

[10] R. Bless and C. Werle, “Network virtualization from a signaling perspective,” in Proc. International Workshop on the Network of the Future(-Future-Net’09), Dresden, Germany, 2009.

[11] D. Schwerdel, D. Gunther et al., “German-lab experimental facility,” Future Internet Symposium(FIS) 2010, 9, 2010.

[12] Hongke Zhang, Wei Quan, Han-chieh Chao and Chunming Qiao, “Smart identifier network: A collaborative architecture for the future network,” IEEE Network, vol. 30, no. 3, pp. 46-51,May, 2016.

[13] Hongke Zhang, Ping Dong, Wei Quan and Bin Hu, “Promoting efficient communication for high-speed railway using smart collaborative networking,” IEEE Wireless Communications, vol.22, no. 6, pp. 92-97, Dec., 2015.

[14] N. McKeown, T. Anderson, H. Balakrishnan et al.,“OpenFlow: enabling innovation in networks,”SIGCOMM Comput. Commum. Rev., vol. 38, no.2, pp. 69-74, Mar. 2008.

[15] S. Bhardwaj, L. Jain, and S. Jain, “Cloud computing: A study of infrastructure as a service(iaas),”Int J. Eng. And Information Technology, vol. 2,pp. 60-63, 2010.

[16] A. Haider, R. Potter, and A. Nakao, “Challenges in resource allocation in network virtualization,”in 20thITC Specialist Seminar, vol. 18, 2009, p.20.

[17] D. G. Anderson, “Theoretical approaches to node assignment,” Dec. 2002, unpunished Manuscript.

[18] J. Kleinberg, “Approximation algorithms for disjoint paths problems,” Ph.D. Dissertation, Massachusetts Institute of Technology, 1996.

[19] S. Kollipoulos and C. Stein, “Improved approximation algorithms for unsplittable flow problem,” in Foundations of Computer Science, 1997.Proceedings., 38thAnnual Symposium on, Oct 1997, pp. 426-436.

[20] A. Belbekkouche, Md. Mahmud Hasan, A. Karmouch, “Resource discovery and allocation in network virtualization,” IEEE Communications Surveys&Tutorials, vol. 14, no. 4, pp. 1114-1128,Feb. 2012.

[21] A. Fischer, J. Betro, et al., “Virtual Network Embedding: A survey,” IEEE Communications Surveys&Tutorials, vol. 15, no. 4, Feb. 2013.

[22] Haotong Cao, Longxiang Yang, et al., “Exact Solutions of VNE: A Survey,” China Communications, vol. 13, no. 6, June. 2016.

[23] Y. Zhu and M. Ammar, “Algorithms for assigning substrate network resources to virtual network components,” in Proc. 25 IEEE INFOCOM, 2006,pp. 1-12.

[24] M. Yu, Y. Yi, et al., “Rethinking virtual network embedding: substrate support for path splitting and migration,” SIGCOMM Comput. Commun.Rev., vol. 38, no. 2, pp. 17-29, Mar. 2008.

[25] T. H. Cormen, C. Stein, R. L. Rivest, and C. E.Leiserson, Introduction to Algorithms, 2nded.New York, NY, USA:McGraw-Hill, 2001.

[26] S. Kollopoulos and C. Stein, “Improved approximation algorithms for unsplittable flow problems,” in Proc. IEEE FOCS, 1997, pp. 426-435.

[27] J. Lischka and H. Karl, “A virtual network embedding algorithm based on subgraph isomorphism detection,” in Proc. 1stACM Workshop VISA, 2009, pp. 81-88.

[28] M. Chowhury, M. Rahman, and R. Boutaba, “Virtual network embedding with coordinated node and link mapping,” in Proc. IEEE INFOCOM, Apr.2009, pp. 783-791.

[29] M. Chowhury, M. Rahman, and R. Boutaba,“Vineyard: Virtual network embedding algorithms with coordinated node and link mapping,” IEEE/ACM Trans. Netw., vol. 20, no. 1, pp.206-219, Feb. 2012.

[30] A. Schrijver, Theory of linear and integer programming, New York, NY, USA: John Wiley &Sons, Inc., 1986.

[31] “GLPK(GNU Linear Programming Kit),” Jul. 2016.Available: http://www.gnu.org/software/glpk/

[32] “IBM ILOG Optimization Products,” Jul. 2016.Available: www=01.ibm.com/software/websphere/products/optimization

[33] J. Botero et al., “Energy eきcient virtual network embedding,” IEEE Commun. Lett., vol. 16, no. 5,pp. 756-759, May 2012.

[34] M. Melo et al., “Optimal Virtual Network Embedding: Node-Link Formulation,” IEEE Trans.Netw. and Serv. Manag., vol. 10, no. 4, pp. 356-368, Dec. 2013.

[35] A. Jarray and A. Karmouch, “Decomposition approaches for virtual network embedding with one-shot node and link mapping,” IEEE/ACM Trans. Netw., vol. 23, no. 3, pp. 1012-1025,Jun.2015.

[36] Long Gong, Huihui Jiang, Yixiang Wang and Zuqing Zhu, “Novel Location-Constrained Virtual Network Embedding(LC-VNE) Algorithms Towards Integrated Node and Link Mapping,”IEEE/ACM Trans. Netw., vol. 24, no. 6, pp. 3648-3661, 2016.

[37] S. Su, et al., “Energy-Aware Virtual Network Embedding,” IEEE/ACM Trans. Netw., vol. 22, no. 5,pp. 1607-1620, Oct. 2014.

[38] R. Mijumbi et al., “A Path Generation Approach to Embedding of Virtual Networks,” IEEE Trans.Netw. and Serv. Manag., vol. 12, no. 3, pp. 334-348, Sep. 2015.

[39] M. R. Rahman, Raouf Boutaba, “SVNE: Survivable Virtual Network Embedding Algorithms for Network Virtualization,” IEEE Trans. Netw. and Serv. Manag., vol. 10, no. 2, pp. 105-118, Feb.2013.

[40] Bingli Guo et al., “Survivable Virtual Network Design and Embedding to Survive a Facility Node Failure,” Journal of Lightwave Technology,vol. 32, no. 3, pp. 483-493, Nov. 2013.

[41] M. Khan et al., “Multi-path Link Embedding for Survivability in Virtual Networks,” IEEE Trans.Netw. and Serv. Manag., vol. 13, no. 2, pp. 253-266, Apr. 2016.

[42] S. Chowdhury et al., “Dedicated Protection for Survivable Virtual Network Embedding,” IEEE Trans. Netw. and Serv. Manag., vol. 13, no. 4, pp.913-926, May. 2016.

[43] D. Eppstein, “Subgraph isomorphism in planar graphs and related problems,” Journal of Graph Algorithms and Applications, vol. 3, no. 3, pp.1-27, 1999.

[44] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An improved algorithm for matching large graphs,” in Proc. 3rdIAPR TC-15 Workshop on Graphbased Representations in Pattern Recognition, Ischia, Italy, 2001.

[45] X. Cheng, S. Su, Z. Zhang, H. Wang, et al., “Virtual network embedding through topology-aware node ranking,” ACM SIGCOMM Computer Communication Review, vol. 42, April. 2011.

[46] L. Page, S. Brin, R. Motwani, and T. Winograd,“The pagerank citation ranking: Bringing order to the web,” Technical report, Stanford Digital Library Technologies Project, 1998.

[47] L. Wang, H. Qu, J. Zhao and Y. Guo, “Virtual network embedding with discrete particle swarm optimisation,” Electronics Letters, vol. 50. No. 4,pp. 285-286, 2014.

[48] R. Eberhart and Y. Shi, “Particle swarmoptimization: developments, applications and resources,”Conf. Evolutionary Computation, Seoul ,Korea,pp. 81-86, May, 2001.

[49] Z. Zhang, X. Cheng, S. Su, Y. Wang, K. Shuang,and Y. Luo, “A uni fied enhanced particle swarm optimization-based virtual network embedding algorithm,” International Journal of Communication Systems, 2012.

[50] Q. Hu, Y. Yang, and X. Gao, “Resolve the virtual network embedding problem: A column generation approach,” in Proc. IEEE INFOCOM, pp.410-414, Apr. 2013.

[51] C. Barnhart, E. L. Johnson, G. L. Nemhauster,M. W. P. Savelsbergh, and P. H. Vance, “Branchand-price: Column generation for solving huge integer programs,” Oper. Res., vol. 46, no. 3, pp.316-329, May. 1998.

[52] S. Su, Z. Zhang, X. Cheng, Y. Wang, Y. Luo, and J. Wang, “Energy-aware virtual network embedding through consolidation.” in Proc. IEEE INFOCOM WS-CCSES: Green Networking and Smart Grids, pp. 2708-2713, 2012.

[53] W. Lau and S. Jha, “Failure-oriented path restoration algorithm for survivable networks,” IEEE Trans. Netw. and Serv. Manag., vol. 1, no. 1, pp.11-20, 2004.

[54] Q. Zheng and K. G. Shin, “Fault-tolerant real-time communication in distributed computing systems,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 5, pp. 470-480, 1988.

[55] M. Rahman, I. Aib, and R. Boutaba, “Survivable virtual network embedding,” in Proc. 2010 IFIP Netw., pp. 40-52.

[56] W. L. Yeow, C. Westphal, and U. C. Kozat, “Designing and embedding reliable virtual infrastructures,” in Proc. ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures (VISA’10), New Delhi, India, 2010.

[57] A. Xiao, Y. Wang, L. Meng, X. Qiu and W. Li,“Topology-aware virtual network embedding to survive multiple node failures,” in Proc. Global Communications Conference (GLOBECOM),2014 IEEE, pp. 1823-1829, 2014.

[58] H. Yu, V. Anand, and Ch. Qiao, “Cost efficient design of survivable virtual infrastructure to recover from facility node failures,” in Proc. IEEE ICC 2011, pp. 1-6, 2011.

[59] C. Qiao, B. Guo, S. Huang, J. Wang, T. Wang, and W. Gu, “A novel two-step approach to surviving facility failures,” in OFC/NFOEC 2011, pp. 1-3,Mar. 2011.

[60] Q. Hu, Y. Wang, and X. Cao, “Location-constrained survivable network virtualiztion,” in Proc. 35thSARNOFF 2012, pp. 1-5, May, 2012.

[61] H.Jiang, L. Gong, Z. Zhu, “Efficient joint approaches for location-constrained survivable virtual network embedding,” in Proc. Global Communications Conference (GLOBECOM),2014 IEEE, pp. 1810-1815, 2014.

[62] M. Khan, N. Shahriar, R. Ahmed, and R. Boutaba,“Multi-path link embedding for survivability in virtual networks,” IEEE Trans. Netw. and Serv.Manag., vol. 13, no. 2, pp. 253-266, 2016.

[63] M. Khan, N. Shahriar, R. Ahmed, and R. Boutaba,“SiMPLE: survivability in multi-path link embedding,” in Proc. IEEE 11thInt. Conf. Netw. Service Manag., Barcelona, Spain, 2015, pp. 210-218.

[64] P. Gil, N. Jain, and N. Nagappan, “Undersatnding network failures in data centers: Measurement,analysis, and implications,” ACM SIGCOMM Comput. Commun. Rev., vol. 41, no. 4, pp. 350-361, Aug. 2011.

[65] A. Markopoulou, G. Iannaccone, S. Bhattachryya, C. Chuah, and C. Diot, “Characterization of failures in an IP backbone,” in Proc. IEEE INFOCOM, vol. 4, Hong Kong, Mar. 2004, pp.2307-2317.

[66] A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual network topology routing in optical WDM networks,” IEEE J. Sel.Areas Commun., vol. 25, no. 6, pp. 63069, Aug.2007.

[67] M. Bienkowski, A. Feldmann, D. Jurca, W.Kellerer, G. Schあarth, S. Schmid, and J. Widmer,“Competitive analysis for service migration in vnets,” in Proc. ACM SIGCOMM workshop on virtualized infrastructure systems and architecture,ser. VISA’10. New York, NY, USA: ACM, 2010, pp.17-24.

[68] G. Chochlidakis, V. Friderikos, “Mobility aware virtual network embedding,” in 2015 IEEE Conference on Communications (ICC), pp. 5846-5852.

[69] G. Chochlidakis, V. Friderikos, “Mobility aware virtual network embedding,” IEEE Transactions on Cloud Computing, vol. pp, no. 99, pp. 1-1,Jul. 2016.

[70] I. Houidi, W. Louati, and D. Zeghlache, “A distributed virtual network mapping algorithm,” in Proc. IEEE International Conference on Communications(ICC’08), Beijing, China, 2008.

[71] I. Houidi, W. Louati, W. B. Ameur, and D. Zeghlache, “Virtual network provisioning across multiple domains,” Computer Networks, vol. 55,no. 4, pp. 1011-1023, 2011, special Issue on Architectures and Protocols for the Future Internet.

[72] M. Chowdhury, F. Sauel, and R. Bouta, “Polyvine:policy-based virtual network embedding across multiple domains,” in Proc. of the second ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures, ser. VISA’10, New York, NY, USA,: ACM, 2010, pp. 49-56.

[73] I. Houidi, W. Louati, D. Zeghlache et al., “Adaptive virtual network provisioning,” in Proc. ACM SIGOMM Workshop on Virtualized Infrastructures Systems and Architectures (VISA’10), New Delhi, India, 2010.

[74] D. Dietrich, A.. Rizk, and P. Papadimitriou,“Multi-provider virtual network embedding with limited information disclosure,” IEEE Trans.Netw. and Serv. Manag., vol. 12, no. 2, pp. 188-201, May. 2015.

[75] F. Zaheer, J. Xiao, and R. Boutaba, “Multi-provider service negotiation and contracting in network virtualization,” in Proc. IEEE NOMS, Osaka,Japan, 2010, pp. 471-478.

[76] A. Leivadeas, C. Papagianni, and S. Papavassiliou, “Efficient resource mapping framework over networked clouds via iterated local searchbased request partitioning,” IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 6, pp. 1077-1086, Jun.2013.

[77] F. Esposito, D. Paola, and I. Matta, “A general distributed approach to slice embedding with guarantees,” in Proc. IFIP Netw., New York, NY,USA, May 2013, pp. 1-9.

[78] T. Mano, T. Inoue, D. Ikarashi, K. Hamada, K.Mizutani, and O. Akashi, “Efficient virtual network optimization across multiple domains without revealing private information, ” IEEE Trans. Netw. and Serv. Manag., vol. 13, no. 3, pp.477-488, Jun. 2016.

[79] O. Goldreich, Foundations of Crytography, Volune 2, Basic Applications. New York, NY, USA:Cambridge Univ. Press, 2004.

[80] T. Mano, K. Mizutani, and O. Akashi, “Secure resource provisioning across multiple domains,”in Proc. IFIP/IEEE IM, Ghent, Belgium, 2013, pp.1129-1134.

[81] J. Brickell and V. Shmatikov, “Privacy-preserving graph algorithms in semi-honest model,” in Proc. ASIACRYPT, Chennai, India, 2005, pp. 236-252.

[82] M. Fukeshima, K. Sugiyama, T. Hasegawa, and A. Nakao, “Minimum disclosure routing for network virtualization and its experimental evaluation,” IEEE/ACM Trans. Netw., vol. 21, no. 6, pp.1839-1851, Dec. 2013.

[83] S. Machiraju and R. H. Katz, “Verifying global invariants in multip-rovider distributed systems,”in Proc. ACM HotNets, San Diego, CA, USA,2004, pp. 149-154.

[84] M. Burkhart, M. Strasser, D. Many, and X. Dimitropoulos, “SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics,” in Proc. USENIX Security, Washington,DC, USA, 2010, p. 15.

[85] M. Feng, J. Liao, J. Wang, S. Qing, and Q. Qi,“Topology-aware virtual network embedding based on multiple characteristics,” in 2014 IEEE Conference on Communications (ICC), pp. 2956-2962.

[86] J. Betero, X. Hesselbach, A. Fischer, and H. Meer,“Optimal mapping of virtual networks with hidden hops,” Telecommunication Systems, vol. 52,no. 3, pp. 1-10, 2013.

[87] A. Leivadeas, C. Papagianni, and S. Papavassiliou, “Soci-aware virtual network embedding,”IEEE Network, vol. 26, no. 5, pp. 35-43, 2012.

[88] H. Di, H. Yu, V. Anand, L. Li, G. Sun, and B. Dong,“Efficient online virtual network embedding using resource evaluation,” Journal of Network and Systems Management, vol. 20, pp. 468-488,2012.

[89] L. Gong, Y. Wen , Z. Zhu and T. Lee, “Revenue-Driven Virtual Network Embedding Based on Global Resource Information,” in Global Communications Conference (GLOBECOM),2013 IEEE, Dec. 2013, pp. 2294-2299.

[90] F. Hsu and C. Gan,“Resource Allocation with Spectrum Aggregation for Wireless Virtual Network Embedding,” in Vehicular Technology Conference (VTC Fall), 2015 IEEE 82nd, Sept.2015, pp. 1-5.

[91] T. Mano, T. Inoue, et al., “Reducing dense virtual networks for fast embedding,” in Computer Communications, IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on,Apr. 2016.

[92] Z. Wang, J. Wu, et al., “Secure virtual network embedding to mitigate the risk of covert channel attacks,” in Computer Communications Workshops (INFOCOM WKSHPS), 2016 IEEE Conference on, Apr. 2016.

[93] P. Han, L. Guo, et al., “A new virtual network embedding framework based on QoS satisfaction and network reconfiguration for fiber-wireless access network,” in Communications (ICC), 2016 IEEE International Conference on, May. 2016.

[94] G. Chochlidakis and V. Friderikos, et al.,“Low Latency Virtual Network Embedding for Mobile Networks,” in Communications (ICC), 2016 IEEE International Conference on, May. 2016.

[95] Z. Wang, J. Wu, G. Cheng and Y. Jiang, “Mutine:A Mutable Virtual Network Embedding with Game-Theoretic Stochastic Routing,” in Global Communications Conference (GLOBECOM),2015 IEEE, Dec. 2015.

[96] Z. Zhang, S. Su, J. Zhang, K. Shuang and P. Xu,“Energy Aware Virtual Network Embedding with Dynamic Demands,” in Communications (ICC),2015 IEEE International Conference on, June 2015, pp. 5386 - 5391.

[97] Y. Yuan, C. Wang, C. Wang, et al., “A Novel Algorithm for Embedding Dynamic Virtual Network Request,” in Information Science and Control Engineering (ICISCE), 2015 2nd International Conference on, Apr. 2015, pp. 28 - 32.

[98] S. Shakya, N. Pradhan, et al., “Virtual Network Embedding and Recon figuration in Elastic Optical Networks,” in Global Communications Conference (GLOBECOM), 2014 IEEE, Dec. 2014, pp.2160 - 2165.

[99] C. Marquezan, L. Granville, G. Nunzi, and M.Brunner, “Distributed autonomic resource management for network virtualization,” in Network Operations and Management Symposium(NOMS), 2010 IEEE, pp. 463-470.

[100] Y. Yuan, C. Wang, et al., “Fault Tolerant Virtual Network Embedding Algorithm Based on Redundant Backup Resource,” in Instrumentation,Measurement, Computer, Communication and Control (IMCCC), 2013 Third International Conference on, Sept. 2013, pp. 354 - 357.

[101] O. Soualah, I. Fajjari, N. Aitsaadi and A. Mellouk,“PR-VNE: Preventive Reliable Virtual Network Embedding Algorithm in Cloud’s Network,” in Global Communications Conference (GLOBECOM), 2013 IEEE, Dec. 2013, pp. 1303 - 1309.

[102] R. Oliveira, D. Marcon, et al., “No More Backups:Toward Efficient Embedding of Survivable Virtual Networks,” in Communications (ICC), 2013 IEEE International Conference on, Jun. 2013, pp.246-250.

[103] J. Duan, Z. Guo and Y. Yang, “Cost Eきcient and Performance Guaranteed Virtual Network Embedding in Multicast Fat-Tree DCNs,” in Computer Communications (INFOCOM), 2015 IEEE Conference on, May. 2015, pp. 136 - 144.

[104] K. Guo, Y. Wang, X. Qiu, W. Li, A. Xiao, “Particle Swarm Optimization Based Multi-Domain Virtual Network Embedding,” in Integrated Network Management (IM), 2015 IFIP/IEEE International Symposium on, May. 2015, pp. 798 - 801.

[105] M. Beck, A. Fischer, H Meer et al., “A Distributed,Parallel, and Generic Virtual Network Embedding Framework,” in 2013 IEEE International Conference on Communications (ICC), Jun.2013, pp. 3471 - 3475.

[106] D. Chen, X. Qiu, Z. Qu, S. Zhang, and W. Li, “Algorithms for virtual nodes reconfiguration on network virtualization,” in Advanced Intelligence and Awareness Internet (AIAI 2011), 2011 International Conference on, Oct. 2011, pp. 333-337.

[107] N. Butt, N. Chowdhury, and R. Boutaba, “Topology-awareness and reoptimization mechanism for virtual network embedding,” in Networking,2010, pp. 27-39.

[108] D. Medhi, “A uni fied approach to network survivability for teletraきc networks: Models,algorithms and analysis,” IEEE Trans. Commun., vol.42, no. 234, pp. 534-548, Feb./Mar./Apr. 1994.

[109] S. Agarwal et al., “Volley: Automated data placement foe GEO-distributed cloud services,”in Proc. NSDI, San Jose, CA, USA, 2010, p.2.

[110] Q. Zhang, M. Zhani, M. Jabri, and R. Boutaba,“Venice: Reliable virtual data center embedding in clouds,” in Proc. IEEE INFOCOM, Toronto, ON,Canada, Apr. 2014, pp. 289-297.

[111] J. Xu, J. Tang, K. Kwait, W. Zhang, and G. Xue,“Survivable virtual infrastructure mapping in virtualized data centers,” in Proc. IEEE 5thInt.Conf. Cloud Comput., Honolulu, HI, USA, 2012,pp. 196-203.

[112] W. Fisher, M. Suchara, and J. Rexford, “Greening backbone networks: reducing energy consumption by shutting oあ cables in bundled links,” in Proc. 2010 ACM SIGCOMM workshop on Green networking, pp. 29-34.

[113] A. Bianzino, C. Chaudet, D.Rossi, and J. Rougier,“A survey of green networking research,” IEEE Communications Surveys&Tutorials, vol. 14, no.1, Feb. 2012.

[114] C. Yang, K. Wang, H. Cheng, C. Kuo, and W. Chu,“Green power management with dynamic resource allocation for cloud virtual machines,” in Proc. Of the 2011 IEEE International Conference on High Performance Computing and Communications, Sep. 2011, pp. 726-733.

[115] J. Chabarek, J. Sommers, P. Barford, C. Estan,D. Tsiang, and S. Wright, “Power awareness in network design and routing,” in Proc. 2008 IEEE INFOCOM.

[116] A. Qureshi, R. Weber, H. Balakrishman, J. Guttag, and B. Maggs, “Cutting the electric bill for Internet-scale systems,” in Proc. ACM SIGCOMM Conf. Data Commun., 2009, pp. 123-134.

[117] L. Rao, X. Liu, and W. Liu, “Minimizing electricity cost: Optimization of distributed Internet data centers in a multi-electricity-market environment,” in Proc. IEEE INFOCOM, 2010, pp. 1-9.

[118] L. Barroso and U. Holzle, “Thee case for energy-proportional computing,” Computer, vol. 40,no. 12, pp. 33-37, Dec. 2007.

[119] K. Park and C. Kim, “A framework for virtual network embedding in wireless networks,” in Proc.Of the 4thInternational Conference on Future Internet Technologies, New York, NY, USA,: ACM,2009, pp. 5-7.

[120] ETSI, “Mobile-edge computing,” European Telecommunications Standard Institute (ETSI), Technical White Paper, Sep. 2014.

[121] P. Lv, X. Wang, and M. Xu, “Virtual across network embedding in wireless mesh networks,”Ad Hoc networks, 2012.

[122] P. Lv, Z. Cai, J. Xu, and M. Xu, “Multicast service-oriented virtual network embedding in wireless mesh networks,” Communications Letters, IEEE, vol. 16, no. 3, pp. 375-377, Mar., 2012.[123] G. Bhanage, I. Seskar, Y. Zhang, and D. Raychaudhuri, “Evaluation of openvz based wireless testbed virtualization,” Rutgers University, Piscataway, NJ, USA, Tech. Rep. WINLAB-TR-331,2008.

[124] S. Singhal, G. Hadjichristofi, I. Seskar, and D.Raychaudhuri, “Evaluation of UML based wireless network virtualization,” in Proc. NGI Netw.,Krakow, Poland, Apr. 2008, 223-230.

[125] G. Smith, A. Chaturvedi, A. Mishara, and S. Banerjee, “Wireless virtualization on commodity 802.11 hardware,” in Proc. 2ndACM Int. Workshop Wireless Netw. Testbeds, Exp. Eval. Characterization, Montreal, QC, Canada, Sep. 2007, pp.75-82.

[126] S. Perez, J. Cabero, and E. Miguel, “Virtualization of the wireless medium: A simulation-based study,” in Proc. IEEE VTC Spring, Barcelona, Apr.2009, pp. 1-5.

[127] G. Bhanage, D. Vete, I. Sesekar, and D. Raychaushuri, “Splitap: Leveraging wireless network virtualization for flexible sharing of WLANs,”in Proc. IEEE GLOBECOM, Miami, FL, USA, Dec.2010, pp. 1-6.

[128] R. Mahindra, G. Bhanage, G. Hadjichristofi, I.Seskar, D. Raychaudhuri, and Y. Zhang, “Space versus time separation for wireless virtualization on an indoor grid,” in Next Generation Internet Networks, 2008. NGI 2008, Apr., 2008, pp. 215-222.

[129] A. Jayasumana, Q. Han, and T. Illangasekare,“Virtual sensor networks - a resource efficient approach for concurrent applications,” in Proc.Of the International Conference on Information Technology, Washington, DC, USA: IEEE Computer Society, 2007, pp. 111-115.

[130] K. Zhang et al., “Research and standards: Advanced cloud and virtuaslization techniques for 5G networks (guest editorial),” IEEE Commun.Mag., vol. 53, no. 6, pp. 16-17, Jun. 2015.

[131] C. Liang, and F. Yu, “Wireless network virtualization: a survey, some research issues and challenges,” IEEE Commun. Sur. & Tuto., vol. 17,no.1, pp. 358-380, 2015.

[132] S. Abdelwahab, B. Hamdaoui， M. Guizaniet al., “Efficient Virtual Network Embedding with Backtrack Avoidance for Dynamic Wireless Networks,” IEEE Trans. on Wire. Comm., vol. 15, no.4, pp. 2669-2683, Apr. 2016.

[133] R. Kokku, R. Mahindra, H. Zhang, and S. Rangarajan, “Nvs: A substrate for virtualizing wireless resources in cellular networks,” IEEE/ACM Trans.Netw., vol. 20, no. 5, pp. 1333-1346, Oct. 2012.

[134] Z. Zhang, S. Su, J. Zhang, K. Shuang and P. Xu,“Energy Aware Virtual Network Embedding with Dynamic Demands: online and offline,” Computer Networks, vol. 93, no. 3, pp. 448-458, Dec.2015.

[135] X. Liu, Z. Zhang, X. Li and S. Su, “Optimal virtual network embedding based artificial bee colony,” J. Wireless Com. Network, Dec. 2016.

[136] Haotong Cao, Longxiang Yang, et al., “An exact VNE algorithm on optimization theory,” in Proc.2016 IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia), pp. 1-4, 2016.

[137] N. Shahriar, R. Ahmed, S. Chowdhury, et al.,“Generalized recovery from node failure in virtual network embedding,” IEEE Trans. Netw. and Serv. Manag., vol. pp, no. 99, pp. 1-14, 2017.

[138] P. Zhang, H. Yao, Y. Liu, “Virtual network embedding based on the degree and clustering coeき-cient information,” IEEE Access, vol. 4, pp. 6572-8580, 2016.

[139] S. Jia, G. Jiang, P. He, J. Wu, “Eきcient algorithm for energy-aware virtual network embedding,”Tsinghua Science and Technology, vol. 21, no. 4,pp. 407-414, Aug. 2016.

[140] H. Cao, Y. Zhu, L. Yang and G. Zheng, “A Eきcient Mapping Algorithm with Novel Node- Ranking Approach for Embedding Virtual Network,” IEEE Access, vol. 5, pp. 22054-22066, 2017.

[141] H. Cao, Y. Zhu, G. Zheng and L. Yang, “A Novel Optimal Mapping Algorithm with Less Computational Complexity for Virtual Network Embedding,” IEEE Trans. Netw. and Serv. Manag., vol.pp, no. 99, pp. 1-16, 2017.

[142] H. Cao, L. Yang and H. Zhu, “Novel Node-Ranking Approach and Multiple Topology Attri-butes-Based Embedding Algorithm for Single-Domain Virtual Network Embedding,” IEEE IoT Journal,vol. pp, no. 99, pp. 1-13, 2017.