一种基于端口聚合流量的Coflow调度机制*

黄 鸿，莫李思，孙 罡

（1.电子科技大学，信息与通信工程学院，四川 成都 611731；2.中国电子科技集团第三十研究所，四川 成都 610041）

0 引 言

Coflow被定义为一组具有共同性能目标的协同数据流量的集合，通常是指同一项并行计算应用在通信阶段产生协同数据流的集合[1]。集合中每条单独流量被称为这个Coflow的一条子流。Coflow的完成时间取决于其中子流传输完成时间的最大值[2]。由于Coflow的传输完成时间上具有协同性，传统的网络流调度相关手段不能很好地适用于Coflow，因此需要对适用于Coflow的流量调度方案进行研究，以便优化Coflow的传输完成时间，从而提高数据中心对并行计算应用的处理能力[3-4]。近年来，数据中心Coflow完成时间的优化问题吸引了广大研究者关注。基于Coflow相关信息的可知性，这方面的研究可以进一步被分为两类——先验知识已知的调度机制[5-7]和先验知识未知的调度机制[8-10]。先验知识已知的调度机制，指决策时能够获知完整的Coflow特征，包括Coflow中子流的数量、各子流的大小以及持续时间等。先验知识未知的调度机制，指决策时不能够获知完整的Coflow特征，或者完全不能知道Coflow的任何特征信息。

上述两个不同的研究场景中，先验知识已知的调度机制由于拥有充足的信息，其思路通常是以最小化平均Coflow完成时间为目标函数，根据网络拓扑、网络容量以及业务需求建立约束条件，建立最优化问题模型。这种场景下的调度方案一般会得到较为详细的调度策略，包括Coflow每条子流的路由指定和在对应路径上的带宽分配，优化效果较好。但是，该场景下的Coflow调度机制通常需要假设主机功能足够强大，能够提供完整的Coflow信息。这通常是不实际的，不适用于实际数据中心网络环境[11-13]。本文是基于先验知识未知场景，以最小化平均Coflow完成时间为目标的Coflow调度机制研究。由于无法知道Coflow中每条子流的大小，通常先验知识未知的Coflow调度机制不会给出明确的路由和带宽分配方案，而是按照一定策略给Coflow制定优先级，并依据Coflow的优先级给不同Coflow分配带宽。其中，关键技术是如何为Coflow制定优先级。以Aalo[8]为代表，现有方案多以Coflow大小作为Coflow优先级的制定标准，缺乏一定的合理性。同时，现有方案为Coflow制定优先级时需要对Coflow大小进行估计，但采用的估计方法通常过于粗糙。

针对以上问题，本文提出了一种基于端口聚合流量的Coflow调度机制（Coflow Scheduling based on Port Aggregate Traffic，CSPAT）。首先改进Coflow大小的估计方式，统计Coflow中每条子流的相关统计量，据此给出Coflow中每条子流的大小估计，再依据各端口子流的聚合情况，得到各端口Coflow聚合流量大小的估计值。然后，改进Coflow优先级制定方式，以Coflow端口最大聚合流量大小作为Coflow优先级划分依据。同时，改进现有方案中优先级阈值的设置方式，改善有效优先级数量退化的问题。仿真结果显示，本文提出的Coflow调度机制相较Aalo能有效提高平均Coflow完成时间的优化效果。

1 CSPAT调度机制核心思想

CSPAT的主要思想是端设备统计各Coflow当前大小，并根据Coflow中各子流的到达速率预测即将到达的子流大小，从而估计各端系统Coflow的大小，将估计结果周期性上报给控制器。控制器根据上报的结果，得到各Coflow的端口聚合流量的大小，再根据端口聚合流量的阈值设置，得到Coflow对应的优先级队列，并下发优先级队列对应关系到各端设备。端设备根据对应关系将Coflow放置到对应优先级队列中。不同优先级队列之间按照WFQ调度策略进行调度，同一优先级队列中的不同Coflow按照FIFO策略进行调度，同一优先级队列中同一Coflow的不同子流之间按照max-min策略进行带宽分配。

CSPAT调度机制基于的网络抽象模型，如图1所示。整个数据中心交换网络被抽象为一个无阻交换机，调度发生在整个抽象无阻交换机的输入端口上。

图1 CSPAT调度机制的网络抽象模型

基于这种抽象的网络结构，CSPAT的调度框架主要由与输入端口相连的主机以及执行调度算法的控制器所构成。图2给出了主机与控制器之间信息交互方式的示意。主机向控制器上报的Coflow大小估计值信息会沿着直线箭头方向，从边缘交换机接入数据平面网络，通过数据平面网络传输到与控制器直连的边缘交换机，最后递交给控制器。而控制器下发的Coflow优先级对应关系信息会沿着虚线箭头所示反向通路，发送到各主机处。

