虚拟网络可生存的启发式可靠映射算法

doi:10.11959/j.issn.1000-436x.2015177

Abstract

Abstract:

For reliable virtual network mapping problem,virtual network survivability constraints are introduced to ensure that the rest of the mapped virtual network remains connected under a single node failure condition in the substrate network,which makes sure the completeness of the virtual network and continuity of services.In order to reduce cost of the substrate network,the reliable heuristic mapping problem is considered as an integer linear programming model and a reliable heuristic mapping method for survivable virtual network is proposed to solve the problem.The simulation results show that average usage of links is reduced and the success rate,average revenue of mapping,recovery success rate of virtual network are increased compared with the existing reliable mapping algorithms.

Key words: cloud computing, survivable virtual network, network virtualization embedding, integer linear programming, colony optimization algorithm

Qiang ZHU,Hui-qiang WANG,Chun-guang MA,Guang-sheng FENG,Hong-wu LV. Reliable heuristic mapping method for survivable virtual network[J]. Journal on Communications, 2015, 36(7): 109-119.

Figures/Tables 9

References 22

[1]	FEAMSTER N , GAO L , REXFORD J . How to lease the Internet in your spare time[J]. ACM SIGCOMM Computer Communication Review, 2007,37(1): 61-64.
[2]	CHOWDHURY N M M K , BOUTABA R . A survey of network virtualization[J]. Computer Networks, 2010,54(5): 862-876.
[3]	ANDERSEN D G . Theoretical approaches to node assignment[EB/OL]. , 2002.
[4]	蔡志平, 刘强, 吕品等. 虚拟网络映射模型及其优化算法[J]. 软件学报, 2012,23(4): 864-877. CAI Z P , LIU Q , LV P , et al. Virtual network mapping model and optimization algorithms[J]. Journal of Software, 2012,23(4): 864-877.
[5]	CHOWDHURY N M M K , RAHMAN M R , BOUTABA B . ViNE Yard:virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE/ACM Transactions on Networking, 2012,20(1): 206-219.
[6]	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.
[7]	HOUIDI I , LOUATI W , DJAMAL Z , et al. A distributed virtual network mapping algorithm[A]. Proceedings of the 2009 IEEE International Conference on Communications[C]. Beijing,China, 2009. 5634-5640.
[8]	LISCHKA J , KARL H . A virtual network mapping algorithm based on subgraph isomorphism detection[A]. Proceedings of the 1st ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures[C]. New York,USA, 2009. 81-88.
[9]	SHEN M , XU K , YANG K ,et al. Towards efficient virtual network embedding across multiple network domains[A]. Proceedings of the 2014 IEEE 22nd International Symposium of Quality of Service[C]. 2014. 61-70.
[10]	FAJJARI I , AITSAADI N , PUJOLLE G , et al. VNE-AC:virtual network embedding algorithm based on ant colony metaheuristic[A]. Proceedings of 2011 IEEE International Conference on Communications[C]. Kyoto,Japan, 2011. 1-6.
[11]	程祥, 张忠宝, 苏森等. 基于粒子群优化的虚拟网络映射算法[J]. 电子学报, 2011,39(10): 2240-2244. CHENG X , ZHANG Z B , SU S , et al. Virtual network embedding based on particle swarm optimization[J]. Chinese Journal of Electronics, 2011,39(10): 2240-2244.
[12]	朱强, 王慧强, 冯光升等. VNE-AFS：基于人工鱼群的网络虚拟化映射算法[J]. 通信学报, 2012,33(Z1): 170-177. ZHU Q , WANG H Q , FENG G S , et al. VNE-AFS:virtual network embedding based on artificial fish swarm[J]. Journal on Communications, 2012,33(Z1): 170-177.
[13]	RAHMAN M , BOUTABA R . SVNE:survivable virtual network embedding algorithms for network virtualization[J]. IEEE Transactions on Network and Service Management, 2013,10(2): 105-118.
[14]	YU H F , QIAO C M , ANAND V , et al. Survivable virtual infrastructure mapping in a federated computing and networking system under single regional failures[A]. Proceedings of 2010 IEEE Global Telecommunications Conference[C]. Miami,USA, 2010. 1-6.
[15]	YEOW W L , WESTPHA C , KOZATL U C . Designing and embedding reliable virtual infrastructures[J]. ACM SIGCOMM Computer Communication Review, 2011,41(2): 57-64.
[16]	BUTT N F , CHOWDHURY M , BOUTABA R . Topology-awareness and reoptimization mechanism for virtual network embedding[A]. Proceedings of 2010 Networking Conference[C]. Chennai,India, 2011. 27-39.
[17]	SOUALAH O , FAJJARI I , AITSAADI N , et al. A reliable virtual network embedding algorithm based on game theory within cloud's backbone[A]. Proceedings of the 2014 IEEE International Conference on Communications[C]. Sydney,Australia, 2014. 2975-2981.
[18]	TODIMALA A , RAMAMURTHY B . A scalable approach for survivable virtual topology routing in optical WDM networks[J]. IEEE Journal on Selected Areas in Communications, 2007,25(6): 63-69.
[19]	卿苏德, 廖建新, 朱晓民等. 网络虚拟化环境中虚拟网络的嵌套映射算法[J]. 软件学报, 2012,23(11): 3045-3058. QING S D , LIAO J X , ZHU X M , et al. Virtual network embedding algorithms in the network virtualization environment[J]. Journal of Software, 2012,23(11): 3045-3058.
[20]	DORIGO M , MANIEZZO V , COLORNI A . Ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems,Man,and Cybernetics, 1996,26(1): 29-41.
[21]	TSUKIYAMA S , SHIRAKAWA I , OZAKI H , et al. An algorithm to enumerate all cutsets of a graph in linear time per cutset[J]. Journal of the Assoctatlon for Computing Machmery, 1980,27(4): 619-632.
[22]	SUN G , YU H , ANAND V , et al. A cost efficient framework and algorithm for embedding dynamic virtual network requests[J]. Future Generation Computer Systems, 2013,29(5): 1265-1277.

