基于瓶颈感知的多级反馈队列Coflow 调度机制

都繁杰，李静，郭志勇，任颖文，尹晓宇，董小菱

（1.南京航空航天大学 计算机科学与技术学院，南京 211106；2.国家电网有限公司信息通信分公司，北京 100761；3.国网安徽省电力有限公司信息通信分公司，合肥 231299）

0 概述

随着云计算、大数据的高速发展，云计算数据中心内部的通信量呈爆炸性增长［1］，逐步代替传统的数据中心。海量通信数据的处理需要大量计算节点协同完成，数据并行计算框架（如Apache Spark［2］、Dryad［3］、MapReduce［4］、CIEL［5］等）广泛应用于云计算数据中心。在数据并行计算框架中，用户上传计算任务，云数据中心通过一系列计算和通信阶段得到计算结果，在收到所有计算结果后才能展示给用户。由于通信阶段可能占任务完成时间的50%以上，因此将显著影响应用程序的性能。然而，传统的流级优化难以满足应用程序低延迟、高吞吐量的要求，因此在应用程序优化方面不够有效。在这种情况下，Coflow 应运而生，弥补了应用程序与框架之间的差距。

Coflow 被称为具有语义相关的一组通信数据流，可以捕获并行应用程序中的通信信息［6］。Coflow 能够高效地对网络资源使用的应用程序级语义进行建模。在建模过程中将Coflow 作为网络资源分配或调度的基本元素，以实现优化目标的目的。Coflow 完成时间（Coflow Completion Time，CCT）缩短的问题通常被称为Coflow 调度问题。因此，Coflow 调度已被广泛应用于数据中心传输设计中。为降低Coflow 的平均CCT，Coflow 调度方法应运而生，如Varys［7］、Aalo［8］、Baraat［9］等，它们在一定程 度上缩短平均CCT。然而大多数Coflow 调度机制未考虑网络瓶颈。云计算数据中心内部存在网络链接故障、路由不均衡问题，容易造成链路拥塞，产生流量传输瓶颈。因此，忽略网络中的瓶颈会导致Coflow 优先级判断错误及核心链路上不必要的带宽争用，极大影响CCT 的性能。

本文根据实际场景中Coflow 的特点，提出基于瓶颈感知的多级反馈队列Coflow 调度机制。将瓶颈感知机制引入到数学建模过程中，分析Coflow 调度的典型场景，描述调度过程的实体信息，根据链路状态与Coflow 大小、宽度等信息，确定流的最大速率。同时基于链路状态与Coflow 已发数据、流速、宽度等信息确定Coflow 的优先级，缩短Coflow 的平均完成时间。

1 相关工作

为提高云数据中心应用的性能，云数据中心需要优化流量调度。传统的优化对象是面向单个数据流，其优化指标为单个数据通信流的完成时间（Flow Completion Time，FCT），主要的研究工作包括pHost［10］、MJS［11］等。该类方法通常是对单一数据流进行调度，因此无法实现整个网络资源最优调度的目的。Coflow 是具有相关语义和并发性能目标的并发流集合，其优化CCT 能够真正优化云计算数据中心的应用通信。

