Computer Science ›› 2020, Vol. 47 ›› Issue (7): 236-242.doi: 10.11896/jsjkx.190600022

• Computer Network • Previous Articles     Next Articles

Virtual Network Embedding Algorithm Based on Topology Comprehensive Evaluation and Weight Adaptation

SHI Chao-wei1, MENG Xiang-ru2, MA Zhi-qiang2, HAN Xiao-yang1   

  1. 1 Schoolof Graduate,Air Force Engineering University,Xi’an 710051,China
    2 School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China
  • Received:2019-06-05 Online:2020-07-15 Published:2020-07-16
  • About author:SHI Chao-wei,born in 1996,postgra-duate.His main research interests include network virtualization and so on.
    MENG Xiang-ru,born in 1963,Ph.D,professor,Ph.D supervisor.His main research interests include next generation internet and cyber security.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61873277)

Abstract: The existing virtual network embedding algorithms do not consider the topological features of nodes comprehensively,the evaluation method of nodes is relative simple and the weights cannot be adaptively adjusted according to the network.To solve these problems,a virtual network embedding algorithm based on topology comprehensive evaluation and weight adaptation is proposed.In the node embedding stage,by considering the centrality,proximity and adjacent aggregation of nodes,this paper establishes a node multi-metric evaluation model combined with the node resource properties such as the node CPU and the sum of adjacent bandwidth.The weights are adjusted adaptively according to the change of network environment by using the entropy weight method.Simulation results show that compared with the latest and classical virtual network embedding algorithms,the acceptance ratio of the proposed algorithm is improved by 2%~23%,and the long-term average revenue-to-cost ratio is increased by 3%~17%.Moreover,the proposed algorithm can maintain good performance for different types of virtual network requests with different resource requirements.

Key words: Virtual network embedding, Topology comprehensive evaluation, Weight adaptation, Regional aggregation, Entropy weight method

CLC Number: 

  • TP393
[1] LI Z F,LU Z B,DENGS H,et al.Self-Adaptive Virtual Network EmbeddingAlgorithmBased on Software-Defined Networks[J].IEEE Transactions on Network and Service Management,2019,16(1):362-373.
[2] CAO H T,HU H,QU Z C,et al.Heuristic Solutions of Virtual NetworkEmbedding:a survey[J].China Communications,2018,15(3):186-219.
[3] LI R Z,WU Q B,TAN Y S,et al.On the optimal approach of survivable virtual networkembedding in virtualized SDN[J].Iei-ce Transactions on Information and Systems,2018,101(3):698-708.
[4] SU Y Z,MENG X R,MENG Q W,et al.Environment Adaptive and Joint Topology Aware VirtualNetwork Embedding Algorithm[J].Journal of Electronics & Information Technology,2018,40(1):79-86.
[5] YU M,YI Y,REXFORD J,et al.Rethinking virtual networkembedding:Substrate support for path splitting and migration[J].ACM SIGCOMM Computer Communication Review,2008,38(2):19-29.
[6] WANG Z H,HAN Y N,LIN T,et al.Resource allocation algorithms in the reconfigurable network based on network centrality and topology potential[J].Journal on Communications,2012,33(8):10-20.
[7] CUI H Y,GAO W J,LIU J,et al.A virtual network embedding algorithm based on virtual topology connection feature[C]//International Symposium on Wireless Personal Multimedia Communications.New Jersey,USA,2013:1-5.
[8] FISCHER A,BOTERO J,BECK M,et al.Virtual network embedding:a survey[J].IEEE Communications Surveys & Tuto-rials,2013,15(4):1888-1906.
[9] LIU X B,WANG B H,YANG Z X,et al.A Virtual Network Embedding Algorithm Based on Topology Potential[J].Journal of Electronics & Information Technology,2018,40(7):1684-1690.
[10] FENG M,LIAO J X,WANG J Y,et al.Topology-aware virtual network embedding based on multiple characteristics[C]//IEEE ICC 2014-Next-Generation Networking Symposium.Sydney City,2014:2956-2962.
[11] URAYAMA Y,TACHIBANA T.Virtual network construction with K-shortest path algorithm and Prim’s MST Algorithm for robust physical networks[J].Lecture Notes in Engineering & Computer Science,2014,2209(1):206-210.
[12] DING J,HUANG T,WANG J,et al.Virtual network embedding through node connectivity[J].Journalof China University of posts & Telecommunications,2015,22(1):17-23.
[13] PENG L M.Virtual Network Embedding Algorithm Based on Breadth-first Search[J].Journal of Sichuan University(Engineering Science Edition),2015,47(2):117-122.
[14] ESPOSITO F,PAOLA D,MATTA I.On Distributed Virtual Network Embedding With Guarantees[J].IEEE/ACMTran-sactions on Networking,2016,24(1):569-582.
[15] OLIVEIRA R,MARCON D,BAYS L,et al.Opportunistic resi-lience embedding(ORE):Toward cost-efficient resilient virtual network[J].Computer Networks,2015,89(7):59-77.
[16] XIE F,MENG X R,ZHAO Z Y,et al.Virtual network mapping algorithm based on adjacent node and topology awareness[J].Computer Engineering,2018,44(9):107-112.
[17] CAO H T,YANG L X,ZHU H B.Novel Node-Ranking Approach and Multiple Topology Attributes-Based Embedding Algorithm for Single-Domain Virtual Network Embedding[J].IEEE Internet of Things Journal,2018,5(1):108-120.
[18] ZHENGQ,LI J,TIAN H L,et al.A 2-Layers Virtual Network Mapping Algorithm Based on Node Attribute and Network Simplex[J].IEEE Access,2018,6:77474-77484.
[19] GONG S Q,CHEN J,HUANG C H,et al.Trust-aware secure virtual network embedding algorithm[J].Journal on Communications,2015,36(11):180-189.
[20] WANG M,ZHUANG L,WANG G Q,et al.Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism[J].Computer Science,2018,45(12):66-70,103.
[21] WANGZ Z,ZHENG Q,CHEN C,et al.Virtual Network Mapping Algorithm Based on Network Simplex[J].Computer Engineering,2019,45(4):13-17,24.
[22] CHENG X,SU S,ZHANG Z B,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):39-47.
[23] EPPSTEIN D.Finding the k shortest paths[J].SIAM Journal ofComputer,1994,28(2):652-763.
[1] ZHU Guo-hui, ZHANG Yin, LIU Xiu-xia, SUN Tian-ao. Energy Efficient Virtual Network Mapping Algorithms Based on Node Topology Awareness [J]. Computer Science, 2020, 47(9): 270-274.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .