数据中心网络中基于ELM 的流簇大小推理机制

叶 进，谢紫琪，肖庆宇，宋 玲，李晓欢

1.广西多媒体通信与网络技术重点实验室（广西大学计算机与电子信息学院），南宁 530004

2.桂林电子科技大学信息与通信学院，广西桂林 541004

3.综合交通大数据应用技术国家工程实验室（广西），南宁 530001

目前，社交网络和网页搜索等大规模网络应用部署在数据中心，产生大量异构任务流。网络测量数据表明，数据中心中任务流数据传输延时实际占应用完成时间的70%[1-2]。如何设计高效的混合任务流调度方法已经成为了提升数据中心应用性能的关键。

在数据中心分布式计算模式下，一个任务所传输的所有流应该被当作一个整体来实施调度。根据应用的语义，同一个任务内流的聚合为一个流簇（Coflow）[3]。从设计角度考虑，流簇调度器需要感知应用级的需求和特征，优化网络的利用率以加速任务的传输。

在信息未知的流簇调度设计中，调度器缺乏流簇大小的先验知识，而是采用推理机制来获取任务信息，但流簇大小推理的精确度会极大地影响流簇调度的效率。例如，D-CLAS（discretized coflow-aware least-attained service）[4]通过统计已传输字节数推断流簇的大小。但这种被动的方法只有当传输开始一段时间后才能检测出流簇的字节数，而此时较小的流簇很可能已经被较大的流簇阻塞，导致了较大的平均任务完成时间。MCS（multiple-attributes-based Coflow scheduling）[5]在D-CLAS 的基础上进行了改进，引入了流簇宽度（流簇内包含的子流数）和流簇长度（流簇内子流中最长子流的字节数）两个特征，通过贝叶斯概率算法推理流簇的大小。然而，在分布式计算模式下调度器很难快速准确感知MCS 的方法所依赖的流簇宽度信息。此外，目前设计的流簇大小推理方法仅针对于其分析的数据集，没有一种能广泛适用的推理模型建模方法。

实际上数据中心执行的大部分任务都是重复的，可以从历史日志中学习混合多任务的特征，进而对流簇大小等任务特征进行推理。因此本文提出了一种基于极限学习机的流簇大小推理方法（machine learning Coflow，MLcoflow），主要贡献在于：

（1）基于FaceBook 数据中心日志的数据挖掘，进行各个特征的权重计算，建立了流簇大小的关联特征集，利用极限学习机训练获得了多特征融合的推理模型。

（2）将MLcoflow 部署到最短任务优先（shortest job first,SJF）的流簇调度器中[6]，和现有的流簇调度器相比，降低了20%的流簇平均完成时间。

（3）由于MLcoflow 使用的流簇特征可以从调度中得到，不需要大规模手动修改应用，因此它可以很容易地部署到各类数据并行框架中如MapReduce、Hadoop 和Spark 等。

本文给出了基于极限学习机的MLcoflow 分类器的详细设计，实验证明其在流簇大小推理的准确率、敏感度及适用性上均具有优势，是一种基于数据驱动的流簇推理的高效机制。

1 相关工作

流簇调度通过给流簇分配适合的优先级和带宽来提升网络传输的效率。现有的流簇调度方法可以分为两类：

（1）信息已知流簇调度

信息已知的流簇调度假设调度时所有关于流簇的先验信息都可以被调度器获取，因此这类调度器在模拟实验中通常能表现出较为卓越的性能。如Varys[7]采用分布式调度算法来提高调度性能，通过一个集中式控制器基于最小效率瓶颈优先算法给网络中的流簇分配速率。Sincronia[8]使用贪婪式的速率分配方法为网络中的流簇分配不同优先级，它证明了在正确设置流簇优先级的情况下可以实现近似最优网络设计。然而，Coflow 是一组来自不同源的并行流集合，这些流通常是异步的，这意味着它们不同时开始。因此在调度中获取先验信息在现有的并行计算框架中是难以实现的[9]。部署这类调度器通常需要对现有的应用进行大规模手动修改[10]，这导致这类调度器难以广泛使用。

（2）信息未知流簇调度

信息未知流簇调度器不需要任何先验信息，它们通过调度中获取的流簇特征来执行调度。其中比较经典的调度器设计包括：D-CLAS，它首个提出信息未知调度设计，通过设置已传输字节数阈值为流簇分配优先级；MCS 通过多种流簇特征及贝叶斯概率论来推测流簇的大小并基于最小最短流簇优先算法为流簇分配优先级。然而，现有的信息未知调度器大部分采用经典的SJF 策略，这种策略有两个目标：一是从小流簇（总传输字节数较少的流簇）中把大流簇筛选出来；二是给小流簇高优先级。这两个目标能保证调度器实现降低平均流簇完成时间的目的。为实现这个目标，调度器必须能准确地推理流簇的大小，不准确的推理可能会导致队头阻塞，从而降低传输效率。

此外，很多工作已经证明了机器学习算法在流大小推理应用中的有效性和可行性。例如，文献[11]通过数据挖掘和机器学习算法，基于历史数据和在线信息，使用一条流中前几个包的特性（例如包大小和包头信息）来预测每个流启动时的大小，主要目的是为了检测大象流。文献[12]设计了一个可以事先估计流大小的框架FLUX，并通过机器学习方法预测流大小并标记数据包让交换机可以感知流的大小信息，最后使用真实实验验证了FLUX 在真实环境中的可实现性和部署性。上述研究证明了机器学习方法在流大小预测中的可行性，这些研究也仅仅是针对流模型。虽然FLUX 将其方法用于流簇模型中，但是流簇是多条流的集合，这意味着这种方法只能通过流大小叠加来实现流簇大小推理，这会导致错误率的叠加从而大幅度降低推理精度。因此，设计了针对数据中心任务特征的流簇大小推理模型。

2 研究动机

流簇信息未知调度器应当同时考虑准确率和敏感度这两方面。一般而言，准确率代表了有多少流簇能被准确推理出其所在大小的分类区间，而敏感度代表了准确推理流簇大小需要多少已知信息。流簇大小的准确率一直是关键指标，但现有的推理方法在设计中都忽略了敏感度的问题。式（1）给出了关注的流簇大小推理的敏感度。

R表示推理器用来计算流簇特征使所使用的子流数占流簇总子流数的比例。本文将敏感度定义为准确率达到1.0 时R的取值，该值越小推理方法敏感度越高，该值为1.0 意味着推理方法完全失败。

本章用一个例子揭示推理敏感度的重要性。图1给出了基于SJF 策略的调度器在不同敏感度推理器下的流簇调度情况。图1（a）和（b）描述了流簇传输场景和信息。为简化问题，在这里只考虑流簇大小的相对关系，此例推理的结果只有优先级高、中、低三种情况。

假设：流簇大小≥4 units 时为低优先级，3 units≤流簇大小<4 units 时为中优先级，流簇大小＜3 units时为高优先级。

图1 描述了三种敏感度下的调度情形，图1（c）描述了直到流簇传输结束后都无法完成推理，因此调度器无法发现三条流之间的优先级，只能按到达顺序传输。图1（d）描述在数据传输到一半时推理出优先级，因此推理器会在T=2.5 时推理出C1 属于低优先级，暂停C1 转而开始传输C2 ；在C2 传输一半的数据时推理出C2 属于中优先级，转而开始传输C3。图1（e）描述了当流簇到达时就能进行区分的情形，当C2 到达时先传输C2，而当C1 达到时，先进行C1的传输。上述三种情况平均流簇完成时间分别为7.333、5.833 和4.667，最理想的情况平均流簇完成时间比最差情况的完成时间减少了近36%。可见推理敏感度将对平均流簇完成时间产生影响，在设计推理器时需要同时考虑准确率和敏感度。但推理器在真实的工作环境中只能利用不完全信息，实现较高敏感度的推理是一个挑战。本文旨在结合任务特征，通过数据驱动式机器学习，设计考虑敏感度的推理机制及其调度算法。

