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

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

摘要/Abstract

摘要：

针对虚拟网络可靠映射问题，引入虚拟网络可生存约束条件，确保在底层网络单节点失效情况下，被映射虚拟网络剩余部分仍保持连通，最大程度确保虚拟网络的完整性和服务的连续性。以最小化底层网络映射开销为目标函数，建立虚拟网络可靠映射的整数线性规划模型，提出一种虚拟网络可生存的启发式可靠映射算法RHM-SVN并进行求解。实验结果表明，该算法能够有效降低资源平均利用率，提高映射成功率、底层网络平均收益和虚拟网络恢复成功率。

关键词: 云计算, 虚拟网络可生存, 虚拟网络可靠映射, 整数线性规划, 蚁群算法

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

朱强,王慧强,马春光,冯光升,吕宏武. 虚拟网络可生存的启发式可靠映射算法[J]. 通信学报, 2015, 36(7): 109-119.

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.

图/表 9

图1

表1

图2

图3

图4

图5

图6

图7

图8

参考文献 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.

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