一种粒子群优化的用户优先级虚拟网络映射算法

doi:10.3969/j.issn.1001-2400.2015.01.003

Abstract

Abstract:

In the forwarding and control separation network, we model the user-priority virtual network embedding problem as an integer linear programming, which is achieved with resource grabbing and re-mapping aiming at maximizing the resource utilization of the substrate physical network. And we propose a modified discrete particle swarm optimization algorithm (M_DPSO) for short to solve the VN embedding problem. In the M_DPSO, the particle evolves more directionally, and the mutually exclusive factor of different particle positions is introduced to resolve the problem of premature and easily becoming local optimal solution. Finally, the performance parameters, including node resource utilization, link resource utilization, the VN accept rate, the average jump number and the long-term operators benefit cost ratio, are evaluated by emulation experiments. In contrast to the greedy algorithm and binary particle swarm optimization algorithm, the M_DPSO is verified to be of high performance.

Key words: forwarding and control separation network, virtual network embedding, discrete particle swarm optimization, user-priority

CLC Number:

TP393

CHANG Lei;GU Huaxi;ZHANG Zhiyi;YU Xiaoshan;ZHAO Yan. Particle swarm optimization user-priority virtual network embedding algorithm[J].J4, 2015, 42(1): 16-22.

References

［1］张顺利, 邱雪松, 孟洛明. 网络虚拟化环境下的服务故障诊断算法［J］. 软件学报, 2012, 23(10): 2772-2782.
Zhang Shunli, Qiu Xuesong, Meng Luoming. Service Fault Diagnosis Algorithm in Network Virtualization Environment［J］. Journal of Software, 2012, 23(10): 2772-2782.
［2］蔡志平, 刘强, 吕品, 等. 虚拟网络映射模型及其优化算法［J］. 软件学报, 2012, 23(4): 864-877.
Cai Zhiping, Liu Qiang, Lü Pin, et al. Virtual Network Mapping Model and Optimization Algorithms［J］. Journal of Software, 2012, 23(4): 864-877.
［3］卿苏德, 廖建新, 朱晓民, 等. 网络虚拟化环境中虚拟网络的嵌套映射算法［J］. 软件学报, 2012, 23(11): 3045-3058.
Qing Sude, Liao Jianxin, Zhu Xiaomin, et al. Virtual Network Embedding Algorithms in the Network Virtualization Environment［J］. Journal of Software, 2012, 23(11): 3045-3058.
［4］刘文志. 网络虚拟化环境下资源管理关键技术研究［D］. 北京: 北京邮电大学, 2012.
［5］ Gopal R L. Seperation of Control and Forwarding Plane Inside a Network Element［C］//5th IEEE International Conference on High Speed Networks and Multimedia Communications. Piscataway: IEEE, 2002: 161-166.
［6］ Doria A, Haas R, Salim J H, et al. ForCES Protocol Specification［DB/OL］. ［2013-08-13］. http://www.ietf.org/internet-drafts/draft-ietf-forces-protocol-13.txt.
［7］ Yang L, Dantu R, Anderson T, et al. Forwarding and Control Element Separation (ForCES) Framework［DB/OL］. ［2013-08-05］. http://www.rfc-editor.org/rfc/pdfrfc/rfc3746.txt.pdf.
［8］ Chowdhury N, Boutaba R. Network Virtualization: State of the Art and Research Challengs［J］. IEEE Communications Magazine, 2009, 47(7): 20-26.
［9］李文, 吴春明, 陈健, 等. 物理节点可重复映射的虚拟网络映射算法［J］. 电子与信息学报, 2011, 33(10): 908-914.
Li Wen, Wu Chunming, Chen Jian, et al. Virtual Network Mapping Algorithm with Repeatable Mapping over Substrate Nodes［J］. Journal of Electronics ＆ Information Technology, 2011, 33(10): 908-914.
［10］吕博, 杨帆, 王振凯, 等. 一种基于区域划分的虚拟网映射新算法［J］. 电子与信息学报, 2011, 33(10): 2347-2352.
Lü Bo, Yang Fan, Wang Zhenkai, et al. A Novel Virtual Network Mapping Algorithm Based on Regionalization［J］. Journal of Electronics ＆ Information Technology, 2011, 33(10): 2347-2352.
［11］ Fischer A, Botero J, Beck M, et al. Virtual Network Embedding: a Survey［J］. IEEE Communications Surveys ＆ Tutorials, 2013, 15(4): 1888-1906.
［12］ Yan Zheping, Deng Chao, Zhou Jiajia, et al. A Novel Two-subpopulation Particle Swarm Optimization［C］//Proceedings of 10th Intelligent Control and Automation(WCICA). Piscataway: IEEE, 2012: 4113-4117.
［13］程祥, 张忠宝, 苏森, 等. 基于粒子群优化的虚拟网络映射算法［J］. 电子学报, 2011, 39(10): 2240-2244.
Cheng Xiang, Zhang Zhongbao, Su Sen, et al. Virtual Network Embedding Based on Particle Swarm Optimization［J］. Acta Electronica Sinica, 2011, 39(10): 2240-2244.
［14］ Zhang Zhongbao, Cheng Xiang, Su Sen, et al. A Unified Enhanced Particle Swarm Optimization-based Virtual Network Embedding Algorithm［J］. International Journal of Communication Systems, 2012, 26(8): 1054-1073.
［15］ Zegura E, Calvert K, Bhattacharjee S. How to Model an Internetwork［C］//IEEE INFOCOM Proceedings. Piscataway: IEEE, 1996: 594—602.
［16］ Yuy M, Yiz Y, Rexfordy 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.
［17］ Cheng X, Su S, Zhang Z, et al. Virtual Network Embedding throuth Topology-aware Node Ranking［J］. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 38-47.