主机侧执行本地或者全局的调度策略。如何选择取决于主机是否收到从控制器下发的关于Coflow的调度策略。若控制器没有下发关于某个Coflow的调度策略，则对该Coflow执行本地调度策略；否则，根据控制器下发的Coflow优先级信息进行调度。同时，主机侧需要周期性上报对应输入端口的Coflow大小估计值，以便控制器能及时感知Coflow的大小估计值的变化，从而制定符合当前负载情况下的调度策略。

图2 CSPAT调度机制中主机与控制器的交互

控制器侧则周期性地整合各入端口上报的Coflow大小估计值，计算各Coflow的端口聚合流量大小，再根据端口聚合流量的大小和优先级阈值，对各Coflow进行优先级划分，并把划分结果下发给各入端口。主机侧根据Coflow对应的优先级，将Coflow放到对应的优先级队列中。不同优先级队列之间利用WFQ策略进行调度。Coflow端口聚合流量的物理意义是指Coflow在数据中心网络入端口和出端口处的最大聚合流量大小，其中聚合流量是指Coflow在该端口所有子流的总和。以上只是简单介绍了主机侧以及控制器侧执行的基本逻辑，详细的算法描述将在第2节进行介绍。

2 CSPAT调度机制算法流程

正如第1节所述，CSPAT调度框架是通过主机侧与控制器侧的相互配合完成的。主机侧和控制器侧设有同步的周期，它们各自在自己的周期里执行各自的算法逻辑。下面将分别对主机侧和控制器侧所执行的算法逻辑进行详细介绍。为了方便算法的描述，先引入一些相关参数的说明，如表1所示。

表1 算法相关参数说明

表1所示的相关参数之间存在一些计算关系，在算法流程中会用到式（1）～式（4）所示的计算。

2.1 主机侧算法流程

主机负责本侧端口的Coflow大小估计和Coflow调度。在自己的周期内，它需要同时执行两套算法逻辑。一是对Coflow相关信息进行统计，并基于这些信息对本侧Coflow大小进行估计，然后周期性上报Coflow大小估计值给控制器，本文将这部分逻辑称为“主机侧Coflow大小估计算法”。二是执行本地或者全局的调度策略，如何选择取决于主机是否收到从控制器下发的关于Coflow的调度策略，若控制器没有下发关于某个Coflow的调度策略，则对该Coflow执行本地调度策略，否则根据控制器下发的Coflow优先级信息进行调度，本文将这部分逻辑称为“主机侧Coflow调度算法”。

图3为“主机侧Coflow子流大小估计算法”流程图。算法实现的功能是对主机本地的Coflow中每条子流的大小做估计。其中，主机侧本地Coflow中每条流的大小估计通过式（1）实现。公式采用了三个统计量的累加值作为流大小的估计值。总的来说，流大小的估计值是由两个已知统计量以及一个估计值之和构成。三个统计量都是动态变化的，其中描述的是流在传输队列中的累计大小，构成了该流已产生但还未被传输的部分，能反映出流到达以及流传输速率的差距；描述的是流已经传输完成的大小，是单调不减的，构成了该流完成传输的部分；a_ periodin,c描述的是根据该流的到达情况，预测下一周期该流即将到达的流量大小。这个假设是基于Coflow中各流的到达速率可能不同，但每条流自身的速率是均匀的，因此用上一周期到达的流量作为下一周期到达流量的一个估计。又因为提前预测了下一个周期可能到达的流量大小，可以在一定程度上平滑控制算法下发策略的延迟造成策略与场景不匹配的情况。另外，算法是周期性执行的，如果没有到仿真结束时间，算法会一直持续周期性运行。

图3 主机侧Coflow大小估计算法流程

“主机侧Coflow调度算法”包含并行的三个环节：数据报文进入传输队列的处理逻辑（数据报文入队逻辑）、数据报文离开传输队列的处理逻辑（数据报文出队逻辑）和控制器报文处理逻辑。图4～图6分别是这三个环节的处理逻辑流程图。

