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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 20

References 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,

Metrics

Recommended 0

No Suggested Reading articles found!

测试函数	峰值序号	最优解	函数值	理论值
	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	√

Data center traffic scheduling strategy based on Fibonacci tree optimization algorithm

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 38

Related Articles 15

Metrics

Recommended 0

[1]	Zhiyong LUO, Yu ZHANG, Qing WANG, Weiwei SONG. Study of SDN intrusion intent identification algorithm based on Bayesian attack graph [J]. Journal on Communications, 2023, 44(4): 216-225.
[2]	Zongxuan SHA, Ru HUO, Chuang SUN, Shuo WANG, Tao HUANG. Forwarding efficiency aware traffic scheduling algorithm based on deep reinforcement learning [J]. Journal on Communications, 2022, 43(8): 30-40.
[3]	Changchuan YIN, Yanjue LI, Hailong ZHU, Xinxin HE, Wenxuan HAN. HSTC: hybrid traffic scheduling mechanism in time-sensitive networking [J]. Journal on Communications, 2022, 43(6): 119-132.
[4]	Jinchuan PEI, Yuxiang HU, Le TIAN, Tao HU, Ziyong LI. Time-sensitive network traffic scheduling method with joint routing planning [J]. Journal on Communications, 2022, 43(12): 54-65.
[5]	Jianzhong SU, Huayu ZHANG, Hailong ZHU. Computing method for periodic stream reservation in TSN combined with SDN controller [J]. Journal on Communications, 2021, 42(10): 23-31.
[6]	Zhenzhen HAN,Guofeng ZHAO,Chuan XU,Wentao ZHOU,Yangyang ZHOU. Dynamic SDN controller placement based on latency in LEO satellite network [J]. Journal on Communications, 2020, 41(3): 126-135.
[7]	Wenlong KE,Yong WANG,Miao YE,Junqi CHEN. Priority differentiated multicast flow scheduling method in Ceph cloud storage network [J]. Journal on Communications, 2020, 41(11): 40-51.
[8]	Xutong ZUO,Mowei WANG,Yong CUI. Low-latency networking:architecture,key scenarios and research prospect [J]. Journal on Communications, 2019, 40(8): 22-35.
[9]	Hongyan QIAN,Hao XUE,Ming CHEN. UDM:NFV-based prevention mechanism against DDoS attack on SDN controller [J]. Journal on Communications, 2019, 40(3): 116-124.
[10]	Guo CHEN,Weifeng ZHANG. ELAB:end-host-based congestion aware load balancing for data center network [J]. Journal on Communications, 2019, 40(3): 196-205.
[11]	Yaomin WANG,Xia WANG,Yi DONG,Lian GAO,Songhai ZHANG,Xinling SHI. Multi-service differentiated traffic management optimization strategy in cloud data center [J]. Journal on Communications, 2019, 40(11): 45-56.
[12]	Hui ZHAO, Liangmin WANG. Hybrid anonymous channel for recipient untraceability via SDN-based node obfuscation scheme [J]. Journal on Communications, 2019, 40(10): 55-66.
[13]	Qian DONG,Jun LI,Yuxiang MA. Traffic scheduling method based on centralized control in named data networking [J]. Journal on Communications, 2018, 39(7): 68-80.
[14]	Tong DUAN,Julong LAN,Yuxiang HU,Hongwei FAN. Orchestration mechanism for VNF hardware acceleration resources in SDN/NFV architecture [J]. Journal on Communications, 2018, 39(6): 98-108.
[15]	Qian DONG,Jun LI,Yuxiang MA,Shujun HAN. Traffic scheduling method based on segment routing in software-defined networking [J]. Journal on Communications, 2018, 39(11): 23-35.