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

doi:10.3969/j.issn.1001-2400.2015.01.003

J4 ›› 2015, Vol. 42 ›› Issue (1): 16-22.doi: 10.3969/j.issn.1001-2400.2015.01.003

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

常磊¹;顾华玺¹;张之义²;余晓杉¹;赵彦¹

(1. 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071；
2. 中国电子科技集团公司第五十四研究所，河北石家庄 050000)

收稿日期:2013-09-11 出版日期:2015-02-20 发布日期:2015-04-14
通讯作者: 常磊
作者简介:常磊(1987-)，男，西安电子科技大学硕士研究生，E-mail：07818654@163.com．
基金资助:
国家自然科学基金资助项目(61472300)；中央高校基本业务费资助项目(JB142001-5)；高等学校学科创新引智计划资助项目(B08038)

Particle swarm optimization user-priority virtual network embedding algorithm

CHANG Lei¹;GU Huaxi¹;ZHANG Zhiyi²;YU Xiaoshan¹;ZHAO Yan¹

(1. State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an 710071, China;
2. The 54th Research Institute of China Electronics Technology Group Corporation, Shijiazhuang 050000, China)

Received:2013-09-11 Online:2015-02-20 Published:2015-04-14
Contact: CHANG Lei

摘要/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

中图分类号:

TP393

常磊;顾华玺;张之义;余晓杉;赵彦. 一种粒子群优化的用户优先级虚拟网络映射算法[J]. J4, 2015, 42(1): 16-22.

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.

参考文献

［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]	闫中江;李波;高田;左晓亚. 一种公平的路边基站下行业务调度算法[J]. J4, 2016, 43(1): 133-138.
[2]	任高明;夏靖波;柏骏;陈珍. 网络数据流流量测量新方法[J]. J4, 2015, 42(5): 125-132.
[3]	胡长俊;袁树杰. 移动传感网基于位置的前向广播算法[J]. J4, 2015, 42(4): 147-152.
[4]	张光华;张玉清;刘雪峰;燕敬博. 一种行为信任模糊评估模型[J]. J4, 2015, 42(1): 29-34.
[5]	左青云;陈鸣;王秀磊;刘波. 一种基于SDN的在线流量异常检测方法[J]. J4, 2015, 42(1): 155-160.
[6]	齐小刚;陆赞赞;郑耿忠;孙二坤;胡明明;谢满德. 一种低能耗低时延的睡眠调度算法[J]. J4, 2015, 42(1): 124-129.
[7]	胡骞;武穆清;郭嵩;彭蠡. 一种用于内容中心网络的缓存随机放置策略[J]. J4, 2014, 41(6): 131-136+187.
[8]	张紫楠;郭渊博;杨奎武;黄惠新;杨占海. 通用可组合认证密钥交换协议[J]. J4, 2014, 41(5): 185-191.
[9]	脱立恒;倪宏;李满天;刘学. 覆盖网络中多服务静态部署算法[J]. J4, 2014, 41(4): 137-143.
[10]	张璐;蔡皖东;彭冬. 有向制造网格节点多重链接权重计算方法[J]. J4, 2014, 41(4): 186-192.
[11]	李晔;王映辉;于振华. 信息物理融合系统的面向对象Petri网建模[J]. J4, 2014, 41(2): 165-171.
[12]	宗汝;高新波;彭建华. 临近空间平台自组织网络优化部署的博弈算法[J]. J4, 2013, 40(5): 188-193.
[13]	张茂森;邱智亮;高雅;黎军. 星上Clos交换网络的逆向调度算法[J]. J4, 2013, 40(4): 96-101.
[14]	彭飞;邓浩江;刘磊. 面向个性化服务推荐的QoS动态预测模型[J]. J4, 2013, 40(4): 174-180.
[15]	徐剑;倪宏;邓浩江;刘磊. 覆盖多播网络中代理服务器的部署算法[J]. J4, 2013, 40(3): 139-144.

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

Particle swarm optimization user-priority virtual network embedding algorithm

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0