Fig.1 Impacts of inferring sensitivity图1 推理敏感度的影响

3 总体思路

本文设计了MLcoflow 调度机制来对流簇实施调度，以降低平均任务的完成时间。图2描述了MLcoflow的工作流程。

推理器的输入是当前核心交换机采集的流簇信息，如当前包含子流数和到达时间等。推理器会首先处理这些信息，从中筛选强关联的特征集，作为推理模型的输入。离散化流簇大小能够加快模型的训练速度，并且使得推理器容易部署。因此将推理模型设计为一个多分类器，推理器将分类结果返回给调度器，据此执行优先级调度。

推理模型将周期性地基于数据中心网络的历史日志进行更新，更新后的模型会被发送至推理器进行在线应用。本文中的周期设定为流到达间隔的2至3 倍，符号为H。为了提高推理算法的敏感度，离线训练中仅使用不完全信息，即流簇内一半的子流信息来挖掘流簇特征。

本文的推理器将基于FaceBook 数据中心发布的日志进行建模[5]，在实际应用中它会通过采集数据中心网络中任务执行的历史日志，筛选与流簇大小相关的特征集合。MLcoflow 使用了极限学习机建立推理模型。本章详细描述了基于数据挖掘的特征提取及流簇大小的多分类建模，最后给出了基于该推理器的调度算法。

3.1 特征提取

为了提升推理的准确性和敏感度，首先需要确定信息未知场景下的可用特征集合。然而，过多的特征信息可能会占用大量的存储空间和计算时间，甚至影响训练模型的收敛性。因此在建模前筛选并去除多余的特征是很重要的。

为简化问题，数据中心的抽象模型为一个无阻塞交换机连接所有主机，调度器仅工作于交换机的出入端口处。因此流簇调度和带宽分配也仅在交换机端口处进行，这是流簇相关研究中最常用的抽象模型[4-8]。

和传统的流抽象模型不同，流簇是一组流的集合，每条流的特征由一个四元组表示。使用Multi-RELIEF[13]方法来筛选特征，它计算每个特征对于推理贡献的权重，通过FaceBook 数据中心日志来分析计算各个特征的权重。为了更好地对比，特征的权重值被归一化后列于表1 中。归一化的权重值相当于该特征对正确推理的贡献，值越大说明该特征越重要。选择了归一化权重值大于0.01 的特征（如表1中1 至6 行所示），最终选取的Coflow 特征集为一个六元组，如式（2）所示。

在实际应用中流簇特征由实时状态确定，它们是累计值，将随着流簇子流的到达率而改变。在表1中“～”用于定义实时值，如。

3.2 推理建模

这里考虑用极限学习机（extreme learning machine，ELM）[14]来生成推理模型，它是一个单隐层前馈神经网络，不需要手动设置太多的参数，训练速度快，泛化性能好，比较适用于数据中心这种实时性要求强的环境。

Table 1 Features and their normalized weighted values表1 特征及其归一化权重值

在数据预处理阶段，历史流簇信息日志被分为两个集合，训练集和测试集。由于分类是由流簇大小确定的，不同分类之间存在逻辑联系，因此训练集的标签使用Label-encoding 处理。此外，本文使用Zscore标准化方法处理

典型的ELM 结构包括了一个输入层、输出层和隐藏层。输入层包含n个神经元，n的值为输出层包含m个神经元，m相当于多分类的分类数。

隐含层包含了k个神经元，激活函数的初始化是随机的，在本文的设计中，激活函数为Sigmoid，式（3）给出了该函数的定义，其中x为ELM 的输入：

通过多个实验验证了参数a、b、k的最佳设置。图3 给出了不同a、b和k下的模型测试错误率。

Fig.3 Parameters optimization experiment图3 参数优化实验

