一种基于子流流量值估计方法的Coflow调度方法

摘要

本发明公开了一种基于子流流量值估计方法的Coflow调度方法，包括如下步骤：S1、将Coflow子流流量的估计值周期性上报给控制器；S2：通过控制器侧Coflow优先级制定方法，计算Coflow对应优先级，并下发报文到各主机；S3、主机侧根据Coflow优先级信息，更新Coflow优先级map和各Coflow优先级对应虚拟传输完成时间，生成数据报文；S4、主机侧对数据报文进行入队处理，得到Coflow报文的存储队列；S5、对数据报文进行出队处理，得到调度报文，实现对Coflow进行调度。本发明解决了现有技术存在的缺乏准确性、影响调度策略的优化效果、方案缺乏合理性以及优化性和处理效率低的问题。

说明书

技术领域

本发明属于互联网技术领域，具体涉及一种基于子流流量值估计方法的 Coflow调度方法。

背景技术

数据中心是指由专业机构拥有的大型专用计算机集群，通常具有不同规模， 以满足多样的使用需求。其中服务器数量过万的数据中心通常被一些大型的线 上服务提供商(比如Google、Microsoft以及Amazon)用于运行一些大规模数 据密集型任务，比如网页索引或者大型数据集分析。这些数据密集型任务通常 借助MapReduce范型(或各式变种)在数据中心的集群间进行并行的计算处理， 并在处理过程中产生并行的协同数据流，这样的协同数据流通常用Coflow模型 进行描述。Coflow被定义为一组具有共同性能目标的协同数据流量的集合，通 常是指同一项并行计算应用在通信阶段产生协同数据流的集合。集合中每条单 独流量被称为这个Coflow的一条子流。Coflow的完成时间取决于其中子流传输 完成时间的最大值。由于Coflow的传输完成时间上具有协同性，传统的网络流 调度相关手段不能很好地适用于Coflow，因此，需要对适用于Coflow的流量调 度方案进行研究，以便优化Coflow的传输完成时间，从而提高数据中心对并行 计算应用的处理能力。实际上，Coflow调度方案主要需解决两个问题：(1)同一 Coflow中的各流量如何分配带宽。(2)不同Coflow中的流量如何分配带宽。

近年来，数据中心Coflow完成时间的优化问题吸引了广大研究者关注。基 于Coflow相关信息的可知性，这方面的研究可以进一步被分为两类——先验知 识已知的调度机制、先验知识未知的调度机制。先验知识已知的调度机制，指 决策时能够获知完整的Coflow特征，包括Coflow中子流的数量，各子流的大 小以及持续时间等。先验知识未知的调度机制，指决策时不能够获知完整的 Coflow特征，或者完全不能知道Coflow的任何特征信息。

上述两个不同的研究场景中，先验知识已知的调度机制由于拥有充足的信 息，其思路通常是以最小化Coflow平均完成时间为目标函数，根据网络拓扑、 网络容量以及业务需求建立约束条件，建立最优化问题模型。这种场景下的调 度方案一般都会得到较为详细的调度策略，包括Coflow每条子流的路由指定和 在对应路径上的带宽分配，优化效果较好。但是，该场景下的Coflow调度机制 通常需要假设主机功能足够强大，能够提供完整的Coflow信息，这通常是不实 际的，不适用于实际数据中心网络环境。

现有技术存在的问题如下：

(1)现有技术的仅发送完成的报文累计大小作为Coflow大小估计值的方 法过于粗糙，没有充分利用已知信息，忽略了Coflow当前在网络中的累计状况， 导致对Coflow大小的估计缺乏准确性，影响调度策略的优化效果；

(2)现有技术且仅依据Coflow大小制定Coflow优先级，方案缺乏合理性；

(3)现有技术依据Coflow大小为Coflow制定优先级在一些场景下不利于 减小Coflow平均完成时间，优化性和处理效率低。

发明内容

针对现有技术中的上述不足，本发明提供了一种准确性高、优化性高、合 理性高、高效性和处理效率高的基于子流流量值估计方法的Coflow调度方法， 解决了现有技术存在的缺乏准确性、影响调度策略的优化效果、方案缺乏合理 性以及优化性和处理效率低的问题。

为了达到上述发明目的，本发明采用的技术方案为：

一种基于子流流量值估计方法的Coflow调度方法，包括如下步骤：

