A uni

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMSmun.Syst.2013;26:1054–1073Published online27January2012in Wiley Online Library().DOI:10.1002/dac.1399A unified enhanced particle swarm optimization-based virtualnetwork embedding algorithmZhongbao Zhang1,Xiang Cheng1,Sen Su1,*,†,Yiwen Wang1,Kai Shuang1andYan Luo21State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,10Xi Tu Cheng Road,Beijing,China2Electrical and Computer Engineering,University of Massachusetts Lowell,One University Ave,Lowell,MA01854,USASUMMARYVirtual network(VN)embedding is a major challenge in network virtualization.In this paper,we aim to increase the acceptance ratio of VNs and the revenue of infrastructure providers by optimizing VN embed-ding costs.Wefirst establish two models for VN embedding:an integer linear programming model for a substrate network that does not support path splitting and a mixed integer programming model when path splitting is supported.Then we propose a unified enhanced particle swarm optimization-based VN embed-ding algorithm,called VNE-UEPSO,to solve these two models irrespective of the support for path splitting. In VNE-UEPSO,the parameters and operations of the particles are well redefined according to the VN embedding context.To reduce the time complexity of the link mapping stage,we use shortest path algorithm for link mapping when path splitting is unsupported and propose greedy k-shortest paths algorithm for the other case.Furthermore,a large to large and small to small preferred node mapping strategy is proposed to achieve better convergence and load balance of the substrate network.The simulation results show that our algorithm significantly outperforms previous approaches in terms of the VN acceptance ratio and long-term average revenue.Copyright©2012John Wiley&Sons,Ltd.Received24June2011;Revised12October2011;Accepted27November2011KEY WORDS:network virtualization;virtual network embedding;integer linear programming;mixed integer programming;metaheuristic;particle swarm optimization1.INTRODUCTIONThe Internet has only been improved incrementally since its inception.In the past,fundamental changes in network architectures have faced strong resistance from realistic experimentation and deployment[1–4].In recent years,network virtualization has emerged to serve as the foundation of the future Internet that allows multiple heterogeneous virtual networks(VNs)to coexist on a shared network substrate,providing adequateflexibility for network innovations.In the network virtualization environment,infrastructure providers(InPs),and service providers (SPs)play two decoupled roles:InPs manage the physical infrastructure,whereas SPs create VNs and offer end-to-end services[1,3,5].Embedding VN requests of the SPs,with both node and link constraints,into the substrate network(also known as VN embedding)is non-deterministic polynomial-time hard(NP-hard).Even if all the virtual nodes are mapped,it is still NP-hard to embed virtual links without violating the bandwidth constraints into the substrate paths[6].Thus,*Correspondence to:Sen Su,State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,10Xi Tu Cheng Road,Beijing,China.†E-mail:susen@UNIFIED EPSO-BASED VNE ALGORITHM1055 to reduce the hardness of the VN embedding problem and enable efficient heuristics,early studies restrict the VN embedding problem space as follows:Assume that the VN requests are known in advance(i.e.,an offline version)[7–9].Ignore one or more types of resource constraints of the VN request(e.g.,CPU,bandwidth,or location)[6–11].Perform no admission control when the resource of the substrate network is insufficient [7,8,10].Focus only on the backbone-star topology[8].Considering all these aforementioned issues,when path splitting is supported by the substrate network,the authors in[12]formulate a mixed integer programming(MIP)for the VN embedding problem and propose several MIP-based online VN embedding algorithms to coordinate node and link mapping stages.However,when path splitting is not supported by the substrate network,their MIP formulation would no longer be appropriate;consequently,the corresponding algorithm they proposed suffers from poor performance.Besides,the linear programming relaxation and round-ing techniques adopted by their algorithms would result in time-consuming and infeasible VN embedding solution.Even if a feasible solution can be obtained,it may still be far from being optimal[13].To address this issue,wefirst note that different VN embedding solutions could result in different total resource costs to the substrate network and reducing such cost may help increase the possi-bility of accepting more future VN requests;thus,we present an integer linear programming(ILP) formulation and a MIP formulation for the VN embedding problem to minimize such cost when path splitting is unsupported and supported by the substrate network,respectively.Solving ILP and MIP is a well-known NP-hard problem[13].Traditional exact algorithms such as branch and bound and cutting plane are guaranteed tofind an optimal solution.These algorithms,however,incur exponential running time,and so only instances of a moderate size could be practically solved[14].So we turn our attention tofinding a feasible solution that is near optimal.The technique of metaheuristics has been shown useful in practice,including genetic algorithm[15],simulated annealing[16],evolutionary programming[17],and particle swarm optimization(PSO)[18].These are iterative search techniques inspired from biological and physical phenomena,which have been successfully applied to a wide range of optimization problems.In particular,PSO is a population-based stochastic global optimizer that can generate better optimal solution in lesser computing time with stable convergence[19]than other population-based methods.It is also easy to implement with a smaller number of adjustable parameters. We are motivated to leverage the benefits of PSO to conceive an efficient online VN embedding algorithm.More specifically,if we consider the position of each particle in PSO as a possible VN embedding solution,and then each particle can adjust its position to achieve better posi-tion according to the individual and global optimal information,finally the approximate optimal solution of VN embedding can be obtained through the evolution process of the particles.How-ever,before we employ PSO to solve our problem,there are still three imperative challenges that must be conqueredfirst:(i)Standard PSO only deals with continuous optimization prob-lem,so it is not directly applicable to the optimal VN embedding problem,which is a discrete optimization problem.(ii)Because the formulations of the VN embedding problem are differ-ent,our PSO-based VN embedding algorithm needs to be well designed to deal with the optimal VN embedding problem irrespective of whether path splitting is supported by the substrate net-work or not.Besides,previous work[6]uses k-shortest path(KSP)for the virtual link mapping when path splitting is unsupported by the substrate;otherwise,it uses multicommodityflow(MCF) algorithm instead;however,if we adopt the same virtual link mapping algorithms,our algorithm may result in very time consuming because of the iteration processes of PSO.(iii)The random-ness of PSO may result in slow convergence for solving our problem.In addition,it may also make the substrate network resources fragmented and hinder the substrate network from accepting larger VN requests.1056Z.ZHANG ET AL.Toward these ends,we present a unified enhanced PSO-based VN embedding algorithm,referred as VNE-UEPSO,to solve the optimal VN embedding problem.In VNE-UEPSO,we conquer the aforementioned challenges as follows:We redefine the parameters and operations of the particles (such as position,velocity and updating operations,etc.)according to our problem.Moreover,because the virtual link mapping algorithm is coupled with the feature of the sub-strate network supported,we only encode the position vector as the virtual node mapping solution and left the virtual link mapping solution to be determined in a position feasibility check procedure.Therefore,this procedure can adopt proper virtual link mapping algorithm according to the feature of the substrate network supported.To reduce the time complexity of the virtual link mapping stage while maintaining the efficiency,we apply the shortest path algorithm for the link mapping when path splitting is unsupported and propose a novel link mapping algorithm called greedy k-shortest paths (GKSP)for the other case.Furthermore,we propose a large to large and small to small (L2S2)preferred local selection strategy for position initialization and update of the particles to achieve better convergence and load balance of the substrate network.The simulation results show that the algorithm we proposed can significantly outperforms the existing approaches in terms of the long-term average revenue and VN request acceptance ratio while decreasing the substrate resource cost irrespective of whether path splitting is supported by the substrate network or not.The rest of this paper is organized as follows.In Section 2,we present the network model and the definition of VN embedding problem and its common objectives.The ILP and MIP models of the VN embedding problem is presented in Section 3.In Section 4,we describe the details of the VNE-UEPSO algorithm.Our VN embedding algorithm is evaluated in Section 5.An overview of the related work is discussed in Section 6.Section 7concludes this paper.WORK MODEL AND PROBLEM DESCRIPTIONIn this section,we will first model the substrate network of InPs and VN of SPs and then give the VN embedding problem description,followed by the definition of objectives.work modelWe denote the topology of the substrate network by a weighted undirected graph G s D .N s ,L s ,A n s ,A l s /,where N s is the set of the substrate nodes and L s is the set of the substrate links.The notations A n s and A l s denote the attributes of the substrate nodes and links,respectively.Theattributes of a node could be processing capacity,storage,and location.The attribute of a link could be the bandwidth and delay.In this paper,we consider the available CPU capacity and location con-straint (e.g.,particular geographic regions)for the node attribute and the available bandwidth for the link attribute.All loop-free paths of the substrate network are denoted by P s .Similarly,the topology of the VN could also be denoted by a weighted undirected graph G v D .N v ,L v ,R n v ,R l v /,where N v is the set of the virtual nodes,L v is the set of the virtuallinks,and R n v and R l v denote CPU requirements and location constraints on virtual nodes and band-width requirements on virtual links,respectively.Each VN request can be denoted by the quad VNR .i/.G v ,t a ,t d ,W /,where the variables t a and t d denote the time of the VN request arriving and the duration of the VN staying in the substrate network,respectively.When the i th VN request arrives,the substrate network should allocate resources to the VN that satisfy the constraints of the virtual nodes and links.If there are no enough substrate resources,the VN request should be rejected or postponed.The allocated substrate resources are released when the VN departs.Similar to the work in [12],here W is a non-negative value expressing how far a virtual node n v 2N v can be placed from the location specified by Loc.n v /.UNIFIED EPSO-BASED VNE ALGORITHM1057 Figure1(b)presents a substrate network,where the numbers in rectangles are the available CPU resources at the nodes and the numbers over the links represent available bandwidths.Figure1(a) and1(c)presents two VN requests with node and link constraints.2.2.Virtual network embedding problem descriptionThe VN embedding problem is defined by a mapping M W G v.N v,L v/!G s.N0s,P0s/from G v to a subset of G s,where N0s N s and P0s P s.The mapping can be decomposed into two mapping steps:Node mapping places the virtual nodes to different substrate nodes that satisfy the node resource constraints.As shown in Figure1(a)and1(b),the node mapping solution of the VN request1is{a!B,b!C,c!F,d!E}.Link mapping assigns the virtual links to loop-free paths on the substrate that satisfy the link resource requirements.The link mapping solution is{.a,b/!.B,C/,.a,c/!.B,F/, .b,d/!.C,E/,.c,d/!.F,E/}in Figure1(a)and1(b).After the node and link mapping stage of the VN request1,the residual capacities of the sub-strate nodes and links are shown in Figure1(d).Figure1(c)and1(d)shows another VN embedding solution for VN request2.Note that the virtual nodes of different VN requests can be mapped onto the same substrate node but the virtual nodes in the same VN request cannot share the same substrate node.2.3.ObjectivesLong-term average revenue.From the InPs’point of view,an efficient and effective online VN embedding algorithm would maximize the revenue of InPs and accept more VN requests in the long run.Similar to the previous work in[6,7,12],wefirst give the revenue definition of accepting a VN request at time t by the following equation:R.G v,t/D X n v2N v CP U.n v/C X l v2L v BW.l v/,(1)where CP U.n v/and BW.L v/are the CPU and bandwidth requirements for the virtual node n v and link l v,respectively.Then like the previous work in[6],the long-term average revenue is given by the following:lim(2)T!1P T t D0R.G v,t/T.1058Z.ZHANG ET AL.VN request acceptance ratio.It can be defined by the following equation:lim T !1P TtD 0VNR s P T t D 0VNR ,(3)where VNR s denotes the VN request successfully accepted by the substrate network.Long-term revenue to cost (R/C)ratio.We first define the cost of accepting a VN request at time t as the sum of the total substrate resources allocated to that VN:C.G v ,t/D X n v 2N v CP U.n v /C X l v 2L v X l s 2L sBW.f l v l s,l v /,(4)where f l v l s2¹0,1ºand f l v l s =1if substrate link l s allocated bandwidth resource to virtual link l v ,otherwise f l v l s D 0.BW.f l v l s ,l v /is the amount of bandwidth l s allocated to l v .We use a modi-fied version of Equation (4)as the objective function of our ILP and MIP models,which will bepresented in the next section.Then we introduce the long-term R/C ratio to quantify the efficiency of substrate resource use,which can be defined as follows:lim T !1P Tt D 0R.G v ,t/P t D 0C.G v ,t/.(5)In this paper,we consider the long-term average revenue as the main objective of the online VN embedding algorithm,in addition to the VN request acceptance ratio,and the long-term R/C ratio.If the long-term average revenues of the VN embedding solutions are nearly the same,higher VN request acceptance ratio and long-term R/C ratio are preferred.3.ILP AND MIP FORMULATIONS FOR OPTIMAL VN EMBEDDINGIn this section,we first give the motivation behind our ILP and MIP formulations for the VN embedding problem and then provide the details of this formulation.3.1.MotivationFor one VN request,different VN embedding solutions may have different substrate resource costs.Let us reconsider the examples of VN embedding presented in Section 2(Figure 1).Assuming that the substrate node B and F can satisfy all the requirements of the virtual node b and c in the VN request 2,we can construct another VN embedding solution for VN request 2,which the node mapping is ¹a !A ,b !B ,c !F ºand the link mapping is {.a ,b/!.A ,B/,.a ,c/!.A ,F /}.Obviously,this VN embedding solution can consume less substrate network resources than the solu-tion proposed in Figure 1(d)and increase the possibility to accept more future VN requests.This observation motivates us to establish an optimal model for the VN embedding problem to minimize this cost.3.2.NOTATIONWe first summarize the notations that will be used throughout this paper in Table I.3.3.Resource cost modelingFor a VN request,because the CPU cost of different VN embedding solutions is a constant value,we only consider the bandwidth resource cost in Formula (6).X .u ,v/2L v X .i ,j /2L sf uv ij BW.l uv /.(6)UNIFIED EPSO-BASED VNE ALGORITHM 1059Table I.Notations.Notation Description i ,jSubstrate nodes u ,v Virtual nodes x u iA binary variable such that x u i D 1if virtual node u is mapped to the substrate node i and 0otherwise f uv ij A binary variable,where it is 1if virtuallink l uv is routed on physical link l ij and 0otherwiseCP U.u/The CPU value of nodes u .BW.l uv /The BW value of link l uv .3.4.Capacity constraints modelingThere are two kinds of capacity constraints:node constraints and link constraints.For the node con-straints,the CPU capacity of the substrate node i must satisfy the CPU request of the virtual node u ,and its location must be within the range of the virtual node specified by W ,which indicates how far the virtual node can be placed from the location specified by Loc.u/.The distance function Dis denotes the Euclidean distance of two nodes.For example,suppose node n 1is located at .x 1,y 1/and node n 2at .x 2,y 2/,then the value of Dis.Loc.i/,Loc.u//is equal to p .x 1 x 2/2C .y 1 y 2/2.For the virtual link constraints,the substrate link .i ,j /must meet the bandwidth requirement for the virtual link .u ,v/.Constraints (7)and (8)specify node constraints and link constraints,respectively.8u 2N v ,8i 2N s ,²x u iCP U.u/6CP U.i/x u i Dis.Loc.i/,Loc.u//6W(7)8.i ,j /2L s ,8.u ,v/2L v ,f uv ij BW.l uv /6BW.l ij /.(8)3.5.Connectivity constraints modelingConstraint (9)is flow conservation constraint for routing one unit of traffic from corresponding sub-strate node of u to corresponding substrate node of v .It requires that equal amounts of flow due to virtual link .u ,v/enter and leave each substrate node that does not correspond to the source u or destination v .Furthermore,the node u has an exogenous input of 1unit of traffic that has to find its way to the substrate corresponding to node v .8i 2N s ,8.u ,v/2L v ,X .i ,j /2L s f uv ij X .j ,i/2L s f uv j i D 8<:1if.x u i D 1/ 1if.x v i D 1/0otherwise.(9)3.6.Variable constraints modeling Constraint (10)ensures that a virtual node must correlate with just one substrate node,and constraint (11)denotes the domain constraints for the variables f uv ij and x u i .If path splitting is not supported,f uv ij is a binary variable in {0,1}(the model is an ILP),otherwise a continuous variable in [0,1](the model is a MIP).8i 2N s ,X u 2N vx u i 61,8u 2N v ,X i 2N s x u i D 1(10)1060Z.ZHANG ET AL.8i2N s,8u2N v,x u i2¹0,1º,8.i,j/2L s,8.u,v/2L v,f uvij2²Œ0,1 if path splitting¹0,1ºotherwise.(11) 3.7.Problem formulationThe goal of VN embedding problem in this paper is to minimize the resource cost for embedding each VN request;thus,we have the following optimization problem:M in X.u,v/2L v X.i,j/2L s f uv ij BW.l uv/(12)subject to Equations(7)–(11),where the model is an ILP if path splitting is not supported,otherwise a MIP.In the next section,we will propose our VNE-UEPSO algorithm to solve this optimal VN embedding problem.4.PROPOSED VNE-UEPSO ALGORITHMIn this section,wefirst give a brief introduction of PSO in Section4.1.When employing PSO to solve our optimal VN embedding problem,there are still some challenges as pointed out in Section1.Sections4.2–4.4describe the details of these challenges and how they are addressed respectively.In Section4.5,we present the algorithmic details of VNE-UEPSO.4.1.Basic Concepts of PSOParticle swarm optimization is an emerging population-based optimization method,first introduced by Eberhart and Kennedy in1995,that is inspired by theflocking behavior of many species, such birds or school offish,in their food hunting.It is a kind of random search algorithm that simulates nature evolutionary process and performs good characteristic in solving some difficult optimization problems.In PSO,a swarm of particles are represented as potential solutions,flying through the problem space by following the current optimum particles,and each particle i is associated with two vectors, that is,the position vector X i DŒx1i,x2i,:::,x D i and the velocity vector V i DŒv1i,v2i,:::,v D i , where D denotes the dimensions of the solution space.The position and velocity of each particle can be initialized randomly within the corresponding ranges.During the evolutionary process,the velocity and position of particle i on dimension d are updated as follows:v d i D wv d i C c1r d1.pBest d i x d i/C c2r d2.gBest d x d i//,(13)x d i D x d i C v d i,(14)where w is the inertia weight,c1is the cognition weight and c2is the social weight,and r d1and r d2are two random values uniformly distributed in the range of[0,1]for the d th dimension.pBest i is the position with the bestfitness found so far for the i th particle,and gBest is the best position in the swarm.4.2.Discrete PSO for VN embeddingBecause the basic PSO can only handle continuous optimization problems,the parameters and operations of the particles in PSO must be redefined to make it suitable to solve the optimal VN embedding problem when considering its discrete characteristic.Although there are some variants of PSO for discrete optimization problems such as[20]and[21],they are problem specific andUNIFIED EPSO-BASED VNE ALGORITHM 1061also cannot directly be used to solve the optimal VN embedding problem.Therefore,we propose a discrete version of PSO for our problem.Label the virtual nodes and substrate nodes,respectively.Redefine the position and velocity parameters for discrete PSO as follows:Position (X ):Let us suppose that the position vector X i D Œx 1i ,x 2i ,:::,x D i of a particle denotes a possible VN embedding solution,where x d i is the order number of the substrate node selected in the candidate node list of the d th virtual node.Here,D denotes the total number of virtual nodes in the VN request.Note that the position vector only represents the node mapping solution and whether the link mapping can be satisfied is unknown.In other words,the feasibility of the position of the particle still need to be checked.Therefore,we introduce a feasibility check procedure for the position that will be presented in the next subsection.Velocity (V ):The velocity vector V i D Œv 1i ,v 2i ,:::,v D i of the particle is used to guide the current VN embedding solution to adjust to an even better solution,where v d i is a binary value,if v d i =0;the corresponding virtual node mapping decision in the current VN embedding solution should be adjusted by reselecting another substrate node from its candidate node list;otherwise,it will remain the current choice.The subtraction,addition,and multiplication operations of the particles are redefined as follows:Subtraction («):X i «X j indicates the differences of the two VN embedding solutions X i and X j .The result value of the corresponding dimension is 1if X i and X j have the same values at the same dimension;otherwise,it is 0.For example,.1,2,3,4,5/«.1,5,3,4,6/D .1,0,1,1,0/.Addition (˚):P i V i ˚P j V j indicates the result of the formula that keeps V i with probability P i and keeps V j with the probability P j in corresponding dimension,where P i C P j D 1.For example,0.1.1,0,0,1,1/˚0.9.1,0,1,0,1/D .1,0, , ,1/. denotes uncertain to be 0or 1.In this example,the first is equal to 0with probability of 0.1and 1with probability of 0.9.Multiplication (˝):x d i ˝v d i indicates the position update process of particles.The result of this operation is a new position that corresponds to a new VN embedding solution.The oper-ating rule is as follows:if the value of V i in d dimension equals to 1,then the value of X i in the corresponding dimension will be kept;otherwise,the value of X i in the corresponding dimension should be adjusted by reselecting another substrate node from its candidate list.Taking .1,2,4,3,8/˝.1,0,1,0,1/as an example,the second and fourth virtual node embedding solutions should be adjusted.As a result,on the basis of the aforementioned redefinition,the velocity and position of parti-cle i on dimension d are determined according to the velocity and position update equations given as follows:v d i D P 1v d i ˚P 2.pBest d i «x d i /˚P 3.gBest d «x d i //,(15)x d i D x d i ˝v d i ,(16)where P 1is inertia weight,and P 2and P 3can be seen as the cognition and social weights,respec-tively.Typically,P 1,P 2,and P 3are set to constant values and satisfy the inequality P 16P 26P 3(P 1C P 2C P 3D 1).4.3.Feasibility check procedure for the position of a particleBecause the position vector only represents the node mapping solution,it is just a possible VN embedding solution,whether the capacity and connectivity constraints presented in Equations (8)and (9)between these mapped virtual nodes can be satisfied still needs to be checked.Here,we introduce a procedure to check the feasibility of the current particle’s position,which is correspond-ing to the link mapping stage of the VN embedding process.If the position is feasible,we can have its linking mapping solution and calculate its fitness value by Formula (6);otherwise,its fitness value is set to infinity.To check the feasibility of the position of a particle is equivalent to finding a link mapping solu-tion for the current VN request.Previous work [6]uses KSP for link mapping when path splitting is unsupported by the substrate;otherwise,MCF algorithm is used.However,if adopting the same1062Z.ZHANG ET AL.link mapping algorithms,our algorithm may become more time consuming as a result of the iter-ation processes of PSO.Thus,we devise the alternative link mapping algorithms according to the following two conditions:(i)On one hand,without path splitting feature for the substrate network, instead of searching the KSPs for increasing values of k,wefind a path that has enough bandwidth to map the corresponding virtual link.Wefirst remove the links,whose bandwidth cannot satisfy the virtual link bandwidth constraints,and then use the shortest path tofind a link solution shown in Algorithm1.(ii)On the other hand,when path splitting is supported by the substrate network,we propose GKSP in the link mapping stage:wefind a corresponding shortest path and make use of it (the substrate network bandwidth resource will be changed),irrespective of whether it can satisfy the virtual link.This procedure repeats until wefind enough bandwidth as shown in Algorithm2. Our GKSP link mapping algorithm can be solved in O.M C N log N C k/time[22]in a substrate network with N nodes and M links while the time complexity of MCF algorithm is approximately O.M2C kN/[23].4.4.L2S2preferred local selection strategyFor the basic PSO,it is common to generate or update the position parameter of the parti-cles randomly within the corresponding ranges with equal probability during the evolutionary process.However,taking the context of VN embedding problem into account,if we overuseUNIFIED EPSO-BASED VNE ALGORITHM1063 the bottleneck resources of the substrate network,it may make the substrate network resource unbalanced and fragmented and hinder the substrate network from accepting larger VN network request.Besides,because the possible VN embedding solutions are encoded by the position param-eter without considering the link mapping stage,it may lead to dissatisfying the connectivity constraints in the linking mapping stage and thereby slow the convergence speed of our algo-rithm.Therefore,we develop a L2S2preferred local selection strategy for position initialization and update processes of the particles both achieve quick convergence and balance the substrate network loads.It may increase the possibility to satisfy the virtual node’s connectivity constraints in the link-ing mapping stage if we embed a virtual node to a substrate node with more bandwidth resource. This is because the more bandwidth a network node has,the more degree it might have.When tak-ing the node mapping stage into consideration,a node with more CPU resource is also preferred. Therefore,similar to the previous work[6],a network node resource measure that can reflect both the CPU resource and the bandwidth resource of a node at the same time is introduced,given by the following:NR.u/D CP U.u/X l2L.u/BW.l/,(17)where,on a substrate network,L.u/is the set of all the adjacent links of u,CP U.u/is the remain-ing CPU resource of u,and BW.l/is the unoccupied bandwidth resource of link l.For a virtual node u,CP U.u/and BW.l/are the capacity constraints of this node.The main principle of the L2S2preferred local selection strategy is that the virtual node with larger resource requirements has higher probability to be mapped to the substrate node with larger available resources.The benefits of such a strategy are twofold:it helps to satisfy the resource requirement of the current VN request and consequently accelerate the convergence of our algorithm;it can balance the substrate network loads in the long run.For a VN request containing n virtual nodes,the L2S2preferred local selection strategy for position initialization(position update)is presented in Algorithm3as follows:4.5.VNE-UEPSO algorithm descriptionThe VNE-UEPSO algorithm shown in Algorithm4takes the substrate network and a VN embedding request as input,Formula6asfitness function f.X/,and an approximate optimal VN embedding solution of our algorithms as output.Theflowchart of VNE-UEPSO algorithm is also presented in Figure2.。