研究人员对Coflow 调度进行研究。文献［7］提出启发式调度算法，以最小化平均CCT 达到Coflow截止时间。文献［8］使用Coflow-Aware 最少服务（D-CLAS）算法，根据已经发送的数据量，将Coflow划分为各种优先级。与上述集中式工作不同，文献［9］提出一种用于任务感知调度的分布式算法，将任务意识引入到网络优化中。CODA［12］是借助机器学习技术检测单个流中的Coflow。MPLBF［13］是通过贪婪策略设计一种高效的在线调度方法，提高在线调度的性能。DRGC［14］调度算法分析了多资源环境中Coflow 调度问题，并对调度序列优先级进行排序。IAOA 调度算法［15］根据作业的权重和瞬时网络状况动态调度Coflow。MCS 调度算法［16］联合利用多个Coflow 级别属性进一步缩短Coflow 完成时间。NC-DRF 调度算法［17］为不同租户提供对资源的隔离访问并保证调度性能，证明最小化CCT 的单一Coflow 路由和调度问题为NP-hard［7］。CoRBA 算法［18］综合考虑路由和带宽分配，以确定路由的最优带宽分配。MCRS 算法［19］基于叶脊拓扑结构设计多跳Coflow 路由和调度策略，以最小化CCT。OMCoflow 算法［20］同时考虑路由和流量调度，具有理论性能的在线算法。以上调度算法将网络抽象为无阻塞大型交换机，而忽略了网络资源受限的问题。Fai 调度算法［21］根据流速和字节发送检测瓶颈，提高带宽分配的效率；DBA 调度算法［22］是通过改进最小剩余时间优先的启发式方法，有效识别网络内瓶颈。在多个Coflow 的情况下，Coflow 之间和Coflow 内部的路径发生重叠现象，并且流将争夺相同的链接资源，产生链路间瓶颈。

云数据中心存在网络内链路故障、路由不平衡等问题，核心链路上可能发生拥塞，流量的瓶颈将转移到网络内部。网络内瓶颈决定实际可使用多少带宽流，直接影响CCT。针对网络中的瓶颈问题，本文从瓶颈感知的角度入手，分析云数据中心架构下Coflow 调度典型场景，提出基于瓶颈感知的多级反馈队列Coflow 调度机制，并通过模拟实验从Coflow的平均完成时间和吞吐量两个角度对调度模型进行有效评估。

2 多级反馈队列Coflow 调度机制

本文首先对Coflow 调度进行分析，构建Coflow调度体系；然后对调度机制进行数学建模，以减小CCT；最后参考已有优化调度的方法，设计适用于当前场景的调度方法。本文结合瓶颈感知、增加链路利用率等需求，设计基于瓶颈感知的多级反馈队列Coflow 调度机制Bamq。

2.1 Coflow 调度分析

传统的流级优化难以满足应用程序低延迟、高吞吐量的要求，因此在应用程序优化方面不够有效。与传统的流定义不同，Coflow 由具有独立输入和输出的多个并行流组成，且具有多个属性。假设第i个Coflow 表示为四元组Ci=＜S，Wk，Le，f＞。其 中：S表示Coflow 流的总大小；Wk表示Coflow 流的宽度，即并行流的个数；Le表示Coflow 流的长度，即并行流中最大流的大小；f表示Coflow 的并行流；Ci={f1，f2，…，fq}表示第i个Coflow包含q个并行子流{f1，f2，…，fq}。Coflow 调度场景如图1 所示。

图1 Coflow 调度场景Fig.1 Coflow scheduling scenarios

云计算数据中心存在网络瓶颈问题。图1（a）有3 个Coflow 同时到达数据输入端口（S1），若平均分配带宽，则会造成带宽争用，形成瓶颈。图1（a）的CCT为（10/3=（3+3+4）/3），图1（b）的CCT 为（7/3=（1+2+4）/3），CCT 明显降低，可以看出若及时发现瓶颈，并调整带宽分配可降低CCT。图1（c）存 在3 个Coflow(C1，C2，C3)，其中C1包括 3个流(C1.1，C1.2，C1.3)，C2包括2 个流（C2.1，C2.2），C3则为较大的流，其完成时间较长，暂不讨论。当C1、C2同时到达数据输入端口（S1、S2、S3），会形成链路间瓶颈，若平均分配带宽，能够有效降低CCT，图1（c）的CCT为（5=（4+6）/2），图1（d）的CCT（4.5=（4+5）/2）。

网络瓶颈包括网络内瓶颈与链路间瓶颈，忽略网络瓶颈会导致Coflow 性能下降。为提高Coflow性能，需要增大Coflow 流的速率，提高吞吐量。然而单方面增大吞吐量会造成网络拥塞，导致链路争用，产生大量链路间瓶颈，造成Coflow 性能下降。因此，在增大吞吐量与避免产生瓶颈之间实现平衡成为研究热点。