S1：使用Coflow子流流量值估计方法，周期性对主机侧各Coflow子流流 量值进行估计，并将Coflow子流流量的估计值周期性上报给控制器；

S2：根据Coflow子流流量的估计值，通过控制器侧Coflow优先级制定方 法，计算Coflow对应优先级，并下发携带Coflow优先级信息的报文到各主机；

S3：在主机侧根据控制器下发的报文中携带的Coflow优先级信息，使用控 制器报文处理方法，调整本地Coflow优先级对应关系，更新Coflow优先级map 和各Coflow优先级对应虚拟传输完成时间，生成数据报文；

S4：在主机侧对步骤S3生成的数据报文进行入队处理，得到Coflow报文 的存储队列；

S5：根据步骤S4得到的存储队列和各Coflow优先级对应虚拟传输完成时 间，对数据报文进行出队处理，得到调度报文，实现对Coflow进行调度。

进一步地，步骤S1中，Coflow子流流量值估计方法，包括如下步骤：

S1-1：判断是否到达主机侧预设上报周期，若是则进入步骤S1-2，执行主 机侧的统计和上报，否则进入步骤S1-4；

S1-2：计算本地Coflow子流的估计值；

S1-3：将Coflow子流周期内到达报文的累计值归零，并重置预设上报周期， 进入步骤S1-1；

S1-4：得到主机侧的Coflow子流周期内到达报文流量的累计值、Coflow子 流在传输队列中的报文流量累计值和Coflow子流传输完成报文流量累计值；

S1-5：判断是否到达预设上报仿真时长，若是则结束主机侧的上报，否则进 入步骤S1-1。

进一步地，步骤S1-2中，本地Coflow子流的估计值的计算公式为：

式中，为本地Coflow子流在发送端主机统计的流量估计值；为 Coflow子流在发送端主机传输队列中的累计报文流量值；为Coflow子流在 发送端主机统计到的传输完成报文累计流量值；为Coflow子流在发 送端主机周期内到达报文的累计值。

进一步地，步骤S2中，控制器侧Coflow优先级制定方法，包括如下步骤：

S2-1：判断是否到达控制器算法预设执行周期，若是则进入步骤S2-2，否 则进入步骤S2-4；

S2-2：根据本地Coflow子流流量的估计值，计算Coflow对应的瓶颈值，并 结合瓶颈阈值，对各Coflow进行优先级的划分，得到各Coflow的对应优先级；

S2-3：将各Coflow的对应优先级编码到报文中，下发至各主机，并重置预 设执行周期，并进入步骤S2-1；

S2-4：统计各主机上报的本地Coflow子流流量的估计值，得到本地Coflow 子流的发送总估计值和本地Coflow子流的接收总估计值；

S2-5：判断是否到达算法预设仿真时长，若是则结束控制器侧控制算法，否 则进入步骤S2-1。

进一步地，步骤S2-2中，Coflow对应的瓶颈值的计算公式为：

式中，bottleneck(c)为Coflow对应的瓶颈值；为本地Coflow子流的发 送总估计值；为本地Coflow子流的接收总估计值；

本地Coflow子流的接收总估计值的计算公式为：

式中，为本地Coflow子流的接收总估计值；为本地Coflow 子流的接收估计值；i∈I_r(n,c)表示接收端主机n中属于Coflow c的流的集合；

本地Coflow子流的发送总估计值的计算公式为：

式中，为本地Coflow子流的发送总估计值；为本地Coflow子 流的发送估计值；I(n,c)为发送端主机n中属于Coflow c的流的集合。

进一步地，步骤S3中，控制器报文处理方法，包括如下步骤：

S3-1：在主机侧解析步骤S2中的报文的内容，得到各Coflow对应的优先 级；

S3-2：根据Coflow与其优先级的对应关系，得到每个优先级包含的Coflow ID，并根据Coflow到达时间的顺序更新Coflow优先级map；

S3-3：判断Coflow优先级map是否改变，若是则进入步骤S3-4，否则不更 新Coflow优先级对应的虚拟传输完成时间，并结束方法；

S3-4：根据WFQ调度方法，计算各Coflow优先级对应的虚拟传输完成时 间。

进一步地，步骤S4中，数据报文入队处理的方法，包括如下步骤：

