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≤i<nPi,Umim=m2n1≤isnU; Find an assignment of substrate time slots to the subrequire- Pmar=max1≤i<npi,max=maT1≤i≤nUi. ments to minimize the number of slots used,such that:1)for We then have the following theorem. the variable subrequirement of the ith virtual link,the number of time slots assigned to it is at least vi;and 2)the expectation Theorem2.Scjf≤Sopt(vmau·oli)/(umim·vol2）,where volr of the sum of the indicators of a set of variable subrequirements and volu are the roots of equations: that a substrate slot is assigned to is no more than a given 1-(1-pmin)o-ol1'pmin·(（1-pnin)o-l=ph, expectation threshold 1-(1-pmaz)-vo2Pmaz(1-pmar)o-1 Theorem 4.The ETSA problem is NP-complete 二ph We replace the condition in line 4 of Algorithm 2 with 5.4 First-Fit by Expectation of Indicators'Sum +>and 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 subrequire￾ment. 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 approxi￾mately 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 subrequire￾ments 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 occur￾ring 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, indi￾cating, 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.