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

Previous Articles     Next Articles

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)

598

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

CLC Number: 

  • 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] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd