基于斐波那契树优化算法的数据中心流量调度策略

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

摘要/Abstract

摘要：

为提高运营商数据中心流量调度能力，同时考虑网络结构和网络流量两方面因素，设计了一种软件定义网络（SDN）架构数据中心的流量分析预测在线调度机制。针对数据中心流量调度的多维、多约束和多模态问题，提出基于斐波那契树优化（FTO）算法的流量调度策略，将 FTO 算法嵌入分析预测和在线调度 2 个阶段，发挥FTO算法全局局部交替迭代寻优和多模特性，得到流量调度的最优解和多个有价值的次优解。模拟平台验证表明， FTO流量调度策略能够对数据中心流量进行合理调度，有效提升运营商数据中心网络的负载均衡能力。

关键词: 数据中心, 软件定义网络, 流量调度, 斐波那契树优化, 多模寻优

Abstract:

To improve traffic scheduling capabilities in network provider data centers,both network structure and network traffic flow were considered at the same time.The analysis prediction and online scheduling mechanism was proposed in data center based on software defined networking (SDN).Aiming at the multi-dimensional,multi-constrained and multi-modal problems of traffic flow scheduling in data centers,the traffic flow scheduling strategy based on Fibonacci tree optimization (FTO) algorithm was proposed.FTO algorithm was embedded into two stages of analysis prediction and online scheduling,took it advantage of global local alternating and multi-model optimization characteristics,the optimal solution and suboptimal solutions of traffic scheduling had been got at one time.The emulator result shows that,the FTO traffic scheduling strategy can schedule traffic in data centers reasonably,which improves the load balancing capability of network providers' data centers effectively.

Key words: data center, SDN, traffic scheduling, Fibonacci tree optimization, multi-modal optimization

中图分类号:

TP393

王耀民,王霞,董易,张松海,施心陵. 基于斐波那契树优化算法的数据中心流量调度策略[J]. 通信学报, 2020, 41(6): 112-127.

Yaomin WANG,Xia WANG,Yi DONG,Songhai ZHANG,Xinling SHI. Data center traffic scheduling strategy based on Fibonacci tree optimization algorithm[J]. Journal on Communications, 2020, 41(6): 112-127.

图/表 20

图1

图2

图3

图4

图5

图6

表1

图7

图8

表2

表3

表4

图9

图10

图11

图12

图13

图14

图15

图16

参考文献 38

[20]	汪硕 . 云数据中心流量调度机制研究[D]. 北京:北京邮电大学, 2018.
	WANG S . Research on cloud data center traffic scheduling mechanism[D]. Beijing:Beijing University of Posts and Telecommunications, 2018.
[21]	ZHANG Y , CUI L , ZHANG Y . A stable matching based elephant flow scheduling algorithm in data center networks[J]. Computer Networks, 2017,120: 186-197.
[22]	NAGARAJ K , BHARADIA D , MAO H ,et al. Numfabric:fast and flexible bandwidth allocation in datacenters[C]// Proceedings of the 2016 ACM SIGCOMM Conference. New York:ACM Press, 2016: 188-202.
[23]	KANDULA S , SENGUPTA S , GREENBERG A G ,et al. The nature of data center traffic:measurements ＆ analysis[C]// ACM SIGCOMM Conference on Internet Measurement Conference. New York:ACM Press, 2009: 202-208.
[24]	张松海, 施心陵, 李鹏 ,等. 多峰函数优化的黄金分割斐波那契树优化算法[J]. 电子学报, 2017,45(4): 791-798.
	ZHANG S H , SHI X L , LI P ,et al. Golden segmentation Fibonacci tree optimization algorithm for multimodal function optimization[J]. Chinese Journal of Electronics, 2017,45(4): 791-798.
[25]	田中大, 李树江, 王艳红 ,等. 基于混沌理论与改进回声状态网络的网络流量多步预测[J]. 通信学报, 2016,37(3): 55-70.
	TIAN Z D , LI S J , WANG Y H ,et al. Multi-step prediction of network traffic based on chaos theory and improved echo state network[J]. Journal on Communications, 2016,37(3): 55-70.
[26]	李捷, 候秀红, 韩志杰 . 基于卡尔曼滤波和小波的网络流量预测算法研究[J]. 电子与信息学报, 2007,29(3): 725-728.
	LI J , HOU X H , HAN Z J . Research on network traffic prediction algorithm based on Kalman filter and wavelet[J]. Journal of Electronics＆ Information Technology, 2007,29(3): 725-728.
[27]	于艳华, 宋俊德 . 一种基于异常点检测的电信网络性能监控策略[J]. 电子与信息学报, 2009,31(9): 2220-2225.
[1]	BACCARELLI E , CORDESCHI N , MEI A ,et al. Energy-efficient dynamic traffic offloading and reconfiguration of networked data centers for big data stream mobile computing:review,challenges,and a case study[J]. Computers ＆ Chemical Engineering, 2016,91(2): 182-194.
[2]	DARABSEH A,AL-AYYOUB M , JARARWEH Y , et al . SDDC:a software defined datacenter experimental framework[C]// International Conference on Future Internet of Things ＆ Cloud. Piscataway:IEEE Press, 2015: 189-194.
[27]	YU Y H , SONG J D . A telecom network performance monitoring strategy based on outlier detection[J]. Journal of Electronics ＆ Information Technology, 2009,31(9): 2220-2225.
[28]	董谦, 李俊, 马宇翔 . 基于集中控制的命名数据网络流量调度方法[J]. 通信学报, 2018,39(7): 72-84.
	DONG Q , LI J , MA Y X . Traffic control method for named data network based on centralized control[J]. Journal on Communications, 2018,39(7): 72-84.
[29]	董谦, 李俊, 马宇翔 ,等. 软件定义网络中基于分段路由的流量调度方法[J]. 通信学报, 2018,39(11): 23-35.
[3]	TANHA M , SAJJADI D , RUBY R ,et al. Traffic engineering enhancement by progressive migration to SDN[J]. IEEE Communications Letters, 2018PP(99):1.
[4]	周桐庆, 蔡志平, 夏竟 ,等. 基于软件定义网络的流量工程[J]. 软件学报, 2016,27(2): 394-417.
[29]	DONG Q , LI J , MA Y X ,et al. Traffic scheduling method based on segment routing in software-defined networking[J]. Journal on Communications, 2018,39(11): 23-35.
[30]	董易, 吕丹桔, 王霞 ,等. 斐波那契树优化算法全局随机性概率收敛分析[J]. 控制与决策, 2018,3(1): 1-10.
[4]	ZHOU T Q , CAI Z P , XIA J ,et al. Traffic engineering based on software defined network[J]. Journal of Software, 2016,27(2): 394-417.
[5]	邓罡, 龚正虎, 王宏 ,等. 现代数据中心网络资源管理技术分析与综述[J]. 通信学报, 2014,35(2): 166-181.
	DENG K , GONG Z H , WANG H ,et al. Analysis and review of network resource management technology in modern data centers[J]. Journal on Communications, 2014,35(2): 166-181.
[6]	CHIESA M , KINDLER G , SCHAPIRA M . Traffic engineering with equal-cost-multipath:an algorithmic perspective[C]// IEEE Infocom. Piscataway:IEEE Press, 2014: 779-792.
[30]	DONG Y , LYU D J , WANG X ,et al. Probabilistic convergence analysis of global randomness for Fibonacci tree optimization algorithm[J]. Control and Decision, 2018,3(1): 1-10.
[31]	王霞, 吕丹桔, 董易 ,等. 基于斐波那契树优化算法的切削参数多方案优化方法[J]. 控制与决策, 2018,8(1): 1373-1381.
[7]	杨洋, 杨家海, 王会 ,等. IP 网络时延敏感型业务流自适应负载衡算法[J]. 通信学报, 2015,36(3): 131-141.
	YANG Y , YANG J H , WANG H ,et al. Adaptive load balancing algorithm for delay-sensitive service flows in IP networks[J]. Journal on Communications, 2015,36(3): 131-141.
