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 requestpolynomials, to capture the time-varying resource require￾ment in a very precise way [20]. However, such smooth functions may increase the representation and communica￾tion 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 subrequire￾ment, 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 representa￾tion 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 subrequire￾ment, 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 frame￾work 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 correspond￾ing 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.