基于二分图K优完美匹配的虚拟网映射算法设计

余建军; 吴春明

doi:10.3969/j.issn.1000-0801.2014.02.009

您当前的位置：

首页 >

文章列表页 >

基于二分图K优完美匹配的虚拟网映射算法设计

研究与开发 | 更新时间：2024-06-05

- 基于二分图K优完美匹配的虚拟网映射算法设计
- Design of Virtual Network Mapping Algorithm Based on K-Best Perfect Matchings of Bipartite Graph
- 电信科学 2014年30卷第2期页码：70-75
- 作者机构：
  
  1. 衢州职业技术学院衢州 324000
  2. 浙江大学人工智能研究所杭州 310027
- 作者简介：
  
  [ "余建军，男，衢州职业技术学院副教授、信息工程学院副院长，主要研究方向为网络虚拟化技术、光网络技术和算法设计与分析等。" ]
  [ "吴春明，男，博士，浙江大学教授、博士生导师，主要研究方向为面向服务提供的大规模可重构柔性网络构建技术、计算机网络QoS、三网融合体系结构和网络虚拟化等。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61070157);国家自然科学基金资助项目(61070213);国家重点基础研究发展计划（“973”计划）基金资助项目;The National Basic Research Program of China（973 Program）(2012CB315900);浙江省教育厅科研项目(Y201225106)
- DOI：10.3969/j.issn.1000-0801.2014.02.009
  中图分类号：
- 网络出版日期：2014-02，
  
  纸质出版日期：2014-02-20
- 稿件说明：
移动端阅览
余建军, 吴春明. 基于二分图K优完美匹配的虚拟网映射算法设计[J]. 电信科学, 2014,30(2):70-75.

Jianjun Yu, Chunming Wu. Design of Virtual Network Mapping Algorithm Based on K-Best Perfect Matchings of Bipartite Graph[J]. Telecommunication science, 2014, 30(2): 70-75.
余建军, 吴春明. 基于二分图K优完美匹配的虚拟网映射算法设计[J]. 电信科学, 2014,30(2):70-75. DOI： 10.3969/j.issn.1000-0801.2014.02.009.

Jianjun Yu, Chunming Wu. Design of Virtual Network Mapping Algorithm Based on K-Best Perfect Matchings of Bipartite Graph[J]. Telecommunication science, 2014, 30(2): 70-75. DOI： 10.3969/j.issn.1000-0801.2014.02.009.

摘要

为提高虚拟节点映射的可行性，基于可行性检验定理和用于衡量节点可用性的节点等级指标，设计了基于二分图K优完美匹配的以降低映射代价为目标的虚拟网映射迭代算法。实验表明，所提出的算法能提高虚拟网构建请求接受率和虚拟网构建收益代价比，从而提高物理网提供商的收益。

Abstract

To improve the feasibility of virtual node mapping，grounded on feasibility test theorem and node rank indicators used to measure node availability，the virtual network mapping iterative algorithm based on K-best perfect matchings of bipartite graph was proposed，aiming at reducing mapping cost.Experiment shows that the proposed algorithm increases virtual network construction request acceptance ratio and benefit cost ratio，and hence can improve profit of physical network service provider.

关键词

Keywords

references

Chowdhury N M M K ， Boutaba R . A survey of network virtualization . Computer Networks ， 2010 ， 54 （ 5 ）： 862 ～ 876

Fischer A ， Botero J F ， Beck M T ， et al . Virtual network embedding：a survey . IEEE Communications Surveys and Tutorials ， 2013 ， 15 （ 4 ）： 1888 ～ 1906

Andersen D G . Theoretical approaches to node assignment . http://www.cs.cmu.edu/～dga/papers/andersen-assign.ps http://www.cs.cmu.edu/～dga/papers/andersen-assign.ps ， 2002

Yu M ， Yi Y ， Rexford J ， et al . Rethinking virtual network embedding：substrate support for path splitting and migration . ACM SIGCOMM on Computer Communication Review ， 2008 ， 38 （ 2 ）： 17 ～ 29

Hou Y ， Zafer M ， Lee K ， et al . On the mapping between logical and physical topologies . Proceedings of the 1st International Conference on Communication Systems and Networks （COMSNETS’09）， Bangalore，India ， 2009 ： 483 ～ 492

Zhu Y ， Ammar M . Algorithms for assigning substrate network resources to virtual network components . IEEE International Conference on Computer Communications（INFOCOM）， Barcelona，Spain ， 2006 ： 1 ～ 12

Botero J F ， Hesselbach X ， Fischer A ， et al . Optimal mapping of virtual networks with hidden hops . Telecommunication Systems ， 2012 ， 51 （ 4 ）： 273 ～ 282

Chowdhury N M M K ， Rahman M R ， Boutaba R . ViNEYard：virtual network embedding algorithms with coordinated node and link mapping . IEEE/ACM Transactions on Networking ， 2012 ， 20 （ 1 ）： 206 ～ 219

Zhang S ， Qian TZ Z ， Wu J ， et al . An opportunistic resource sharing and topology-aware mapping framework for virtual networks . IEEE International Conference on Computer Communications （INFOCOM）， Orlando，Florida，USA ， 2012 ： 2408 ～ 2416

Jens L ， Holger K . A virtual network mapping algorithm based on subgraph isomorphism detection . Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures ， Barcelona，Spain ， 2009 ： 81 ～ 88

Cheng X ， Su S ， Zhang Z B . Virtual network embedding through topology-aware node ranking . ACM SIGCOMM Computer Communication Review ， 2011 ， 41 （ 2 ）： 39 ～ 47

Alkmim G P ， Batista D M ， Fonseca N L S . Optimal mapping of virtual networks . Proceedings of the IEEE Global Telecommunications Conference （GLOBECOM’11）， Houston，Texax，USA ， 2011 ： 1 ～ 6

刘新刚，怀进鹏，高庆一等 . 一种保持节点紧凑的虚拟网络映射方法 . 计算机学报， 2012 ， 35 （ 12 ）： 2492 ～ 2504

Zhang Z B ， Cheng X ， Su S ， et al . A unified enhanced particle swarm optimization- based virtual network embedding algorithm . International Journal of Communication Systems ， 2012 （ 2 ）

朱强，王慧强，吕宏武等 . VNE-AFS：基于人工鱼群的网络虚拟化映射算法 . 通信学报， 2012 ， 33 （ Z1 ）： 170 ～ 177

黄彬彬，林荣恒，彭凯等 . 基于粒子群优化的负载均衡的虚拟网络映射 . 电子与信息学报， 2013 ， 35 （ 7 ）： 1753 ～ 1759

Chegireddy C R ， Hamacher H W . Algorithms for finding K-best perfect matchings . Discrete Applied Mathematics ， 1987 ， 18 （ 2 ）： 155 ～ 165

， Lovász L ， Plummer M D . Matching Theory . North Holland ： Elsevier Science Publishers ， 1985

王海英 . 图论算法及其MATLAB实现 . 北京：北京航空航天大学出版社， 2010

浏览量

659

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据