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 timecontains 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