基于差分进化融合蚁群算法的数据中心流量调度机制

doi:10.11772/j.issn.1001-9081.2021101766

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (12): 3863-3869.DOI: 10.11772/j.issn.1001-9081.2021101766

• 网络与通信 • 上一篇

基于差分进化融合蚁群算法的数据中心流量调度机制

代荣荣, 李宏慧(), 付学良

内蒙古农业大学计算机与信息工程学院，呼和浩特 010011

收稿日期:2021-10-14 修回日期:2022-01-04 接受日期:2022-01-13 发布日期:2022-01-20 出版日期:2022-12-10
通讯作者: 李宏慧
作者简介:代荣荣（1996—），女（蒙古族），内蒙古呼和浩特人，硕士研究生，主要研究方向：软件定义网络、数据中心网络
付学良（1969—），男，内蒙古赤峰人，教授，博士，主要研究方向：智能计算、数据挖掘、数字水文、水资源环境评价。
基金资助:
国家自然科学基金资助项目(62041211);国家重点研发计划项目(2019YFC049205);内蒙古自然科学基金资助项目(2020MS06011)

Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm

Rongrong DAI, Honghui LI(), Xueliang FU

College of Computer and Information Engineering，Inner Mongolia Agricultural University，Hohhot Inner Mongolia 010011，China

Received:2021-10-14 Revised:2022-01-04 Accepted:2022-01-13 Online:2022-01-20 Published:2022-12-10
Contact: Honghui LI
About author:DAI Rongrong， born in 1996， M. S. candidate. Her research interests include software defined network， data center network.
FU Xueliang， born in 1969， Ph. D.， professor. His research interests include intelligent computing， data mining， digital hydrology，water resources and environmental assessment.
Supported by:
National Natural Science Foundation of China(62041211);National Key Research and Development Program of China(2019YFC049205);Natural Science Foundation of Inner Mongolia Autonomous Region(2020MS06011)

摘要/Abstract

摘要：

针对数据中心网络的传统流量调度方法容易引起网络拥塞及链路负载不均衡等问题，提出了一种差分进化（DE）融合蚁群（ACO）算法（DE-ACO）的动态流量调度机制，对数据中心网络中的大象流调度进行优化。首先，利用软件定义网络（SDN）技术捕获实时网络状态信息并设定流量调度的优化目标；然后，通过优化目标重定义DE算法，计算出多条可用候选路径，作为ACO算法的初始化全局信息素；最后，结合全局网络状态以求得全局最优路径，并重新路由拥堵链路上的大象流。实验结果表明，以在随机通信模式下为例，与等价多路径路由（ECMP）算法和基于蚁群算法的SDN数据中心网络流量调度（ACO-SDN）算法相比，所提算法的平均对分带宽分别提高了29.42%~36.26%和5%~11.51%，降低了网络的最大链路利用率（MLU），较好地实现了网络负载均衡。

关键词: 软件定义网络, 数据中心网络, 流量调度, 差分进化算法, 蚁群算法

Abstract:

As the traditional flow scheduling method for data center network is easy to cause network congestion and link load imbalance， a dynamic flow scheduling mechanism based on Differential Evolution （DE） and Ant Colony Optimization （ACO） algorithm （DE-ACO） was proposed to optimize elephant flow scheduling in data center networks. Firstly， Software Defined Network （SDN） technology was used to capture the real-time network status information and set the optimization objectives of flow scheduling. Then， DE algorithm was redefined by the optimization objectives， several available candidate paths were calculated and used as the initialized global pheromone of the ACO algorithm. Finally， the global optimal path was obtained by combining with the global network status， and the elephant flow on the congested link was rerouted. Experimental results show that compared with Equal-Cost Multi-Path routing （ECMP） algorithm and network flow scheduling algorithm of SDN data center based on ACO algorithm （ACO-SDN）， the proposed algorithm increases the average bisection bandwidth by 29.42% to 36.26% and 5% to 11.51% respectively in random communication mode， reducing the Maximum Link Utilization （MLU） of the network， and achieving better load balancing of the network.

Key words: Software Defined Network (SDN), data center network, flow scheduling, Differential Evolution (DE) algorithm, Ant Colony Optimization (ACO) algorithm

中图分类号:

TP393

代荣荣, 李宏慧, 付学良. 基于差分进化融合蚁群算法的数据中心流量调度机制[J]. 计算机应用, 2022, 42(12): 3863-3869.

Rongrong DAI, Honghui LI, Xueliang FU. Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm[J]. Journal of Computer Applications, 2022, 42(12): 3863-3869.

图/表 8

图1 DE-ACO大象流调度机制流程

Fig.1 DE-ACO elephant flow scheduling process

图2 变异操作示例

Fig. 2 Variation operation example

图3 交叉操作示例

Fig. 3 Crossover operation example

表1 DE-ACO主要参数值

Tab. 1 Major parameter values of DE-ACO

