proposed a VNE algorithm with better coordination between REFERENCES node mapping and link mapping based on linear programming [1]J.Turner and D.Taylor,"Diversifying the Internet,"in /EEE GLOBE- and deterministic/randomized rounding.but added location C0M2005,vol.2,2-22005,Pp.6Pp.-760. constraints to simplify the problem.Chowdhury et al.[13] [2]T.Anderson,L.Peterson,S.Shenker,and J.Turner,"Overcoming the Intemet impasse through virtualization,"Computer,vol.38,no.4.pp presented a policy-based decentralized inter-domain virtual 34-41,apml2005. network embedding framework and also designed a location- [3]N.Feamster,L.-X.Gao,and J.Rexford,"How to lease the Internet in aware VN request forwarding mechanism.Zhang et al.[20] your spare time,"ACM SIGCOMM Comput.Commun.Rev.,vol.37, no.1,Pp.61-642007. focused on flexibility and proposed a simulated annealing- [4]N.Chowdhury and R.Boutaba,"A survey of network virtualization." based algorithm to control the tradeoff between result accuracy Computer Nerworks,vol.54,no.5,pp.862-876,2010. [5]D.G.Andersen,"Theoretical approaches to node assignment,"Dec. and the running time of the embedding algorithm.Zhang et 2002,unpublished Manuscript. al.[18]investigated the opportunistic bandwidth sharing in a [6]R.Ricci,C.Alfeld,and J.Lepreau,"A solver for the network testbed single physical link among multiple virtual links from different mapping problem,"ACM SIGCOMM Comput.Commun.Rev..vol.33. VNs;however,in this paper,we study opportunistic resource no.2,pp.65-81,2003. [7]Y.Zhu and M.Ammar,"Algorithms for assigning substrate network sharing at the entire network level. resources to virtual network components,"in IEEE INFOCOM 2006. apri2006,Pp.1-12. C.Topology-Awareness in Virtual Network Mapping [8]N.Chowdhury,M.Rahman,and R.Boutaba,"Virtual network embed- ding with coordinated node and link mapping,"in IEEE INFOCOM To the best of our knowledge,there are only two research 2009,19-252009,Pp.783-791. [9]J.Lu and J.Turner,"Efficient mapping of virtual networks onto a shared articles [12,14]that incorporate topology into virtual network substrate,"Washington Universiry,Tech.Rep.WUCSE-2006-35,2006. embedding.Butt et al.[14]differentiated substrate resources [10]M.Yu,Y.Yi,J.Rexford,and M.Chiang."Rethinking virtual network by introducing scaling factors:Critical Index,which measures embedding:substrate support for path splitting and migration,"ACM the likelihood of a residual substrate network partition due to SIGCOMM Comput.Commun.Rev,vol.38.no.2.pp.17-29,2008. [11]J.Lischka and H.Karl,"A virtual network mapping algorithm based on its unavailability,and Popularity Index,which measures "how subgraph isomorphism detection."in ACM VISA 2009.2009.pp.81-88. many different VNs are affected when a link or a node is [12]X.Cheng.S.Su,Z.Zhang.H.Wang.F.Yang.Y.Luo,and J.Wang. unavailable".Cheng et al.[12]formulated a Markov random "Virtual network embedding through topology-aware node ranking, SIGCOMM Comput.Commun.Rev.,vol.41.pp.38-47,April 2011. walk model to compute the topology-aware resource ranking [13]M.Chowdhury,F.Samuel,and R.Boutaba,"Polyvine:policy-based vir- of nodes in a substrate network;however,in this paper,we tual network embedding across multiple domains,"in ACM S/GCOMM VISA 2010.New York,NY,USA:ACM,2010,pp.49-56 observe that we only need to consider a walk from a substrate [14]N.But.N.Chowdhury,and R.Boutaba,"Topology-awareness and re- node to itself or one of its neighbors because the impact is optimization mechanism for virtual network embedding,"in Nerworking, recursive in a Markov chain 2010,pp.27-39 [15]I.Houidi,W.Louati,D.Zeghlache,P.Papadimitriou,and L.Mathy, "Adaptive virtual network provisioning,"in ACM S/GCOMM VISA 2010. VIII.CONCLUSIONS ACM,2010,Pp.41-48. This paper re-examines the virtual network mapping prob- [16]Auckland Data Trace.http://pma.nlanr.net/traces/long/auck2.html. [17刀Q.Zhao and B.Sadler,.“A survey of dynamic spectrum access,.”EEE lem in network virtualization from two novel perspectives, Signal Processing Magazine..vol.24.no.3,pp.79-89.May 2007. i.e.,opportunistic resource sharing and topology-aware node [18]S.Zhang.Z.Qian,B.Tang.J.Wu,and S.Lu,"Opportunistic band- ranking,which are incorporated into our proposed framework, width sharing for virtual network mapping."in IEEE Globecom 2011. December 2011. ORSTA.ORS TA contains three main parts,opportunistic [19]H.Schwarz,D.Marpe,and T.Wiegand,"Overview of the scalable video resource sharing-based local time slot assignment,estimation coding extension of the h.264/avc standard,"IEEE TCSVT,vol.17,no.9. of residual resources and topology-aware node ranking.The Pp.1103-1120,sept.2007. [20]S.Zhang.Z.Qian,S.Guo,and S.Lu,"FELL:A flexible virtual network effectiveness of our framework is confirmed by extensive embedding algorithm with guaranteed load balancing."in IEEE ICC simulations.We are currently seeking the proof of the NP- 2011,June2011. [21]L.Page,S.Brin,R.Motwani,and T.Winograd,"The pagerank citation Completeness of Problem 1 and are exploring methods of ranking:Bringing order to the web."Stanford InfoLab,Technical Report scheduling packets when a collision occurs in a time slot. 1999-66.November 1999. [22]"Markov chain,"http:/en.wikipedia.org/wiki/Markov_chain. [23]V.V.Vazirani.Approximation Algorithms.Berlin:Springer.2003. ACKNOWLEDGMENTS (24]J.Fan and M.H.Ammar,"Dynamic topology configuration in service We would like to thank Yitong Yin for his Randomized overlay networks:A study of reconfiguration policies,"in IEEE INFO- COM2006,april2006,pp.1-12. Algorithms and Combinatorics courses,and the anonymous [25]B.Ishibashi.N.Bouabdallah,and R.Boutaba,"Qos performance reviewers for their insightful suggestion. analysis of cognitive radio-based virtual wireless networks,"in IEEE This work is supported in part by the National NSF NF0C0M2008,april2008,pp.2423-2431. [26]K.Shiomoto,I.Inoue,and E.Oki,"Network virtualization in high-speed of China under Grant No.61073028 and No.61021062: huge-bandwidth optical circuit switching network,"in /EEE INFOCOM Key Project of Jiangsu Research Program under Grant 2008 Workshops,april 2008.pp.1-6. No.BE2010179:Jiangsu Natural Science Foundation under [27]Y.Zhu,R.Zhang-Shen,S.Rangarajan,and J.Rexford,"Cabernet: connectivity architecture for better network services,"in ACM CoNEXT Grant No.BK2011510;the National 973 Basic Research 2008. New York,NY,USA:ACM,2008,pp.64:1-64:6. Program of China under Grant No.2009CB320705 and [28]J.He,R.Zhang-Shen,Y.Li,C.-Y.Lee,J.Rexford,and M.Chiang. "Davinci:dynamically adaptive virtual networks for a customized inter- No.2011CB302800;US NSF grants ECCS 1128209,CNS net,"in ACM CoNEXT 2008.ACM.2008.pp.15:1-15:12. 1065444.CCF1028167.CNS0948184.and CC℉0830289. 2416proposed a VNE algorithm with better coordination between node mapping and link mapping based on linear programming and deterministic/randomized rounding, but added location constraints to simplify the problem. Chowdhury et al. [13] presented a policy-based decentralized inter-domain virtual network embedding framework and also designed a location￾aware VN request forwarding mechanism. Zhang et al. [20] focused on flexibility and proposed a simulated annealing￾based algorithm to control the tradeoff between result accuracy and the running time of the embedding algorithm. Zhang et al. [18] investigated the opportunistic bandwidth sharing in a single physical link among multiple virtual links from different VNs; however, in this paper, we study opportunistic resource sharing at the entire network level. C. Topology-Awareness in Virtual Network Mapping To the best of our knowledge, there are only two research articles [12, 14] that incorporate topology into virtual network embedding. Butt et al. [14] differentiated substrate resources by introducing scaling factors: Critical Index, which measures the likelihood of a residual substrate network partition due to its unavailability, and Popularity Index, which measures “how many different VNs are affected when a link or a node is unavailable”. Cheng et al. [12] formulated a Markov random walk model to compute the topology-aware resource ranking of nodes in a substrate network; however, in this paper, we observe that we only need to consider a walk from a substrate node to itself or one of its neighbors because the impact is recursive in a Markov chain. VIII. Conclusions This paper re-examines the virtual network mapping prob￾lem in network virtualization from two novel perspectives, i.e., opportunistic resource sharing and topology-aware node ranking, which are incorporated into our proposed framework, ORS T A. ORS T A contains three main parts, opportunistic resource sharing-based local time slot assignment, estimation of residual resources and topology-aware node ranking. The effectiveness of our framework is confirmed by extensive simulations. We are currently seeking the proof of the NP￾Completeness of Problem 1 and are exploring methods of scheduling packets when a collision occurs in a time slot. Acknowledgments We would like to thank Yitong Yin for his Randomized Algorithms and Combinatorics courses, and the anonymous reviewers for their insightful suggestion. This work is supported in part by the National NSF of China under Grant No. 61073028 and No. 61021062; Key Project of Jiangsu Research Program under Grant No.BE2010179; Jiangsu Natural Science Foundation under Grant No. BK2011510; the National 973 Basic Research Program of China under Grant No. 2009CB320705 and No. 2011CB302800; US NSF grants ECCS 1128209, CNS 1065444, CCF 1028167, CNS 0948184, and CCF 0830289. References [1] J. Turner and D. Taylor, “Diversifying the Internet,” in IEEE GLOBE￾COM 2005, vol. 2, 2-2 2005, pp. 6 pp. –760. [2] T. Anderson, L. Peterson, S. Shenker, and J. Turner, “Overcoming the Internet impasse through virtualization,” Computer, vol. 38, no. 4, pp. 34 – 41, april 2005. [3] N. Feamster, L.-X. Gao, and J. Rexford, “How to lease the Internet in your spare time,” ACM SIGCOMM Comput. Commun. Rev., vol. 37, no. 1, pp. 61–64, 2007. [4] N. Chowdhury and R. Boutaba, “A survey of network virtualization,” Computer Networks, vol. 54, no. 5, pp. 862–876, 2010. [5] D. G. Andersen, “Theoretical approaches to node assignment,” Dec. 2002, unpublished Manuscript. [6] R. Ricci, C. Alfeld, and J. Lepreau, “A solver for the network testbed mapping problem,” ACM SIGCOMM Comput. Commun. Rev., vol. 33, no. 2, pp. 65–81, 2003. [7] Y. Zhu and M. Ammar, “Algorithms for assigning substrate network resources to virtual network components,” in IEEE INFOCOM 2006, april 2006, pp. 1 –12. [8] N. Chowdhury, M. Rahman, and R. Boutaba, “Virtual network embed￾ding with coordinated node and link mapping,” in IEEE INFOCOM 2009, 19-25 2009, pp. 783 –791. [9] J. Lu and J. Turner, “Efficient mapping of virtual networks onto a shared substrate,” Washington University, Tech. Rep. WUCSE-2006-35, 2006. [10] M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking virtual network embedding: substrate support for path splitting and migration,” ACM SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 17–29, 2008. [11] J. Lischka and H. Karl, “A virtual network mapping algorithm based on subgraph isomorphism detection,” in ACM VISA 2009, 2009, pp. 81–88. [12] X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, “Virtual network embedding through topology-aware node ranking,” SIGCOMM Comput. Commun. Rev., vol. 41, pp. 38–47, April 2011. [13] M. Chowdhury, F. Samuel, and R. Boutaba, “Polyvine: policy-based vir￾tual network embedding across multiple domains,” in ACM SIGCOMM VISA 2010. New York, NY, USA: ACM, 2010, pp. 49–56. [14] N. Butt, N. Chowdhury, and R. Boutaba, “Topology-awareness and re￾optimization mechanism for virtual network embedding,” in Networking, 2010, pp. 27–39. [15] I. Houidi, W. Louati, D. Zeghlache, P. Papadimitriou, and L. Mathy, “Adaptive virtual network provisioning,” in ACM SIGCOMM VISA 2010. ACM, 2010, pp. 41–48. [16] Auckland Data Trace. http://pma.nlanr.net/traces/long/auck2.html. [17] Q. Zhao and B. Sadler, “A survey of dynamic spectrum access,” IEEE Signal Processing Magazine,, vol. 24, no. 3, pp. 79–89, May 2007. [18] S. Zhang, Z. Qian, B. Tang, J. Wu, and S. Lu, “Opportunistic band￾width sharing for virtual network mapping,” in IEEE Globecom 2011, December 2011. [19] H. Schwarz, D. Marpe, and T. Wiegand, “Overview of the scalable video coding extension of the h.264/avc standard,” IEEE TCSVT, vol. 17, no. 9, pp. 1103 –1120, sept. 2007. [20] S. Zhang, Z. Qian, S. Guo, and S. Lu, “FELL: A flexible virtual network embedding algorithm with guaranteed load balancing,” in IEEE ICC 2011, June 2011. [21] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Technical Report 1999-66, November 1999. [22] “Markov chain,” http://en.wikipedia.org/wiki/Markov chain. [23] V. V. Vazirani, Approximation Algorithms. Berlin: Springer, 2003. [24] J. Fan and M. H. Ammar, “Dynamic topology configuration in service overlay networks: A study of reconfiguration policies,” in IEEE INFO￾COM 2006, april 2006, pp. 1 –12. [25] B. Ishibashi, N. Bouabdallah, and R. Boutaba, “Qos performance analysis of cognitive radio-based virtual wireless networks,” in IEEE INFOCOM 2008, april 2008, pp. 2423 –2431. [26] K. Shiomoto, I. Inoue, and E. Oki, “Network virtualization in high-speed huge-bandwidth optical circuit switching network,” in IEEE INFOCOM 2008 Workshops, april 2008, pp. 1 –6. [27] Y. Zhu, R. Zhang-Shen, S. Rangarajan, and J. Rexford, “Cabernet: connectivity architecture for better network services,” in ACM CoNEXT 2008. New York, NY, USA: ACM, 2008, pp. 64:1–64:6. [28] J. He, R. Zhang-Shen, Y. Li, C.-Y. Lee, J. Rexford, and M. Chiang, “Davinci: dynamically adaptive virtual networks for a customized inter￾net,” in ACM CoNEXT 2008. ACM, 2008, pp. 15:1–15:12. 2416