首先对数据报文入队逻辑进行说明。为了便于动态调整Coflow的优先级，Coflow报文入队时首先不会进入到物理传输队列中。本方案在设计中采用了一个虚拟队列，按照Coflow编号分类来存储这些到达的Coflow报文。这个虚拟队列即图4中提到的“与Coflow编号对应的存储队列”。入队逻辑对到达的Coflow报文的处理分两种情况：若某个报文所属Coflow已经在之前到达过虚拟队列，则该报文直接放入对应Coflow编号的存储队列；若该报文所属Coflow是新到达的（图中用“没有该Coflow记录”来表征这种情况），则将该Coflow编号按照到达时间顺序，加入到“Coflow优先级map”的最高优先级对应集合，即图中所说的“更新Coflow优先级map”。这里对“Coflow优先级map”进行说明。这个结构需要用一个map来实现，其key值为按照Coflow的端口聚合流量划分的优先级，而每个key对应的value是经控制器计算具有同一个优先级的Coflow编号的集合。这个集合是有序的，会按照Coflow到达的先后顺序进行排序，这就是图4中存储Coflow到达时间的原因。这部分逻辑在每次产生报文即将进入传输队列时被触发。

图4 数据报文入队逻辑

图5的数据报文出队逻辑则比较简单，主要是通过WFQ调度策略获得本轮应该被传输的Coflow编号，然后通过编号找到对应的Coflow存储队列，对该Coflow存储队列中的报文进行传输。其中，WFQ策略是根据优先级对应权重，实现不同优先级队列中的流量按照权重公平分配带宽的一种队列调度方法，具体的原理如文献[14]所述。这部分逻辑将在前一个报文传输完成后和有新报文入队时被触发。

图5 数据报文出队逻辑

图6 所示的控制器报文处理逻辑，在主机端接收到从控制器发来的报文时被触发，主要用于更新上面提到的“Coflow优先级map”。由于对Coflow的端口聚合流量的估计会随时间变化，经控制器算法的计算，Coflow的优先级也有可能发生改变。这部分逻辑用于让主机适应动态的Coflow优先级对Coflow进行调度。

2.2 控制器侧算法流程

控制器负责在自己的周期内整合各主机上报的Coflow大小估计值，计算每个Coflow的端口聚合流量大小，再根据端口聚合流量的大小和优先级阈值，对各Coflow进行优先级划分，并把划分结果下发给各主机，供主机执行“主机侧Coflow调度算法”使用。本研究中将这部分逻辑称为“Coflow优先级制定算法”。

图7即为“Coflow优先级制定算法”流程图。在算法执行周期内，控制器会不断接收来自各主机上报的本地Coflow子流大小估计值，并对其进行存储。到了控制器算法周期时，根据这些存储的数据计算每个Coflow对应的端口聚合流量的大小。有了各Coflow的端口聚合流量的大小，再根据端口聚合流量优先级阈值，可以得到各Coflow的优先级。Coflow优先级的计算每隔一定周期触发执行一次，如果没有到仿真结束时间，算法会一直持续周期性运行。

图6 控制器报文处理逻辑

图7 Coflow优先级制定算法

这里对算法中使用的端口聚合流量优先级阈值进行说明。为了避免传统的阈值设置方式中采用绝对数值导致有效优先级数量退化的情况，本文将阈值设置成一组从小到大、取值范围在（0，1）的数值。若该阈值共包含k个数值，设这些数值分别为{d1,d2,…,dk}，则该组数值能将端口聚合流量可能的取值范围分为k+1个区间，分别为{[0,d1],[d1,d2],…[dk,1]}，k的取值是人为指定的。各区间对应的下限数值越小，则该区间对应的优先级越高，对应权重越大。设Coflow总数为N，则Coflow端口最大聚合流量大小按从小到大的顺序排序后，排序在0到d1×N的Coflow对应最高优先级，排序在d×N到d2×N的Coflow对应第二优先级，以此类推。这样的优先级阈值设置方式，可以尽可能让Coflow分布在不同的优先级中，避免Coflow全部集中在某一优先级中导致有效优先级数量退化的问题。

3 算法仿真及性能分析

CSPAT调度机制中存在几个环节，可能对整个调度机制的性能产生影响，包括控制器算法周期和阈值的设置。分别对这些环节进行仿真实验，说明采样周期和阈值设置对CSPAT调度机制性能带来的影响，最后综合考察CSPAT调度机制相较文献[8]提出的Aalo调度机制的性能优势。仿真采用的是一个包含132个主机节点的2层CLOS交换网络，如图8所示。以下仿真均基于该网络拓扑。

图8 仿真拓扑

3.1 控制算法周期对CSPAT性能的影响