可以看到，当a和b值改变时，k的最佳参数设置总位于40 到50 之间，因此在本文的实验中选择将k值设置为45。同时可以发现，a和b值的改变对结果影响不大，通常为了保证模型泛化性能，它们在ELM中也是随机设置的，因此设置a、b服从随机分布N=(μ,σ2)，μ=0，σ=1.0。

和其他工作类似，流簇大小可以离散成多个分类[4-6]。本文分析了来自FaceBook 数据中心Hive/MapReduce 数据仓库真实的日志及其流簇大小的分布，图4 给出了本文统计得出的流簇大小累积分布函数（cumulative distribution function，CDF）图，图中可见它近似于指数分布。

Fig.4 CDF of Coflow size and classification periods图4 流簇大小的CDF 图及分类区间

在这种分布中，如果使用平均分割法会导致某些分类中的流簇数目很少甚至没有流簇，因此选择了根据CDF 分布来进行流簇分类。

在调度中每个分类将被映射一个优先级队列，假设存在有m个分类，那么优先级队列集合就为Q={Q1,Q2,…,Qm}，则有流簇C属于某一队列Qi(i∈[1,m])的条件为：

其中，CS代表流簇C的预测大小。本文假设流簇的大小分布服从函数y(x)，如下所示：

通过拟合分布曲线得到c=1.5×106，a=-11，且本文中m设置为8。

3.3 流簇调度

基于MLcoflow 的调度器将根据推理结果给流簇分配优先级。算法执行过程中，Agent 从当前端口的流簇信息中提出流簇特征并将其发送给位于核心控制器处的Master，Master 通过使用MLcoflow 推理流簇的大小并将推理结果返回给Agent。收到结果后，部署在Agent 处的调度器会根据推理结果给流簇分配优先级队列。

MLcoflow 调度算法如算法1 所示。新流簇到达交换机后调度器会提取该流簇的特征集并使用推理器推理流簇的实际大小及该大小的流簇所属的分类，通过其大小所属分类为流簇分配优先级队列。对于n个流簇，该算法的时间复杂度为O(n)。

当前的数据中心流量大，且流量行为变化复杂[15]，因此为了保证模型推理的准确性和对环境变化的适应性，算法中设置了触发标志F作为定期更换新模型的触发机制，当F为真时Agent 里的调度器会询问本地存储器是否存在新的模型，若存在则进行模型更新。F的值变化判断条件由应用层决定。

4 仿真实验

将MLcoflow 的性能评估分成两部分：第一部分评估推理方法的准确性和敏感度；第二部分评估基于MLcoflow 调度器的性能。

4.1 推理算法的对比

本节对比了ELM算法和其他两类机器学习算法，包括：

（1）CART（classification and regression trees）[16]，一种常用的决策树算法，使用基尼指数来分割数据。在CART 中树的深度限制为6，典型设置为3～10 之间，发现设置为3 太浅导致准确率较低，而设置为10太深导致过拟合，因此选择了一个中间值。

（2）XGBoost（extreme gradient Boosting）[17]，一种基于梯度增强的集成学习算法。在XGBoost 中，设置了100 个分类器，每个分类器的深度限制为6。

数据预处理中，它们的标签方式都和ELM 相同，而特征集在CART 和XGBoost 中保持原始数据。使用的数据集一部分取样自FaceBook 数据中心的日志，用FB 表示。此外，另一部分由一个流簇日志生成器[18]生成，它通过分析FB 数据集的特征来生成新的日志，用Custom 表示，Custom 后的数字表示数据集包含的流簇数目。

由于本文的模型是一个多分类模型，一些传统的模型评估基准（如F1score 和准确率）不再适用，因为它们不够全面。本文采用Macro-F1score(MaF1)和Micro-F1score(MiF1)来评估本文的模型[19]。MaF1对所有分类的权重相等。而MiF1 对每个实例有相同的权重，因此数量较多的类别对该分数的影响更大。采用十折交叉验证法测试数据。表2 给出了三种算法在不同测试集中的测试结果。

Table 2 Test results of MaF1 and MiF1表2 MaF1 和MiF1 测试结果

