816 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3,MARCH 2014 Virtual Network Embedding with Opportunistic Resource Sharing Sheng Zhang,Student Member,IEEE,Zhuzhong Qian,Member,IEEE, Jie Wu,Fellow,IEEE,Sanglu Lu,Member,IEEE,and Leah Epstein Abstract-Network virtualization has emerged as a promising approach to overcome the ossification of the Intemet.A major challenge in network virtualization is the so-called virtua/network embedding problem,which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network.A number of heuristics have been proposed to cope with the NP- hardness of this problem;however,all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network.In this paper,we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration,and we present an opportunistic resource sharing-based mapping framework,ORS,where substrate resources are opportunistically shared among multiple virtual networks.We formulate the time slot assignment as an optimization problem;then,we prove the decision version of the problem to be NP-hard in the strong sense.Observing the resemblance between our problem and the bin packing problem,we adopt the core idea of first-fit and propose two practical solutions:first-fit by collision probability(CFF)and first-fit by expectation of indicators'sum (EFF).Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes. Index Terms-Virtual network embedding,opportunistic resource sharing,NP-hard,3-partition,bin packing 1 INTRODUCTION HE Internet has been extremely successful in support- flexible [7].Second,physical resources can be used more L ing global commerce,communication,and defense [1], efficiently,and thus,high energy efficiency can be achieved. [2].However,the multiprovider nature of the Internet and The fundamental challenge that network virtualization end-to-end design of Internet Protocol (IP)are now faces is how to embed multiple virtual networks with creating hurdles for the further evolution of the Internet. resource constraints into a substrate network,so as to Network virtualization has been proposed recently as a efficiently utilize substrate resources.Known as the virtual promising approach to overcome the current ossification network embedding (VNE)problem,it is proven to be NP- of the Internet [2],[3],[4],and it has been investigated in complete by reducing the multiway separator problem to this several projects,including CABO [3],PlanetLab [5],and problem [8];therefore,a number of heuristics [9],[10],[11], VINI [6]. [12],[13l,[14,[15l,[16,[17],[18l,[19]have been proposed. In a network virtualization environment,an infrastructure Unfortunately,all of the prior proposals reserve fixed provider (InP)maintains a physical/substrate network (SN), resources throughout the entire lifetime of a virtual net- which is composed of substrate nodes and links;a service work,which wastes the precious substrate resources.First, provider (SP)leases physical resources (e.g.,CPU,band- SPs potentially target users all over the world,so it is width,and memory space)from InPs and creates custo- extremely difficult to predict the workload before they are mized virtual networks (VNs)to provide value-added ready to serve end users.As the resource requirement of a services (e.g.,video conferencing,VolP,content distribu- VN at a particular time is generally proportional to the tion)for end users.Network virtualization has some workload at that time,to cope with a peak workload on desirable properties.First,the separation of the control demand,service providers often overpurchase substrate and data tiers makes the network core programmable and resources,which may lead to a considerable waste of resources for a normal workload.Second,the resource .S.Zhang,Z.Qian,and S.Lu are with the State Key Laboratory for Novel requirements of many applications experience significant Softiare Technology,Nanjing University,Computer Science Building, changes over time [20].Given these two factors,provision- Xianlin Campus Mailbox 603,163 Xianlin Avenue,Qixia District, Nanjing,Jiangsu 210023,P.R.China. ing fixed resources for virtual networks throughout their E-mail:zhangsheng@dislab.nju.edu.cn,fqzz,sanglul@nju.edu.cn. lifetimes is clearly wasteful. .I.Wu is with the Department of Computer and Information Sciences, In this paper,we exploit this key observation and propose Temple UIniversity,Room 302,Wachman Hall,1805 North Broad Street, a Philadelphia,PA 19122.E-mail:jiewu@temple.edu. novel model that reflects the time-varying resource L.Epstein is with the Department of Mathematics,University of Haifa, requirement of a VN.More specifically,we model the Mount Carmel,Haifa 31905,Israel.E-mail:lea@math.haifa.ac.il. resource requirement of a VN as the combination of a basic Manuscript received 26 Sept.2012;revised 15 Jan.2013;accepted 14 Feb. subrequirement,which exists throughout the lifetime of the 2013;published online 27 Feb.2013. VN,and a variable subrequirement,which occurs with a Recommended for acceptance by X.Tang. For information on obtaining reprints of this article,please send e-mail to: probability.Based on this model,this paper designs an tpds@computer.org,and reference IEEECS Log Number TPDS-2012-09-0992. opportunistic resource sharing-based embedding framework, Digital Object Identifier no.10.1109/TPDS.2013.64. ORS [21],which in general consists of two components,i.e., 1045-9219/14/S31.00C2014IEEE Published by the IEEE Computer Society
Virtual Network Embedding with Opportunistic Resource Sharing Sheng Zhang, Student Member, IEEE, Zhuzhong Qian, Member, IEEE, Jie Wu, Fellow, IEEE, Sanglu Lu, Member, IEEE, and Leah Epstein Abstract—Network virtualization has emerged as a promising approach to overcome the ossification of the Internet. A major challenge in network virtualization is the so-called virtual network embedding problem, which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network. A number of heuristics have been proposed to cope with the NPhardness of this problem; however, all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network. In this paper, we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration, and we present an opportunistic resource sharing-based mapping framework, ORS, where substrate resources are opportunistically shared among multiple virtual networks. We formulate the time slot assignment as an optimization problem; then, we prove the decision version of the problem to be NP-hard in the strong sense. Observing the resemblance between our problem and the bin packing problem, we adopt the core idea of first-fit and propose two practical solutions: first-fit by collision probability (CFF) and first-fit by expectation of indicators’ sum (EFF). Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes. Index Terms—Virtual network embedding, opportunistic resource sharing, NP-hard, 3-partition, bin packing Ç 1 INTRODUCTION THE Internet has been extremely successful in supporting global commerce, communication, and defense [1], [2]. However, the multiprovider nature of the Internet and end-to-end design of Internet Protocol (IP) are now creating hurdles for the further evolution of the Internet. Network virtualization has been proposed recently as a promising approach to overcome the current ossification of the Internet [2], [3], [4], and it has been investigated in several projects, including CABO [3], PlanetLab [5], and VINI [6]. In a network virtualization environment, an infrastructure provider (InP) maintains a physical/substrate network (SN), which is composed of substrate nodes and links; a service provider (SP) leases physical resources (e.g., CPU, bandwidth, and memory space) from InPs and creates customized virtual networks (VNs) to provide value-added services (e.g., video conferencing, VoIP, content distribution) for end users. Network virtualization has some desirable properties. First, the separation of the control and data tiers makes the network core programmable and flexible [7]. Second, physical resources can be used more efficiently, and thus, high energy efficiency can be achieved. The fundamental challenge that network virtualization faces is how to embed multiple virtual networks with resource constraints into a substrate network, so as to efficiently utilize substrate resources. Known as the virtual network embedding (VNE) problem, it is proven to be NPcomplete by reducing the multiway separator problem to this problem [8]; therefore, a number of heuristics [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19] have been proposed. Unfortunately, all of the prior proposals reserve fixed resources throughout the entire lifetime of a virtual network, which wastes the precious substrate resources. First, SPs potentially target users all over the world, so it is extremely difficult to predict the workload before they are ready to serve end users. As the resource requirement of a VN at a particular time is generally proportional to the workload at that time, to cope with a peak workload on demand, service providers often overpurchase substrate resources, which may lead to a considerable waste of resources for a normal workload. Second, the resource requirements of many applications experience significant changes over time [20]. Given these two factors, provisioning fixed resources for virtual networks throughout their lifetimes is clearly wasteful. In this paper, we exploit this key observation and propose a novel model that reflects the time-varying resource requirement of a VN. More specifically, we model the resource requirement of a VN as the combination of a basic subrequirement, which exists throughout the lifetime of the VN, and a variable subrequirement, which occurs with a probability. Based on this model, this paper designs an opportunistic resource sharing-based embedding framework, ORS [21], which in general consists of two components, i.e., 816 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 . S. Zhang, Z. Qian, and S. Lu are with the State Key Laboratory for Novel Software Technology, Nanjing University, Computer Science Building, Xianlin Campus Mailbox 603, 163 Xianlin Avenue, Qixia District, Nanjing, Jiangsu 210023, P.R. China. E-mail: zhangsheng@dislab.nju.edu.cn, {qzz, sanglu}@nju.edu.cn. . J. Wu is with the Department of Computer and Information Sciences, Temple University, Room 302, Wachman Hall, 1805 North Broad Street, Philadelphia, PA 19122. E-mail: jiewu@temple.edu. . L. Epstein is with the Department of Mathematics, University of Haifa, Mount Carmel, Haifa 31905, Israel. E-mail: lea@math.haifa.ac.il. Manuscript received 26 Sept. 2012; revised 15 Jan. 2013; accepted 14 Feb. 2013; published online 27 Feb. 2013. Recommended for acceptance by X. Tang. For information on obtaining reprints of this article, please send e-mail to: tpds@computer.org, and reference IEEECS Log Number TPDS-2012-09-0992. Digital Object Identifier no. 10.1109/TPDS.2013.64. 1045-9219/14/$31.00 2014 IEEE Published by the IEEE Computer Society
ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 817 the macrolevel node-to-node/link-to-path embedding,and 12 10 (8,4,0.3) (6,4,0.5) the microlevel time slot assignment.In the macrolevel (a (b) embedding,we adopt a traditional greedy strategy (e.g, (3,1.0.2) [13])to derive the mapping results of virtual nodes to (4,2,0.3) 3,1,0.1) 6 (3,3.0.3) substrate nodes and virtual links to substrate paths. d d c In the microlevel time slot assignment,we focus on the 14 7,7,0.2 (6,6,0.4) scenario in a single substrate link.The results can adapt (a)Traditional virtual (b)VN request with time-varying naturally to the other substrate links and nodes (details are network request resource requirement in Section 5).Suppose that the substrate link is based on time-division multiplexing,where time is partitioned into Fig.1.Each node or link is associated with a fixed resource requirement in the traditional VN request,while,in our model,the resource multiple frames of equal length,and each frame is further requirement of each node or link is expressed in a tuple . divided into time slots of equal length.The number of time slots in a frame depends on the physical bandwidth of this in Section 3.We then provide the overview of ORS in substrate link.Several virtual links are embedded in this Section 4,describe the details of ORS in Section 5,and substrate link;then,the problem becomes how to map the conduct performance evaluations in Section 6.Before bandwidth requirement of virtual links to the physical time concluding the paper in Section 8,we survey related work slots.For the basic bandwidth subrequirement from a in Section 7 virtual link,which exists throughout the lifetime of the respective VN,we have no choice but to allocate the corresponding required slots to it.For the variable 2 VIRTUAL NETWORK REQUEST WITH TIME- bandwidth subrequirement,we propose to opportunisti- VARYING RESOURCE REQUIREMENT cally share time slots among multiple virtual links to In this section,we first present the traditional virtual improve resource utilization.However,collisions accom- network request model,and then,we introduce a model pany sharing.To break the tradeoff between utilization and that captures the time-varying properties of virtual network collision,we use a collision probability threshold to resource requirements. represent the "volume"of a time slot and formulate the time slot assignment as an optimization problem.We prove 2.1 Traditional Virtual Network Request Model the decision-version problem to be NP-hard by reducing The main substrate resources that we consider in this paper the 3-partition problem [22]to it.An integer linear are CPU and bandwidth,which is the typical case in almost programming-based (ILP)optimal solution is also pro-all of the related literature so far.However,our framework vided.Due to the similarities between this problem and the can naturally adapt to the scenario where a node has bin packing problem [23],we then propose two practical multiple types of resources.We will give remarks on the first-fit-based solutions from different perspectives:first-fit adaptation in Section 5 when needed. by collision probability (CFF)and first-fit by expectation of For the purpose of unifying resource notations,we indicators'sum (EFF). assume that the substrate network is based on time-division Through extensive simulations,we demonstrate that,in multiplexing,where time is partitioned into multiple frames the long run,ORS accepts more virtual network requests of equal length,and each frame is further divided into equal and provides a more efficient utilization of substrate time slots.In doing so,both CPU and bandwidth require- resources than two state-of-the-art fixed-resource embed- ments can be expressed in time slots. ding schemes.The contributions are summarized as follows: A traditional virtual network request is denoted by a weighted undirected graph,G=(N,E),where N and 1.To the best of our knowledge,this is the first E"are the sets of virtual nodes and links,respectively.Each attempt that considers virtual network embedding virtual node n"E N"is associated with a CPU requirement in the context of opportunistic resource sharing at C(n")in time slots,and each virtual link e"=(n,n)EE the level of the entire network.To provide efficient is associated with a bandwidth requirement B(e")in time resource utilization,which is of great benefit to both slots.Fig.la shows an example,where the corresponding InPs and SPs,an embedding framework,ORS,is resource requirement of each node or link is written next to designed;its effectiveness is confirmed by extensive the respective node or link that represents it. simulations. 2. We propose a novel model that reflects the time-2.2 The Time-Varying Resource Requirement Model varying properties of the resource requirement of a SPs can hardly predict the number of end users of the VN,based on which we formulate the microlevel applications deployed in their virtual networks;to guaran- time slot assignment problem as an optimization tee the quality-of-service of a peak workload,SPs always problem.We first prove the decision version of overpurchase substrate resources.Besides,the resource this problem to be NP-hard in the strong sense,then requirements of many applications experience significant propose an ILP-based optimal solution and two changes over time.Therefore,provisioning fixed resources practical algorithms. for VNs throughout their lifetimes is clearly wasteful.To We conduct extensive theoretical analysis and avoid such wasteful situations,we need to model the time- simulation studies to verify the performance of ORS. varying resource requirement of a VN in the first place. We now continue by proposing the resource requirement By using profiling experimentations,one can potentially model in Section 2 before we introduce the VNE problem derive some complicated functions,for example,high-order
the macrolevel node-to-node/link-to-path embedding, and the microlevel time slot assignment. In the macrolevel embedding, we adopt a traditional greedy strategy (e.g., [13]) to derive the mapping results of virtual nodes to substrate nodes and virtual links to substrate paths. In the microlevel time slot assignment, we focus on the scenario in a single substrate link. The results can adapt naturally to the other substrate links and nodes (details are in Section 5). Suppose that the substrate link is based on time-division multiplexing, where time is partitioned into multiple frames of equal length, and each frame is further divided into time slots of equal length. The number of time slots in a frame depends on the physical bandwidth of this substrate link. Several virtual links are embedded in this substrate link; then, the problem becomes how to map the bandwidth requirement of virtual links to the physical time slots. For the basic bandwidth subrequirement from a virtual link, which exists throughout the lifetime of the respective VN, we have no choice but to allocate the corresponding required slots to it. For the variable bandwidth subrequirement, we propose to opportunistically share time slots among multiple virtual links to improve resource utilization. However, collisions accompany sharing. To break the tradeoff between utilization and collision, we use a collision probability threshold to represent the “volume” of a time slot and formulate the time slot assignment as an optimization problem. We prove the decision-version problem to be NP-hard by reducing the 3-partition problem [22] to it. An integer linear programming-based (ILP) optimal solution is also provided. Due to the similarities between this problem and the bin packing problem [23], we then propose two practical first-fit-based solutions from different perspectives: first-fit by collision probability (CFF) and first-fit by expectation of indicators’ sum (EFF). Through extensive simulations, we demonstrate that, in the long run, ORS accepts more virtual network requests and provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes. The contributions are summarized as follows: 1. To the best of our knowledge, this is the first attempt that considers virtual network embedding in the context of opportunistic resource sharing at the level of the entire network. To provide efficient resource utilization, which is of great benefit to both InPs and SPs, an embedding framework, ORS, is designed; its effectiveness is confirmed by extensive simulations. 2. We propose a novel model that reflects the timevarying properties of the resource requirement of a VN, based on which we formulate the microlevel time slot assignment problem as an optimization problem. We first prove the decision version of this problem to be NP-hard in the strong sense, then propose an ILP-based optimal solution and two practical algorithms. 3. We conduct extensive theoretical analysis and simulation studies to verify the performance of ORS. We now continue by proposing the resource requirement model in Section 2 before we introduce the VNE problem in Section 3. We then provide the overview of ORS in Section 4, describe the details of ORS in Section 5, and conduct performance evaluations in Section 6. Before concluding the paper in Section 8, we survey related work in Section 7. 2 VIRTUAL NETWORK REQUEST WITH TIMEVARYING RESOURCE REQUIREMENT In this section, we first present the traditional virtual network request model, and then, we introduce a model that captures the time-varying properties of virtual network resource requirements. 2.1 Traditional Virtual Network Request Model The main substrate resources that we consider in this paper are CPU and bandwidth, which is the typical case in almost all of the related literature so far. However, our framework can naturally adapt to the scenario where a node has multiple types of resources. We will give remarks on the adaptation in Section 5 when needed. For the purpose of unifying resource notations, we assume that the substrate network is based on time-division multiplexing, where time is partitioned into multiple frames of equal length, and each frame is further divided into equal time slots. In doing so, both CPU and bandwidth requirements can be expressed in time slots. A traditional virtual network request is denoted by a weighted undirected graph, Gv ¼ ðNv; EvÞ, where Nv and Ev are the sets of virtual nodes and links, respectively. Each virtual node nv 2 Nv is associated with a CPU requirement CðnvÞ in time slots, and each virtual link ev ¼ ðnv i ; nv j Þ 2 Ev is associated with a bandwidth requirement BðevÞ in time slots. Fig. 1a shows an example, where the corresponding resource requirement of each node or link is written next to the respective node or link that represents it. 2.2 The Time-Varying Resource Requirement Model SPs can hardly predict the number of end users of the applications deployed in their virtual networks; to guarantee the quality-of-service of a peak workload, SPs always overpurchase substrate resources. Besides, the resource requirements of many applications experience significant changes over time. Therefore, provisioning fixed resources for VNs throughout their lifetimes is clearly wasteful. To avoid such wasteful situations, we need to model the timevarying resource requirement of a VN in the first place. By using profiling experimentations, one can potentially derive some complicated functions, for example, high-order ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 817 Fig. 1. Each node or link is associated with a fixed resource requirement in the traditional VN request, while, in our model, the resource requirement of each node or link is expressed in a tuple
818 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.25,NO.3,MARCH 2014 (8,4.0.3 6,4.0.5 18 substrate node or link is written next to the respective node (a) b A 10 3,1.0.20 or link that represents it. 14,2,0.3) (3,1,0.1) The embedding of a VN G is defined as mapping M (3,3,0.31 (d (c) from G to a subset of G,such that the resource (7,70.2 (6.6,0.4) 18B requirement of G is satisfied and the resource capacities VN request G in Gs are not violated.It can be further decomposed into 9 two components:1)node mapping Mn:N-Ns,which 5,20.2)(720.3到(5,20.2 maps different virtual nodes to different substrate nodes; D 02'a,0.2⑨ e 10 10 20 20 20 and 2)link mapping M:E-Ps,which maps a virtual link VN request G2 substrate network to a substrate loop-free path. nFig.2,the node mapping for G is{a一A,b一 Fig.2.An example of virtual network embedding G,c一D,d→C,and the link mapping is{(ab)一{AG, (bc)-{GH,HD},(cd一{DC,(da)一{CB,BA}；the polynomials,to capture the time-varying resource require- node mapping for G?is{e→H,f→D,g-E,and the ment in a very precise way [20].However,such smooth link mapping is{(ef)一{HD},(fg)一{DE} functions may increase the representation and communica- Our main interest is to propose an embedding frame- tion burden of SPs,as well as complicate the resource work for InPs to cope with a sequence of VN requests that provisioning in SNs.To strike a balance between modeling arrive and depart over time.Upon the arrival of request G, precision and implementation difficulties,and to initiate a an InP must decide to either accept or reject it.Here,we tractable study as a first step,this paper resorts to a assume that VN requests arrive one by one,and batch probability-based modeland leavesexploringother tradeoffs processing is not the focus of this paper.From the as future work. standpoint of an InP,the objective is to maximize its In our model,the time-varying resource requirement of revenue through efficiently utilizing its substrate resources. a virtual node or link is composed of a basic subrequire- Following prior research [12],[13],the revenue,R(G),of ment,which exists throughout the lifetime of the respective embedding G?can be defined as VN,and a variable subrequirement,which occurs with a probability.Based on this resource requirement mode,we R(G)= ∑(b(n)+(n')+w∑6(e)+(e') replace the C(n)and B(e")in the traditional representa- e"EE tion with tuples and ,respectively,where b(n")(respectively,b(e")) where we and wb are the weights,providing the flexibility to denotes the number of time slots in the basic subrequire- tradeoff between the costs of two kinds of resources,and T ment,and u(n")(respectively,v(e"))denotes the number of is the lifetime of G.Note that the length of substrate paths time slots in the variable subrequirement,which occurs that virtual links are mapped to does not affect the revenue, with probability p(n").Take virtual node a in Fig.1b,for since an SP is only willing to pay a rent to the InP that is example,since =,we then proportional to the amount of requested resources.To maximize the revenue,VN requests should be intelligently know that virtual node a needs eight slots with a probability of 0.7 and 12 slots with a probability of 0.3. deployed on top of an SN.This paper revisits this problem Overall,we admit that many challenges remain,for from the perspective of opportunistic resource sharing. example,how does an SP choose suitable tuples to best reflect the time-varying resource requirement of his/ 4 THE OVERVIEW OF OUR FRAMEWORK her VN.However,the thesis of this paper is the notion of In this section,we present an overview of our framework, opportunistic resource sharing,and what it brings to InPs ORS.The details are introduced in Section 5. and SPs.We hope that this simplified model can provide ORS generally consists of two components,as shown in some insights on the design of future VNE algorithms. Algorithm 1.The macrolevel node-to-node/link-to-path embedding component adopts a traditional greedy strategy 3 THE VIRTUAL NETWORK EMBEDDING PROBLEM in [13]to derive the mapping of virtual nodes to substrate nodes and virtual links to substrate paths.In this A substrate network is modeled as a weighted undirected component,we first place virtual nodes in queue Q with graph,G=(N,E),where Ns and Es are the sets of decreasing (b(Q[i])+p(Qfil)v(Q[i])),which is the expected substrate nodes and links,respectively.Similarly,each number of time slots required by a virtual node Qi];then, substrate node n"E Ns is associated with a CPU capacity we map each virtual node from the head to the end of Q to C(n")in time slots,and each substrate link e"=(n,n)EE the unused substrate node with the most residual resource. is associated with a bandwidth capacity B(e)in time slots.If the residual resource of a substrate node is less than the The set of loop-free paths from n;to n is denoted as expected number of time slots required by the correspond- P"(n,n).The residual resources of n'and e"are denoted as ing virtual node,the VN request is rejected.This kind of RC(n')and RB(e"),respectively.The computation of "maximum-first"embedding fashion is beneficial to future RC"(n")and RB(e")in the context of opportunistic requests that may require some scarce or bottleneck resource sharing is not trivial,as we shall discuss shortly resources.We then map each virtual link to the shortest in Section 5.6.The right side of Fig.2 shows a substrate path [24]with sufficient bandwidth between its end hosts, network,where the corresponding resource capacity of each to minimize the span.We note that,when the VN request
polynomials, to capture the time-varying resource requirement in a very precise way [20]. However, such smooth functions may increase the representation and communication burden of SPs, as well as complicate the resource provisioning in SNs. To strike a balance between modeling precision and implementation difficulties, and to initiate a tractable study as a first step, this paper resorts to a probability-based model and leaves exploring other tradeoffs as future work. In our model, the time-varying resource requirement of a virtual node or link is composed of a basic subrequirement, which exists throughout the lifetime of the respective VN, and a variable subrequirement, which occurs with a probability. Based on this resource requirement mode, we replace the CðnvÞ and BðevÞ in the traditional representation with tuples and , respectively, where bðnvÞ (respectively, bðevÞ) denotes the number of time slots in the basic subrequirement, and vðnvÞ (respectively, vðevÞ) denotes the number of time slots in the variable subrequirement, which occurs with probability pðnvÞ. Take virtual node a in Fig. 1b, for example, since ¼ , we then know that virtual node a needs eight slots with a probability of 0.7 and 12 slots with a probability of 0.3. Overall, we admit that many challenges remain, for example, how does an SP choose suitable tuples to best reflect the time-varying resource requirement of his/ her VN. However, the thesis of this paper is the notion of opportunistic resource sharing, and what it brings to InPs and SPs. We hope that this simplified model can provide some insights on the design of future VNE algorithms. 3 THE VIRTUAL NETWORK EMBEDDING PROBLEM A substrate network is modeled as a weighted undirected graph, Gs ¼ ðNs; EsÞ, where Ns and Es are the sets of substrate nodes and links, respectively. Similarly, each substrate node ns 2 Ns is associated with a CPU capacity CðnsÞ in time slots, and each substrate link es ¼ ðns i ; ns j Þ 2 Es is associated with a bandwidth capacity BðesÞ in time slots. The set of loop-free paths from ns i to ns j is denoted as Psðns i ; ns j Þ. The residual resources of ns and es are denoted as RCsðnsÞ and RBsðesÞ, respectively. The computation of RCsðnsÞ and RBsðesÞ in the context of opportunistic resource sharing is not trivial, as we shall discuss shortly in Section 5.6. The right side of Fig. 2 shows a substrate network, where the corresponding resource capacity of each substrate node or link is written next to the respective node or link that represents it. The embedding of a VN Gv i is defined as mapping M from Gv i to a subset of Gs, such that the resource requirement of Gv i is satisfied and the resource capacities in Gs are not violated. It can be further decomposed into two components: 1) node mapping Mn : Nv i ! Ns, which maps different virtual nodes to different substrate nodes; and 2) link mapping Ml : Ev i ! Ps, which maps a virtual link to a substrate loop-free path. In Fig. 2, the node mapping for Gv 1 is fa ! A; b ! G; c ! D; d ! Cg, and the link mapping is fðabÞ!fAGg; ðbcÞ!fGH; HDg; ðcdÞ!fDCg; ðdaÞ!fCB; BAgg; the node mapping for Gv 2 is fe ! H;f ! D; g ! Eg, and the link mapping is fðefÞ!fHDg;ðfgÞ!fDEgg. Our main interest is to propose an embedding framework for InPs to cope with a sequence of VN requests that arrive and depart over time. Upon the arrival of request Gv i , an InP must decide to either accept or reject it. Here, we assume that VN requests arrive one by one, and batch processing is not the focus of this paper. From the standpoint of an InP, the objective is to maximize its revenue through efficiently utilizing its substrate resources. Following prior research [12], [13], the revenue, RðGv iÞ, of embedding Gv i can be defined as RðGv iÞ ¼ !c X nv2Nv ðbðnv Þ þ vðnv ÞÞ þ !b X ev2Ev ðbðev Þ þ vðev ÞÞ " #Tv i ; where !c and !b are the weights, providing the flexibility to tradeoff between the costs of two kinds of resources, and Tv i is the lifetime of Gv i . Note that the length of substrate paths that virtual links are mapped to does not affect the revenue, since an SP is only willing to pay a rent to the InP that is proportional to the amount of requested resources. To maximize the revenue, VN requests should be intelligently deployed on top of an SN. This paper revisits this problem from the perspective of opportunistic resource sharing. 4 THE OVERVIEW OF OUR FRAMEWORK In this section, we present an overview of our framework, ORS. The details are introduced in Section 5. ORS generally consists of two components, as shown in Algorithm 1. The macrolevel node-to-node/link-to-path embedding component adopts a traditional greedy strategy in [13] to derive the mapping of virtual nodes to substrate nodes and virtual links to substrate paths. In this component, we first place virtual nodes in queue Q with decreasing ðbðQ½iÞ þ pðQ½iÞvðQ½iÞÞ, which is the expected number of time slots required by a virtual node Q½i; then, we map each virtual node from the head to the end of Q to the unused substrate node with the most residual resource. If the residual resource of a substrate node is less than the expected number of time slots required by the corresponding virtual node, the VN request is rejected. This kind of “maximum-first” embedding fashion is beneficial to future requests that may require some scarce or bottleneck resources. We then map each virtual link to the shortest path [24] with sufficient bandwidth between its end hosts, to minimize the span. We note that, when the VN request 818 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 Fig. 2. An example of virtual network embedding.
ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 819 contains multiple edges between a pair of nodes,we turn component takes O(FN2);therefore,the overall time to find the k shortest paths [25]to reduce the sum of complexity of ORS is O(N+FN). the lengths of multiple substrate paths that these edges are mapped to. 5 MICROLEVEL TIME SLOT ASSIGNMENT-AN Algorithm 1.The ORS embedding framework. OPPORTUNISTIC RESOURCE SHARING VIEW 1:Wait until a VN request G"arrives In this section,we will first provide a formal description of 2:Macrolevel node-to-node/link-to-path mapping: the time slot assignment problem and its hardness result. 3:for all n∈Vs do unu.sed(n)←-1 end for Then,we present an ILP-based optimal solution and two 4:Q-sorted N with decreasing practical first-fit-based solutions.We also show how to (b(Q)+p(Q)v(Q[) estimate residual resources of substrate nodes and links. 5:for i=1 to Q.length do Finally,we will give a brief summary of this section. 6: Mn(Q[)←-argmaz(RC(n）·unused(n) if RC"(M,(Q[i]))<(b(Q[i])+p(Q[i])u(Q[i])) 5.1 Problem Formulation then reject G and return Since both CPU and bandwidth requirements can be 9:end for expressed as time slots,this section only takes the time slot 10:for all e"=(n",m")EE do assignment in a substrate link for illustration.The solutions 11: P'←-{pathRB(path)≥(p(e")v(e)+b(e), can be applied to substrate nodes without any changes. path E Ps(Mn(n"),Mn(m))} Consider the following scenario,where a set of n virtual 12: if ps ==0 then reject G"and return links from different VNs are embedded across a substrate 13: Mi(e")-argmin(hop(path)) link.For simplicity,the resource requirements from (the shortest path [24]or the k:shortest paths [25]) different VN requests are assumed to be independent of 14:end for each other.This seems to be reasonable,since VNs are 15:Microlevel time slot assignment: operated by different SPs and offer different services to 16:for all n"∈N"do different users.For the basic subrequirements that exist 17: if false =CFF(u(n"),p(n"))(or EFF) throughout the lifetime of the respective VN request,we 18: then reject G"and return must allocate the required number of dedicated time slots 19: for them;however,for the variable subrequirements,since update RC(Mn(n")) 20:end for they occur with a probability that is less than 1,sharing may be a viable choice to conserve substrate resources for future 21:for all e"∈Ewdo VN requests.Therefore,we will only consider how to assign 22: for all e∈M(e")do substrate slots to variable subrequirements in the remainder 23: if false ==CFF(v(e"),p(e"))(or EFF) of this section. 24 then reject G"and return We propose to assign one substrate slot to multiple units 25: update RB(e") of variable subrequirements.However,collisions may 26: end for happen,i.e.,multiple units of subrequirements occur 27:end for simultaneously.To strike a tradeoff between utilization In the microlevel component,we run CFF or EFF in each and collision,we use a collision threshold p to represent of the substrate nodes and links that are involved in the the "volume"of a substrate time slot. mapping of G"to deal with time slot allocations;then,we Denote by Di,the set of variable subrequirements that update residual resources of them.The details of this substrate slot tsj is assigned to;let Xi indicate whether the component are introduced in Section 5.It is worth ith variable subrequirement occurs,i.e.,Pr[Xi=1]=pi. elaborating on that lines 7 and 11 of Algorithm 1 only Then,the probability of a collision happening at slot tsj provide early-reject conditions;even when the node denoted by Pr(Di),is mapping Mn passes the checking condition in line 7,and the link mapping M passes checking condition of line 11,it is still possible that the resource requirement of G could not be guaranteed in the microlevel time slot assignment. While the "maximum-first"strategy of the macrolevel component largely comes from [13],the main contributions of this paper lie in the microlevel component.We conclude this section by presenting the time complexity of ORS.In macrolevel embedding,the sorting and mapping of virtual We have the following optimization problem: nodes takes O(Nllog(N)+N)time,and finding the k Problem 1 (The Time Slot Assignment Problem-TSA). shortest paths takes O(E+Nllog(IN)+k)[25];since Given a set of n virtual links from different VNs,the variable we need to execute the k shortest paths algorithm at most subrequirement of the ith virtual link is vi time slots,each of IN*times,this component takes ((Nllog(N)+N)+ which is needed with probability pi.Find an assignment of IN(E+Nsllog(IN)+))=O(IN)time in all.Here, substrate time slots to the subrequirements to minimize the we have simplified the summations by using E= number of slots used,such that:1)for the variable O(N2).Based on the results in Section 5.7,the microlevel subrequirement of the ith virtual link,the number of time
contains multiple edges between a pair of nodes, we turn to find the k shortest paths [25] to reduce the sum of the lengths of multiple substrate paths that these edges are mapped to. Algorithm 1. The ORS embedding framework. 1: Wait until a VN request Gv arrives 2: Macrolevel node-to-node/link-to-path mapping: 3: for all ns 2 Ns do unusedðnsÞ 1 end for 4: Q sorted Nv with decreasing ðbðQ½iÞ þ pðQ½iÞvðQ½iÞÞ 5: for i ¼ 1 to Q:length do 6: MnðQ½iÞ argmaxðRCsðnsÞ unusedðnsÞÞ 7: if RCsðMnðQ½iÞÞ < ðbðQ½iÞ þ pðQ½iÞvðQ½iÞÞ 8: then reject Gv and return 9: end for 10: for all ev ¼ ðnv; mvÞ 2 Ev do 11: Ps0 fpathjRBsðpathÞ ðpðevÞvðevÞ þ bðevÞÞ, path 2 PsðMnðnvÞ;MnðmvÞÞg 12: if Ps0 ¼¼ ; then reject Gv and return 13: MlðevÞ argminðhopðpathÞÞ (the shortest path [24] or the k shortest paths [25]) 14: end for 15: Microlevel time slot assignment: 16: for all nv 2 Nv do 17: if false ¼¼ CFFðvðnvÞ; pðnvÞÞ (or EFF) 18: then reject Gv and return 19: update RCsðMnðnvÞÞ 20: end for 21: for all ev 2 Ev do 22: for all es 2 MlðevÞ do 23: if false ¼¼ CFFðvðevÞ; pðevÞÞ (or EFF) 24: then reject Gv and return 25: update RBsðesÞ 26: end for 27: end for In the microlevel component, we run CFF or EFF in each of the substrate nodes and links that are involved in the mapping of Gv to deal with time slot allocations; then, we update residual resources of them. The details of this component are introduced in Section 5. It is worth elaborating on that lines 7 and 11 of Algorithm 1 only provide early-reject conditions; even when the node mapping Mn passes the checking condition in line 7, and the link mapping Ml passes checking condition of line 11, it is still possible that the resource requirement of Gv could not be guaranteed in the microlevel time slot assignment. While the “maximum-first” strategy of the macrolevel component largely comes from [13], the main contributions of this paper lie in the microlevel component. We conclude this section by presenting the time complexity of ORS. In macrolevel embedding, the sorting and mapping of virtual nodes takes OðjNvjlogðjNvjÞ þ jNvjÞ time, and finding the k shortest paths takes OðjEsjþjNsjlogðjNsjÞ þ kÞ [25]; since we need to execute the k shortest paths algorithm at most jNsj 2 times, this component takes OððjNvjlogðjNvjÞ þ jNvjÞ þ jNsj 2 ðjEsjþjNsjlogðjNsjÞ þ kÞÞ ¼ OðjNsj 4 Þ time in all. Here, we have simplified the summations by using jEsj ¼ OðjNsj 2 Þ. Based on the results in Section 5.7, the microlevel component takes OðFjNsj 2 Þ; therefore, the overall time complexity of ORS is OðjNsj 4 þ FjNsj 2 Þ. 5 MICROLEVEL TIME SLOT ASSIGNMENT—AN OPPORTUNISTIC RESOURCE SHARING VIEW In this section, we will first provide a formal description of the time slot assignment problem and its hardness result. Then, we present an ILP-based optimal solution and two practical first-fit-based solutions. We also show how to estimate residual resources of substrate nodes and links. Finally, we will give a brief summary of this section. 5.1 Problem Formulation Since both CPU and bandwidth requirements can be expressed as time slots, this section only takes the time slot assignment in a substrate link for illustration. The solutions can be applied to substrate nodes without any changes. Consider the following scenario, where a set of n virtual links from different VNs are embedded across a substrate link. For simplicity, the resource requirements from different VN requests are assumed to be independent of each other. This seems to be reasonable, since VNs are operated by different SPs and offer different services to different users. For the basic subrequirements that exist throughout the lifetime of the respective VN request, we must allocate the required number of dedicated time slots for them; however, for the variable subrequirements, since they occur with a probability that is less than 1, sharing may be a viable choice to conserve substrate resources for future VN requests. Therefore, we will only consider how to assign substrate slots to variable subrequirements in the remainder of this section. We propose to assign one substrate slot to multiple units of variable subrequirements. However, collisions may happen, i.e., multiple units of subrequirements occur simultaneously. To strike a tradeoff between utilization and collision, we use a collision threshold pth to represent the “volume” of a substrate time slot. Denote by Dj, the set of variable subrequirements that substrate slot tsj is assigned to; let Xi indicate whether the ith variable subrequirement occurs, i.e., P r½Xi ¼ 1 ¼ pi. Then, the probability of a collision happening at slot tsj, denoted by P rðDjÞ, is P rðDjÞ ¼ P r X i2Dj Xi 1 2 4 3 5 ¼ 1 Y i2Dj ð1 piÞ X i2Dj pi Y k2Dj ;k6¼i ð1 pkÞ 0 @ 1 A: ð1Þ We have the following optimization problem: Problem 1 (The Time Slot Assignment Problem—TSA). Given a set of n virtual links from different VNs, the variable subrequirement of the ith virtual link is vi time slots, each of which is needed with probability pi. Find an assignment of substrate time slots to the subrequirements to minimize the number of slots used, such that: 1) for the variable subrequirement of the ith virtual link, the number of time ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 819
820 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3,MARCH 2014 0=0.4 P3=0.2 P0.4 5.3 First-Fit by Collision Probability 12 [12 [123 12 In the bin packing problem [23],we are given n items with sizes s1,s2,...,sn E(0,1],and the objective is to find a Pm=0.1 packing method in unit-sized bins that minimizes the number of bins used.We observe that,when each variable ts1 ts2 ts3 ts4 ts5 ts6 ts7 tse.tsN subrequirement requires only one time slot,ie.,v;=1 for frame all 1Pth do Digital Library at http://doi.ieeecomputersociety.org/ 5: index←-inder+1 10.1109/TPDS.2013.64,for the detailed proofs of all the 6: if index N return false theorems in this paper. 7: end while Theorem 1.TSA is NP-hard in the strong sense. & Dinder←-Dinder U{i} 9: cnt←-cn.t+l,inder←-index+i 5.2 An ILP-Based Optimal Solution 10: if index N return false Inspired by the cutting stock problem,we can formulate the 11:end while TSA problem by means of ILP.Denote a set of variable 12:return true subrequirements whose collision probability is no more than The resemblance between the two problems inspires us Puh as a pattern.Denote the number of all possible patterns as to adopt the core idea of first-fit and design the "first-fit m.For each possible pattern j,let jrepresent the times that by collision probability"algorithm,shown in Algorithm 2. pattern j appears in a feasible assignment.Thus,the TSA In the algorithm,N is the total number of substrate time problem can be formulated as slots,and D;is the set of subrequirements that the jth substrate time slot is assigned to;the function min i getCollision Pro(Dinder,pi)returns the collision probability of subrequirements Dinder Ufi}and can be implemented (2) st.(a)≥，i∈{L,2,n}, in an incremental manner.Let A(D)=Π1-pm), rj,nonnegative integer,vie{1,2,...,m}, hEDi where aji indicates whether pattern j contains the ith subrequirement.Ideally,(2)can be optimally solved using intelligent exhaustive search approaches,such as back- tracking and branch-and-bound [24].However,it is not Then,the collision probability in (1)can be rewritten as practical.First,the number of possible patterns can be Pr(Di)=1-A(Dj)-B(Dj).We have exponentially large,the construction of which costs ex- A(DU{i})=A(D)1-), ponential time;second,the intelligent exhaustive search (3) approach usually consists of a systematic enumeration of all B(DU{i)=B(D)(1-)+A(D)P. candidate solutions,which is also difficult to apply in Let us look at the performance guarantee of CFF.Denote practice.This motivates us to design practical solutions, by Seff the assignment results from CFF,and by Sopt the which are introduced in the next two sections. results from the optimal solution.Abusing the notation a bit,we also use Seff and Sopt to denote the number of 1.Cutting stock problem [26].Given a number of rolls of paper of fixed width waiting to be cut,yet different customers want different numbers of substrate slots used in these results,respectively,if no rolls of various-sized widths,find a cutting method to minimize the waste. confusion can be caused.Let
slots assigned to it is at least vi; and 2) the collision probability at each substrate time slot is no more than a given collision threshold pth. For example, Fig. 3 shows a feasible assignment. ts1 can be assigned to two variable subrequirements because they collide with a probability 0.08, which is less than pth ¼ 0:1; however, ts4 cannot be assigned to the second and fourth subrequirements simultaneously, because the collision probability 0.12 is larger than pth. For the hardness of the TSA problem, we have the following theorem: Please refer to the supplemental material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2013.64, for the detailed proofs of all the theorems in this paper. Theorem 1. TSA is NP-hard in the strong sense. 5.2 An ILP-Based Optimal Solution Inspired by the cutting stock problem,1 we can formulate the TSA problem by means of ILP. Denote a set of variable subrequirements whose collision probability is no more than pth as a pattern. Denote the number of all possible patterns as m. For each possible pattern j, let xj represent the times that pattern j appears in a feasible assignment. Thus, the TSA problem can be formulated as minXm j¼1 xj; s:t: Xm j¼1 ðajixjÞ vi; 8i 2 f1; 2; ... ; ng; xj; nonnegative integer; 8j 2 f1; 2; ... ; mg; ð2Þ where aji indicates whether pattern j contains the ith subrequirement. Ideally, (2) can be optimally solved using intelligent exhaustive search approaches, such as backtracking and branch-and-bound [24]. However, it is not practical. First, the number of possible patterns can be exponentially large, the construction of which costs exponential time; second, the intelligent exhaustive search approach usually consists of a systematic enumeration of all candidate solutions, which is also difficult to apply in practice. This motivates us to design practical solutions, which are introduced in the next two sections. 5.3 First-Fit by Collision Probability In the bin packing problem [23], we are given n items with sizes s1; s2; ... ; sn 2 ð0; 1, and the objective is to find a packing method in unit-sized bins that minimizes the number of bins used. We observe that, when each variable subrequirement requires only one time slot, i.e., vi ¼ 1 for all 1 i n, TSA is similar to bin packing, except that the size of multiple items is the sum of them in bin packing; the collision probability of multiple subrequirements is neither linear nor multiplicative, as shown in (1). The first-fit algorithm [23] is a greedy approximation algorithm of factor 2 for bin packing. In first-fit, items are considered in an arbitrary order, and for each item, first-fit attempts to place the item in the first bin that can accommodate the item. If this is not possible, the item is placed into a new bin. First-fit can be executed online and has a low time complexity. Algorithm 2. First-Fit by Collision Probability (CFF). 1: Input: vi and pi 2: cnt 0, index 0 3: while cnt pth do 5: index index þ 1 6: if index > N return false 7: end while 8: Dindex Dindex [ fig 9: cnt cnt þ 1, index index þ 1 10: if index > N return false 11: end while 12: return true The resemblance between the two problems inspires us to adopt the core idea of first-fit and design the “first-fit by collision probability” algorithm, shown in Algorithm 2. In the algorithm, N is the total number of substrate time slots, and Dj is the set of subrequirements that the jth substrate time slot is assigned to; the function getCollisionP roðDindex; piÞ returns the collision probability of subrequirements Dindex [ fig and can be implemented in an incremental manner. Let AðDjÞ ¼ Y h2Dj ð1 phÞ; BðDjÞ ¼ X h2Dj ph Y k2Dj ; k6¼h ð1 pkÞ : Then, the collision probability in (1) can be rewritten as P rðDjÞ ¼ 1 AðDjÞ BðDjÞ. We have AðDj [ figÞ ¼ AðDjÞð1 piÞ; BðDj [ figÞ ¼ BðDjÞð1 piÞ þ AðDjÞpi: ð3Þ Let us look at the performance guarantee of CFF. Denote by Scff the assignment results from CFF, and by Sopt the results from the optimal solution. Abusing the notation a bit, we also use Scff and Sopt to denote the number of substrate slots used in these results, respectively, if no confusion can be caused. Let 820 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 1. Cutting stock problem [26]. Given a number of rolls of paper of fixed width waiting to be cut, yet different customers want different numbers of rolls of various-sized widths, find a cutting method to minimize the waste. Fig. 3. The time slot assignment problem. The probability threshold serves as the “volume” of a substrate time slot.
ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 821 P30.2 12 P=01 e=0.1 P=0.1 ts,ts2 tss ts4 ts5 ts6 ts7 tsg.tsN ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts1 ts2 ts3 ts4 ts5 ts6 ts7 tsg tsN frame frame frame (a)The original assignment (b)Without rearrangement. (c)With rearrangement Fig.4.Fragmentation of time slots due to the dynamics of virtual networks.(a)The original assignment;after some time,the first virtual link leaves and the fifth virtual link comes.(b)and(c)The scenarios without and with rearrangement,respectively.We see that the rearrangement reduces the number of slots used by 2. Pmim=m2n1≤iand name the new algorithm"first-fit In Algorithm 2,the getCollisionPro function is invoked by expectation of indicators'sum".In doing so,the whenever we want to see whether a substrate slot can checking condition in line 4 is reduced to one addition accommodate a unit of variable subrequirement,and it still operation,suggesting that EFF may run faster than CFF. costs five additions and three multiplications,even when It turns out that using an expectation threshold decreases using incremental calculation.Recall that the number of the number of variable subrequirements that a substrate slot substrate nodes and links may be very large;if we could can be assigned to;however,this relaxation gap is a bit reduce the time complexity of getCollisionPro a little,then more subtle than it might initially appear.To motivate it, the total benefit would be great. we start with the following illuminating example: Denote X;as the indicator of the ith variable subrequire- Consider a substrate slot that is assigned to n variable ment.Our motivational question is,for a given p,does a subrequirements from different virtual links,each occur- corresponding value exist such that,if the sum of the ring with the same probability p;then,the collision indicators of a set of variable subrequirements is less than that value,then we can definitely know that the collision probability Pr[colll is 1-(1-p)"-np(1-p)"-1 and the expectation of the sum of indicators E[y]is np.For each probability of them is less than p?Fortunately,based on E[Y],we obtain a value of pu by Theorem 3.Fig.5 shows Chernoff bound [27],we prove the following theorem. the relaxation gap.For instance,when n=2 and p=0.1, Theorem3.fEl∑iep,X≤hh,then Pr[D引≤pth,whee we have E[Y]=2×0.1=0.2,Pr[coll=1-(1-0.1)2 uthel-=pth,and e is the exponential constant. 2×0.1×(1-0.1)=0.0L,ph=EY]e1-y=0.445,indi- cating,if we use th=0.2 as the expectation threshold, Given the value of pth,we have to solve a transcendental then the collision probability is guaranteed to be no more equation ph=el to get the corresponding h In our than 0.445.However,the collision probability of these two implementation,we resort to numerical methods.We notice subrequirements is 0.01,which is much smaller than 0.445. that the curve of puh=ute is similar to a parabola; The main reason behind this phenomenon is that mutual therefore,polynomial interpolation is used to approxi- independence is ignored in the EFF algorithm due to the mately calculate th.Given three points,(0.1,0.245), linearity of expectation.To make up the relaxation gap,we (0.5,0.824),and(0.9,0.994),we get replace by h in EFF,i.e.Pi+keP>Auth Here, ph≈-1.278124h2+2.214374h+0.0363438 the parameter A is used to control the relaxation,and its empirical value will be investigated in our simulations. With the help of this theorem,the original determination of whether a substrate slot can accommodate a unit of variable subrequirement turns into evaluating whether the D=0.1 p=0.2 Prlcolll EY Prlcoll pu expectation of the sum of the subrequirements'indicators is 0.1 .245 02 0 0.445 less than th.We then modify the TSA problem a little and 0.2 0.01 0.445 0.4 0.04 0.729 get the following problem. 03 0.2 0.604 0.6 0.104 0.895 0 0.052 D.729 0.8 0.181 0.977 Problem 2(The Expectation-Based Time Slot Assignment 5 0.5 0.081 0.824 Problem-ETSA).Given a set of n virtual links from 9 0.9 0.225 0.994 different VNs,the variable subrequirement of the ith virtual Fig.5.Due to the linearity of expectation,the mutual independence is link is v;time slots,each of which is needed with probability pi. ignored in EFF,leading to a relaxation gap
pmin ¼ min1inpi; vmin ¼ min1invi; pmax ¼ max1inpi; vmax ¼ max1invi: We then have the following theorem. Theorem 2. Scff Soptðvmax vol1Þ=ðvmin vol2Þ, where volI and volII are the roots of equations: 1 ð1 pminÞ vol1 vol1 pmin ð1 pminÞ vol11 ¼ pth; 1 ð1 pmaxÞ vol2 vol2 pmax ð1 pmaxÞ vol21 ¼ pth: 5.4 First-Fit by Expectation of Indicators’ Sum In Algorithm 2, the getCollisionPro function is invoked whenever we want to see whether a substrate slot can accommodate a unit of variable subrequirement, and it still costs five additions and three multiplications, even when using incremental calculation. Recall that the number of substrate nodes and links may be very large; if we could reduce the time complexity of getCollisionPro a little, then the total benefit would be great. Denote Xi as the indicator of the ith variable subrequirement. Our motivational question is, for a given pth, does a corresponding value exist such that, if the sum of the indicators of a set of variable subrequirements is less than that value, then we can definitely know that the collision probability of them is less than pth? Fortunately, based on Chernoff bound [27], we prove the following theorem. Theorem 3. If E½ P i2Dj Xi th, then P r½Dj pth, where the1th ¼ pth, and e is the exponential constant. Given the value of pth, we have to solve a transcendental equation pth ¼ the1th to get the corresponding th. In our implementation, we resort to numerical methods. We notice that the curve of pth ¼ the1th is similar to a parabola; therefore, polynomial interpolation is used to approximately calculate th. Given three points, (0.1,0.245), (0.5,0.824), and (0.9,0.994), we get pth 1:27812th2 þ 2:21437th þ 0:0363438: With the help of this theorem, the original determination of whether a substrate slot can accommodate a unit of variable subrequirement turns into evaluating whether the expectation of the sum of the subrequirements’ indicators is less than th. We then modify the TSA problem a little and get the following problem. Problem 2 (The Expectation-Based Time Slot Assignment Problem—ETSA). Given a set of n virtual links from different VNs, the variable subrequirement of the ith virtual link is vi time slots, each of which is needed with probability pi. Find an assignment of substrate time slots to the subrequirements to minimize the number of slots used, such that: 1) for the variable subrequirement of the ith virtual link, the number of time slots assigned to it is at least vi; and 2) the expectation of the sum of the indicators of a set of variable subrequirements that a substrate slot is assigned to is no more than a given expectation threshold th. Theorem 4. The ETSA problem is NP-complete. We replace the condition in line 4 of Algorithm 2 with pi þ P k2Dindex pk > th, and name the new algorithm “first-fit by expectation of indicators’ sum”. In doing so, the checking condition in line 4 is reduced to one addition operation, suggesting that EFF may run faster than CFF. It turns out that using an expectation threshold decreases the number of variable subrequirements that a substrate slot can be assigned to; however, this relaxation gap is a bit more subtle than it might initially appear. To motivate it, we start with the following illuminating example: Consider a substrate slot that is assigned to n variable subrequirements from different virtual links, each occurring with the same probability p; then, the collision probability P r½coll is 1 ð1 pÞ n npð1 pÞ n1 and the expectation of the sum of indicators E½Y is np. For each E½Y , we obtain a value of pth by Theorem 3. Fig. 5 shows the relaxation gap. For instance, when n ¼ 2 and p ¼ 0:1, we have E½Y ¼ 2 0:1 ¼ 0:2;Pr½coll ¼ 1 ð1 0:1Þ 2 2 0:1 ð1 0:1Þ ¼ 0:01, pth ¼ E½Y e1E½Y ¼ 0:445, indicating, if we use th ¼ 0:2 as the expectation threshold, then the collision probability is guaranteed to be no more than 0.445. However, the collision probability of these two subrequirements is 0.01, which is much smaller than 0.445. The main reason behind this phenomenon is that mutual independence is ignored in the EFF algorithm due to the linearity of expectation. To make up the relaxation gap, we replace th by th in EFF, i.e., pi þ P k2Dindex pk > th. Here, the parameter is used to control the relaxation, and its empirical value will be investigated in our simulations. ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 821 Fig. 4. Fragmentation of time slots due to the dynamics of virtual networks. (a) The original assignment; after some time, the first virtual link leaves and the fifth virtual link comes. (b) and (c) The scenarios without and with rearrangement, respectively. We see that the rearrangement reduces the number of slots used by 2. Fig. 5. Due to the linearity of expectation, the mutual independence is ignored in EFF, leading to a relaxation gap.
822 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3.MARCH 2014 5.5 Rearrangement D2 D3 D4 D6 D7 P-0.1 Due to the dynamics of virtual network requests,the substrate resources may become fragmented,i.e.,some tsz -tss ts4 ts5 tse ts7 ts8.tsN shared time slots are not in full use.In this section,we frame propose to use rearrangement to avoid resource fragmenta- Fig.6.A snapshot of time slot allocation in a substrate link.ts and tss tion and improve resource utilization. are assigned to some basic subrequirements:each of ts2,tss,ts,ts, We start with an illustrating example,shown in Fig.4. and ts is assigned to a set of variable subrequirements,denoted as Di, Fig.4a shows a snapshot of the time slot assignment in a respectively;the other slots are unused. substrate link.Note that only the shared time slots are shown in the figure,since the dedicated time slots are in full use all tsi and tss are assigned to some basic subrequirements;each the time.After some time,the first virtual link along with its of ts2,ts3,ts4,ts6,and ts7 is assigned to a set of variable variable subrequirement leaves,and the fifth virtual link subrequirements,denoted as Di;the other slots are unused. along with its variable subrequirement arrives.According to The residual resource should include the unused slots and the first-fit-based algorithms,we first check whether ts can the residual "room"in the shared slots.We then propose a accommodate a unit of subrequirement from the fifth virtual reasonable method to properly measure the latter. link,and it cannot,since paps =0.12 pth.We then check the For a substrate node or link that has N time slots,where following slots and,finally,reach the assignment shown in N=C(n")if it is a substrate node n',or N B(e)if it is a Fig.4b,where eight slots are used. substrate link e,denote the set of slots that are assigned to However,if we rearrange the time slot assignment when basic subrequirements as So;denote the set of slots that are the first virtual link leaves,we could assign ts and ts2 to assigned to variable subrequirements as S;and denote the the variable subrequirements from the fourth virtual link.In rest as S.For example,in Fig.6,S=(1,5),S={2,3, doing so,slots tss and ts would be assigned to the newly 4,6,7),and S.=(1,2,3.....N)(SUS). arrived virtual link.The final assignment is shown in The residual room rre in the kth slot which belongs to Fig.4c,where we can see that the rearrangement reduces S is defined as a probability that satisfies the following the number of slots used by 2. condition:if we assign tsk to a new variable subrequire- This example motivates us to propose the rearrangement ment,which occurs with this probability,then the collision protocol as follows:On a virtual network request's leave,or at intervals set by an InP,the following operations are probability would be equal to pth.This definition is performed in every substrate node and link:for decreasing j intuitively reasonable,as it indicates the maximum from N to 1,the subrequirements in D;are reassigned by probability of a variable subrequirement that we can using CFF or EFF.The loop ends upon an encounter with a assign tsk to. substrate slot,which is just assigned to a new subrequire- When Dl =1 and D=[h},rrk pth/ph;when Dl> ment by this rearrangement protocol. 1,according to (3),we have In a sense,rearrangement "compresses"the assignment so that it takes up less time slots,which is beneficial to 1-A(De)(1-rrk)-(B(D)(1-rrk)+A(De)rrk)=pth. future VN requests,and improves substrate resources After solving it,we get utilization.It is worth noticing that,after the rearrangement is performed,the residual resources of substrate nodes and Tk三 A(D)+B(D)+pu-1_Pu Pr(De) (4) links change.To capture this change,the residual resource B(Dk B(Dk) estimation should be executed.We can see that the rearrangement incurs some computational overhead;there- Thereby,the residual resource of this substrate link is fore,our protocol allows InPs to achieve a tradeoff between resource utilization and computational overhead by tuning RB(e)=Sul+>minfrrk:1}. (5) kES the trigger intervals. Take ts in Fig.2,for example,Pr({1,3))=0.08, 5.6 Estimating Residual Resource B({1,31)=0.44;thus,the residual room in ts is rr= This section presents how we estimate the residual (ph-Pr({1,3})/B({1,3})≈0.045. resources of each substrate node and link in the context of opportunistic resource sharing. 5.7 Remarks and Summary Residual resources are traditionally defined as follows: In summary,this section starts with the formulation and the RC"(n")=C(n")-vn-fe(n",n")and RB(e")=B(e")- NP-hard result of the microlevel time slot assignment ve f(e",e"),where fe(n",n")denotes the amount of the problem and then provides an ILP-based optimal solution, CPU resources in n"that are allocated to n",and fo(e",e") which is not practical.The similarities between our problem denotes the amount of the bandwidth resources in es that and bin packing further motivate us to propose two first-fit- are allocated to e".Since both CPU and bandwidth are based heuristics,the performances of which are to be expressed in time slots,this section focuses on RB(e); investigated in our extensive simulations.We then design a RC"(n")can be analyzed similarly. simple rearrangement protocol to cope with resource However,when we apply opportunistic resource sharing fragmentation and show how to estimate residual resources to the resource allocation in substrate networks,some of substrate nodes and links.We also provide in Section 1 of substrate time slots are shared among multiple virtual the supplemental material,available online,some intuitive networks;then,it is nontrivial to calculate the amount of insights on how opportunistic resource sharing can lead to a residual resources in a substrate node or link.Fig.6 shows a win-win situation-service providers'costs are lowered, time slot allocation snapshot in a substrate link.We see that while infrastructure providers'revenues increase,as well
5.5 Rearrangement Due to the dynamics of virtual network requests, the substrate resources may become fragmented, i.e., some shared time slots are not in full use. In this section, we propose to use rearrangement to avoid resource fragmentation and improve resource utilization. We start with an illustrating example, shown in Fig. 4. Fig. 4a shows a snapshot of the time slot assignment in a substrate link. Note that only the shared time slots are shown in the figure, since the dedicated time slots are in full use all the time. After some time, the first virtual link along with its variable subrequirement leaves, and the fifth virtual link along with its variable subrequirement arrives. According to the first-fit-based algorithms, we first check whether ts1 can accommodate a unit of subrequirement from the fifth virtual link, and it cannot, since p3p5 ¼ 0:12 > pth. We then check the following slots and, finally, reach the assignment shown in Fig. 4b, where eight slots are used. However, if we rearrange the time slot assignment when the first virtual link leaves, we could assign ts1 and ts2 to the variable subrequirements from the fourth virtual link. In doing so, slots ts5 and ts6 would be assigned to the newly arrived virtual link. The final assignment is shown in Fig. 4c, where we can see that the rearrangement reduces the number of slots used by 2. This example motivates us to propose the rearrangement protocol as follows: On a virtual network request’s leave, or at intervals set by an InP, the following operations are performed in every substrate node and link: for decreasing j from N to 1, the subrequirements in Dj are reassigned by using CFF or EFF. The loop ends upon an encounter with a substrate slot, which is just assigned to a new subrequirement by this rearrangement protocol. In a sense, rearrangement “compresses” the assignment so that it takes up less time slots, which is beneficial to future VN requests, and improves substrate resources utilization. It is worth noticing that, after the rearrangement is performed, the residual resources of substrate nodes and links change. To capture this change, the residual resource estimation should be executed. We can see that the rearrangement incurs some computational overhead; therefore, our protocol allows InPs to achieve a tradeoff between resource utilization and computational overhead by tuning the trigger intervals. 5.6 Estimating Residual Resource This section presents how we estimate the residual resources of each substrate node and link in the context of opportunistic resource sharing. Residual resources are traditionally defined as follows: RCsðnsÞ ¼ CsðnsÞ P 8nv fcðnv; nsÞ and RBsðesÞ ¼ Bsðes P Þ 8ev fbðev; esÞ, where fcðnv; nsÞ denotes the amount of the CPU resources in ns that are allocated to nv, and fbðev; esÞ denotes the amount of the bandwidth resources in es that are allocated to ev. Since both CPU and bandwidth are expressed in time slots, this section focuses on RBsðesÞ; RCsðnsÞ can be analyzed similarly. However, when we apply opportunistic resource sharing to the resource allocation in substrate networks, some substrate time slots are shared among multiple virtual networks; then, it is nontrivial to calculate the amount of residual resources in a substrate node or link. Fig. 6 shows a time slot allocation snapshot in a substrate link. We see that ts1 and ts5 are assigned to some basic subrequirements; each of ts2, ts3, ts4, ts6, and ts7 is assigned to a set of variable subrequirements, denoted as Di; the other slots are unused. The residual resource should include the unused slots and the residual “room” in the shared slots. We then propose a reasonable method to properly measure the latter. For a substrate node or link that has N time slots, where N ¼ CsðnsÞ if it is a substrate node ns, or N ¼ BsðesÞ if it is a substrate link es, denote the set of slots that are assigned to basic subrequirements as Sb; denote the set of slots that are assigned to variable subrequirements as Sv; and denote the rest as Su. For example, in Fig. 6, Sb ¼ f1; 5g, Sv ¼ f2; 3; 4; 6; 7g, and Su ¼ f1; 2; 3; ... ; NgnðSb [ SvÞ. The residual room rrk in the kth slot which belongs to Sv is defined as a probability that satisfies the following condition: if we assign tsk to a new variable subrequirement, which occurs with this probability, then the collision probability would be equal to pth. This definition is intuitively reasonable, as it indicates the maximum probability of a variable subrequirement that we can assign tsk to. When jDkj ¼ 1 and Dk ¼ fhg, rrk ¼ pth=ph; when jDkj > 1, according to (3), we have 1 AðDkÞð1 rrkÞðBðDkÞð1 rrkÞ þ AðDkÞrrkÞ ¼ pth: After solving it, we get rrk ¼ AðDkÞ þ BðDkÞ þ pth 1 BðDkÞ ¼ pth P rðDkÞ BðDkÞ : ð4Þ Thereby, the residual resource of this substrate link is RBs ðes Þ¼jSuj þ X k2Sv minfrrk; 1g: ð5Þ Take ts1 in Fig. 2, for example, P rðf1; 3gÞ ¼ 0:08, Bðf1; 3gÞ ¼ 0:44; thus, the residual room in ts1 is rr1 ¼ ðpth P rðf1; 3gÞÞ=Bðf1; 3gÞ 0:045. 5.7 Remarks and Summary In summary, this section starts with the formulation and the NP-hard result of the microlevel time slot assignment problem and then provides an ILP-based optimal solution, which is not practical. The similarities between our problem and bin packing further motivate us to propose two first-fitbased heuristics, the performances of which are to be investigated in our extensive simulations. We then design a simple rearrangement protocol to cope with resource fragmentation and show how to estimate residual resources of substrate nodes and links. We also provide in Section 1 of the supplemental material, available online, some intuitive insights on how opportunistic resource sharing can lead to a win-win situation—service providers’ costs are lowered, while infrastructure providers’ revenues increase, as well. 822 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 Fig. 6. A snapshot of time slot allocation in a substrate link. ts1 and ts5 are assigned to some basic subrequirements; each of ts2, ts3, ts4, ts6, and ts7 is assigned to a set of variable subrequirements, denoted as Di, respectively; the other slots are unused
ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 823 40 600 1400 s00 500 100 400 400 80 30 200 20 8400 400 100 2100 200 。 un8ergvarbebu8ne2.o Numr vare (a)p∈(0.05,0.10】 (b)p5∈(0.05,0.20) (a)p:∈(0.05,0.10) (b)p∈(0.05,0.20) Fig.7.Comparison of CFF and EFF under varying n while keeping Fig.8.Comparison of CFF and EFF under varyingr while keeping Pth 0.1 and vmar=10.EFF(x)denotes =r. Pu =0.1 and n 50. We note that the adaptation of the microlevel time slot "total slots."We note that,when n increases from assignment to the scenario where a node has multiple types 20 to 100 with an increment of 20,the data points of resources is trivial,since the algorithms in this section are are linear in shape,indicating that the number of microlevel and are executed in every substrate and link. substrate slots used grows linearly with n.We also When there are multiple types of resources,the InPs just see that,when A increases,the results of EFF(A) have to run the algorithms for them individually. occupy less substrate slots,since a larger A allows We conclude this section by presenting the time more subrequirements to be accommodated in a complexity results.Denote the maximum variable sub- single substrate slot.We also find that EFF (14) requirement among all of the virtual nodes and links from achieves almost the same results as CFF;however, a virtual network as max(v);denote the maximum when A>14,as we shall explain shortly in Fig.9, capacity among all of the substrate nodes and links in a the collision probability would be bigger than the substrate network as max(max(B),max(C)).Let F= threshold. max(v).max(max(B),max(C));then,both CFF and EFF 2. The impact of vmar:Fig.8 shows the corresponding have at most O(F)comparisons.The estimation of residual results,where we keep the other parameters fixed, resources takes O(N+E)time.The overall time for example,pth =0.1 and n =50.When Umar goes complexity of the microlevel component is O((Ns+ up from 10 to 50 with an increment of 10,the E)(1+F))=O(FIN2),where N]and E are the substrate slots used also grows linearly with vmar.By cardinalities of Ns and E",respectively. comparing Fig.8a with Fig.8b,we find that,when pi doubles on average,the number of slots used nearly 6 PERFORMANCE EVALUATION doubles.The main reason behind this phenomenon is that,when p;increases on average,the number of In this section,we first concentrate on the scenario of a subrequirements that a substrate slot can accommo- single substrate link in an effort to quantify the benefits of date decreases;however,as the collision probability opportunistic resource sharing and compare the perfor- is neither additive nor multiplicative,the double of mances of CFF and EFF.We then compare ORS with two Pi does not necessarily lead to a doubling of the state-of-the-art fixed-resource embedding schemes. number of slots used. 6.1 Single Substrate Link 3. Comparison of running fimes:Fig.9a demonstrates the We first consider a scenario where a single substrate link is comparison results between the running times of shared among multiple virtual links from different virtual CFF and EFF,where Pth =0.1,Umar =30,and network requests.Since we have no choice but to allocate piE(0.05,0.10).We make two observations.First, the corresponding required slots for basic subrequirements, EFF generally runs faster than CFF.The main reason we do not consider the basic subrequirements in this behind this phenomenon is that,as we mentioned in section.The number of variable subrequirements is n,and Section 5.4,EFF replaces the getCollision Pro func- tion,which requires five additions and three multi- the ith (1<i<n)subrequirement needs vi slots with plications,with just one addition.Second,EFF(A) probability pi.In our simulation,v;is uniformly generated runs faster when A is increasing.The reason is between 2 and Umari Pi is uniformly generated from two intervals,i.e.,(0.05,0.10)and (0.05,0.20);the collision threshold puh is chosen from (0.1,0.2,0.3}.We try to 16000 02 compare the performances of CFF and EFF,and see the 81400 81200 02 effects of n,Umar,and pth. 100 .1 0000 6.2 Results of Single Substrate Link 600 400 52000 1. The impact of n:Fig.7 shows the corresponding results,where we keep the other parameters fixed, for example,pth =0.1 and Umar =10.We denote (a)Comparison of running (b)The ratio of EFF(14)toto- tal slots under different thresholds. EFF with relaxation parameter A by EFF(A),and the time.pth =0.1,Umax 30 andp:∈(0.05,0.10j where n =100 andma =10 number of substrate slots that are needed,if opportunistic resource sharing is not adopted,by Fig.9.Running time comparison and the impact of p
We note that the adaptation of the microlevel time slot assignment to the scenario where a node has multiple types of resources is trivial, since the algorithms in this section are microlevel and are executed in every substrate and link. When there are multiple types of resources, the InPs just have to run the algorithms for them individually. We conclude this section by presenting the time complexity results. Denote the maximum variable subrequirement among all of the virtual nodes and links from a virtual network as maxðvÞ; denote the maximum capacity among all of the substrate nodes and links in a substrate network as maxðmaxðBÞ; maxðCÞÞ. Let F ¼ maxðvÞ maxðmaxðBÞ; maxðCÞÞ; then, both CFF and EFF have at most OðFÞ comparisons. The estimation of residual resources takes OðjNsjþjEsjÞ time. The overall time complexity of the microlevel component is OððjNsj þ jEsjÞð1 þ FÞÞ ¼ OðFjNsj 2 Þ, where jNsj and jEsj are the cardinalities of Ns and Es, respectively. 6 PERFORMANCE EVALUATION In this section, we first concentrate on the scenario of a single substrate link in an effort to quantify the benefits of opportunistic resource sharing and compare the performances of CFF and EFF. We then compare ORS with two state-of-the-art fixed-resource embedding schemes. 6.1 Single Substrate Link We first consider a scenario where a single substrate link is shared among multiple virtual links from different virtual network requests. Since we have no choice but to allocate the corresponding required slots for basic subrequirements, we do not consider the basic subrequirements in this section. The number of variable subrequirements is n, and the ith ð1 i nÞ subrequirement needs vi slots with probability pi. In our simulation, vi is uniformly generated between 2 and vmax; pi is uniformly generated from two intervals, i.e., ð0:05; 0:10Þ and ð0:05; 0:20Þ; the collision threshold pth is chosen from f0:1; 0:2; 0:3g. We try to compare the performances of CFF and EFF, and see the effects of n, vmax, and pth. 6.2 Results of Single Substrate Link 1. The impact of n: Fig. 7 shows the corresponding results, where we keep the other parameters fixed, for example, pth ¼ 0:1 and vmax ¼ 10. We denote EFF with relaxation parameter by EFF(), and the number of substrate slots that are needed, if opportunistic resource sharing is not adopted, by “total slots.” We note that, when n increases from 20 to 100 with an increment of 20, the data points are linear in shape, indicating that the number of substrate slots used grows linearly with n. We also see that, when increases, the results of EFF() occupy less substrate slots, since a larger allows more subrequirements to be accommodated in a single substrate slot. We also find that EFF (14) achieves almost the same results as CFF; however, when > 14, as we shall explain shortly in Fig. 9, the collision probability would be bigger than the threshold. 2. The impact of vmax: Fig. 8 shows the corresponding results, where we keep the other parameters fixed, for example, pth ¼ 0:1 and n ¼ 50. When vmax goes up from 10 to 50 with an increment of 10, the substrate slots used also grows linearly with vmax. By comparing Fig. 8a with Fig. 8b, we find that, when pi doubles on average, the number of slots used nearly doubles. The main reason behind this phenomenon is that, when pi increases on average, the number of subrequirements that a substrate slot can accommodate decreases; however, as the collision probability is neither additive nor multiplicative, the double of pi does not necessarily lead to a doubling of the number of slots used. 3. Comparison of running times: Fig. 9a demonstrates the comparison results between the running times of CFF and EFF, where pth ¼ 0:1, vmax ¼ 30, and pi 2 ð0:05; 0:10Þ. We make two observations. First, EFF generally runs faster than CFF. The main reason behind this phenomenon is that, as we mentioned in Section 5.4, EFF replaces the getCollisionP ro function, which requires five additions and three multiplications, with just one addition. Second, EFF() runs faster when is increasing. The reason is ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 823 Fig. 7. Comparison of CFF and EFF under varying n while keeping pth ¼ 0:1 and vmax ¼ 10. EFF(x) denotes ¼ x. Fig. 8. Comparison of CFF and EFF under varying vmax while keeping pth ¼ 0:1 and n ¼ 50. Fig. 9. Running time comparison and the impact of pth.
824 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3,MARCH 2014 09 08 .0 是7 0 0.4 0. 0.2 02 03 02 100020003000400050006000 0.1 02 0.3 0.4 0.5 0.1 0.2 03 04 0 Time Node utilization ratio Link utilization rato (a)Acceptance ratio over time (b)CDF of node utilization ratio (c)CDF of link utilization ratio Fig.10.Comparison results among ORS,R-ViNE,and Greedy,where E[b+=10,E[b/(b+)]=0.5,Elp =0.15. implicit,if somewhat subtle:one substrate slot can virtual network is assumed to be exponentially distributed accommodate more variable subrequirements when with an average of 10 minutes.The arrivals of VN requests A becomes larger;thus,the value of index in EFF(A) are modeled as a Poisson process with an average rate of becomes smaller on average. five requests per minute.The collision probability threshold The impact of puh:Fig.9b shows the ratio of EFF(14)to is set to 0.1 throughout this evaluating scenario.The results total slots under different thresholds,while we keep are averaged over 100 times of running.(Results over n=100 and Umar =10.We note that,for fixed Umar, ARPANET are similar and are omitted due to space the ratio goes down when the threshold increases. limitations.)Our framework ORS is compared with the This is reasonable,since the threshold serves as the following two algorithms: "volume"of a substrate slot,and a larger threshold allows a substrate slot to accommodate more R-ViNE [12]:coordinated node and link mapping subrequirements.For fixed pth,the ratio goes up through mixed integer programming formulation when Umar increases.This is because a larger Umar and randomized rounding. makes the number of subrequirements that a Greedy [13]:greedy node mapping and path splitting. substrate slot can accommodate decrease,and hence, The performance metrics we use for comparison include EFF (14)needs more substrate slots. acceptance ratio,which is the ratio of the number of accepted In our simulations,we also find that,when A>14,the virtual network requests to all requests,node ufilization ratio, collision probability in the embedding results of EFF which is the ratio of the amount of the allocated CPU would be bigger than pu=0.1.In addition,this critical resources to overall CPU resources in the substrate network, value is about 10 when pth=0.2,and about eight when and link utilization ratio,which is the ratio of the amount of pth=0.3.We explain this as follows:if we replace every pi the allocated bandwidth resources to overall bandwidth with Pmar =mar(sisn)pi,then the number of subrequire- resources in the substrate network.We are also interested in ments that a single substrate slot can accommodate, denoted as y,,can be resolved by 1-(1-pmar)"- the impacts of the following parameters: pmar(1-pmaz)y=pth.Then,by double counting the .Eb+:the average total number of slots required indicators'sum,we get h =Pmary.When Pth goes up, by a virtual node or link; both y and h go up,but A goes down,indicating that h ● Eb/(b+v)]:the average percentage of the number of grows faster than y. slots in a basic subrequirement to the total number of We also conducted simulations with ph=0.2 and slots required by a virtual node or link;and p=0.3.The results are similar to the above and are, therefore,omitted due to space limitations.Briefly speak- Ep]:the average happening probability of variable subrequirements of virtual nodes and links ing,both CFF and EFF improve the resource utilization,and EFF is less time-consuming and more flexible than CFF. 6.4 Results of Entire Substrate Network 6.3 Entire Substrate Network 1. Comparison of acceptance ratios.Figs.10a,10b,and 10c In this section,we consider VNE at the level of the entire show the comparison of the acceptance ratio over network,compare our framework with two state-of-the-art time,cumulative distribution function (CDF)of node fixed-resource embedding algorithms [12],[13],and inves- utilization ratio,and CDF of link utilization ratio, tigate the impacts of various parameters. respectively.In these experiments,Eb+u is 10, Our simulation settings follow prior work [12],[13],as E[b/(b+v)]=0.5,and Elp]=0.15.In Fig.10a,as a network virtualization is still in its infancy.We use whole,the acceptance ratio of ORS is the highest, ANSNET and ARPANET as the substrate network topolo- and Greedy is the lowest,indicating that opportu- gies.Both CPU and bandwidth capacities in substrate nistic resource sharing indeed improves the deploy- networks are generated uniformly from the interval ment of virtual networks,which further enables the between 50 and 100.For virtual networks,the number of substrate network to accept more VN requests.We virtual nodes is determined by a uniform distribution notice that the acceptance ratio of three algorithms is between 2 and 10,and each pair of virtual nodes is about 0.4 on average,which is a little low.The main connected with a probability of 0.5.We also check whether reason is that links in the substrate network a virtual network is connected;if it is not,we just regenerate (ANSNET has 32 nodes and 58 links,ARPANET it until we get a connected topology.The lifetime of each has 20 nodes and 32 links)are sparse,while each
implicit, if somewhat subtle: one substrate slot can accommodate more variable subrequirements when becomes larger; thus, the value of index in EFF() becomes smaller on average. 4. The impact of pth: Fig. 9b shows the ratio of EFF (14) to total slots under different thresholds, while we keep n ¼ 100 and vmax ¼ 10. We note that, for fixed vmax, the ratio goes down when the threshold increases. This is reasonable, since the threshold serves as the “volume” of a substrate slot, and a larger threshold allows a substrate slot to accommodate more subrequirements. For fixed pth, the ratio goes up when vmax increases. This is because a larger vmax makes the number of subrequirements that a substrate slot can accommodate decrease, and hence, EFF (14) needs more substrate slots. In our simulations, we also find that, when > 14, the collision probability in the embedding results of EFF would be bigger than pth ¼ 0:1. In addition, this critical value is about 10 when pth ¼ 0:2, and about eight when pth ¼ 0:3. We explain this as follows: if we replace every pi with pmax ¼ maxð1inÞpi, then the number of subrequirements that a single substrate slot can accommodate, denoted as y, can be resolved by 1 ð1 pmaxÞ y pmaxð1 pmaxÞ y1 y ¼ pth. Then, by double counting the indicators’ sum, we get th ¼ pmaxy. When pth goes up, both y and th go up, but goes down, indicating that th grows faster than y. We also conducted simulations with pth ¼ 0:2 and pth ¼ 0:3. The results are similar to the above and are, therefore, omitted due to space limitations. Briefly speaking, both CFF and EFF improve the resource utilization, and EFF is less time-consuming and more flexible than CFF. 6.3 Entire Substrate Network In this section, we consider VNE at the level of the entire network, compare our framework with two state-of-the-art fixed-resource embedding algorithms [12], [13], and investigate the impacts of various parameters. Our simulation settings follow prior work [12], [13], as network virtualization is still in its infancy. We use ANSNET and ARPANET as the substrate network topologies. Both CPU and bandwidth capacities in substrate networks are generated uniformly from the interval between 50 and 100. For virtual networks, the number of virtual nodes is determined by a uniform distribution between 2 and 10, and each pair of virtual nodes is connected with a probability of 0.5. We also check whether a virtual network is connected; if it is not, we just regenerate it until we get a connected topology. The lifetime of each virtual network is assumed to be exponentially distributed with an average of 10 minutes. The arrivals of VN requests are modeled as a Poisson process with an average rate of five requests per minute. The collision probability threshold is set to 0.1 throughout this evaluating scenario. The results are averaged over 100 times of running. (Results over ARPANET are similar and are omitted due to space limitations.) Our framework ORS is compared with the following two algorithms: . R V iNE [12]: coordinated node and link mapping through mixed integer programming formulation and randomized rounding. . Greedy [13]: greedy node mapping and path splitting. The performance metrics we use for comparison include acceptance ratio, which is the ratio of the number of accepted virtual network requests to all requests, node utilization ratio, which is the ratio of the amount of the allocated CPU resources to overall CPU resources in the substrate network, and link utilization ratio, which is the ratio of the amount of the allocated bandwidth resources to overall bandwidth resources in the substrate network. We are also interested in the impacts of the following parameters: . E½b þ v: the average total number of slots required by a virtual node or link; . E½b=ðb þ vÞ: the average percentage of the number of slots in a basic subrequirement to the total number of slots required by a virtual node or link; and . E½p: the average happening probability of variable subrequirements of virtual nodes and links. 6.4 Results of Entire Substrate Network 1. Comparison of acceptance ratios. Figs. 10a, 10b, and 10c show the comparison of the acceptance ratio over time, cumulative distribution function (CDF) of node utilization ratio, and CDF of link utilization ratio, respectively. In these experiments, E½b þ v is 10, E½b=ðb þ vÞ ¼ 0:5, and E½p ¼ 0:15. In Fig. 10a, as a whole, the acceptance ratio of ORS is the highest, and Greedy is the lowest, indicating that opportunistic resource sharing indeed improves the deployment of virtual networks, which further enables the substrate network to accept more VN requests. We notice that the acceptance ratio of three algorithms is about 0.4 on average, which is a little low. The main reason is that links in the substrate network (ANSNET has 32 nodes and 58 links, ARPANET has 20 nodes and 32 links) are sparse, while each 824 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 Fig. 10. Comparison results among ORS, R V iNE, and Greedy, where E½b þ v ¼ 10; E½b=ðb þ vÞ ¼ 0:5; E½p ¼ 0:15.
ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 825 0.9 introduced to maximize the aggregate performance across 0.8 multiple virtual networks in [31]. 月0.7 80.8 g08 For the virtual network embedding problem,a large 05 0 number of algorithms have been proposed in the past. 0.4 These algorithms give good inspiration to the design of ORS.Simulated annealing was introduced to cope with 0100200900500600 100200050 0 VNE's NP-completeness in [9]and [19].Embedding with unlimited substrate resources is studied in [11]and [10l (a)Impact of C and B (b)Impact of b and p Zhu and Ammar [11]focused on load balancing and on- Fig.11.Sensitivity analysis.In (a),E[/(+)]=0.5,E[p]=0.15;and in demand assignments,and Lu and Turner [10]attempted to (b),Eb+对=10. minimize the embedding cost of a single virtual network with a backbone-star topology.Yu et al.[13]envisioned pair of nodes in a virtual network is connected with path splitting support from substrate networks and a probability of 0.5.Thus,topology becomes the proposed to first map virtual nodes greedily,then handle dominating factor in our simulation scenarios. link mapping based on the multicommodity flow algo- 2 Comparison of node and link utilization ratios.In rithm.Lischka and Karl [14]proposed a backtracking Figs.10b and 10c,the node/link utilization ratios algorithm based on subgraph isomorphism detection,but of ORS and R-ViNE are the highest and the restricted the length of the substrate paths.Chowdhury second highest,respectively.We notice that the link et al.[12]proposed a linear programming and determinis- utilization ratio is a little higher than node utilization tic/randomized rounding-based algorithm with better ratio in every algorithm,i.e.,each CDF curve in coordination between node and link mappings,but added Fig.10b is in the left of the corresponding curve in location constraints to simplify the problem.Chowdhury Fig.10c,if we can put these two figures together and et al.[16]presented a policy-based decentralized inter- look at them.This is reasonable,since a virtual link domain virtual network embedding framework and also spans over several substrate links,while a virtual designed a location-aware VN request forwarding mechan- node only exists in a substrate node. ism.Recently,Bienkowski et al.[32]presented a competi- 3. The impact of E[b+v.Fig.11b shows the results of tive analysis framework for service migration in a mobile the impact of Eb+v.We note that,in the case of a network virtualization architecture,where thin clients on small Eb+vl,the acceptance ratio is high.However, mobile devices access services that can be migrated closer to with increasing Eb+v,the substrate network the access points,as to reduce user latency.Even et al.[7] resources become scarce,which causes more and proposed a competitive online algorithm for admission more VN requests to be rejected.In this figure, control,while assuming the existence of an oracle that helps (Eb+v=15)achieves almost the same acceptance ratio as(Eb+=20).The main reason behind this to compute the embedding. Comparatively,while prior embedding algorithms re- phenomenon is that (Eb+v=15)is sufficiently serve fixed resources throughout the lifetime of a virtual large compared to the average capacity of substrate nodes and links,i.e.,75 in our simulation. network,this work rethinks this paradigm and proposes to opportunistically share resources among multiple virtual The impact of E[b/(b+v)]and Elpl.Fig.11c shows the networks,so as to make efficient use of the precious impact of them,where (E[b/(b+v)]=0.30,Elp] 0.15)has the best performance,and (E[b/(b+v)]= substrate resources. 0.50,Elp]=0.05)has the second best,indicating that the basic subrequirement percentage b/(b+v)plays 8 CONCLUSIONS a more important role than the occurring probability p,which is reasonable,since the basic subrequire- In this paper,we rethink the virtual network embedding ments cannot be shared. problem from the perspective of opportunistic resource sharing,and we propose an embedding framework that In summary,simulations of the single substrate link consists of the macrolevel node-to-node/link-to-path em- scenario demonstrate that both CFF and EFF improve the bedding and the microlevel time slot assignment.Extensive resource utilization of substrate networks,and EFF is more simulations confirm the effectiveness of our framework. flexible and less time consuming than CFF.In addition, simulations of the entire substrate network show that our framework outperforms two state-of-the-art fixed-resource ACKNOWLEDGMENTS embedding algorithms,in terms of both acceptance ratio The authors would like to thank the anonymous reviewers and utilization ratio.Our results also show some insights for their insightful suggestions.This work was supported in into the impacts of various parameters. part by NSFC Grants (Nos.61073028,61202113,and 61021062),Key Project of Jiangsu Research Program Grant 7 RELATED WORK (No.BE2010179),Jiangsu NSF Grant (No.BK2011510),973 Program of China Grants (Nos.2009CB320705 and For the general network virtualization,cognitive radio- 2011CB302800),College graduate research and innovation based virtual networks are envisioned in [28];optical project of Jiangsu Grant (No.CXZZ12_0055),and US backbone network virtualization is investigated in [29]. National Science Foundation (NSF)Grants (ECCS 1128209, Virtualization is used to lower the barrier for deploying CNS 1065444,CCF 1028167,CNS 0948184,and CCF wide-area services in [30].Adaptive resource allocation is 0830289).Zhuzhong Qian is the corresponding author
pair of nodes in a virtual network is connected with a probability of 0.5. Thus, topology becomes the dominating factor in our simulation scenarios. 2. Comparison of node and link utilization ratios. In Figs. 10b and 10c, the node/link utilization ratios of ORS and R V iNE are the highest and the second highest, respectively. We notice that the link utilization ratio is a little higher than node utilization ratio in every algorithm, i.e., each CDF curve in Fig. 10b is in the left of the corresponding curve in Fig. 10c, if we can put these two figures together and look at them. This is reasonable, since a virtual link spans over several substrate links, while a virtual node only exists in a substrate node. 3. The impact of E½b þ v. Fig. 11b shows the results of the impact of E½b þ v. We note that, in the case of a small E½b þ v, the acceptance ratio is high. However, with increasing E½b þ v, the substrate network resources become scarce, which causes more and more VN requests to be rejected. In this figure, ðE½b þ v ¼ 15Þ achieves almost the same acceptance ratio as ðE½b þ v ¼ 20Þ. The main reason behind this phenomenon is that ðE½b þ v ¼ 15Þ is sufficiently large compared to the average capacity of substrate nodes and links, i.e., 75 in our simulation. 4. The impact of E½b=ðb þ vÞ and E½p. Fig. 11c shows the impact of them, where ðE½b=ðb þ vÞ ¼ 0:30; E½p ¼ 0:15Þ has the best performance, and ðE½b=ðb þ vÞ ¼ 0:50; E½p ¼ 0:05Þ has the second best, indicating that the basic subrequirement percentage b=ðb þ vÞ plays a more important role than the occurring probability p, which is reasonable, since the basic subrequirements cannot be shared. In summary, simulations of the single substrate link scenario demonstrate that both CFF and EFF improve the resource utilization of substrate networks, and EFF is more flexible and less time consuming than CFF. In addition, simulations of the entire substrate network show that our framework outperforms two state-of-the-art fixed-resource embedding algorithms, in terms of both acceptance ratio and utilization ratio. Our results also show some insights into the impacts of various parameters. 7 RELATED WORK For the general network virtualization, cognitive radiobased virtual networks are envisioned in [28]; optical backbone network virtualization is investigated in [29]. Virtualization is used to lower the barrier for deploying wide-area services in [30]. Adaptive resource allocation is introduced to maximize the aggregate performance across multiple virtual networks in [31]. For the virtual network embedding problem, a large number of algorithms have been proposed in the past. These algorithms give good inspiration to the design of ORS. Simulated annealing was introduced to cope with VNE’s NP-completeness in [9] and [19]. Embedding with unlimited substrate resources is studied in [11] and [10]. Zhu and Ammar [11] focused on load balancing and ondemand assignments, and Lu and Turner [10] attempted to minimize the embedding cost of a single virtual network with a backbone-star topology. Yu et al. [13] envisioned path splitting support from substrate networks and proposed to first map virtual nodes greedily, then handle link mapping based on the multicommodity flow algorithm. Lischka and Karl [14] proposed a backtracking algorithm based on subgraph isomorphism detection, but restricted the length of the substrate paths. Chowdhury et al. [12] proposed a linear programming and deterministic/randomized rounding-based algorithm with better coordination between node and link mappings, but added location constraints to simplify the problem. Chowdhury et al. [16] presented a policy-based decentralized interdomain virtual network embedding framework and also designed a location-aware VN request forwarding mechanism. Recently, Bienkowski et al. [32] presented a competitive analysis framework for service migration in a mobile network virtualization architecture, where thin clients on mobile devices access services that can be migrated closer to the access points, as to reduce user latency. Even et al. [7] proposed a competitive online algorithm for admission control, while assuming the existence of an oracle that helps to compute the embedding. Comparatively, while prior embedding algorithms reserve fixed resources throughout the lifetime of a virtual network, this work rethinks this paradigm and proposes to opportunistically share resources among multiple virtual networks, so as to make efficient use of the precious substrate resources. 8 CONCLUSIONS In this paper, we rethink the virtual network embedding problem from the perspective of opportunistic resource sharing, and we propose an embedding framework that consists of the macrolevel node-to-node/link-to-path embedding and the microlevel time slot assignment. Extensive simulations confirm the effectiveness of our framework. ACKNOWLEDGMENTS The authors would like to thank the anonymous reviewers for their insightful suggestions. This work was supported in part by NSFC Grants (Nos. 61073028, 61202113, and 61021062), Key Project of Jiangsu Research Program Grant (No. BE2010179), Jiangsu NSF Grant (No. BK2011510), 973 Program of China Grants (Nos. 2009CB320705 and 2011CB302800), College graduate research and innovation project of Jiangsu Grant (No. CXZZ12_0055), and US National Science Foundation (NSF) Grants (ECCS 1128209, CNS 1065444, CCF 1028167, CNS 0948184, and CCF 0830289). Zhuzhong Qian is the corresponding author. ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 825 Fig. 11. Sensitivity analysis. In (a), E½b=ðb þ vÞ ¼ 0:5; E½p ¼ 0:15; and in (b), E½b þ v ¼ 10.