参数	值	参数	值
最大迭代次数MaxT	50	信息素启发式因子 $α$	2
种群个数 $M$	50	期望启发因子 $β$	3
影响因子a	1	信息素挥发系数 $ρ$	0.6
影响因子b	10	信息素总量 $G$	100
蚂蚁个数N	10

表1 DE-ACO主要参数值

Tab. 1 Major parameter values of DE-ACO

参数	值	参数	值
最大迭代次数MaxT	50	信息素启发式因子 $α$	2
种群个数 $M$	50	期望启发因子 $β$	3
影响因子a	1	信息素挥发系数 $ρ$	0.6
影响因子b	10	信息素总量 $G$	100
蚂蚁个数N	10

图4 Random模式下平均对分带宽比较

Fig.4 Comparison of average bisection bandwidth in Random mode

图5 Stride 模式下平均对分带宽比较

Fig.5 Comparison of average bisection bandwidth in Stride mode

图6 Staggered模式下平均对分带宽比较

Fig.6 Comparison of average bisection bandwidth in Staggered mode

图7 Stride模式下最大链路利用率比较

Fig.7 Comparison of maximum link utilization in stride mode

参考文献 22

1	李文信，齐恒，徐仁海，等. 数据中心网络流量调度的研究进展与趋势［J］. 计算机学报， 2020， 43（4）： 600-617. 10.11897/SP.J.1016.2020.00600
	LI W X， QI H， XU R H， et al. Data center network flow scheduling progress and trends［J］. Chinese Journal of Computers， 2020， 43（4）： 600-617. 10.11897/SP.J.1016.2020.00600
2	蔡岳平，王昌平. 软件定义数据中心网络混合路由机制［J］. 通信学报， 2016， 37（4）： 44-52. 10.11959/j.issn.1000-436x.2016071
	CAI Y P， WANG C P. Software defined data center network with hybrid routing［J］. Journal on Communications， 2016， 37（4）： 44-52. 10.11959/j.issn.1000-436x.2016071
3	CURTIS A R， KIM W， YALAGANDULA P. Mahout： low-overhead datacenter traffic management using end-host-based elephant detection［C］// Proceedings of the 2011 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2011： 1629-1637. 10.1109/infcom.2011.5934956
4	ESCUDERO-SAHUQUILLO J， GARCÍA P J， QUILES F J， et al. A new proposal to deal with congestion in InfiniBand-based fat-trees［J］. Journal of Parallel and Distributed Computing， 2014， 74（1）： 1802-1819. 10.1016/j.jpdc.2013.09.002
5	HOPPS C. Analysis of an equal-cost multi-path algorithm： RFC 2992 ［S］. Reston， VA： Internet Society， 2000-11. 10.17487/rfc2992
6	KANDULA S， SENGUPTA S， GREENBERG A， et al. The nature of data center traffic： measurements & analysis［C］// Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement. New York： ACM， 2009： 202-208. 10.1145/1644893.1644918
7	BENSON T， AKELLA A， MALTZ D A. Network traffic characteristics of data centers in the wild［C］// Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement. New York： ACM， 2010： 267-280. 10.1145/1879141.1879175
8	Al-FARES M， RADHAKRISHNAN S， RAGHAVAN B， et al. Hedera： dynamic flow scheduling for data center networks［C］// Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2010： 281-296.
9	CHAKRABORTY S， CHEN C. A low-latency multipath routing without elephant flow detection for data centers［C］// Proceedings of the IEEE 17th International Conference on High Performance Switching and Routing. Piscataway： IEEE， 2016： 49-54. 10.1109/hpsr.2016.7525638
10	刘振鹏，任少松，李明，等. 软件定义网络的数据中心动态流量调度方案［J］. 吉林大学学报（工学版）， 2021， 51（3）： 1040-1047.
	LIU Z P， REN S S， LI M， et al. Software defines dynamic traffic scheduling scheme for network data center［J］. Journal of Jilin University （Engineering and Technology Edition）， 2021， 51（3）： 1040-1047.
11	朱素霞，龙翼飞，孙广路. 基于大流调度的软件定义数据中心网络负载均衡算法［J］. 计算机应用与软件， 2021， 38（1）： 27-32， 75. 10.3969/j.issn.1000-386x.2021.01.005
	ZHU S X， LONG Y F， SUN G L. Software-defined data center network load balancing algorithm based on large flows scheduling［J］. Computer Applications and Software， 2021， 38（1）： 27-32， 75. 10.3969/j.issn.1000-386x.2021.01.005
12	林智华，高文，吴春明，等. 基于离散粒子群算法的数据中心网络流量调度研究［J］. 电子学报， 2016， 44（9）： 2197-2202. 10.3969/j.issn.0372-2112.2016.09.026
	LIN Z H， GAO W， WU C M， et al. Data center network flow scheduling based on DPSO algorithm［J］. Acta Electronica Sinica， 2016， 44（9）： 2197-2202. 10.3969/j.issn.0372-2112.2016.09.026