可以看到测试集上的结果与训练集FB 的结果相比出现了变化，所有算法的评分都出现了不同程度的下降。总体而言，CART评分下降了35.4%，XGBoost的评分下降了11.7%，而ELM 的评分仅下降了7.3%，相比CART 和XGBoost，ELM 的平均分数分别提高37.6%和9.2%。和其他两个算法相比，ELM 的两个分数都表现最优，且分数变化最小证明其泛化能力较好。

本文使用FB 测试了三种算法生成模型的推理敏感度，结果如图5 所示。R<0.7 时，ELM 具有明显的优势，从R=0.7 开始，XGBoost的敏感度才接近ELM，显而易见CART 的敏感度是最差的。若以0.9 的准确率定义敏感度，则ELM 和XGBoost的敏感度相近，若以小于0.9 的准确率定义敏感度，则ELM 存在明显的优势。相比其他两种算法，ELM 的敏感度平均提高了10.2%以上。

Fig.5 Inferring sensitivity of three algorithms图5 三种算法的推理敏感度对比

图6（a）给出了三种算法的训练时间（样本量100～1 000），图6（b）给出了测试（推理）时间（样本量1 000～10 000）。可以看出，ELM 的耗时低于XGBoost 高于CART，但是其训练时间及测试时间都在100 ms 以内，能够满足绝大多数数据中心的处理需求。

综上，CART、XGBoost 与ELM 均能够在大多数数据中心的在线流簇调度中使用，因为它们准确、敏感，训练和测试速度快。但是，CART 的准确率和敏感度均比较低，难以满足要求较高的数据中心。而XGBoost作为Boost框架算法，其模型结构比较复杂，导致部署的复杂性高，开销较大。因此认为ELM 具备更好的广泛适用性。

Fig.6 Time cost comparisons of three algorithms图6 三种算法的耗时对比

4.2 调度性能对比

本文使用日志驱动的仿真器[4]评估流簇调度的性能，该仿真器内置了许多传统流簇调度器如DCLAS，它是流簇相关研究[5-8]中最常用的实验工具。在这个模拟器上，实现了MCS、基于MLcoflow 的SJF策略调度器。实验网络拓扑如图7 所示，它是一个广泛应用于各类数据中心的Leaf-spine 结构[20]，由144台服务器组成。

本文将基于MLcoflow 的调度器与以下三个流簇调度器进行对比：

（1）先入先出（first in first out，FIFO）[4]，最基础的流簇调度方法，根据流簇的到达顺序（即表1 中的ST）传输流簇。

（2）D-CLAS，根据已传输字节数S推理流簇的大小，优先传输小流簇。

（3）MCS，根据流簇宽度W、已传输字节数S和长度L来推理流簇的大小，优先传输最小最窄的流簇。

Fig.7 Network topology图7 网络拓扑

Fig.8 Average CCT of four coflow schedulers图8 四种流簇调度器的平均流簇完成时间

图8 显示了它们在不同测试集中的平均流簇完成时间（average coflow completion time,Average CCT）。

从结果可以看出，MLcoflow 与MCS、D-CLAS 相比，平均降低了15～20 ms 的平均CCT。而且随着测试集规模的增大，MLcoflow 的优势变得更加明显，因为同一时间需要调度的流簇增加了，同时也导致推理错误时产生的代价更大。性能最差的是FIFO，因为它的调度没有基于流簇的整体特性进行优先级设置。

5 结束语

本文提出了一种基于ELM 的流簇大小推理模型，它利用多种特征推理流簇大小。该推理方法具有较高的准确率和敏感度，基于MLcoflow 的流簇调度器可以有效降低平均流簇完成时间。由于该模型不需要对应用程序进行大规模人工修改，仅基于数据中心网络历史日志即可建模，因此具备较好的可行性。通过同其他几种机器学习算法的分析和比较，可以看到ELM 是一种具有广泛适用性的推理算法。在未来的工作中，将考虑更多类型的机器学习算法，如无监督学习算法和增强学习算法。