针对以上问题，本文设计基于瓶颈感知的多级反馈队列Coflow 调度机制Bamq，通过对云数据中心进行建模，实现流速最大化。由于单方面增大吞吐量会形成链路争用，造成Coflow 流排队，产生链路间瓶颈，因此设计基于Lyapunov 优化的流量调度进行队列建模，使得数据在有限时间内离开发送队列，确保队列稳定，避免产生网络拥塞，从而提高Coflow 调度性能。

2.2 Coflow 调度过程建模

假设一个云计算数据中心有N个主机、M台交换器，并具有任意的拓扑结构以形成L条链路，将流量传输过程抽象成无向图G(V，E)，其中|V|=N+M，|E|=L。对于无向图G，节点V对应云计算数据中心的一个节点，每条边E代表一个全双工链路。

假设Coflow 所有内部流同时到达端口，即使内部流异步到达，可将它们视为一起到达，并将最后一个流的到达时间视为Coflow 的到达时间。

2.2.1 数学模型

Map/Reduce 的计算阶段和CPU 的计算速度都与网络的传播速度直接相关。当CPU 计算速度更快时，主机接收数据后被立即处理而不用排队，因此可将网络传输时间作为reducer 的完成时间。当网络传输更快时，主机接收到的数据不能被及时处理，导致数据排队、缓存，因此在网络完成传输后需要额外的计算时间。因为Coflow 调度过程要关注网络调度问题，在数学分析中将忽略任务在每个reducer 上的计算时间，而只考虑网络传输时间。以上问题抽象化可简化数学建模过程，在实验评估中，由于实验使用真实的网络环境，因此不需要强制遵从这些抽象问题。数学模型的参数设置如表1 所示。

表1 数学模型的参数设置Table 1 Parameter settings of mathematical model

在不损失通用性的情况下，假设CoflowCi包含关于流Ci的所有信息，在时间Ti到达网络时立即开始传输，当时间t＞Ti时，流Ci被分配到速率(t)的路径上。当(t)为零时，说明此流正等待传输。在此基础上，将调度问题表示为时间t内的优化问题，如式（1）所示：

其中，式（1）应该满足的约束条件如下：

对式（1）进行变换得：

式（2）表示链路状态，在任何时刻聚合流带宽不能超过链路容量，即网络内瓶颈。为简化模型，式（3）在单位时间内将Coflow 分配的带宽看作Coflow 分配的流速和。一方面，为最小化CCT，该问题可看作是一个线性规划问题，1(Sk(t)+df(t))可以看作流f的流速(t)的权重，然后加权和求最小，为了使加权和最小，即需要增大流速(t)；另一方面，增大流速会造成链路争用，产生链路间瓶颈，导致拥塞，反而会增加总体CCT。因此，Coflow 调度过程需要在增大吞吐量与减少瓶颈之间实现平衡。

此外，最小化CCT 是NP-hard 问题。在实际生产中，网络中多个Coflow 可能同时竞争链路资源，导致Coflow 调度更加复杂。凸优化广泛应用于机器学习等领域。凸优化是通过寻找这些非凸优化问题中“凸”的结构，从而解决众多非凸优化的问题。最小化CCT 的NP-hard 问题是通过将原问题转换为凸问题，提高求解速率。

2.2.2 Lagrange 优化

Lagrange 对偶［23］思想是在目标函数中考虑问题的约束条件，原问题的Lagrange 函数如式（7）所示。原函数的Lagrange 对偶函数如式（8）所示。

对偶函数是一族关于(λ，v)仿射函数的逐点下确界。此外，对偶函数是原问题最优解p*的下界，即对于任意λ≥0和v成立，如式（9）所示：

设(r～，λ，v)为原问题的一个可行解，如式（10）所示：

