ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 823 40 600 1400 s00 500 100 400 400 80 30 200 20 8400 400 100 2100 200 。 un8ergvarbebu8ne2.o Numr vare (a)p∈(0.05,0.10】 (b)p5∈(0.05,0.20) (a)p:∈(0.05,0.10) (b)p∈(0.05,0.20) Fig.7.Comparison of CFF and EFF under varying n while keeping Fig.8.Comparison of CFF and EFF under varyingr while keeping Pth 0.1 and vmar=10.EFF(x)denotes =r. Pu =0.1 and n 50. We note that the adaptation of the microlevel time slot "total slots."We note that,when n increases from assignment to the scenario where a node has multiple types 20 to 100 with an increment of 20,the data points of resources is trivial,since the algorithms in this section are are linear in shape,indicating that the number of microlevel and are executed in every substrate and link. substrate slots used grows linearly with n.We also When there are multiple types of resources,the InPs just see that,when A increases,the results of EFF(A) have to run the algorithms for them individually. occupy less substrate slots,since a larger A allows We conclude this section by presenting the time more subrequirements to be accommodated in a complexity results.Denote the maximum variable sub- single substrate slot.We also find that EFF (14) requirement among all of the virtual nodes and links from achieves almost the same results as CFF;however, a virtual network as max(v);denote the maximum when A>14,as we shall explain shortly in Fig.9, capacity among all of the substrate nodes and links in a the collision probability would be bigger than the substrate network as max(max(B),max(C)).Let F= threshold. max(v).max(max(B),max(C));then,both CFF and EFF 2. The impact of vmar:Fig.8 shows the corresponding have at most O(F)comparisons.The estimation of residual results,where we keep the other parameters fixed, resources takes O(N+E)time.The overall time for example,pth =0.1 and n =50.When Umar goes complexity of the microlevel component is O((Ns+ up from 10 to 50 with an increment of 10,the E)(1+F))=O(FIN2),where N]and E are the substrate slots used also grows linearly with vmar.By cardinalities of Ns and E",respectively. comparing Fig.8a with Fig.8b,we find that,when pi doubles on average,the number of slots used nearly 6 PERFORMANCE EVALUATION doubles.The main reason behind this phenomenon is that,when p;increases on average,the number of In this section,we first concentrate on the scenario of a subrequirements that a substrate slot can accommo- single substrate link in an effort to quantify the benefits of date decreases;however,as the collision probability opportunistic resource sharing and compare the perfor- is neither additive nor multiplicative,the double of mances of CFF and EFF.We then compare ORS with two Pi does not necessarily lead to a doubling of the state-of-the-art fixed-resource embedding schemes. number of slots used. 6.1 Single Substrate Link 3. Comparison of running fimes:Fig.9a demonstrates the We first consider a scenario where a single substrate link is comparison results between the running times of shared among multiple virtual links from different virtual CFF and EFF,where Pth =0.1,Umar =30,and network requests.Since we have no choice but to allocate piE(0.05,0.10).We make two observations.First, the corresponding required slots for basic subrequirements, EFF generally runs faster than CFF.The main reason we do not consider the basic subrequirements in this behind this phenomenon is that,as we mentioned in section.The number of variable subrequirements is n,and Section 5.4,EFF replaces the getCollision Pro func- tion,which requires five additions and three multi- the ith (1<i<n)subrequirement needs vi slots with plications,with just one addition.Second,EFF(A) probability pi.In our simulation,v;is uniformly generated runs faster when A is increasing.The reason is between 2 and Umari Pi is uniformly generated from two intervals,i.e.,(0.05,0.10)and (0.05,0.20);the collision threshold puh is chosen from (0.1,0.2,0.3}.We try to 16000 02 compare the performances of CFF and EFF,and see the 81400 81200 02 effects of n,Umar,and pth. 100 .1 0000 6.2 Results of Single Substrate Link 600 400 52000 1. The impact of n:Fig.7 shows the corresponding results,where we keep the other parameters fixed, for example,pth =0.1 and Umar =10.We denote (a)Comparison of running (b)The ratio of EFF(14)toto- tal slots under different thresholds. EFF with relaxation parameter A by EFF(A),and the time.pth =0.1,Umax 30 andp:∈(0.05,0.10j where n =100 andma =10 number of substrate slots that are needed,if opportunistic resource sharing is not adopted,by Fig.9.Running time comparison and the impact of p.We note that the adaptation of the microlevel time slot assignment to the scenario where a node has multiple types of resources is trivial, since the algorithms in this section are microlevel and are executed in every substrate and link. When there are multiple types of resources, the InPs just have to run the algorithms for them individually. We conclude this section by presenting the time complexity results. Denote the maximum variable sub￾requirement among all of the virtual nodes and links from a virtual network as maxðvÞ; denote the maximum capacity among all of the substrate nodes and links in a substrate network as maxðmaxðBÞ; maxðCÞÞ. Let F ¼ maxðvÞ maxðmaxðBÞ; maxðCÞÞ; then, both CFF and EFF have at most OðFÞ comparisons. The estimation of residual resources takes OðjNsjþjEsjÞ time. The overall time complexity of the microlevel component is OððjNsj þ jEsjÞð1 þ FÞÞ ¼ OðFjNsj 2 Þ, where jNsj and jEsj are the cardinalities of Ns and Es, respectively. 6 PERFORMANCE EVALUATION In this section, we first concentrate on the scenario of a single substrate link in an effort to quantify the benefits of opportunistic resource sharing and compare the perfor￾mances of CFF and EFF. We then compare ORS with two state-of-the-art fixed-resource embedding schemes. 6.1 Single Substrate Link We first consider a scenario where a single substrate link is shared among multiple virtual links from different virtual network requests. Since we have no choice but to allocate the corresponding required slots for basic subrequirements, we do not consider the basic subrequirements in this section. The number of variable subrequirements is n, and the ith ð1  i  nÞ subrequirement needs vi slots with probability pi. In our simulation, vi is uniformly generated between 2 and vmax; pi is uniformly generated from two intervals, i.e., ð0:05; 0:10Þ and ð0:05; 0:20Þ; the collision threshold pth is chosen from f0:1; 0:2; 0:3g. We try to compare the performances of CFF and EFF, and see the effects of n, vmax, and pth. 6.2 Results of Single Substrate Link 1. The impact of n: Fig. 7 shows the corresponding results, where we keep the other parameters fixed, for example, pth ¼ 0:1 and vmax ¼ 10. We denote EFF with relaxation parameter by EFF(), and the number of substrate slots that are needed, if opportunistic resource sharing is not adopted, by “total slots.” We note that, when n increases from 20 to 100 with an increment of 20, the data points are linear in shape, indicating that the number of substrate slots used grows linearly with n. We also see that, when increases, the results of EFF() occupy less substrate slots, since a larger allows more subrequirements to be accommodated in a single substrate slot. We also find that EFF (14) achieves almost the same results as CFF; however, when > 14, as we shall explain shortly in Fig. 9, the collision probability would be bigger than the threshold. 2. The impact of vmax: Fig. 8 shows the corresponding results, where we keep the other parameters fixed, for example, pth ¼ 0:1 and n ¼ 50. When vmax goes up from 10 to 50 with an increment of 10, the substrate slots used also grows linearly with vmax. By comparing Fig. 8a with Fig. 8b, we find that, when pi doubles on average, the number of slots used nearly doubles. The main reason behind this phenomenon is that, when pi increases on average, the number of subrequirements that a substrate slot can accommo￾date decreases; however, as the collision probability is neither additive nor multiplicative, the double of pi does not necessarily lead to a doubling of the number of slots used. 3. Comparison of running times: Fig. 9a demonstrates the comparison results between the running times of CFF and EFF, where pth ¼ 0:1, vmax ¼ 30, and pi 2 ð0:05; 0:10Þ. We make two observations. First, EFF generally runs faster than CFF. The main reason behind this phenomenon is that, as we mentioned in Section 5.4, EFF replaces the getCollisionP ro func￾tion, which requires five additions and three multi￾plications, with just one addition. Second, EFF() runs faster when is increasing. The reason is ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 823 Fig. 7. Comparison of CFF and EFF under varying n while keeping pth ¼ 0:1 and vmax ¼ 10. EFF(x) denotes ¼ x. Fig. 8. Comparison of CFF and EFF under varying vmax while keeping pth ¼ 0:1 and n ¼ 50. Fig. 9. Running time comparison and the impact of pth.