吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (01): 165-171.

• 论文 • 上一篇    下一篇

基于优化的同构子图搜索的虚拟网络映射算法

魏晓辉, 邹磊, 李洪亮   

  1. 吉林大学 计算机科学与技术学院, 长春 130012
  • 收稿日期:2012-01-20 出版日期:2013-01-01 发布日期:2013-01-01
  • 通讯作者: 李洪亮(1983-),男,讲师,博士.研究方向:分布式系统,虚拟化.E-mail:lihongliang@jlu.edu.cn E-mail:lihongliang@jlu.edu.cn
  • 作者简介:魏晓辉(1972-),男,教授,博士生导师.研究方向:分布式系统,网格系统,网络安全.E-mail:weixh@jlu.edu.cn
  • 基金资助:

    国家自然科学基金项目(61170004);新世纪优秀人才支持计划项目(NCET-09-0428);深部探测技术与实验研究专项项目(SinoProbe-09-01).

Virtual network embedding algorithm based on improved sub-graph isomorphism search

WEI Xiao-hui, ZOU Lei, LI Hong-liang   

  1. College of Computer Science and Technology, Jilin University, Changchun 130012, China
  • Received:2012-01-20 Online:2013-01-01 Published:2013-01-01

PDF (PC)

603

摘要： 针对现有虚拟网络映射算法的不足,首先提出了一个综合考虑网络中节点资源需求(能力)和拓扑属性的节点资源能力评价方法,合理地评价节点资源能力,优化了虚拟节点的映射顺序;其次改进了虚拟节点映射时备选物理节点的选择过程,提高了虚拟链路映射质量;最后通过考虑物理网络子区域内的资源总量,优化了算法中初始资源分配区域的选择。实验结果表明:与已有的算法相比,本文映射算法在映射质量、长期平均收益、长期平均接收率、算法执行时间等方面均有明显提高。

关键词: 计算机应用, 虚拟网络, 映射算法, 同构子图搜索, 网络拓扑结构

Abstract: A new Virtual Network Embedding (VNE) algorithm is proposed, which improves the original sub-graph isomorphism search process, and overcomes the defects in existing VNE algorithm. First, a node resource evaluation method is proposed, which takes both node resource requirement (capability) and topology attribute into account, to improve the mapping order of the virtual nodes. Second, the algorithm improves the selection process of candidate substrate nodes when mapping the virtual nodes, which enhances the quality of virtual link mapping. Third, the algorithm improves the selection of resource allocation sub-area in substrate network by considering the total resource capability in the sub-area. Experiment results show that the proposed algorithm performs better in mapping quality, revenue, acceptance ratio and runtime compared with existing algorithms.

Key words: computer application, virtual network, mapping algorithm, sub-graph isomorphism search, network topology

中图分类号: 

  • TP393
[1] ChowdhuryN M M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping//INFOCOM 2009, IEEE, 2009: 783-791.

[2] Chowdhury N M M K, Boutaba R. Network virtualization: state of the art and research challenges[J]. IEEE Communications Magazine, 2009, 47(7):20-26.

[3] Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[4] Fan J, Ammar M. Dynamic topology configuration in service overlay networks: a study of reconfiguration policies//The 25th IEEE International Conference on Computer Communications, 2006:1-12.

[5] Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate. Department of Computer Science and Engineering, Washington University in St. Louis, Technical Report WUCSE-2006-35, 2006.

[6] Zhu Y, Ammar M. Algorithms for assigning substrate network resources to virtual network components//IEEE INFOCOM Proceedings, Barcelona, Spain, 2006:1-12.

[7] Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection//The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures Proceedings, Barcelona, Spain, 2009:81-88.

[8] Cordella L P, Foggia P, Sansone C, et al. A (sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2004, 26(10):1367-1372.

[9] Butt N, Chowdhury M, Boutaba R. Topology-awareness and re-optimization mechanism for virtual network embedding//The 9th International Ifip Tc 6 Networking Conference, Chennai, India, 2010:27-39.

[10] Zegura E, Calvert K, Bhattacharjee S. How to model an Internetwork?//IEEE INFOCOM Proceedings,San Francisco, CA, USA, 1996: 594-602.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发