TABLE III ALGORITHMS IN COMPARISON Notation Description ORSTA The entire framework,including opportunistic resource sharing,topology-aware ranking,and greedy node/link mapping ORS A partial framework,including opportunistic resource sharing.and greedy node/link mapping TA A partial framework.including topology-awareness,and greedy node/link mapping Greedy The traditional greedy embedding algorithm,including greedy node/link mapping ORSTA ORSTA ORSTA 0.8 0.8 Greedy Greedy 0.8 06 0.6 0.6 0.4 0.4 04 0.2 0.2 02 1000 20003000 400050006000 0.1 0.2 0.30.4 0.5 0.1 0.2 0.30.40.5 0.6 Time Node Utilization Ratio Link Utilization Ratio Fig.4. Acceptance ratio over time Fig.5. CDF of node utilization ratios Fig.6. CDF of link utilization ratios ORSTA(W,=0.3) ORSTA(EI ORSTA(Ebwl]-0.50.E PWI-0.15 0.8 口QT ORSTA 0.8 -070E 06 08 0.4 04 0.4 r70019611829911 0.2 02 0.2 2 100020003000 40005000 6000 0 1000 2000 3000 40005000 6000 0 100020003000400050006000 Time Time Time Fig.7.Effect of w Fig.8. Effect of E[C]and E[B"] Fig.9.Effect of E[bwl]and E[pwl] VII.RELATED WORK introducing the connectivity layer,which,in fact,is a special A.Network Virtualization virtual network that provides a necessary geographic footprint, reliability,and performance.He et al.[28]proposed Davinci In networking literature,virtual private networks (VPNs), architecture,where resource allocation is dynamic and used overlay networks,and network virtualization deal with select- optimization theory to show that adaptive resource allocation ing nodes to construct logical paths.However,the differences are:(i)VPNs only need to determine the locations of logical can be stable and can maximize the aggregate performance across virtual networks. links while network virtualizaiton simultaneously considers locations of logical nodes and links [7,8];(ii)only link B.Virtual Network Embedding constraints are considered in VPNs while both link and node To cope with the NP-hardness of the VNE problem,re- constraints are considered in network virtualization [7,8]; searchers resorted to heuristics to reduce computational time. (iii)overlays are designed in the application layer on top Ricci et al.[6]considered only bandwidth constraints and of the network layer [4].The most relevant work in the proposed the Assign algorithm based on simulated annealing overlay networks is [24].where Fan et al.investigated the with the assumption that the substrate node can only be used dynamic topology configuration problem in service overlay by one virtual node.Lu et al.[9]developed a method for the networks.They first acquired general properties of the optimal VNE problem in a cost-efficient way and attempted to find reconfiguration topology by observing small cases,and then the best topology in a family of backbone-star topologies. used observations as heuristics to design algorithms for large-Zhu et al.[7]assumed that the substrate nodes and links scale cases of networks. have unlimited CPU and bandwidth resources and focused In network virtualization,Ishibashi et al.[25]envisioned on load balancing and on-demand assignments.Yu et al.[10] cognitive radio-based virtual wireless networks and tried to assumed that SN supports path splitting and proposed a two- make efficient use of residual wasted bandwidth of the primary stage online algorithm:firstly,map the virtual nodes greedily, service providers.Shiomoto et al.[26]developed a network then deal with link mapping based on the multi-commodity virtualization method to represent the resources in the optical flow problem.Lischka et al.[11]proposed a backtracking backbone network of the service network.Zhu et al.[27]tried algorithm based on subgraph isomorphism detection,but re- to lower the barrier for deploying wide-area services through stricted the length of the substrate paths.Chowdhury et al.[8] 2415TABLE III Algorithms in Comparison Notation Description ORS T A The entire framework, including opportunistic resource sharing, topology-aware ranking, and greedy node/link mapping ORS A partial framework, including opportunistic resource sharing, and greedy node/link mapping T A A partial framework, including topology-awareness, and greedy node/link mapping Greedy The traditional greedy embedding algorithm, including greedy node/link mapping 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA TA ORS Greedy Fig. 4. Acceptance ratio over time 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 CDF Node Utilization Ratio ORSTA TA ORS Greedy Fig. 5. CDF of node utilization ratios 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 CDF Link Utilization Ratio ORSTA TA ORS Greedy Fig. 6. CDF of link utilization ratios 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA(w1=0.3) ORSTA(w1=0.5) ORSTA(w1=0.7) ORSTA(w1=0.9) Fig. 7. Effect of w1 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA(E[Cv ]=E[Bv ]=05) ORSTA(E[Cv ]=E[Bv ]=10) ORSTA(E[Cv ]=E[Bv ]=15) ORSTA(E[Cv ]=E[Bv ]=20) Fig. 8. Effect of E[C v ] and E[B v ] 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA(E[bwl]=0.50,E[pwl]=0.15) ORSTA(E[bwl]=0.50,E[pwl]=0.05) ORSTA(E[bwl]=0.50,E[pwl]=0.25) ORSTA(E[bwl]=0.30,E[pwl]=0.15) ORSTA(E[bwl]=0.70,E[pwl]=0.15) Fig. 9. Effect of E[bwl] and E[pwl] VII. Related Work A. Network Virtualization In networking literature, virtual private networks (VPNs), overlay networks, and network virtualization deal with select￾ing nodes to construct logical paths. However, the differences are: (i) VPNs only need to determine the locations of logical links while network virtualizaiton simultaneously considers locations of logical nodes and links [7, 8]; (ii) only link constraints are considered in VPNs while both link and node constraints are considered in network virtualization [7, 8]; (iii) overlays are designed in the application layer on top of the network layer [4]. The most relevant work in the overlay networks is [24], where Fan et al. investigated the dynamic topology configuration problem in service overlay networks. They first acquired general properties of the optimal reconfiguration topology by observing small cases, and then used observations as heuristics to design algorithms for large￾scale cases of networks. In network virtualization, Ishibashi et al. [25] envisioned cognitive radio-based virtual wireless networks and tried to make efficient use of residual wasted bandwidth of the primary service providers. Shiomoto et al. [26] developed a network virtualization method to represent the resources in the optical backbone network of the service network. Zhu et al. [27] tried to lower the barrier for deploying wide-area services through introducing the connectivity layer, which, in fact, is a special virtual network that provides a necessary geographic footprint, reliability, and performance. He et al. [28] proposed DaVinci architecture, where resource allocation is dynamic and used optimization theory to show that adaptive resource allocation can be stable and can maximize the aggregate performance across virtual networks. B. Virtual Network Embedding To cope with the NP-hardness of the VNE problem, re￾searchers resorted to heuristics to reduce computational time. Ricci et al. [6] considered only bandwidth constraints and proposed the Assign algorithm based on simulated annealing with the assumption that the substrate node can only be used by one virtual node. Lu et al. [9] developed a method for the VNE problem in a cost-efficient way and attempted to find the best topology in a family of backbone-star topologies. Zhu et al. [7] assumed that the substrate nodes and links have unlimited CPU and bandwidth resources and focused on load balancing and on-demand assignments. Yu et al. [10] assumed that SN supports path splitting and proposed a two￾stage online algorithm: firstly, map the virtual nodes greedily, then deal with link mapping based on the multi-commodity flow problem. Lischka et al. [11] proposed a backtracking algorithm based on subgraph isomorphism detection, but re￾stricted the length of the substrate paths. Chowdhury et al. [8] 2415