13	李宏慧，杨光，路海亮，等. 基于蚁群算法的SDN数据中心网络大象流调度研究［J］. 计算机应用研究， 2019， 36（12）： 3837-3841. 10.19734/j.issn.1001-3695.2018.07.0430
	LI H H， YANG G， LU H L， et al. Flow scheduling of elephant flows in SDN data center network based on ant colony algorithm［J］. Application Research of Computers， 2019， 36（12）： 3837-3841. 10.19734/j.issn.1001-3695.2018.07.0430
14	STORN R， PRICE K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces［J］. Journal of Global Optimization， 1997， 11（4）： 341-359. 10.1023/a:1008202821328
15	丁青锋，尹晓宇. 差分进化算法综述［J］. 智能系统学报， 2017， 12（4）： 431-442. 10.11992/tis.201605015
	DING Q F， YIN X Y. Research survey of differential evolution algorithms［J］. CAAI Transactions on Intelligent Systems， 2017， 12（4）： 431-442. 10.11992/tis.201605015
16	YEN J Y. Finding the K shortest loopless paths in a network［J］. Management Science， 1971， 17（11）： 712-716. 10.1287/mnsc.17.11.712
17	段海滨，张祥银，徐春芳. 仿生智能计算［M］. 北京：科学出版社， 2011：36-61.
	DUAN H B， ZHANG X Y， XU C F. Bio-inspired Computing［M］. Beijing： Science Press， 2011： 36-61.
18	庄怀东，杜庆伟.一种基于SDN的数据中心网络动态流量调度方法［J］.计算机与现代化，2016（7）：80-86.
	ZHUANG H D， DU Q W. A method of data center network dynamic traffic scheduling based on SDN ［J］. Computer and Modernization，2016（7）：80-86.
19	LI H H， LU H L， FU X L. An optimal and dynamic elephant flow scheduling for SDN-based data center networks［J］. Journal of Intelligent and Fuzzy Systems， 2020， 38（1）： 247-255. 10.3233/jifs-179399
20	沈耿彪，李清，江勇，等. 数据中心网络负载均衡问题研究［J］. 软件学报， 2020， 31（7）： 2221-2244.
	SHEN G B， LI Q， JIANG Y， et al. Research on load balancing in data center networks［J］. Journal of Software， 2020， 31（7）： 2221-2244.
21	杨振宇，唐珂. 差分进化算法参数控制与适应策略综述［J］. 智能系统学报， 2011， 6（5）： 415-423. 10.3969/j.issn.1673-4785.2011.05.005
	YANG Z Y， TANG K. An overview of parameter control and adaptation strategies in differential evolution algorithm［J］. CAAI Transactions on Intelligent Systems， 2011， 6（5）： 415-423. 10.3969/j.issn.1673-4785.2011.05.005
22	甘屹，李胜. 蚁群算法的参数优化配置研究［J］. 制造业自动化， 2011， 33（5）： 66-69. 10.3969/j.issn.1009-0134.2011.3a.23
	GAN Y， LI S. Studies on parameters configuration for microhabitat ant colony optimization algorithm［J］. Manufacturing Automation， 2011， 33（5）： 66-69. 10.3969/j.issn.1009-0134.2011.3a.23

[1]	聂青青, 万定生, 朱跃龙, 李致家, 姚成. 基于时域卷积网络的水文模型[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1756-1761.
[2]	刘向举, 路小宝, 方贤进, 尚林松. 软件定义网络环境下的低速率拒绝服务攻击检测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1301-1307.
[3]	韩舒宁, 徐敏, 董学士, 林青, 沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 695-700.
[4]	张立群, 林海涛, 郇文明, 毕文婷. 基于OpenFlow的软件定义网络流规则冲突检测系统[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 528-533.
[5]	陈何雄, 罗宇薇, 韦云凯, 郭威, 杭菲璐, 毛正雄, 张振红, 何映军, 罗震宇, 谢林江, 杨宁. 基于区块链的软件定义网络数据帧安全验证机制[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3074-3083.
[6]	刘志硕, 刘若思, 陈哲. 基于混合蚁群算法的冷链电动汽车车辆路径问题[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3244-3251.
[7]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[8]	李二超, 齐款款. B样条曲线融合蚁群算法的机器人路径规划[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3558-3564.
[9]	马晓航, 廖灵霞, 李智, 秦斌, 赵涵捷. 基于动态混合超时的软件定义网络多目标优化[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3658-3665.
[10]	陈港, 孟相如, 康巧燕, 阳勇. 基于拓扑分割与聚类分析的虚拟软件定义网络映射算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3309-3318.
[11]	朱梦迪, 束永安. 软件定义网络中控制数据平面一致性的验证[J]. 计算机应用, 2020, 40(6): 1751-1754.
[12]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[13]	向雄, 田检. 基于软件定义网络的对等网传输调度优化[J]. 计算机应用, 2020, 40(3): 777-782.
[14]	赵季红, 吴豆豆, 曲桦, 殷振宇. 基于软件定义网络的可靠性虚拟网络映射保障机制[J]. 计算机应用, 2020, 40(3): 770-776.
[15]	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.

基于差分进化融合蚁群算法的数据中心流量调度机制

Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 22

相关文章 15

编辑推荐

Metrics