S4-1：判断主机本地是否有该数据报文所属Coflow的记录，若是则进入步 骤S4-5，否则进入步骤S4-2；

S4-2：判断Coflow优先级map中最高优先级对应队列是否为空，若是则 进入步骤S4-3，否则不更新Coflow最高优先级对应虚拟传输完成时间，并进入 步骤S4-4；

S4-3：根据WFQ调度方法，计算Coflow最高优先级对应虚拟传输完成时 间；

S4-4：将该Coflow的优先级设为最高优先级，并更新主机本地的Coflow优 先级map；

S4-5：将数据报文和该Coflow数据报文的到达时间存入与Coflow编号对应 的存储队列中，并输出存储队列。

8.根据权利要求7所述的基于子流流量值估计方法的Coflow调度方法，其 特征在于，所述步骤S4-3中，Coflow最高优先级对应虚拟传输完成时间的计算 公式为：

式中，V_finish[i]为Coflow优先级对应虚拟传输完成时间；A[i]为位于首位 的Coflow对应存储队列中队首报文的到达时间；P[i]为位于首位的Coflow对应 存储队列中队首报文的报文大小值；w[i]为Coflow优先级i对应权重；w[l]为 Coflow优先级l的对应权重；R为实际链路速率。

进一步地，步骤S5中，数据报文出队处理的方法，包括如下步骤：

S5-1：根据WFQ调度方法和各Coflow优先级对应虚拟传输完成时间，选 择对应虚拟传输完成时间最小的优先级作为本轮待调度Coflow优先级；

S5-2：根据本轮待调度优先级包含的Coflow中的Coflow到达时间，得到 到达时间最早的Coflow作为待调度Coflow，其编号作为TRAN_ID；

S5-3：选择编号为TRAN_ID的Coflow存储队列，从中选择队首报文弹出， 输出调度报文。

S5-4：判断步骤S5-1中得到的本轮待调度Coflow优先级中对应的Coflow 报文是否为空，若是则不更新本轮待调度Coflow优先级的虚拟传输完成时间， 并结束方法，否则进入步骤S5-5；

S5-5：根据WFQ调度方法，计算本轮待调度Coflow优先级的虚拟传输完 成时间。

进一步地，Coflow优先级的虚拟传输完成时间的计算公式为：

式中，V_finish[i]为Coflow优先级对应虚拟传输完成时间；V_start[i]为Coflow优先级对应虚拟传输开始时间；P[i]为位于首位的Coflow对应存储队列中队首 报文的报文大小值；w[i]为Coflow优先级i对应权重；w[l]为Coflow优先级l的 对应权重；R为实际链路速率；

V_start[i]＝max{A[i],V_pre[i]}

式中，V_start[i]为Coflow优先级对应虚拟传输开始时间；A[i]为位于首位的Coflow对应存储队列中队首报文的到达时间；V_pre[i]为Coflow优先级map中 优先级i上一次计算的虚拟传输完成时间。

本方案的有益效果为：

(1)本发明根据Coflow瓶颈大小制定Coflow优先级，充分利用已知信息， 提高了准确性；

(2)改进了Coflow子流大小的估计方法，提高了方案的合理性；

(3)有效减小了平均Coflow完成时间，提高并行计算应用的处理效率；

(4)本发明所提出的Coflow调度机制，部署简单，算法复杂度低，可应 用于大业务量场景，实现数据中心高效的Coflow调度。

附图说明

图1为基于子流流量值估计方法的Coflow调度方法流程图；

图2为Coflow子流流量值估计方法流程图；

图3为控制器侧Coflow优先级制定方法流程图；

图4为控制器报文处理方法流程图；

图5为数据报文入队处理的方法流程图；

图6为数据报文出队处理的方法流程图。

具体实施方式

下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理 解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的 普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精 神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保 护之列。

本发明实施例中，一种基于子流流量值估计方法的Coflow调度方法，如图1 所示，包括如下步骤：

S1：使用Coflow子流流量值估计方法，周期性对主机侧各Coflow子流流 量值进行估计，并将Coflow子流流量的估计值周期性上报给控制器；

Coflow子流流量值估计方法，如图2所示，包括如下步骤：

S1-1：判断是否到达主机侧预设上报周期，若是则进入步骤S1-2，执行主 机侧的统计和上报，否则进入步骤S1-4；