虽然式（11）成立，但是当g(λ，v)=-∞时，对偶函数的意义不大。只有当λ≥0 且(λ，v)∈domg 时，即g(λ，v)≠-∞时，对偶函数才能给出p*的一个非平凡下界，满足λ≥0 及(λ，v)∈domg 的(λ，v)是对偶可行的。

因此，不等式的对偶问题是在满足约束λ≥0 的条件下极大化对偶函数g(λ，v)，如式（12）所示：

通过梯度下降法求解(r，λ，v)，令和(λ*，v*)分别为原问题和对偶问题的某对最优解，对偶间隙为零。因为L(，λ*，v*)是在处取得最小值，所以函数在处的梯度为零，即：

显然，必存在(λ*，v*)使得下式成立：

因此，在上述凸优化过程中满足KKT 最优性条件。本文调度机制通过Lagrange 优化将原问题转换为凸优化问题进行求解，加快求解速度，求解每条链路的最优解，使得CCT 最小。Lagrange 优化是通过增加Coflow 流的流速来减小CCT，客观上会造成链路争用，形成网络拥塞。

2.2.3 Lyapunov 优化

Lagrange 优化［24］在增大流速过程中会占用链路带宽，造成Coflow 流在等待队列中积压，导致网络拥塞。本文设计全新的瓶颈因子，确保队列的稳定性，以优化多级反馈队列的Coflow 调度。队列稳定性指网络总是在追求一个理想的状态，以确保所有到达的数据在有限时间内离开缓冲区，实现高性能与公平性之间的平衡。在现实场景中，网络大多数处于不平衡状态，但队列稳定性可以使其具有理想的均衡特性。

发送队列模型如式（16）～式（19）所示：

其中：为流最大流速；为严格的凸函数；为优先级系数，即瓶颈因子。虚拟队列中Coflow 流的优先级与β相关，即Coflow 流发送的数据越大，其数据本身也就越大，并且其宽度越小时，优先级越高。是Coflow 流的流速，流速状态直接表示链路的拥塞情况，因此，流速对虚拟队列中Coflow 流的优先级的影响极为关键。虚拟队列如式（20）所示：

其中：Ql(t)为虚拟队列的长度，其与分配Coflow 流的流速及链路带宽Bl直接相关。

到达云计算平台的独立任务具有随机性，离散时间排队过程Ql(t)达到队列稳定状态，如式（21）所示：

Lyapunov 函数如式（22）所示：

则单位时间内Lyapunov 漂移可以表示为：

本文通过Lyapunov 漂移Δ(Q(t))求解队列稳定性。虚拟队列的DPP 如式（24）所示：

其中：V为惩罚因子，通过最小化式（24），得到网络稳定性。然后直接求解随机和非线性Lyapunov 漂移式（24）。本文通过在式（25）中推导出式（24）的上界，然后以极小化式（24）的上界为目标，得到极小化式（24）。基于Lyapunov 优化的启发式搜索算法中，∀V≥0和∀Q(t)，使得式（24）转化为：

其中：α为最差情况值的上界。α值是有限的，由于集合χ被假定为连续的，因此对于每个时间间隙有在式（20）两边同时平方，可以得到如下不等式：

对不等式（26）求和，得到：

Coflow 调度假定所有到达者都被立即放置在路径的所有链接上，是近似于实际网络动态排队的方法。

2.3 调度机制设计

基于瓶颈感知的Coflow 调度机制Bamq 分为调节机制优化和调度模型2 个部分。

2.3.1 调度机制优化

整个调度机制分为信息收集、数据预处理、性能优化3 个步骤。

1）信息收集。Coflow 是具有语义相关的一组通信数据流，若一组Coflow 流没有发送，便无法提前获取每个流发送的字节数、Coflow 关系和Coflow 宽度信息，采用文献［8］和文献［12］提出的两种方法来收集信息。信息收集一方面采集Coflow 相关信息，另一方面监控整体网络状态。当Coflow 较多时，会产生链路竞争，导致网络拥塞，信息收集模块采集Coflow 调度过程中的网络信息，将信息传给调度器进行网络优化。

