|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|