S1-2：计算本地Coflow子流的估计值；

本地Coflow子流的估计值的计算公式为：

式中，为本地Coflow子流在发送端主机统计的流量估计值；为 Coflow子流在发送端主机传输队列中的累计报文流量值；为Coflow子流在 发送端主机统计到的传输完成报文累计流量值；为Coflow子流在发 送端主机周期内到达报文的累计值；

S1-3：将Coflow子流周期内到达报文的累计值归零，并重置预设上报周期， 进入步骤S1-1；

S1-4：得到主机侧的Coflow子流周期内到达报文流量的累计值、Coflow子 流在传输队列中的报文流量累计值和Coflow子流传输完成报文流量累计值；

S1-5：判断是否到达预设上报仿真时长，若是则结束主机侧的上报，否则进 入步骤S1-1；

在Coflow子流流量值估计方法运行时，不会在第一个循环内到达预设上报 周期，从而方法由步骤S1-1直接进入步骤S1-4，得到主机侧的Coflow子流周 期内到达报文流量的累计值、Coflow子流在传输队列中的报文流量累计值和 Coflow子流传输完成报文流量累计值，预设上报周期小于预设上报仿真时长， 重新进入步骤S1-1，当到达主机侧预设上报周期时，进行本地Coflow子流的估 计值的计算；

S2：根据Coflow子流流量的估计值，通过控制器侧Coflow优先级制定方 法，计算Coflow对应优先级，并下发携带Coflow优先级信息的报文到各主机；

控制器侧Coflow优先级制定方法，如图3所示，包括如下步骤：

S2-1：判断是否到达控制器算法预设执行周期，若是则进入步骤S2-2，否 则进入步骤S2-4；

S2-2：根据本地Coflow子流流量的估计值，计算Coflow对应的瓶颈值，并 结合瓶颈阈值，对各Coflow进行优先级的划分，得到各Coflow的对应优先级；

Coflow对应的瓶颈值的计算公式为：

式中，bottleneck(c)为Coflow对应的瓶颈值；为本地Coflow子流的发 送总估计值；为本地Coflow子流的接收总估计值；

本地Coflow子流的接收总估计值的计算公式为：

式中，为本地Coflow子流的接收总估计值；为本地Coflow 子流的接收估计值；i∈I_r(n,c)表示接收端主机n中属于Coflow c的流的集合；

本地Coflow子流的发送总估计值的计算公式为：

式中，为本地Coflow子流的发送总估计值；为本地Coflow子 流的发送估计值；I(n,c)为发送端主机n中属于Coflow c的流的集合；

S2-3：将各Coflow的对应优先级编码到报文中，下发至各主机，并重置预 设执行周期，并进入步骤S2-1；

S2-4：统计各主机上报的本地Coflow子流流量的估计值，得到本地Coflow 子流的发送总估计值和本地Coflow子流的接收总估计值；

S2-5：判断是否到达算法预设仿真时长，若是则结束控制器侧控制算法，否 则进入步骤S2-1；

在控制器侧Coflow优先级制定方法运行时，不会在第一个循环内到达控制 器算法预设执行周期，从而方法由步骤S2-1直接进入步骤S2-4，统计各主机上 报的本地Coflow子流流量的估计值，得到本地Coflow子流的发送总估计值和 本地Coflow子流的接收总估计值，预设执行周期小于算法预设仿真时长，重新 进入步骤S2-1，当到达控制器算法预设执行周期时，根据本地Coflow子流流量 的估计值，计算Coflow对应的瓶颈值，并结合瓶颈阈值，对各Coflow进行优先 级的划分，得到各Coflow的对应优先级；

S3：在主机侧根据控制器下发的报文中携带的Coflow优先级信息，使用控 制器报文处理方法，调整本地Coflow优先级对应关系，更新Coflow优先级map 和各Coflow优先级对应虚拟传输完成时间，生成数据报文；

控制器报文处理方法，如图4所示，包括如下步骤：

S3-1：在主机侧解析步骤S2中的报文的内容，得到各Coflow对应的优先 级；

S3-2：根据Coflow与其优先级的对应关系，得到每个优先级包含的Coflow ID，并根据Coflow到达时间的顺序更新Coflow优先级map；

S3-3：判断Coflow优先级map是否改变，若是则进入步骤S3-4，否则不更 新Coflow优先级对应的虚拟传输完成时间，并结束方法；

