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

doi:10.11772/j.issn.1001-9081.2021101766

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (12): 3863-3869.DOI: 10.11772/j.issn.1001-9081.2021101766

Special Issue: 网络与通信

• Network and communications • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP393

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.

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

Figures/Tables 8

Fig.1 DE-ACO elephant flow scheduling process

Fig. 2 Variation operation example

Fig. 3 Crossover operation example

Tab. 1 Major parameter values of DE-ACO

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

Tab. 1 Major parameter values of DE-ACO

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

Fig.4 Comparison of average bisection bandwidth in Random mode

Fig.5 Comparison of average bisection bandwidth in Stride mode

Fig.6 Comparison of average bisection bandwidth in Staggered mode

Fig.7 Comparison of maximum link utilization in stride mode

References 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]	Fengfeng WEI, Weineng CHEN. Distributed data-driven evolutionary computation for multi-constrained optimization [J]. Journal of Computer Applications, 2024, 44(5): 1393-1400.
[2]	Yawei HUANG, Xuezhong QIAN, Wei SONG. Improved differential evolution algorithm based on dual-archive population size adaptive method [J]. Journal of Computer Applications, 2024, 44(12): 3844-3853.
[3]	Chenyang GE, Qinrang LIU, Xue PEI, Shuai WEI, Zhengbin ZHU. Efficient collaborative defense scheme against distributed denial of service attacks in software defined network [J]. Journal of Computer Applications, 2023, 43(8): 2477-2485.
[4]	Jiahao ZHU, Wei ZHENG, Fengyu YANG, Xin FAN, Peng XIAO. Software quality prediction based on back propagation neural network optimized by ant colony optimization algorithm [J]. Journal of Computer Applications, 2023, 43(11): 3568-3573.
[5]	Qingqing NIE, Dingsheng WAN, Yuelong ZHU, Zhijia LI, Cheng YAO. Hydrological model based on temporal convolutional network [J]. Journal of Computer Applications, 2022, 42(6): 1756-1761.
[6]	Xiangju LIU, Xiaobao LU, Xianjin FANG, Linsong SHANG. Low-rate denial-of-service attack detection method under software defined network environment [J]. Journal of Computer Applications, 2022, 42(4): 1301-1307.
[7]	Hexiong CHEN, Yuwei LUO, Yunkai WEI, Wei GUO, Feilu HANG, Zhengxiong MAO, Zhenhong ZHANG, Yingjun HE, Zhenyu LUO, Linjiang XIE, Ning YANG. Blockchain-based data frame security verification mechanism in software defined network [J]. Journal of Computer Applications, 2022, 42(10): 3074-3083.
[8]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[9]	LI Mengmeng, QIN Wei, LIU Yi, DIAO Xingchun. Hybrid ant colony optimization algorithm with brain storm optimization [J]. Journal of Computer Applications, 2021, 41(8): 2412-2417.
[10]	XU Hongliang, YANG Guiqin, JIANG Zhanjun. Data center adaptive multi-path load balancing algorithm based on software defined network [J]. Journal of Computer Applications, 2021, 41(4): 1160-1164.
[11]	FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582.
[12]	Xiaohang MA, Lingxia LIAO, Zhi LI, Bin QIN, Han-chieh CHAO. Multi-objective optimization based on dynamic mixed flow entry timeouts in software defined network [J]. Journal of Computer Applications, 2021, 41(12): 3658-3665.
[13]	WANG Hongyu, ZHANG Yu, YANG Heng, MU Nan. Salient object detection in weak light images based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2021, 41(10): 2970-2978.
[14]	XIONG Yong, ZHANG Jia, YU Jiajun, ZHANG Benren, LIANG Xuanzhuo, ZHU Qige. Intelligent layout optimization algorithm for 3D pipelines of ships [J]. Journal of Computer Applications, 2020, 40(7): 2164-2170.
[15]	ZHU Mengdi, SHU Yong’an. Verification of control-data plane consistency in software defined network [J]. Journal of Computer Applications, 2020, 40(6): 1751-1754.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 22

Related Articles 15

Recommended Articles

Metrics