2）数据预处理。在初始化阶段，Coflow 调度采用简单的调度机制，即平均分配每个流的带宽，等待队列采用FIFO 的策略。

3）性能优化。传统的Coflow 调度采用平均分配带宽的策略，造成大量的剩余空间，影响Coflow的调度性能。针对上述问题，Lagrange 优化增大部分Coflow 的流速，从而降低CCT。因增大吞吐量会导致Coflow 流产生链路争用，造成网络拥塞。因此，Bamq 通过Lyapunov 优化，确定调度队列中不同Coflow 流的优先级，达到增大吞吐量与减少拥塞平衡的目的。

2.3.2 调度模型

根据Coflow 调度机制，基于瓶颈感知的多级反馈队列Coflow 调度模型如图2 所示。

图2 本文调度模型结构Fig.2 Structure of the proposed scheduling model

Coflow 调度模型包括主节点、工作节点、守护进程和监视器。主节点是系统的大脑，起着控制器的作用；工作节点具有优化信息的作用；守护进程则作为全局调度器，协同处理主节点，从工作节点收集Coflow 信息，执行Coflow 优先级调度；监控模块则收集Coflow 信息，监控链路状态以判断拥塞情况。

当发送一组Coflow 后，监视器收集Coflow 信息，包括每个流的发送字节数、Coflow 关系和Coflow 宽度信息，为调度提供初始信息。守护进程根据监控信息，初始化调度过程，采用简单的调度策略处理数据，即平均分配每个流的带宽，等待队列采用FIFO 的策略等。同时，监控节点实时监控链路状况，检测到拥塞时，立即通知主节点的调度器进行优化。

随着Coflow 流的增加，简单的调度机制已不能满足CCT 需求，通过Lagrange 优化，增大部分流流速，从而缩短CCT。然而增大吞吐量会产生链路竞争，部分流会进入等待队列，影响CCT 性能。Lyapunov 优化根据等待队列中的Coflow 流的瓶颈因子，为其分配不同的优先级，并进行优先调度，达到增大吞吐量与减少拥塞的稳定状态，最终降低CCT。

算法2Bamq 算法

3 模拟实验

本文基于小规模流级别的模拟器和开源网络模拟器，使用Facebook 的真实数据集对Bamq 调度机制进行验证，通过对比现有先验知识已知和先验知识未知场景下的调度机制来验证Bamq 调度机制的有效性。

3.1 实验设置

3.1.1 调度模型实验环境

CoflowSim 是基于Java 语言的开源调度器，已经实现了多种Coflow 调度机制，如Varys、Aalo，被广泛应用于Coflow 领域。本文在单机模拟下进行实验，CoflowSim 模拟器部署环境具体为：Intel®CoreTMi7-9700 CPU 3.00 GHz、64 GB 内存，操作系统为Linux version 4.15.0-142-generic，JDK 为java 1.8.0_231。实验使用maven 工具将CoflowSim 导入到IDEA，通过CoflowSim 内部数据中心的抽象模型，验证Coflow 调度机制。

本文采用Facebook 改进的数据集。原始的Facebook 数据集包含3 000 台150 机架的MapReduce集群，其合成后数据包含526 个Coflow 信息。每个数据包含以下信息：Coflow ID，mapper数量，reduce 数量，总Shuffle字节数，最大Shuffle字节数，持续时间，Coflow已发送字节数，Coflow 宽度等。由于Facebook 记录的Coflow 仅包含发送主机、接收主机和传送的字节数，没有包含流级别信息，且不包含任务信息。因此，本文实验随机划分为多个Coflow 任务，使其构成依赖关系。Facebook 数据集如图3 所示。

图3 Facebook 数据集相关信息Fig.3 Related information of Facebook dataset