S3-4：根据WFQ调度方法，计算各Coflow优先级对应的虚拟传输完成时 间；

Coflow优先级的虚拟传输完成时间的计算公式为：

式中，V_finish[i]为Coflow优先级对应虚拟传输完成时间；V_start[i]为Coflow优先级对应虚拟传输开始时间；P[i]为位于首位的Coflow对应存储队列中队首 报文的报文大小值；w[i]为Coflow优先级i对应权重；w[l]为Coflow优先级l的 对应权重；R为实际链路速率；

V_start[i]＝max{A[i],V_pre[i]}

式中，V_start[i]为Coflow优先级对应虚拟传输开始时间；A[i]为位于首位的Coflow对应存储队列中队首报文的到达时间；V_pre[i]为Coflow优先级map中 优先级i上一次计算的虚拟传输完成时间；

S4：在主机侧对步骤S3生成的数据报文进行入队处理，得到Coflow报文 的存储队列；

数据报文入队处理的方法，如图5所示，包括如下步骤：

S4-1：判断主机本地是否有该数据报文所属Coflow的记录，若是则进入步 骤S4-5，否则进入步骤S4-2；

S4-2：判断Coflow优先级map中最高优先级对应队列是否为空，若是则 进入步骤S4-3，否则不更新Coflow最高优先级对应虚拟传输完成时间，并进入 步骤S4-4；

S4-3：根据WFQ调度方法，计算Coflow最高优先级对应虚拟传输完成时 间；

Coflow最高优先级对应虚拟传输完成时间的计算公式为：

式中，V_finish[i]为Coflow优先级对应虚拟传输完成时间；A[i]为位于首位 的Coflow对应存储队列中队首报文的到达时间；P[i]为位于首位的Coflow对应 存储队列中队首报文的报文大小值；w[i]为Coflow优先级i对应权重；w[l]为 Coflow优先级l的对应权重；R为实际链路速率；

S4-4：将该Coflow的优先级设为最高优先级，并更新主机本地的Coflow优 先级map；

S4-5：将数据报文和该Coflow数据报文的到达时间存入与Coflow编号对应 的存储队列中，并输出存储队列；

S5：根据步骤S4得到的存储队列和各Coflow优先级对应虚拟传输完成时 间，对数据报文进行出队处理，得到调度报文，实现对Coflow进行调度；

数据报文出队处理的方法，如图6所示，包括如下步骤：

S5-1：根据WFQ调度方法和各Coflow优先级对应虚拟传输完成时间，选 择对应虚拟传输完成时间最小的优先级作为本轮待调度Coflow优先级；

S5-2：根据本轮待调度优先级包含的Coflow中的Coflow到达时间，得到 到达时间最早的Coflow作为待调度Coflow，其编号作为TRAN_ID；

S5-3：选择编号为TRAN_ID的Coflow存储队列，从中选择队首报文弹出， 输出调度报文。

S5-4：判断步骤S5-1中得到的本轮待调度Coflow优先级中对应的Coflow 报文是否为空，若是则不更新本轮待调度Coflow优先级的虚拟传输完成时间， 并结束方法，否则进入步骤S5-5；

S5-5：根据WFQ调度方法，计算本轮待调度Coflow优先级的虚拟传输完 成时间；

Coflow优先级的虚拟传输完成时间的计算公式为：

式中，V_finish[i]为Coflow优先级对应虚拟传输完成时间；V_start[i]为Coflow优先级对应虚拟传输开始时间；P[i]为位于首位的Coflow对应存储队列中队首 报文的报文大小值；w[i]为Coflow优先级i对应权重；w[l]为Coflow优先级l的 对应权重；R为实际链路速率；

V_start[i]＝max{A[i],V_pre[i]}

式中，V_start[i]为Coflow优先级对应虚拟传输开始时间；A[i]为位于首位的Coflow对应存储队列中队首报文的到达时间；V_pre[i]为Coflow优先级map中 优先级i上一次计算的虚拟传输完成时间。

本发明提供了一种准确性高、优化性高、合理性高、高效性和处理效率高 的基于子流流量值估计方法的Coflow调度方法，解决了现有技术存在的缺乏准 确性、影响调度策略的优化效果、方案缺乏合理性以及优化性和处理效率低的 问题。