Metrics

Recommended 0

No Suggested Reading articles found!

算法名称	算法描述
RHM-SVN	本文提出的虚拟网络可生存的启发式可靠映射算法
RHM-SVN-Simple	在本文提出的RHM-SVN基础上，去掉最短路径提供最佳带宽资源因子ψ(p)，采用最短路径方法分配路径
SVNE-ORP	文献[15]中基于优化冗余池的资源共享机制
SVNE-TAP	文献[16]中基于拓扑感知的节点迁移与链路重映射方法

Reliable heuristic mapping method for survivable virtual network

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 9

References 22

Related Articles 15

Metrics

Recommended 0

[1]	Ling MA, Qiliang FAN, Ting XU, Guanchen GUO, Shenglin ZHANG, Yongqian SUN, Yuzhi ZHANG. Scheduling framework based on reinforcement learning in online-offline colocated cloud environment [J]. Journal on Communications, 2023, 44(6): 90-102.
[2]	Hongrui NIE, Shaosheng LI, Yong LIU. Optimized scheduling mechanism based on IEEE 802.1Qch standard in time-sensitive networking [J]. Journal on Communications, 2022, 43(9): 12-26.
[3]	Huaqun WANG, Zhe LIU, Debiao HE, Jiguo LI. Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud [J]. Journal on Communications, 2021, 42(7): 52-60.
[4]	Jianhong ZHANG, Menglong WU, Jing WANG, Pei LIU, Zhengtao JIANG, Changgen PENG. Secure and verifiable multi-keyword searchable encryption scheme in cloud [J]. Journal on Communications, 2021, 42(4): 139-149.
[5]	Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application [J]. Journal on Communications, 2021, 42(3): 11-22.
[6]	Jiawei ZHANG, Jianfeng MA, Zhuo MA, Teng LI. Time-based and privacy protection revocable and traceable data sharing scheme in cloud computing [J]. Journal on Communications, 2021, 42(10): 81-94.
[7]	Wenjuan WANG, Xuehui DU, Dibin SHAN. Construction method of attack scenario in cloud environment based on dynamic probabilistic attack graph [J]. Journal on Communications, 2021, 42(1): 1-17.
[8]	Youliang TIAN,Qin LUO. Verifiable multi-keyword search scheme based on improved Merkle-Tree authentication method [J]. Journal on Communications, 2020, 41(9): 118-129.
[9]	Na WANG,Kun ZHENG,Junsong FU,Jian LI. Method of ciphertext retrieval in mobile edge computing based on block segmentation [J]. Journal on Communications, 2020, 41(7): 95-102.
[10]	Lindong ZHAO,Wenqin ZHUANG,Jianxin CHEN,Liang ZHOU. Hierarchical task offloading in heterogeneous cellular network:modeling and optimization [J]. Journal on Communications, 2020, 41(4): 34-44.
[11]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[12]	Bing LIANG,Wen JI. Multiuser computation offloading for edge-cloud collaboration using submodular optimization [J]. Journal on Communications, 2020, 41(10): 25-36.
[13]	SU Mingfeng,WANG Guojun,LI Renfa. Multidimensional QoS cloud computing resource scheduling method based on stakeholder perspective [J]. Journal on Communications, 2019, 40(6): 102-115.
[14]	CHEN Xingshu,HUA Qiang,WANG Yitong,GE Long,ZHU Yi. Research on low-rate DDoS attack of SDN network in cloud environment [J]. Journal on Communications, 2019, 40(6): 210-222.
[15]	Wanliang WANG, Zelin ZANG, Guoqi CHEN, Hangyao TU, Yule WANG, Linyan LU. Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem [J]. Journal on Communications, 2019, 40(5): 180-191.