1、第 40 卷第 3 期计算机应用与软件Vol.40 No 32023 年 3 月Computer Applications and SoftwareMar 2023E-Aalo:面向无先验知识 Coflow 的高效多级队列调度施凌鹏1卢士达1刘云飞2李静21(国网上海市电力公司信息通信公司上海 200072)2(南京航空航天大学计算机科学与技术学院江苏 南京 211106)收稿日期:2020 04 09。施凌鹏，高工，主研领域:信息通信。卢士达，高工。刘云飞，硕士生。李静，副教授。摘要过高的 Coflow 调度时间将会导致数据中心性能下降，如何减小数据中心中语义相关流(Coflow)的平均完成
2、时间是目前数据中心网络流量调度需要解决的重点问题。为了降低先验未知情况下的 Coflow 调度的时间，提出一种面向无先验知识 Coflow 的高效多级队列调度 E-Aalo(Enhanced-Aalo)。采用 Coflow 流量放置策略选择合适的节点减少 Coflow 中需传输的数据量，降低 Coflow 调度的平均完成时间。通过提前调度多级队列中低优先级队列流量进一步优化 Coflow 调度的平均完成时间。实验结果表明，与已有的 Aalo 方法相比，Coflow 调度平均完成时间降低了 12 28%，更接近先验已知情况下的最优调度。关键词Coflow 调度多级队列调度平均完成时间流量放置中图
3、分类号TP3文献标志码ADOI:10 3969/j issn 1000-386x 2023 03 031E-AALO:EFFICIENT MULTI-LEVEL QUEUE SCHEDULING FOCOFLOW WITHOUT PIO KNOWLEDGEShi Lingpeng1Lu Shida1Liu Yunfei2Li Jing21(Information Communication Company，Shanghai Municipal Electric Power Co，Ltd，State Grid，Shanghai 200072，China)2(College of Computer
4、 Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，Jiangsu，China)AbstractExcessive Coflow scheduling time will lead to data center performance degradation How to reduce theaverage completion time of semantically related flows(Coflow)in the data center is a key
5、problem that needs to besolved in data center network traffic scheduling In order to reduce the Coflow scheduling time under priori unknownsituations，an efficient multi-level queue scheduling E-Aalo(Enhanced-Aalo)for Coflow scheduling without priorknowledge is proposed The Coflow traffic placement s
6、trategy was used to select appropriate nodes to reduce the amountof data to be transmitted in Coflow and reduce the average completion time for Coflow schedulingThe averagecompletion time of Coflow scheduling was further optimized by scheduling the low-priority queue traffic in the multi-levelqueue
7、in advance Experimental results show that compared with the existing Aalo method，the average completion timeof Coflow scheduling is reduced by 12 28%，which is closer to the optimal scheduling under the known prior knowledgeKeywordsCoflow schedulingMulti-level queue schedulingAverage completion timeC
8、oflow traffic placement0引言目前，为了提高资源利用率和大规模任务处理的效率，往往通过集群技术将大量多余闲置的计算机连接起来形成云数据中心。在云数据中心中，通常采用Mapeduce1、Spark2 等分布式并行计算框架来处理大规模的数据。由于采用了分布式计算框架，一个作业往往会被划分成多个子任务然后交给数据中心中的多台计算机来完成，在对子任务进行分发及子任务结果进行合并时，会产生大量的中间通信数据流。如果其中的某条数据流没能及时完成，依赖这条数据流结果的后续子任务将无法继续，最终导致作业的完成时间延长3。文献 4 表明这些中间数据通信流传输花202计算机应用与软件2023
9、 年费的时间平均占作业总完成时间的 33%，最高可达50%。所以优化这些中间数据流的完成时间具有十分重要的意义。目前的研究中，具有语义相关的一组通信数据流被称为 Coflow5。Coflow 是一组数据流(flow)的集合，以 Mapeduce 并行计算框架为例，Map 映射阶段需要对作业的任务进行划分和分发(shuffle)，会产生中间通信数据流，educe 归并阶段需要读取 Map 阶段处理完成后的中间结果，也会产生中间通信数据流。为了提高云数据中心的性能，提高其中作业的完成时间，需要对 Coflow 的完成时间(Coflow Completion Time，CCT)进行优化，而不是对单个
10、数据通信流的完成时间(Flow Completion Time，FCT)进行优化。因为对于一个网络，只有当此阶段的所有流都完成，这个阶段的通信才算真正完成，才可以进行下一个阶段的任务。目前的一些研究者在改进降低 FCT 的同时，忽略了应用程序级别的要求，例如方法 PDQ6和 pFab-ric7，往往不能做到网络资源的最优调度。而 Coflow抽象则可以通过网络公开应用程序级别的语义进行弥补，文献 8 9指出这种语义相关的抽象可以提高计算平台的性能。但是目前 Coflow 调度方法也存在一定的缺陷，目前最优方法 Varys10由于需要额外的先验知识而导致其实用性较差;Aalo11无需先验知识但仍
11、存在可以优化的闲置空间和可利用的端口信息。对目前 Coflow 调度的主流方法进行介绍，然后分析目前主流方法存在的实用性不强和 Coflow 平均完成时间过高的缺陷，并提出一种面向无先验知识 Co-flow 的高效多级队列调度 E-Aalo。通过 Coflow 流量放置策略选择所需传输数据最小且负载最小的接收节点来减小 Coflow 的发送量，并对现有 Aalo 方法中的多级队列调度存在的闲置空间通过提前调度低优先级队列中流量进行优化来降低 Coflow 调度的 CCT。最后基于Facebook 的 Mapeduce 公开数据集和 CoflowSim 框架与现有方法进行对比验证。1相关工作为了
12、提高云数据中心应用的性能，对流量进行调度的方法从优化的对象上主要可以分为两类:(1)面向单个数据流(single flow)，优化目标是最小化其FCT，主要的研究工作包括 PDQ6、pFabric7 等，这一类方法往往因为是对单一数据流的调度，而无法做到整个网络资源的最优调度12。(2)面向 Coflow，优化目标是最小化 CCT，主要的研究工作包括 Varys10、Baraat9 和 Aalo10 等。Varys10 基于最小有效瓶颈优先的机制对 Coflow 进行调度，是目前先验知识已知情况下效果最好的方法。Baraar9 采用 FIFO(First InFirst Out)和公平共享机制
13、提高带宽的利用率，进而减少平均 CCT。Aalo10 则是基于队列的多级调度器，为不同的 Coflow 分配不同的优先级来进行调度。目前主要的研究都是围绕面向 Coflo 优化的第二类问题展开，即最小化平均 CCT。对 Coflow 进行优化的方法可分为两类:(1)拥有Coflow 大小等先验知识的 Coflow 调度方法。这方面主要的调度效果最好的有 Varys10，它采用一种最小瓶颈优先(Smallest-Effective-Bottleneck-First，SEBF)机制对瓶颈较小的流优先调度，且控制不同内部流的发送速度，节省了端口的带宽并为其他 Coflow 腾出空间，可以使所有内部流
14、的完成时间一致。其缺陷在于需要提前获取 Coflow 的大小等信息，而这一点往往只有在Coflow 完成之后才能知晓，因此实用性不强。(2)在没有 Coflow 先验信息的情况下对 Coflow 进行调度。Aalo10 是目前最具代表性的方法之一，Aalo 不需要提前知晓 Coflow 的流量大小信息，而是根据 Coflow 当前已经发送的字节数目来判断 Coflow 的大小，通过设置不同优先级的队列并按照优先级对 Coflow 进行调度。Aalo 为每个队列设置阈值，当 Coflow 已发送的字节数超过阈值时降低 Coflow 的优先级。Aalo 拥有较强的实用性，但是其缺陷在于只考虑了 C
15、oflow 当前已发送的字节数目，而没有充分考虑其他有用的信息，如 Co-flow 的宽度信息也是可以利用的，且多级队列也存在可以优化的闲置空间。对于较大一点的 Coflow，Aalo由于缺乏先验知识而表现不如 Varys。A-SEBF(Ap-proximate Smallest-Effective-Bottleneck-First)3 是在先验信息未知的情况下的一种近似最小有效瓶颈优先的 Coflow 调度机制，通过 Coflow 当前大小和宽度信息决定 Coflow 的调度信息，其核心思想是在一定程度上提高宽度大的 Coflow 的优先级，相比于 Aalo，能够显著降低 CCT，效果接近于
16、利用先验知识的 SEBF方法。针对上面方法中存在的 Coflow 平均完成时间较高和可用性不强的问题，提出面向无先验知识 Coflow的高效多级队列调度 E-Aalo，在无先验知识的情况下通过基于计算节点状态的流量放置策略和优化多级队列调度中的闲置空间来降低 Coflow 的平均完成时间，并保证可用性。第 3 期施凌鹏，等:E-Aalo:面向无先验知识 Coflow 的高效多级队列调度2032研究背景2 1数据中心网络抽象模型数据中心中包含大量的计算节点，为了研究的方便，可以将整个数据中心抽象为一个连接了所有计算机的无阻塞大型交换机。这个大型交换机的入口端口对应于服务器的出口链路，而出口端口则对应于服务器的入口链路13 14。通过这种抽象，该模型的优势在于只需要考虑入口端口和出口端口，便于对 Coflow 流量的调度进行分析，且在简单且全平分带宽拓扑结构下具有很高的实用性，目前已经被大量的研究者采纳。数据中心抽象模型如图 1 所示。图 1 是由 n 个入口端口和 n 个出口端口组成的一个大型无阻塞交换机，即数据中心抽象模型，这些入口端口和出口端口是对数据中心中各个主机的流量输入和输出端