[31]	WANG X , LYU D J , DONG Y ,et al. Optimization of cutting parameters based on Fibonacci tree optimization algorithm[J]. Control and Decision, 2018,8(1): 1373-1381.
[32]	周云才 . 黄金分割法在无穷远处是最优的[J]. 石油天然气学报, 1993(1): 97-101.
[8]	杨洋, 杨家海, 秦董洪 ,等. DraLCD:一种新的数据中心流量工程方法[J]. 电子学报, 2017,45(5): 1261-1267.
	YANG Y , YANG J H , QIN D H ,et al. DraLCD:a new data center traffic engineering method[J]. Journal of Electronics, 2017,45(5): 1261-1267.
[32]	ZHOU Y C . The golden section method is optimal at infinity[J]. Journal of Oil and Gas Technology, 1993(1): 97-101.
[33]	吴汉洪 . 次优理论述评[J]. 学术论坛, 2002(1): 74-76.
[9]	HARTERT R , VISSICCHIO S , SCHAUS P ,et al. A declarative and expressive approach to control forwarding paths in carrier-grade networks[J]. ACM SIGCOMM Computer Communication Review, 2015,45(5): 15-28.
[10]	AL-FARES M , RADHAKRISHNAN S , RAGHAVAN B ,et al. Hedera:dynamic flow scheduling for data center networks[C]// USENIX Symposium on Networked Systems Design ＆ Implementation. New York:ACM Press, 2010: 281-296.
[33]	WU H H . A review of suboptimal theory[J]. Academic Forum, 2002(1): 74-76.
[34]	OLIVEIRA R L S D , SHINODA A A , SCHWEITZER C M ,et al. Using Mininet for emulation and prototyping software-defined networks[C]// Communications ＆ Computing. Piscataway:IEEE Press, 2014: 25-42.
[11]	林智华, 高文, 吴春明 ,等. 基于离散粒子群算法的数据中心网络流量调度研究[J]. 电子学报, 2016,44(9): 2197-2202.
	LIN Z H , GAO W , WU C M ,et al. Research on data center network traffic scheduling based on discrete particle swarm optimization[J]. Chinese Journal of Electronics, 2016,44(9): 2197-2202.
[35]	RAMADONA S , HIDAYATULLOH B A , SISWANTO D F ,et al. The simulation of SDN network using POX controller:case in PoliteknikCaltex Riau[C]// International Conference on Telecommunication Systems Services ＆ Applications. Piscataway:IEEE Press, 2015: 1186-1217.
[36]	刘红, 白栋, 丁炜 . 应用于MPLS网络负载均衡的启发式自适应遗传算法研究[J]. 通信学报, 2003,24(10): 39-45.
[12]	SUBBIAH S , PERUMAL V . Energy-aware network resource allocation in SDN[C]// International Conference on Wireless Communications. Piscataway:IEEE Press, 2016,doi:10.1109/WiSPNET.2016.7566506.
[13]	唐宏, 王欣欣, 刘亦星 . 面向带宽碎片最小化和QoS保障的数据中心网络流量调度算法[J]. 电子与信息学报, 2019,41(4): 987-994.
[36]	LIU H , BAI D , DING W . Research on heuristic adaptive genetic algorithm for load balancing in MPLS networks[J]. Journal on Communications, 2003,24(10): 39-45.
[37]	伊鹏, 刘洪, 胡宇翔 . 一种可扩展的软件定义数据中心网络流调度策略[J]. 电子与信息学报, 2017,38(4): 825-831.
[13]	TANG H , WANG X X , LIU Y X . A traffic scheduling algorithm for bandwidth fragmentation minimization and QoS guarantee in data center network[J]. Journal of Electronics ＆ Information Technology, 2019,41(4): 987-994.
[14]	王欣欣 . 基于蚁群算法的数据中心网络流量调度策略研究[D]. 重庆:重庆邮电大学, 2019.
[37]	YI P , LIU H , HU Y X . A scalable software-defined data center network flow scheduling strategy[J]. Journal of Electronics ＆ Information Technology, 2017,38(4): 825-831.
[38]	王耀民 . 昆明电信IP城域网网络路由优化改造方案的技术研究[D]. 南京:南京邮电大学,
[14]	WANG X X . Research on data center network traffic scheduling strategy based on ant colony algorithm[D]. Chongqing:Chongqing University of Posts and Telecommunications, 2019.
[15]	王歆平, 王茜, 刘恩慧 ,等. 基于SDN的按需智能路由系统研究与验证[J]. 电信科学, 2014,30(4): 8-14.
	WANG Y P , WANG Q , LIU E H ,et al. Research and verification of SDN-based intelligent routing system on demand[J]. Telecommunications Science, 2014,30(4): 8-14.