Facebook 数据类型如表2 所示。根据长度（Long 和Short）和宽度（Narrow 和Wide）分为4 类，SN 表示短窄流（Short-Narrow）；LN 表示长窄流（Long-Narrow）；SW 表示短宽流（Short-Wide）；LW表示长宽流（Long-Wide）。若Coflow 流的最长流小于5 MB，则为短流（Short）；若Coflow 流的宽度小于50，则为窄流（Narrow）。此外，基于Facebook 记录的Coflow 信息不包含流速、吞吐量等信息，因此需要使用开源网络模拟器，模拟链路状况。

表2 Facebook 数据集的Coflow 类型Table 2 Coflow types of Facebook data set %

NS-3（Network Simulator）是一个用于Internet 系统的离散事件网络模拟器，用于面向对象编程C++开发的开源项目。NS-3 模拟器抽象出几个核心概念，即节点是连接到网络的最基本实体，包括用于应用程序、协议和网络设备的容器类。网络系统是分配MAC 地址，以及配置节点的协议栈。基于这些特点，NS-3 模拟器简化了api的繁琐工作，用于构建各种类型的仿真场景。NS-3模拟器部署环境为：Ubuntu16.04.7 LTS、nsallinone-3.32、gcc5.4.0。实验通过编写C++代码模拟链路情况，验证调度机制的有效性。

3.1.2 实验对比

Bamq 调度机制是一种改进的多级队列调度机制，通过与以下3 种经典机制对比，以验证Bamq 调度的有效性。

1）Baraat 机制：用于数据中心的分布式任务感知调度系统，将任务感知调度问题转化成流优先级问题。通过一种简单的启发式方法设置流的优先级，结合优先级和显式速率协议的优点，解决繁重任务的实时识别并相应地改变多路复用的级别等问题。

2）Varys 机制：是一种已知信息下最短作业优先的多级队列反馈机制，基于网络瓶颈处的完成时间调度Coflow，然后使用最小化分配期望持续时间算法将速率分配给各个流，进而降低平均CCT。

3）Aalo 机制：提出Coflow-Aware Least-Attained Service 的Inter-Coflow 调度器，是最少获得优先服务的多级队列反馈机制，为每个Coflow 分配优先级且该优先级随着Coflow 己经发送总字节数的增加而减小，以此降低平均CCT。

Coflow 调度过程的性能指标如下：

1）CCT：是Coflow 调度机制中最主要的指标，分别计算平均CCT 和95%CCT。为消除极值影响，95%CCT 是将每种机制前2.5%和后2.5%结果去掉，重新计算结果。通过对CCT 进行归一化处理，得到Coflow 完成时间。

2）吞吐量：是数据中心应用关注的基本指标。在数据中心中，除了数据量小的Coflow 外，还有数据量大的后台Coflow（>1GB）用于数据更新。如此大的Coflows 占传输总字节的99.1%，因此吞吐量也能评价调度性能。

3.2 实验结果与分析

本文选择CCT 与吞吐量2 个指标作为判断标准。CCT 指标作为判断Coflow 调度性能的直接指标被广泛使用。为有效对比链路的利用率，本文对不同调度机制的吞吐量进行对比。

3.2.1 CCT 指标

本文对Facebook 数据集中526 个Coflow 进行随机分配任务，其任务到达时间遵循参数为θ的Poisson 分布，并将4 种不同类型的Coflow 流作为工作负载。图4表示Baraat、Varys、Aalo 与Bamq 的Coflow 完成时间对比。从图4（a）可以看出，Bamq 的CCT 平均比Baraat、Varys、Aalo 分别提高9.2%、13.5%、39.1%。这是因为Bamq 考虑网络内瓶颈，从而比Varys 具有更精确的Coflow 优先级和带宽分配，Bamq 提高了链路利用率。从图4（b）可以看出，95%CCT 中Bamq 的CCT 平均比Baraat、Varys、Aalo 降低9.6%、14.6%、39.7%。Bamq 和Baraat 提高了链路利用率。

