虚拟网映射竞争算法设计与分析
|
摘要
对网络虚拟化技术中的虚拟网映射问题及其研究现状进行了介绍,针对虚拟节点映射已知且物理网不支持路径分割的虚拟网映射问题,提出以物理网提供商收益最大化为目标的虚拟网映射竞争算法,并给出了算法的竞争比分析。实验表明,所提出的算法能提高物理网资源的负载均衡度和利用率,从而提高了虚拟网构建请求的接受率和物理网提供商的收益。
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.
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.
引文
[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 Tutorials,2013,15(4):1888-1906
[3]李小玲,王怀民,丁博,等.虚拟网络映射问题研究及其进展[J].软件学报,2012,23(11):3009-3028
[4]Andersen D.Theoretical approaches to node assignment[OL].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,39(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 International 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,51(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,20(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,48(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 Embedding Through 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,35(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,26(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 Competitive Analysis[M].New York:Cambridge University Press,1998:1-19
[24]Jon Michael Kleinberg.Approximation algorithms for disjoint paths problems[OL].http://www.citeulike.org/user/djlin/article/271384
[2]Fischer A,Botero J F,Beck M T,et al.Virtual Network Embedding:A Survey[J].IEEE Communications Surveys and Tutorials,2013,15(4):1888-1906
[3]李小玲,王怀民,丁博,等.虚拟网络映射问题研究及其进展[J].软件学报,2012,23(11):3009-3028
[4]Andersen D.Theoretical approaches to node assignment[OL].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,39(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 International 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,51(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,20(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,48(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 Embedding Through 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,35(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,26(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 Competitive Analysis[M].New York:Cambridge University Press,1998:1-19
[24]Jon Michael Kleinberg.Approximation algorithms for disjoint paths problems[OL].http://www.citeulike.org/user/djlin/article/271384