[16]	BENSON T , AKELLA A , MALTZ D A . Network traffic characteristics of data centers in the wild[C]// ACM SIGCOMM Conference on Internet Measurement. New York:ACM Press, 2010: 267-280.
[17]	金勇, 刘亦星, 王欣欣 . 基于SDN的数据中心网络多路径流量调度算法[J]. 计算机科学, 2019(6): 90-94.
	JIN Y , LIU Y X , WANG X X . Multi-path traffic scheduling algorithm for data center networks based on SDN[J]. Computer Science, 2019(6): 90-94.
[18]	刘亦星 . 基于 SDN 的数据中心多路径流量调度策略研究[D]. 重庆:重庆邮电大学, 2019.
	LIU Y X . Research on multi-path traffic scheduling strategy of data center based on SDN[D]. Chongqing:Chongqing University of Posts and Telecommunications, 2019.
[19]	王耀民, 王霞, 董易 ,等. 面向云数据中心的多业务差异化流量管理优化策略[J]. 通信学报, 2019,40(11): 45-56.
	WANG Y M , WANG X , DONG Y ,et al. Multi-service differentiated traffic management optimization strategy for cloud data centers[J]. Journal on Communications, 2019,40(11): 45-56.
[38]	WANG Y M . Technical research on the optimization and reconstruction scheme of Kunming Telecom’s IP metropolitan area network[D]. Nanjing:Nanjing University of Posts and Telecommunications,

测试函数	峰值序号	最优解	函数值	理论值
	1	0.099 9	-0.998 5	-1.000 0
	2	0.299 6	-0.927 5	-0.927 4
f ₁(x)	3	0.499 2	-0.771 2	-0.771 2
	4	0.698 8	-0.574 1	-0.574 1
	5	0.898 4	-0.382 6	-0.382 6
	1	2.651 2	-1.944 6	—
	2	3.010 8	-1.516 2	—
	3	2.116 6	-0.725 4	—
	4	3.281 1	-0.699 5	—
f₂ (x)	5	3.949 0	-0.466 9	—
	6	3.494 8	-0.158 8	—
	7	3.819 6	-0.140 5	—
	8	1.048 1	-0.013 3	—
	9	3.670 5	-1.632 8e-04	—
	1	(-0.010 6,0.010 9)	-3 566.800 0	-3 600
	2	(-5.120 0,5.120 0)	-2 748.800 0	-2 748
f ₃(x)	3	(5.120 0,-5.120 0)	-2 748.800 0	-2 748
	4	(5.120 0,5.120 0)	-2 748.800 0	-2 748
	5	(-5.120 0,- 5.120 0)	-2 748.800 0	-2 748

实验参数	参数设置
网络节点	D=20
网络链路	L=48
业务数量	K=50
业务带宽	(0,1 000)随机取值
实验1迭代次数	300
所需解	3
距离参数	200
业务数量	K=100
业务带宽	(500,1 000)随机取值
实验2迭代次数	500
所需解	3
距离参数	100

算法	最优解	次优解	次次优解	迭代次数	多模特性
GA	55.43%	—	—	300	×
ACO算法	53.62%	—	—	300	×
FTO算法	46.53%	47.26%	51.83%	300	√

算法	最优解	次优解	次次优解	迭代次数	多模特性
GA	83.16%	—	—	500	×
ACO算法	76.22%	—	—	500	×
FTO算法	71.56%	74.37%	81.49%	500	√