ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 825 0.9 introduced to maximize the aggregate performance across 0.8 multiple virtual networks in [31]. 月0.7 80.8 g08 For the virtual network embedding problem,a large 05 0 number of algorithms have been proposed in the past. 0.4 These algorithms give good inspiration to the design of ORS.Simulated annealing was introduced to cope with 0100200900500600 100200050 0 VNE's NP-completeness in [9]and [19].Embedding with unlimited substrate resources is studied in [11]and [10l (a)Impact of C and B (b)Impact of b and p Zhu and Ammar [11]focused on load balancing and on- Fig.11.Sensitivity analysis.In (a),E[/(+)]=0.5,E[p]=0.15;and in demand assignments,and Lu and Turner [10]attempted to (b),Eb+对=10. minimize the embedding cost of a single virtual network with a backbone-star topology.Yu et al.[13]envisioned pair of nodes in a virtual network is connected with path splitting support from substrate networks and a probability of 0.5.Thus,topology becomes the proposed to first map virtual nodes greedily,then handle dominating factor in our simulation scenarios. link mapping based on the multicommodity flow algo- 2 Comparison of node and link utilization ratios.In rithm.Lischka and Karl [14]proposed a backtracking Figs.10b and 10c,the node/link utilization ratios algorithm based on subgraph isomorphism detection,but of ORS and R-ViNE are the highest and the restricted the length of the substrate paths.Chowdhury second highest,respectively.We notice that the link et al.[12]proposed a linear programming and determinis- utilization ratio is a little higher than node utilization tic/randomized rounding-based algorithm with better ratio in every algorithm,i.e.,each CDF curve in coordination between node and link mappings,but added Fig.10b is in the left of the corresponding curve in location constraints to simplify the problem.Chowdhury Fig.10c,if we can put these two figures together and et al.[16]presented a policy-based decentralized inter- look at them.This is reasonable,since a virtual link domain virtual network embedding framework and also spans over several substrate links,while a virtual designed a location-aware VN request forwarding mechan- node only exists in a substrate node. ism.Recently,Bienkowski et al.[32]presented a competi- 3. The impact of E[b+v.Fig.11b shows the results of tive analysis framework for service migration in a mobile the impact of Eb+v.We note that,in the case of a network virtualization architecture,where thin clients on small Eb+vl,the acceptance ratio is high.However, mobile devices access services that can be migrated closer to with increasing Eb+v,the substrate network the access points,as to reduce user latency.Even et al.[7] resources become scarce,which causes more and proposed a competitive online algorithm for admission more VN requests to be rejected.In this figure, control,while assuming the existence of an oracle that helps (Eb+v=15)achieves almost the same acceptance ratio as(Eb+=20).The main reason behind this to compute the embedding. Comparatively,while prior embedding algorithms re- phenomenon is that (Eb+v=15)is sufficiently serve fixed resources throughout the lifetime of a virtual large compared to the average capacity of substrate nodes and links,i.e.,75 in our simulation. network,this work rethinks this paradigm and proposes to opportunistically share resources among multiple virtual The impact of E[b/(b+v)]and Elpl.Fig.11c shows the networks,so as to make efficient use of the precious impact of them,where (E[b/(b+v)]=0.30,Elp] 0.15)has the best performance,and (E[b/(b+v)]= substrate resources. 0.50,Elp]=0.05)has the second best,indicating that the basic subrequirement percentage b/(b+v)plays 8 CONCLUSIONS a more important role than the occurring probability p,which is reasonable,since the basic subrequire- In this paper,we rethink the virtual network embedding ments cannot be shared. problem from the perspective of opportunistic resource sharing,and we propose an embedding framework that In summary,simulations of the single substrate link consists of the macrolevel node-to-node/link-to-path em- scenario demonstrate that both CFF and EFF improve the bedding and the microlevel time slot assignment.Extensive resource utilization of substrate networks,and EFF is more simulations confirm the effectiveness of our framework. flexible and less time consuming than CFF.In addition, simulations of the entire substrate network show that our framework outperforms two state-of-the-art fixed-resource ACKNOWLEDGMENTS embedding algorithms,in terms of both acceptance ratio The authors would like to thank the anonymous reviewers and utilization ratio.Our results also show some insights for their insightful suggestions.This work was supported in into the impacts of various parameters. part by NSFC Grants (Nos.61073028,61202113,and 61021062),Key Project of Jiangsu Research Program Grant 7 RELATED WORK (No.BE2010179),Jiangsu NSF Grant (No.BK2011510),973 Program of China Grants (Nos.2009CB320705 and For the general network virtualization,cognitive radio- 2011CB302800),College graduate research and innovation based virtual networks are envisioned in [28];optical project of Jiangsu Grant (No.CXZZ12_0055),and US backbone network virtualization is investigated in [29]. National Science Foundation (NSF)Grants (ECCS 1128209, Virtualization is used to lower the barrier for deploying CNS 1065444,CCF 1028167,CNS 0948184,and CCF wide-area services in [30].Adaptive resource allocation is 0830289).Zhuzhong Qian is the corresponding author.pair of nodes in a virtual network is connected with a probability of 0.5. Thus, topology becomes the dominating factor in our simulation scenarios. 2. Comparison of node and link utilization ratios. In Figs. 10b and 10c, the node/link utilization ratios of ORS and R  V iNE are the highest and the second highest, respectively. We notice that the link utilization ratio is a little higher than node utilization ratio in every algorithm, i.e., each CDF curve in Fig. 10b is in the left of the corresponding curve in Fig. 10c, if we can put these two figures together and look at them. This is reasonable, since a virtual link spans over several substrate links, while a virtual node only exists in a substrate node. 3. The impact of E½b þ v. Fig. 11b shows the results of the impact of E½b þ v. We note that, in the case of a small E½b þ v, the acceptance ratio is high. However, with increasing E½b þ v, the substrate network resources become scarce, which causes more and more VN requests to be rejected. In this figure, ðE½b þ v ¼ 15Þ achieves almost the same acceptance ratio as ðE½b þ v ¼ 20Þ. The main reason behind this phenomenon is that ðE½b þ v ¼ 15Þ is sufficiently large compared to the average capacity of substrate nodes and links, i.e., 75 in our simulation. 4. The impact of E½b=ðb þ vÞ and E½p. Fig. 11c shows the impact of them, where ðE½b=ðb þ vÞ ¼ 0:30; E½p ¼ 0:15Þ has the best performance, and ðE½b=ðb þ vÞ ¼ 0:50; E½p ¼ 0:05Þ has the second best, indicating that the basic subrequirement percentage b=ðb þ vÞ plays a more important role than the occurring probability p, which is reasonable, since the basic subrequire￾ments cannot be shared. In summary, simulations of the single substrate link scenario demonstrate that both CFF and EFF improve the resource utilization of substrate networks, and EFF is more flexible and less time consuming than CFF. In addition, simulations of the entire substrate network show that our framework outperforms two state-of-the-art fixed-resource embedding algorithms, in terms of both acceptance ratio and utilization ratio. Our results also show some insights into the impacts of various parameters. 7 RELATED WORK For the general network virtualization, cognitive radio￾based virtual networks are envisioned in [28]; optical backbone network virtualization is investigated in [29]. Virtualization is used to lower the barrier for deploying wide-area services in [30]. Adaptive resource allocation is introduced to maximize the aggregate performance across multiple virtual networks in [31]. For the virtual network embedding problem, a large number of algorithms have been proposed in the past. These algorithms give good inspiration to the design of ORS. Simulated annealing was introduced to cope with VNE’s NP-completeness in [9] and [19]. Embedding with unlimited substrate resources is studied in [11] and [10]. Zhu and Ammar [11] focused on load balancing and on￾demand assignments, and Lu and Turner [10] attempted to minimize the embedding cost of a single virtual network with a backbone-star topology. Yu et al. [13] envisioned path splitting support from substrate networks and proposed to first map virtual nodes greedily, then handle link mapping based on the multicommodity flow algo￾rithm. Lischka and Karl [14] proposed a backtracking algorithm based on subgraph isomorphism detection, but restricted the length of the substrate paths. Chowdhury et al. [12] proposed a linear programming and determinis￾tic/randomized rounding-based algorithm with better coordination between node and link mappings, but added location constraints to simplify the problem. Chowdhury et al. [16] presented a policy-based decentralized inter￾domain virtual network embedding framework and also designed a location-aware VN request forwarding mechan￾ism. Recently, Bienkowski et al. [32] presented a competi￾tive analysis framework for service migration in a mobile network virtualization architecture, where thin clients on mobile devices access services that can be migrated closer to the access points, as to reduce user latency. Even et al. [7] proposed a competitive online algorithm for admission control, while assuming the existence of an oracle that helps to compute the embedding. Comparatively, while prior embedding algorithms re￾serve fixed resources throughout the lifetime of a virtual network, this work rethinks this paradigm and proposes to opportunistically share resources among multiple virtual networks, so as to make efficient use of the precious substrate resources. 8 CONCLUSIONS In this paper, we rethink the virtual network embedding problem from the perspective of opportunistic resource sharing, and we propose an embedding framework that consists of the macrolevel node-to-node/link-to-path em￾bedding and the microlevel time slot assignment. Extensive simulations confirm the effectiveness of our framework. ACKNOWLEDGMENTS The authors would like to thank the anonymous reviewers for their insightful suggestions. This work was supported in part by NSFC Grants (Nos. 61073028, 61202113, and 61021062), Key Project of Jiangsu Research Program Grant (No. BE2010179), Jiangsu NSF Grant (No. BK2011510), 973 Program of China Grants (Nos. 2009CB320705 and 2011CB302800), College graduate research and innovation project of Jiangsu Grant (No. CXZZ12_0055), and US National Science Foundation (NSF) Grants (ECCS 1128209, CNS 1065444, CCF 1028167, CNS 0948184, and CCF 0830289). Zhuzhong Qian is the corresponding author. ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 825 Fig. 11. Sensitivity analysis. In (a), E½b=ðb þ vÞ ¼ 0:5; E½p ¼ 0:15; and in (b), E½b þ v ¼ 10.