[1]	YAN Zhongjiang;LI Bo;GAO Tian;ZUO Xiaoya. Fair traffic scheduling algorithm for the roadside unit [J]. J4, 2016, 43(1): 133-138.
[2]	REN Gaoming;XIA Jingbo;BAI Jun;CHEN Zhen. Novel per-flow traffic measurement algorithm [J]. J4, 2015, 42(5): 125-132.
[3]	HU Changjun;YUAN Shujie. Position-based forward broadcast algorithm in the mobile sensor network [J]. J4, 2015, 42(4): 147-152.
[4]	ZHANG Guanghua;ZHANG Yuqing;LIU Xuefeng;YAN Jingbo. Behavior trust fuzzy evaluation model [J]. J4, 2015, 42(1): 29-34.
[5]	ZUO Qingyun;CHEN Ming;WANG Xiulei;LIU Bo. Online traffic anomaly detection method for SDN [J]. J4, 2015, 42(1): 155-160.
[6]	QI Xiaogang;LU Zanzan;ZHENG Gengzhong;SUN Erkun;HU Mingming;XIE Mande. Low-power and low-delay sheep scheduling algorithm based on the data aggregation tree [J]. J4, 2015, 42(1): 124-129.
[7]	HU Qian;WU Muqing;GUO Song;PENG Li. Random cache placement strategy for content-centric networking [J]. J4, 2014, 41(6): 131-136+187.
[8]	ZHANG Zinan;GUO Yuanbo;YANG Kuiwu;HUANG Huixin;YANG Zhanhai. Universally composable security authenticated key exchange protocol [J]. J4, 2014, 41(5): 185-191.
[9]	TUO Liheng;NI Hong;LI Mantian;LIU Xue. Static multi-service deployment algorithm on the overlay network [J]. J4, 2014, 41(4): 137-143.
[10]	ZHANG Lu;CAI Wandong;PENG Dong. Calculation methods for nodal multilink weight in the directed manufacturing grid [J]. J4, 2014, 41(4): 186-192.
[11]	LI Ye;WANG Yinghui;YU Zhenhua. Formal modeling of cyber-physical systems using object-oriented Petri nets [J]. J4, 2014, 41(2): 165-171.
[12]	ZONG Ru;GAO Xinbo;PENG Jianhua. Deployment optimization of the self-organized network on near space platforms based on the game theoretical learning algorithm [J]. J4, 2013, 40(5): 188-193.
[13]	ZHANG Maosen;QIU Zhiliang;GAO Ya;LI Jun. Reverse dispatching scheme for satellite Clos-network switches [J]. J4, 2013, 40(4): 96-101.
[14]	PENG Fei;DENG Haojiang;LIU Lei. QoS-aware temporal prediction model for personalized service recommendation [J]. J4, 2013, 40(4): 174-180.
[15]	XU Jian;NI Hong;DENG Haojiang;LIU Lei. Proxy placement algorithm for the overlay multicast network [J]. J4, 2013, 40(3): 139-144.

Particle swarm optimization user-priority virtual network embedding algorithm

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0