Computer Science ›› 2015, Vol. 42 ›› Issue (2): 33-38.doi: 10.11896/j.issn.1002-137X.2015.02.007

Previous Articles     Next Articles

Design and Analysis of Virtual Network Mapping Competitive Algorithms

YU Jian-jun and WU Chun-ming   

  • Online:2018-11-14 Published:2018-11-14

Abstract: This paper reviewed the virtual network mapping problem in network visualization area and the current research progress for this problem.For the virtual network mapping problem with known virtual node mapping but no support of path splitting by physical network,this paper proposed a virtual network mapping competitive algorithm aiming at maximizing the profit of physical network provider.This paper also provided the competitive analysis of the algorithm and the experiment result shows that the proposed algorithm increases the load balancing metric and utilization of physical network resource,and hence can improve the acceptance ratio of virtual network construction request and profit of physical network provider.

Key words: Virtual network mapping,Link mapping,Primal dual approach,Competitive algorithms

[1] Chowdhury N,Boutaba R.A survey of network virtualization[J].Computer Networks,2010,54(5):862-876
[2] Fischer A,Botero J F,Beck M T,et al.Virtual Network Embedding:A Survey[J].IEEE Communications Surveys and Tuto-rials,2013,15(4):1888-1906
[3] 李小玲,王怀民,丁博,等.虚拟网络映射问题研究及其进展[J].软件学报,2012,23(11):3009-3028
[4] Andersen D.Theoretical approaches to node assignment.http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps,2002
[5] Yu M,Yi Y,Rexford J,et al.Rethinking virtual network embedding:Substrate Support for path splitting and migration[J].ACM SIGCOMM on Computer Communication Review,2008,38(2):17-29
[6] Szeto W,Iraqi Y,Boutaba R.A multi-Commodity flow based approach to virtual network resource allocation[C]∥Proceedings of the IEEE Global Telecommunications Conference.San Francisco,USA,2003:3004-3008
[7] 姜明,王保进,吴春明.网络虚拟化与虚拟网映射算法研究[J].电子学报,2011,9(6):1315-1320
[8] Even G,Medina M,Schaffrath G,et al.Competitive and Deterministic Embeddings of Virtual Networks[J].Theoretical Computer Science,2013,496:184-194
[9] Hou Y,Zafer M,Lee K,et al.On the mapping between logical and physical topologies[C]∥Proceedings of the 1st Internatio-nal Conference on Communication Systems and Networks(COMSNETS’09).Bangalore India,2009:483-492
[10] Zhu Y,Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]∥IEEE International Conference on Computer Communications (INFOCOM).Barcelona,Spain,2006:1-12
[11] Botero J F,Hesselbach X,Fischer A,et al.Optimal mapping of virtual networks with hidden hops[J].Telecommjunications Systems,2012,1(4):273-282
[12] Mosharaf Kablr Chowdhury N M,Muntasir Raihan R,Raouf B.ViNEYard:Virtual network embedding algorithms with coordinated node and link mapping[J].IEEE/ACM Transactions on Networking,2012,0(1):206-219
[13] Zhang S,Qian Z Z,Wu J,et al.An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks[C]∥IEEE International Conference on Computer Communications (INFOCOM).Orlando,USA,2012:2408-2416
[14] 李小玲,郭长国,李小勇,等.一种基于约束优化的虚拟网络映射方法[J].计算机研究与发展,2012,8(9):1601-1610
[15] Jens L,Holger K.A virtual network mapping algorithm based on subgraph isomorphism detection[C]∥Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures.Barcelona,Spain,2009:81-88
[16] Cheng X,Su S,Zhang Z B.Virtual Network EmbeddingThrough Topology-Aware Node Ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):39-47
[17] Alkminm G P,Batista D M,Fonseca N L S.Optimal mapping of virtual networks[C]∥Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM’11).Houston,USA,2011:1-6
[18] Hu Q,Wang Y,Cao X J.Resolve the virtual network embedding problem:A column generation approach[C]∥Proceedings IEEE INFOCOM.Turin,Italy,2013:410-41488
[19] 刘新刚,怀进鹏,高庆一,等.一种保持结点紧凑的虚拟网络映射方法[J].计算机学报,2012,5(12):2492-2504
[20] Zhang Z B,Cheng X,Su S,et al.A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J].International Journal of Communication Systems,2013,6(8):1054-1073
[21] 黄彬彬,林荣恒,彭凯,等.基于粒子群优化的负载均衡的虚拟网络映射[J].电子与信息学报,2013,35(7):1753-1759
[22] Chang X L,Mi X M,Muppala J K.Performance evaluation of artificial intelligence algorithms for virtual network embedding[J].Engineering Applications of Artificial Intelligence,2013,26(10):2540-2550
[23] Borodin A,Ei Yaniv R.Online Computation and CompetitiveAnalysis[M].New York:Cambridge University Press,1998:1-19
[24] Jon Michael Kleinberg.Approximation algorithms for disjointpaths problems.http://www.citeulike.org/user/djlin/article/271384

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!