2)A first-fit-based online approximation algorithm:the Case I:we use a particular variable sub-traffic flow,which design of our algorithm is based on the following observation: requires dmin time slots and occurs with probability Pmin, when each variable sub-traffic requires one single time slot. to replace all of the variable sub-traffic.Then.the maximal i.e.,(1 -bwli).B'(e)=1 for all i,Problem 1 is very similar allowable number of sub-traffic,vol,in a substrate slot is to bin packing.However,the occupied size in each bin is the determined by: sum of the sizes of all of the packed items in bin packing, whereas in Problem 1,the collision probability in a time slot, 1-(1-Pmin)vol-volt Pmin(1-Pmin)vol-1=Puh as shown in Eq.2,is neither linear nor multiplicative. Hence,in this case,the number of time slots required by First-fit [23]is a heuristic algorithm with an approximation all of the n sub-traffic is: factor of 2 for bin packing.In first-fit,items are considered in an arbitrary order,and for each item,first-fit attempts to place s1=”dnn the item in the first bin that can accommodate the item.If not. the item is placed into a new bin.First-fit can be executed Case II:we use another particular variable sub-traffic flow, online and has a low time complexity. which requires dmax time slots and occurs with probability Their resemblance sheds light on the design of FFA,which Pmax,to replace all of the variable sub-traffic.Then,the is based on the core idea of first-fit.The FFA Algorithm is maximal allowable number of sub-traffic,voly,in a substrate presented in Algorithm 2. slot is determined by: 1-(1-Pmax)you-voln Pmax(1-Pmaxolu-1=Pth Algorithm 2 FFA(Pih) 1:Wait until variable sub-traffic from e arrives Similarly,the number of time slots required by all of the n 2:counter←-0 sub-traffic in this case is: 3:While(counter <(1-bwli).B:(e)) ·dmar Let pos←-0 5: While(Collision(tspos,e)>Pth) 6: pos←←p05+1 Theorem I:Sffa≤(dmar·voli）/(dmin·voli）Sopr 个 Proof:it is straightforward to see that: Assign tspos to e 8: counter←counter+1 0<S1≤Som≤Sffa≤Sn then: 3)Incremental Calculation:Collision(tspos,e)is a func- SifaSμ=dmaxvoll tion that returns the probability of a collision at tspos if tspos is assigned to e'.To calculate the collision probability efficiently, :≤Si=dminvol we adopt the following incremental approach.Let De be the The theorem follows immediately. ■ set of variable sub-traffic that ts is currently assigned to.Also B.Residual Resource Estimation let: A(Dk)= 1-pwli) The amount of the residual resource in a substrate node/link iED is an important metric in VNE process.In a traditional sce- B(D)= S(pwlr (1-pwl)》 nario,where opportunistic resource sharing is not considered, iED jEDu,jti the residual CPU,RC(n),of a substrate node,n,and residual then,the collision probability Preollision(D)=1-A(D)- bandwidth,RB(e),of a substrate link,e,are defined as: B(D).When slot k is to be assigned to a new sub-traffic from RCom)=Cn-∑0n,n) e,then: Vnv A(D&Ulep)=A(Dg)(1-pwlh) RB'(e)=B'(e)- ∑fi(e',e) (3) B(D&Ulep])=B(D)(1-pwlh)+A(Dg).pwlh where fe(n",n)denotes the CPU resources of ns allocated This can be used to calculate the new collision probability. to n",and fo(e",e)denotes the bandwidth resources of es 4)Approximation Ratio:we denote by Sffa the solution allocated to e". generated by FFA,and by Sop the optimal solution.Abusing However,with opportunistic resource sharing,the residual the notation a bit,we will also use Sffa and Sopr to denote resource becomes complicated.Fig.3 shows a snapshot of the the number of time slots needed by these two solutions, time slot allocation in a substrate link.Intuitively,the residual respectively,if no confusion can be caused.Let, resource consists of the right part and the available room in Pmin minisisnpwli,dmin =minisisn((1-bwli).B(e)) the middle part which is allocated to variable sub-traffic.The pmax maxisisnpwli,dmax =maxisisn((1-bwli).B(e)) former is easy to compute while the latter is not so obvious. Suppose that the capacity of a substrate link,e",is B(e), Bin packing [23]:given n items with sizes s1.52....s.(0,1].find a and there are L time slots in a frame.There are b slots allocated packing method in unit-sized bins that minimizes the number of bins used.to basic sub-traffic and another d slots allocated to variable 24122) A first-fit-based online approximation algorithm: the design of our algorithm is based on the following observation: when each variable sub-traffic requires one single time slot, i.e., (1 − bwli) · B v i (e v i ) = 1 for all i, Problem 1 is very similar to bin packing1 . However, the occupied size in each bin is the sum of the sizes of all of the packed items in bin packing, whereas in Problem 1, the collision probability in a time slot, as shown in Eq. 2, is neither linear nor multiplicative. First-fit [23] is a heuristic algorithm with an approximation factor of 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 not, the item is placed into a new bin. First-fit can be executed online and has a low time complexity. Their resemblance sheds light on the design of FFA, which is based on the core idea of first-fit. The FFA Algorithm is presented in Algorithm 2. Algorithm 2 FFA(pth) 1: Wait until variable sub-traffic from e v i arrives 2: counter ← 0 3: While(counter < (1 − bwli) · B v i (e v i )) 4: Let pos ← 0 5: While(Collision(tspos, e v i ) > pth) 6: pos ← pos + 1 7: Assign tspos to e v i 8: counter ← counter + 1 3) Incremental Calculation: Collision(tspos, e v i ) is a func￾tion that returns the probability of a collision at tspos if tspos is assigned to e v i . To calculate the collision probability efficiently, we adopt the following incremental approach. Let Dk be the set of variable sub-traffic that tsk is currently assigned to. Also let: A(Dk) = ∏ i∈Dk (1 − pwli) B(Dk) = ∑ i∈Dk (pwli · ∏ j∈Dk , j,i (1 − pwlj)) then, the collision probability Prcollision(Dk) = 1 − A(Dk) − B(Dk). When slot k is to be assigned to a new sub-traffic from e v h , then: A(Dk ∪ {e v h }) = A(Dk)(1 − pwlh) B(Dk ∪ {e v h }) = B(Dk)(1 − pwlh) + A(Dk) · pwlh (3) This can be used to calculate the new collision probability. 4) Approximation Ratio: we denote by S f f a the solution generated by FFA, and by S opt, the optimal solution. Abusing the notation a bit, we will also use S f f a and S opt to denote the number of time slots needed by these two solutions, respectively, if no confusion can be caused. Let, pmin = min1≤i≤n pwli , dmin =min1≤i≤n((1 − bwli) · B v i (e v i )) pmax = max1≤i≤n pwli , dmax =max1≤i≤n((1 − bwli) · B v i (e v i )) 1Bin packing [23]: given n items with sizes s1,s2,...,sn ∈ (0, 1], find a packing method in unit-sized bins that minimizes the number of bins used. Case I: we use a particular variable sub-traffic flow, which requires dmin time slots and occurs with probability pmin, to replace all of the variable sub-traffic. Then, the maximal allowable number of sub-traffic, volI , in a substrate slot is determined by: 1 − (1 − pmin) volI − volI · pmin · (1 − pmin) volI−1 = pth Hence, in this case, the number of time slots required by all of the n sub-traffic is: S I = n volI · dmin Case II: we use another particular variable sub-traffic flow, which requires dmax time slots and occurs with probability pmax, to replace all of the variable sub-traffic. Then, the maximal allowable number of sub-traffic, volII, in a substrate slot is determined by: 1 − (1 − pmax) volII − volII · pmax · (1 − pmax) volII−1 = pth Similarly, the number of time slots required by all of the n sub-traffic in this case is: S II = n volII · dmax Theorem 1: S f f a ≤ (dmax · volI)/(dmin · volII) · S opt Proof: it is straightforward to see that: 0 < S I ≤ S opt ≤ S f f a ≤ S II then: S f f a S opt ≤ S II S I = dmax · volI dmin · volII The theorem follows immediately. B. Residual Resource Estimation The amount of the residual resource in a substrate node/link is an important metric in VNE process. In a traditional sce￾nario, where opportunistic resource sharing is not considered, the residual CPU, RCs (n s ), of a substrate node, n s , and residual bandwidth, RBs (e s ), of a substrate link, e s , are defined as: RCs (n s ) = C s (n s )− ∑ ∀n v fc(n v , n s ) RBs (e s ) = B s (e s )− ∑ ∀e v fb(e v , e s ) where fc(n v , n s ) denotes the CPU resources of n s allocated to n v , and fb(e v , e s ) denotes the bandwidth resources of e s allocated to e v . However, with opportunistic resource sharing, the residual resource becomes complicated. Fig. 3 shows a snapshot of the time slot allocation in a substrate link. Intuitively, the residual resource consists of the right part and the available room in the middle part which is allocated to variable sub-traffic. The former is easy to compute while the latter is not so obvious. Suppose that the capacity of a substrate link, e s , is B s (e s ), and there are L time slots in a frame. There are b slots allocated to basic sub-traffic and another d slots allocated to variable 2412