基于离散粒子群算法的数据中心网络流量调度研究

doi:10.3969/j.issn.0372-2112.2016.09.026

电子学报 ›› 2016, Vol. 44 ›› Issue (9): 2197-2202.DOI: 10.3969/j.issn.0372-2112.2016.09.026

基于离散粒子群算法的数据中心网络流量调度研究

林智华^1,2, 高文², 吴春明², 李勇燕³

1. 福建江夏学院电子信息科学学院, 福建福州 350108;
2. 浙江大学计算机学院, 浙江杭州 310027;
3. 绍兴文理学院上虞分院, 浙江上虞 312300

收稿日期:2014-11-10 修回日期:2015-03-06 出版日期:2016-09-25
- 作者简介:
- 林智华 男,1972年12月生于福建福州,现为福建江夏学院电子信息科学学院副教授,主要研究方向为新一代网络技术.E-mail:lindiva@126.com
- 基金资助:
- 973计划 (No.2012CB315903）; 浙江省重点科技创新团队 (No.2011R50010-21）; 国家科技支撑计划 (No.2014BAH24F01）; 国家自然科学基金 (No.61379118）

Data Center Network Flow Scheduling Based on DPSO Algorithm

LIN Zhi-hua^1,2, GAO Wen², WU Chun-ming², LI Yong-yan³

1. College of Electronics Information Engineering, Fujian Jiangxia University, Fuzhou, Fujian 350108, China;
2. College of Computer Science, Zhejiang University, Hangzhou, Zhejiang 310027, China;
3. University of Shaoxing at Shangyu, Shangyu, Zhejiang 312300, China

Received:2014-11-10 Revised:2015-03-06 Online:2016-09-25 Published:2016-09-25
- Supported by:
- National Program on Key Basic Research Project of China (973 Program) (No.2012CB315903); Key Science and Technology Innovation Team of Zhejiang Province (No.2011R50010-21); National Key Technology Research and Development Program of the Ministry of Science and Technology (No.2014BAH24F01); National Natural Science Foundation of China (No.61379118)

摘要/Abstract

摘要：

数据中心网络利用多个并行路径为集群计算等网络服务提供高对分带宽.然而，现有的流量调度算法可能会引起链路负载不均衡，核心交换机冲突加剧，造成网络总体性能降低.本文将流调度问题转化成0-K背包问题求解，提出基于离散粒子群的流调度算法DPSOFS（Discrete Particle Swarm Optimization Flow Scheduling）.该算法根据Fat-Tree结构特点定义了粒子速度、位置和运算规则，以两次迭代冲突流个数差值作为目标函数，并限定路径搜索范围，减少随机搜索的盲目性.仿真实验验证了该算法对减少流冲突快速有效，能提高网络对分带宽.

关键词: Fat-Tree, 数据中心网络, 离散粒子群, 流调度

Abstract:

Data center networks leverage multiple parallel paths connecting end host pairs to offer high bisection bandwidth forcluster computing applications.However,state of the art flow scheduling algorithms may cause unfair link utilization and saturation of core switches,resulting in overall bandwidth loss.In the paper,we regard the flow scheduling problem as a 0-K knapsack problem and propose a new flow scheduling algorithm named DPSOFS based on DPSO.DPSOFS formulates the position,velocity and their operation rules of particles according to Fat-Tree topology structure,and defines objective function as the difference of the number of conflict flows between two iterations.Moreover,our proposed mechanism reduces random search blindness by limiting the range of the path search.The simulation suggests that it can improve overall network bisection efficiently.

Key words: Fat-Tree, data center network, DPSO, flow scheduling

中图分类号:

TP393

林智华, 高文, 吴春明, 等. 基于离散粒子群算法的数据中心网络流量调度研究[J]. 电子学报, 2016, 44(9): 2197-2202.

LIN Zhi-hua, GAO Wen, WU Chun-ming, et al. Data Center Network Flow Scheduling Based on DPSO Algorithm[J]. Acta Electronica Sinica, 2016, 44(9): 2197-2202.

参考文献

[1] Hammadi A,Mhamdi L.A survey on architectures and energy efficiency in data center networks[J].Computer Communications,2014,40(1):1-21.
[2] Zhang Y,Ansari N.On architecture design,congestion notification,TCP incast and power consumption in data centers[J].Communications Surveys & Tutorials,IEEE,2013,15(1):39-64.
[3] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review,2008,38(4):63-74.
[4] Mysore R N,Pamboris A,Farrington N,et al.PortLand:a scalable fault-tolerant layer 2 data center network fabric[J].ACM SIGCOMM Computer Communication Review,2009,39(4):39-50.
[5] Mudigonda J,Yalagandula P,Al-Fares M,et al.SPAIN:COTS data-center ethernet for multipathing over arbitrary topologies[A].Proceedings of Networked System Design and Implementation[C].San Jose:NSDI,2010.265-280.
[6] Guo C,Wu H,Tan K,et al.DCell:a scalable and fault-tolerant network structure for data centers[J].ACM SIGCOMM Computer Communication Review,2008,38(4):75-86.
[7] Guo C,Lu G,Li D,et al.BCube:a high performance,server-centric network architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2009,39(4):63-74.
[8] Lin D,Liu Y,Hamdi M,et al.Hyper-bcube:A scalable data center network[A].Proceedings of International Conferenceon Communications (ICC)[C].Ottawa:IEEE,2012.2918-2923.
[9] Escudero-Sahuquillo J,Garcia 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] Tso F P,Hamilton G,Weber R,et al.Longer is better:exploiting path diversity in data center networks[A].Proceedings of Distributed Computing Systems[C].Philadelphia:IEEE,2013.430-439.
[11] Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:dynamic flow scheduling for data center networks[A].Proceedings of Networked System Design and Implementation[C].San Jose:NSDI,2010.19-19.
[12] Zhang-Shen R,McKeown N.Designing a predictable internet backbone with valiant load-balancing[A].Proceedings of Quality of Service-IWQoS[C].Passau:Springer,2005.178-192.
[13] Bharti S,Pattanaik K K.Dynamic distributed flow scheduling with load balancing for data center networks[J].Procedia Computer Science,2013,19(1):124-130.
[14] Bharti S,Pattanaik K K.Dynamic distributed flow scheduling for effective link utilization in data center networks[J].Journal of High Speed Networks,2014,20(1):1-10.
[15] Cui W,Qian C.Difs:Distributed flow scheduling for adaptive routing in hierarchical data center networks[J].Measurement,2014,5(1):17.
[16] 程祥,张忠宝.基于粒子群优化的虚拟网络映射算法[J].电子学报,2011,39(10):2240-2244. Cheng Xiang,Zhang Zhong-bao.Virutal network embedding based on particle swarm optimization[J].Acta Electronica Sinica,2011,39(10):240-2244.(in Chinese)
[17] Lantz B,Heller B,McKeown N.A network in a laptop:rapid prototyping for software-defined networks[A].Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks[C].New Delhi:ACM,2010.

基于离散粒子群算法的数据中心网络流量调度研究

Data Center Network Flow Scheduling Based on DPSO Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

[1]	崔子熙, 胡宇翔, 兰巨龙, 王雨. 基于流分类的数据中心网络负载均衡机制[J]. 电子学报, 2021, 49(3): 559-565.
[2]	罗智勇, 朱梓豪, 谢志强, 孙广路. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
[3]	臧韦菲, 兰巨龙, 胡宇翔. 基于松弛时间与累计发送量的数据中心网络混合流调度机制[J]. 电子学报, 2019, 47(10): 2061-2068.
[4]	马腾, 胡宇翔, 张校辉. 基于深度增强学习的数据中心网络coflow调度机制[J]. 电子学报, 2018, 46(7): 1617-1624.
[5]	符强, 汪鹏君, 童楠, 王铭波, 张会红. 基于多策略离散粒子群算法的MPRM电路延时与面积优化[J]. 电子学报, 2016, 44(5): 1202-1207.
[6]	马羚, 李海军, 王成刚, 李国峰. 基于改进离散粒子群算法的传感器优化配置[J]. 电子学报, 2015, 43(12): 2408-2413.
[7]	周雅兰, 王甲海, 黄聪. 求解排列问题的分布估计离散粒子群优化算法[J]. 电子学报, 2014, 42(3): 561-571.
[8]	宣恒农, 张润驰, 左苗, 刘田田. 面向数据中心网络的分层式故障诊断算法[J]. 电子学报, 2014, 42(12): 2536-2542.
[9]	尹浩, 张长胜, 张斌, 孙若男, 刘婷婷. 一种求解SLA等级感知服务组合问题的多目标离散粒子群优化算法[J]. 电子学报, 2014, 42(10): 1983-1990.
[10]	朱喜华, 李颖晖, 李宁, 曹华金. 基于改进离散粒子群算法的传感器布局优化设计[J]. 电子学报, 2013, 41(10): 2104-2108.
[11]	黄岚, 齐季, 谭颖, 杨滨. 一种求解矩形排样问题的遗传-离散粒子群优化算法[J]. 电子学报, 2012, 40(6): 1103-1107.
[12]	商云飞, 徐明伟, 李丹. 互联网路由设备与协议节能研究综述[J]. 电子学报, 2012, 40(11): 2290-2297.
[13]	周雅兰;王甲海;印鉴. 一种基于分布估计的离散粒子群优化算法[J]. 电子学报, 2008, 36(6): 1242-1248.
[14]	张国富, 蒋建国, 夏娜, 苏兆品. 基于离散粒子群算法求解复杂联盟生成问题[J]. 电子学报, 2007, 35(2): 323-327.