ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (9): 1920-1930.doi: 10.7544/issn1000-1239.2018.20180156

所属专题: 2018优青专题

• 综述 • 上一篇    下一篇



  1. (并行与分布处理国家重点实验室(国防科技大学) 长沙 410073) (国防科技大学计算机学院 长沙 410073) (
  • 出版日期: 2018-09-01
  • 基金资助: 
    国家自然科学基金优秀青年科学基金项目(61222205) This work was supported by the National Natural Science Foundation of China for Excellent Young Scientists (61222205).

Recent Advances in Datacenter Flow Scheduling

Hu Zhiyao, Li Dongsheng, Li Ziyang   

  1. (Science and Technology on Parallel and Distributed Processing Laboratory (National University of Defense Technology), Changsha 410073) (College of Computer, National University of Defense Technology, Changsha 410073)
  • Online: 2018-09-01

摘要: 数据中心网络流调度技术对数据中心网络的性能具有重要影响.它是指对数据中心应用产生的网络数据流,通过控制和调度这些网络流在数据中心网络中的传输链路、传输优先级、传输速率等,以优化网络流量的传输(包括减少数据流平均完成时间、降低加权的平均完成时间、降低数据流尾部完成时间、最大化满足有传输时限的数据流、提高网络资源利用率等),最终实现优化用户体验的目的.首先,对数据中心网络流调度问题及其面临的挑战进行简单介绍.流调度的关键挑战在于设计低开销、高效率的调度算法,以及在终端电脑或者网络交换机上实现调度算法.然后,从独立数据流调度方法和网络流组的调度方法进行综述.这2类流调度技术的区别在于应用的环境(如Web搜索和大数据分析)不同.最后,对未来流调度技术的发展方向进行展望,并且提出多个尚未解决、但仍值得研究的问题.

关键词: 数据中心, 独立数据流调度, 数据流调度, 分布式计算, 网络流组调度

Abstract: Flow scheduling techniques impose an important impact on the performance of the data center. Flow scheduling techniques aim at optimizing the user experience by controlling and scheduling the transmission link, priority and transmission rate of data flows. Flow scheduling techniques can achieve various optimization objects such as reducing the average or weighted flow completion time, decreasing the delay of long-tail flows, optimizing the transmission of flows with deadline constraints, improving the utilization of the network link. In this paper, we mainly review the recent research involving flow scheduling techniques. First, we briefly introduce data center and flow scheduling problem and challenges. These challenges mainly lie in the means to implement flow scheduling on network devices or terminal hosts, and how to design low-overhead highly-efficient scheduling algorithms. Especially, the coflow scheduling problem is proved NP-Hard to solve. Then, we review the latest progress of flow scheduling techniques from two aspects, i.e., single-flow scheduling and coflow scheduling. The divergence between single-flow scheduling techniques and coflow scheduling techniques is the flow relationship under different applications like Web search and big data analytics. In the end of the paper, we outlook the future development direction and point out some unsolved problems involving flow scheduling.

Key words: data center, single-flow scheduling, flow scheduling, distributed computing, coflow scheduling