为了缩短仿真时间，仿真中注入了5个Coflow，18条流，共计30 647个TCP报文进行仿真。主机直连链路带宽为1 Gb/s。选取了0.1 ms到1 s内的12个不同周期取值，记录在不同控制算法周期下Coflow的平均完成时间，仿真结果如图9所示（横坐标采用对数坐标）。从仿真结果看，控制算法周期过小以及过大都会使Coflow平均完成时间增加，严重影响CSPAT调度机制的性能。算法周期是否选择合适，要考虑几个方面的因素：（1）周期不能大于仿真时间，且在仿真时间内周期也不宜过大，以至于在一次仿真中不能进行有效次数的调度；（2）周期不宜过小，以至于网络场景波动大.以上一个较短周期数据做出的决策，可能不会适用于策略下发时的场景。

如图9所示，算法周期取值在1 ms、2 ms、5 ms时，能在选取的所有周期中得到最好的优化效果。本文的仿真中考虑到通信开销，会将周期选定为5 ms。

图9 不同控制算法周期下的Coflow完成时间统计

3.2 优先级阈值设置对CSPAT性能的影响

CSPAT调度机制依据优先级阈值为不同Coflow制定优先级，并依据优先级进行调度.因此，优先级阈值设置对调度机制性能有着重要影响。优先级阈值设置包括优先级数量和优先级阈值区间两个方面。但是，同时考虑这两个方面的协同作用会导致问题求解难度过大。为了简化该问题的分析，得到可行的优先级阈值设置方案，本文使得优先级阈值的数量恒定，仅讨论优先级阈值区间设置对调度机制性能的影响。根据Aalo调度机制的优先级阈值设置方式，当优先级阈值数量大于等于5时，能取得不错的效果。而考虑到过多的优先级阈值数量会增加计算复杂度，本文将优先级阈值数量恒定为5，并分别对表2所示的5种不同的优先级阈值区间取值方式进行性能测试，测试结果如图10所示。

表2 CSPAT优先级阈值区间取值类型

如表2所示，测试中A类型的特点是尽可能使得每个区间对应优先级包含的Coflow数量相同；B类型和C类型的特点都是使得高优先级包含的Coflow数量相较于低优先级更多，区别是B类型和C类型在高优先级到低优先级包含的Coflow数量递减比例上有所不同。

图10 不同优先级阈值设置下的调度机制性能对比

从图10可以看出，B类型阈值取值方式是最优的，而A类型这种平均的区间划分方式虽在平均Coflow完成时间的优化效果上不及B类型，但差距不是很大。相比之下，C类型则会对平均Coflow完成时间的优化造成较大影响。考虑到递减比例设置不当会明显有损性能，之后的仿真都采用A类型所代表的优先级阈值设置方式。

3.3 CSPAT性能对比分析

本节将对CSPAT与现有其他两种Coflow调度机制Aalo以及MCS进行性能对比。

在合适的控制算法周期和优先级阈值的设置下，采用在Facebook数据源中随机采样的方法生成多组流量数据进行仿真，测试在真实流量环境下CSPAT、Aalo以及MCS各自的性能表现。图11是在不同Coflow规模下，CSPAT、Aalo以及MCS调度机制的仿真结果。其中，平均Coflow完成时间以CSPAT的结果为标准进行了归一化处理。

图11 不同调度机制的平均Coflow完成时间统计

从图11可以看出，在服从Facebook数据源分布生成随机的仿真数据时，CSPAT能够取得优于Aalo的优化效果，相较Aalo能够减少3%的Coflow平均完成时间。而相较MCS调度机制，则性能提升不大，在1.5%左右。最好情况下，CSPAT相较于MCS有2%左右的性能提升。CSPAT能够有效提高平均Coflow完成时间的优化效果。

4 结 语

本文提出了一种基于端口聚合流量的Coflow队列调度机制CSPAT。它是基于SDN框架的调度方案，主要思想是端设备统计各Coflow当前大小，并根据Coflow中各子流的到达速率预测即将到达的子流大小，从而估计各端系统Coflow的大小，并将估计结果周期性上报给控制器。控制器根据上报的结果，得到各Coflow的端口聚合流量的大小，然后根据端口聚合流量的阈值设置，得到Coflow对应的优先级队列，并下发优先级队列对应关系到各端设备。端设备根据对应关系，在不同优先级的Coflow之间按照WFQ调度策略进行调度。同一优先级队列中的不同Coflow按照FIFO策略进行调度，同一优先级队列中，同一Coflow的不同子流之间按照max-min策略进行带宽分配。

此外，本文对该机制中的部分参数设置进行了仿真分析，得到了效果较好的周期和队列阈值设置方法，并在合适的参数设置下，与Aalo调度机制进行了性能对比。结果显示，在Facebook数据源场景下，CSPAT调度机制在“最小化平均Coflow完成时间”上，相较Aalo有3%左右的性能提升。可见，CSPAT在不引入较大通信开销的基础上，能够有效减小并行计算应用通信阶段的Coflow平均完成时间。