Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci    0, Vol. Issue () : 446-457    https://doi.org/10.1007/s11704-013-2108-4
Topology-aware virtual network embedding based on closeness centrality
Zihou WANG1(), Yanni HAN1, Tao LIN1, Yuemei XU1, Song CI1,2, Hui TANG1
1. High Performance Network Laboratory, Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China; 2. Department of Computer and Electronics Engineering, University of Nebraska-Lincoln, NE 68182, USA
 Download: PDF(498 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): WANG Zihou,Email:wangzh@hpnl.ac.cn   
Issue Date: 01 June 2013
 Cite this article:   
Zihou WANG,Yanni HAN,Tao LIN, et al. Topology-aware virtual network embedding based on closeness centrality[J]. Front Comput Sci, 0, (): 446-457.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-2108-4
https://academic.hep.com.cn/fcs/EN/Y0/V/I/446
1 Anderson T, Peterson L, Shenker S, Turner J. Overcoming the internet impasse through virtualization. Computer , 2005, 38(4): 34-41
doi: 10.1109/MC.2005.136
2 Turner J, Taylor D. Diversifying the internet. In: Proceedings of the 2005 IEEE Global Telecommunications Conference . 2005, 6-12
doi: 10.1109/GLOCOM.2005.1577741
3 Chowdhury N, Boutaba R. A survey of network virtualization. Computer Networks , 2010, 54(5): 862-876
doi: 10.1016/j.comnet.2009.10.017
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
doi: 10.1145/1151659.1159916
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
doi: 10.1145/956981.956988
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
doi: 10.1145/1355734.1355737
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
doi: 10.1109/TNET.2011.2159308
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
doi: 10.1145/1592648.1592662
14 Houidi I, Louati W, Ben Ameur W, Zeghlache D. Virtual network provisioning across multiple substrate networks. Computer Networks , 2011, 55(4): 1011-1023
doi: 10.1016/j.comnet.2010.12.011
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
doi: 10.1109/TEST.2011.6139139
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
doi: 10.1145/1971162.1971168
17 Freeman L. Centrality in social networks conceptual clarification. Social networks , 1979, 1(3): 215-239
doi: 10.1016/0378-8733(78)90021-7
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
doi: 10.1038/30918
20 Barabási A, Albert R. Emergence of scaling in random networks. Science , 1999, 286(5439): 509-512
doi: 10.1126/science.286.5439.509
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
doi: 10.1145/321992.321993
24 Eppstein D. Finding the k shortest paths. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science . 1994, 154-165
doi: 10.1109/SFCS.1994.365697
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
doi: 10.1109/LCOMM.2003.814708
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
doi: 10.1145/1198255.1198265
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
doi: 10.1145/1544012.1544076
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
doi: 10.1109/MIC.2011.128
30 Khan A, Zugenmaier A, Jurca D, Kellerer W. Network virtualization: a hypervisor for the internet? IEEE Communications Magazine , 2012, 50(1): 136-143
doi: 10.1109/MCOM.2012.6122544
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
doi: 10.1145/380752.380830
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
doi: 10.1109/TNET.2002.803918
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
doi: 10.1109/LCOMM.2012.030912.120082
[1] Tianming ZHANG, Jie ZHAO, Cibo YU, Lu CHEN, Yunjun GAO, Bin CAO, Jing FAN, Ge YU. Labeling-based centrality approaches for identifying critical edges on temporal graphs[J]. Front. Comput. Sci., 2025, 19(2): 192601-.
[2] Suyu MEI. A framework combines supervised learning and dense subgraphs discovery to predict protein complexes[J]. Front. Comput. Sci., 2022, 16(1): 161901-.
[3] Zonghua LIU , Xiaoyan WU , Pak-Ming HUI , . An alternative approach to characterize the topology of complex networks and its application in epidemic spreading[J]. Front. Comput. Sci., 2009, 3(3): 324-334.
[4] Lili RONG , Tianzhu GUO , Jiyong ZHANG , . A new centrality measure based on sub-tree[J]. Front. Comput. Sci., 2009, 3(3): 356-360.
[5] Weifeng PAN , Yutao MA , Jing LIU , Yeyi QIN , Bing LI , . Class structure refactoring of object-oriented softwares using community detection in dependency networks[J]. Front. Comput. Sci., 2009, 3(3): 396-404.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed