通信学报 ›› 2020, Vol. 41 ›› Issue (6): 112-127.doi: 10.11959/j.issn.1000-436x.2020075
王耀民1,2,王霞1,董易1,张松海1,施心陵1
修回日期:
2020-03-15
出版日期:
2020-06-25
发布日期:
2020-07-04
作者简介:
王耀民(1986- ),男,云南昆明人,云南大学博士生,主要研究方向为数据中心、软件定义网络、智能优化算法|王霞(1985- ),女,云南保山人,云南大学博士生,主要研究方向为信号系统、智能优化算法|董易(1985- ),男,云南保山人,云南大学博士生,主要研究方向为信号系统、智能优化算法|张松海(1991- ),男,云南昆明人,云南大学硕士生,主要研究方向为智能优化算法|施心陵(1956- ),男,云南昆明人,云南大学教授、博士生导师,主要研究方向为信号处理与信息系统、智能优化算法
基金资助:
Yaomin WANG1,2,Xia WANG1,Yi DONG1,Songhai ZHANG1,Xinling SHI1
Revised:
2020-03-15
Online:
2020-06-25
Published:
2020-07-04
Supported by:
摘要:
为提高运营商数据中心流量调度能力,同时考虑网络结构和网络流量两方面因素,设计了一种软件定义网络(SDN)架构数据中心的流量分析预测在线调度机制。针对数据中心流量调度的多维、多约束和多模态问题,提出基于斐波那契树优化(FTO)算法的流量调度策略,将 FTO 算法嵌入分析预测和在线调度 2 个阶段,发挥FTO算法全局局部交替迭代寻优和多模特性,得到流量调度的最优解和多个有价值的次优解。模拟平台验证表明, FTO流量调度策略能够对数据中心流量进行合理调度,有效提升运营商数据中心网络的负载均衡能力。
中图分类号:
王耀民,王霞,董易,张松海,施心陵. 基于斐波那契树优化算法的数据中心流量调度策略[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.
表1
多峰函数的录优结果"
测试函数 | 峰值序号 | 最优解 | 函数值 | 理论值 |
1 | 0.099 9 | -0.998 5 | -1.000 0 | |
2 | 0.299 6 | -0.927 5 | -0.927 4 | |
f 1(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 | — | |
f2 (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 3(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 |
[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] | 王东滨, 吴东哲, 智慧, 郭昆, 张勖, 时金桥, 张宇, 陆月明. 软件定义网络抗拒绝服务攻击的流表溢出防护[J]. 通信学报, 2023, 44(2): 1-11. |
[2] | 沙宗轩, 霍如, 孙闯, 汪硕, 黄韬. 基于深度强化学习的转发效能感知流量调度算法[J]. 通信学报, 2022, 43(8): 30-40. |
[3] | 尹长川, 李妍珏, 朱海龙, 何欣欣, 韩文璇. HSTC:TSN中的混合流量调度机制[J]. 通信学报, 2022, 43(6): 119-132. |
[4] | 燕昺昊, 刘勤让, 沈剑良, 汤先拓, 梁栋. 软件定义网络中一种快速无循环路径迁移策略[J]. 通信学报, 2022, 43(5): 24-35. |
[5] | 吴平, 常朝稳, 左志斌, 马莹莹. 基于地址重载的SDN分组转发验证[J]. 通信学报, 2022, 43(3): 88-100. |
[6] | 李传煌, 陈泱婷, 唐晶晶, 楼佳丽, 谢仁华, 方春涛, 王伟明, 陈超. QL-STCT:一种SDN链路故障智能路由收敛方法[J]. 通信学报, 2022, 43(2): 131-142. |
[7] | 裴金川, 胡宇翔, 田乐, 胡涛, 李子勇. 联合路由规划的时间敏感网络流量调度方法[J]. 通信学报, 2022, 43(12): 54-65. |
[8] | 吴平, 常朝稳, 马莹莹. 基于端址重载的SDN包转发验证[J]. 通信学报, 2021, 42(7): 70-83. |
[9] | 常朝稳, 金建树, 韩培胜, 祝现威. 基于属性签名标识的SDN数据包转发验证方案[J]. 通信学报, 2021, 42(6): 131-144. |
[10] | 周启钊, 于俊清, 李冬. SDN控制层泛洪防御机制研究:检测与缓解[J]. 通信学报, 2021, 42(11): 41-53. |
[11] | 李硕朋, 方娟, 陈肯. 基于SRv6的确定性网络服务共享保护方案[J]. 通信学报, 2021, 42(10): 32-42. |
[12] | 张千里, 张超凡, 王继龙, 唐翔宇, 沈钲晨, 王会. 基于Telemetry架构的数据中心网络纳秒级时间同步[J]. 通信学报, 2021, 42(10): 117-129. |
[13] | 姚蓝,兰巨龙. 基于联盟博弈的自适应SDN交换机迁移机制[J]. 通信学报, 2020, 41(8): 1-10. |
[14] | 韩珍珍,赵国锋,徐川,周文涛,周洋洋. 基于时延的LEO卫星网络SDN控制器动态放置方法[J]. 通信学报, 2020, 41(3): 126-135. |
[15] | 赖英旭,蒲叶玮,刘静. 基于最小代价路径的交换机迁移方法研究[J]. 通信学报, 2020, 41(2): 131-142. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
|