Topology-aware virtual network embedding based on closeness centrality

Abstract

Network virtualization aims to provide a way to overcome ossification of the Internet. However, making efficient use of substrate resources requires effective techniques for embedding virtual networks: mapping virtual nodes and virtual edges onto substrate networks. Previous research has presented several heuristic algorithms, which fail to consider that the attributes of the substrate topology and virtual networks affect the embedding process. In this paper, for the first time, we introduce complex network centrality analysis into the virtual network embedding, and propose virtual network embedding algorithms based on closeness centrality. Due to considering of the attributes of nodes and edges in the topology, our studies are more reasonable than existing work. In addition, with the guidance of topology quantitative evaluation, the proposed network embedding approach largely improves the network utilization efficiency and decreases the embedding complexity. We also investigate our algorithms on real network topologies (e.g., AT&T, DFN) and random network topologies. Experimental results demonstrate the usability and capability of the proposed approach.

Keywords

network virtualization / virtual network embedding / complex networks / closeness centrality

References

[1] Anderson T, Peterson L, Shenker S, Turner J. Overcoming the internet impasse through virtualization. Computer, 2005, 38(4): 34-41

[2] Turner J, Taylor D. Diversifying the internet. In: Proceedings of the 2005 IEEE Global Telecommunications Conference. 2005, 6-12

[3] Chowdhury N, Boutaba R. A survey of network virtualization. Computer Networks, 2010, 54(5): 862-876

[4] Guo C, Lu G, Wang H, Yang S, Kong C, Sun P, Wu W, Zhang Y. Secondnet: a data center network virtualization architecture with bandwidth guarantees. In: Proceedings of the 6th International Conference. 2010, 1-12

[5] Bavier A, Feamster N, Huang M, Peterson L, Rexford J. In vini veritas: realistic and controlled network experimentation. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 3-14

[6] The global environment for network innovations (GENI) project. http://www.geni.net

[7] The FP7 4WARD project. http://www.4ward-project.eu

[8] Ricci R, Alfeld C, Lepreau J. A solver for the network testbed mapping problem. ACM SIGCOMM Computer Communication Review, 2003 33(2): 65-81

[9] Lu J, Turner J. Effcient mapping of virtual networks onto a shared substrate. Washington University Technical Report, 2006

[10] Zhu Y, Ammar M. Algorithms for assigning substrate network resources to virtual network components. In: Proceedings of the 25th IEEE International Conference on Computer Communications. 2006, 1-12

[11] Yu M, Yi Y, Rexford J, Chiang M. Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29

[12] Chowdhury M, Rahman M, Boutaba R. ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Transactions on Networking, 2012, 20(1): 206-219

[13] Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection. In: Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. 2009, 81-88

[14] Houidi I, Louati W, Ben Ameur W, Zeghlache D. Virtual network provisioning across multiple substrate networks. Computer Networks, 2011, 55(4): 1011-1023

[15] Zhang S, Qian Z, Tang B, Wu J, Lu S. Opportunistic bandwidth sharing for virtual network mapping. In: Proceedings of the 2011 IEEE Global Telecommunications Conference. 2011, 1-5

[16] Cheng X, Su S, Zhang Z, Wang H, Yang F, Luo Y, Wang J. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 38-47

[17] Freeman L. Centrality in social networks conceptual clarification. Social networks, 1979, 1(3): 215-239

[18] Freeman L. The development of social network analysis: A study in the sociology of science. Empirical Press Vancouver. 2004

[19] Watts D, Strogatz S. Collective dynamics of aösmall-worldaŕrnetworks. Nature, 1998, 393(6684): 440-442

[20] Barabási A, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-512

[21] Li D. Artificial intelligence with uncertainty. IEEE Computer Society. 2004

[22] Gan W W. A hierarchical clustering method based on data fields. Chinese Journal of Electronics, 2006, 34(2): 258 -262

[23] Johnson D. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM (JACM), 1977, 24(1): 1-13

[24] Eppstein D. Finding the k shortest paths. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994, 154-165

[25] Zegura E, Calvert K, Bhattacharjee S. How to model an internetwork. In: Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies. 1996, 594-602

[26] Heckmann O, Piringer M, Schmitt J, Steinmetz R. Generating realistic isp-level network topologies. IEEE Communications Letters, 2003, 7(7): 335-336

[27] Feamster N, Gao L, Rexford J. How to lease the internet in your spare time. ACM SIGCOMM Computer Communication Review, 2007, 37(1): 61-64

[28] Zhu Y, Zhang-Shen R, Rangarajan S, Rexford J. Cabernet: connectivity architecture for better network services. In: Proceedings of the 2008 ACM CoNEXT Conference. 2008, 1-6

[29] Lemay M, Nguyen K, St-Arnaud B, Cheriet M. Convergence of cloud computing and network virtualization: Towards a zero-carbon network. IEEE Internet Computing Magazine, 2011, 16(6): 51-59

[30] Khan A, Zugenmaier A, Jurca D, Kellerer W. Network virtualization: a hypervisor for the internet? IEEE Communications Magazine, 2012, 50(1): 136-143

[31] Gupta A, Kleinberg J, Kumar A, Rastogi R, Yener B. Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. 2001, 389-398

[32] Duffield N, Goyal P, Greenberg A, Mishra P, Ramakrishnan K, Merwe V. d J. Resource management with hoses: point-to-cloud services for virtual private networks. IEEE/ACM Transactions on Networking, 2002, 10(5): 679-692

[33] Botero J, Hesselbach X, Duelli M, Schlosser D, Fischer A, De Meer H. Energy efficient virtual network embedding. IEEE Communications Letters, 2012, 16(5): 756-759

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg