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 <b,v.p>. 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 <b; v; p>
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 <b(n"),v(n"),p(n")>and <b(e"),v(e"), p(e")>,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 <b(a),v(a),p(a)>=<8,4,0.3>,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 <b,v,p>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 <bðnvÞ; vðnvÞ; pðnvÞ> and <bðevÞ; vðevÞ; pðevÞ>, 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 <bðaÞ; vðaÞ; pðaÞ> ¼ <8; 4; 0:3>, 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 <b; v; p> 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 1<i<n,TSA is similar to bin packing,except that the Fig.3.The time slot assignment problem.The probability threshold size of multiple items is the sum of them in bin packing;the serves as the "volume"of a substrate time slot. collision probability of multiple subrequirements is neither linear nor multiplicative,as shown in (1). slots assigned to it is at least vi;and 2)the collision probability The first-fit algorithm [23]is a greedy approximation at each substrate time slot is no more than a given collision algorithm of factor 2 for bin packing.In first-fit,items are threshold pth. considered in an arbitrary order,and for each item,first-fit attempts to place the item in the first bin that can For example,Fig.3 shows a feasible assignment.tsi can accommodate the item.If this is not possible,the item is be assigned to two variable subrequirements because they placed into a new bin.First-fit can be executed online and collide with a probability 0.08,which is less than ph=0.1; however,tsa cannot be assigned to the second and fourth has a low time complexity. subrequirements simultaneously,because the collision Algorithm 2.First-Fit by Collision Probability(CFF). probability 0.12 is larger than pth. 1:Input:vi and pi For the hardness of the TSA problem,we have the 2:cnt←-0，indexr←-0 following theorem:Please refer to the supplemental 3:while cnt <vi do material,which can be found on the Computer Society 名 while getCollistion Pro(Dinder:Pi)>Pth 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 < vi do 4: while getCollistionP roðDindex; piÞ > 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.