图4 不同调度机制的CCT 对比Fig 4 CCT comparison among different scheduling mechanisms

图5 表示4 种调度机制Coflow 完成时间的累积分布函数（Cumulative Distribution Function，CDF）。从图5 可以看出，在这两种负载下，Bamq 几乎在所有百分比上都优于Varys、Baraat 和Aalo。在负载较小时，Bamq 的CCT 与Baraat 相似，主要与收敛速度相关。这个结果与图4 的结果一致。

图5 不同调度机制的Coflow 累积分布函数对比Fig 5 Cumulative distribution function of Coflow comparison among different scheduling mechanisms

3.2.2 吞吐量

Baraat、Varys、Aalo、Bamq 这4 种调度机制在不同工作负载下的吞吐量对比如图6 所示。吞吐量是通过整个网络传输的所有数据量除以所有Coflow的最大完成时间。在较低负荷下，4 种算法具有相似的吞吐量，在更大的负载下，Bamq 的吞吐量明显高于Varys，略低于Baraat，相对于Baraat，Bamq 有一个收敛过程吞吐量损失很小。因此，Bamq 在优化CCT的同时保持了良好的链接利用率。

图6 不同调度机制的吞吐量对比Fig 6 Throughput comparison among different scheduling mechanisms

为验证Bamq 调度机制的收敛性，本文随机选取3 个流，3 个流的收敛速度如图7 所示。除了给初始流包让路外，在短时间内3 个流大多收敛到最优速率，收敛前的平均速率也不小于最优速率，因为流量是从较大值开始收敛的。

图7 流的收敛速度Fig.7 Convergence rate of flow

3.2.3 结果分析

Bamq 调度机制是一种改进的多级队列调度机制。初始化Coflow 优先级，然后在该队列下，最大化Coflow 流的流速，以此降低CCT。通过设置多级队列来分配其他Coflow 流，以此减低拥塞。

Bamq 根据Coflow 的已发大小、宽度、流速设计了全新的瓶颈因子，根据瓶颈因子大小决定Coflow 的优先级。流速是识别链路拥塞情况的关键信息，根据流速大小可以快速判断网络状况。为评估CCT 与Coflow宽度等属性的相关性，本文通过选择Person 相关系数（PCC）作为评估指标。PCC 定义如下：

PCC 可以很好衡量两个变量的线性关系，值越大，表明两个变量的线性相关性越强。Person 相关性系数在计算2 个总体之间的相关性时要求两个总体必须符合正态分布，对Person 相关性系数取对数，使其符合正态分布。Coflow 属性相关度如表3 所示。

表3 Coflow 属性相关度Table 3 Correlation degree of Coflow attributes

从表3 可以看出，CCT 与Coflow 大小强相关，由于CCT 反映Coflow 的完成时间，必然与Coflow 大小线性相关。CCT 与Coflow 宽度强相关，因此，Bamq 的瓶颈因子可以很好地反映CCT 性能。Coflow 大小与宽度强相关。在Hadoop 分布式框架中，Map 任务的数量与输入数据的大小相关，即输入数据越大，map任务越多，其相应的reduce 任务越多，Coflow 宽度越大。

4 结束语

针对在云数据中心Coflow 调度过程中存在网络瓶颈的问题，本文提出基于瓶颈感知的多级反馈队列Coflow 调度机制Bamq。利用Lagrange 对偶优化Coflow 流速，以充分利用链路带宽，从而减少CCT，为减少网络拥塞，利用Lyapunov 优化多级反馈队列模型，以确保队列稳定性。在Facebook 的真实数据集和开源网络模拟器NS-3 上的实验结果表明，Bamq 调度机制在降低平均CCT 的前提下，能够增大吞吐量，并且提高链路利用率。下一步将利用光电路交换机制优化流量调度，并结合边缘技术提高核心互联网络的带宽利用率。