开放科学（资源服务）标志码（OSID）：

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表示为四元组$ {C}_{i}= < S, {W}_{k}, {L}_{e}, f > $。其中：$ S $表示Coflow流的总大小；$ {W}_{k} $表示Coflow流的宽度，即并行流的个数；$ {L}_{e} $表示Coflow流的长度，即并行流中最大流的大小；$ f $表示Coflow的并行流；$ {C}_{i}=\left\{{f}_{1}, {f}_{2}, \cdots , {f}_{q}\right\} $表示第$ i $个Coflow包含$ q $个并行子流$ \left\{{f}_{1}, {f}_{2}, \cdots , {f}_{q}\right\} $。Coflow调度场景如图 1所示。

云计算数据中心存在网络瓶颈问题。图 1（a）有3个Coflow同时到达数据输入端口（S₁），若平均分配带宽，则会造成带宽争用，形成瓶颈。图 1（a）的CCT为（10/3=（3+3+4）/3），图 1（b）的CCT为（7/3=（1+2+4）/3），CCT明显降低，可以看出若及时发现瓶颈，并调整带宽分配可降低CCT。图 1（c）存在3个Coflow$ ({C}_{1}, {C}_{2}, {C}_{3}) $，其中$ {C}_{1} $包括3个流$ ({C}_{1.1}, {C}_{1.2}, {C}_{1.3}) $，$ {C}_{2} $包括2个流（$ {C}_{2.1}, {C}_{2.2} $），$ {C}_{3} $则为较大的流，其完成时间较长，暂不讨论。当$ {C}_{1}\mathrm{、}{C}_{2} $同时到达数据输入端口（S₁、S₂、S₃），会形成链路间瓶颈，若平均分配带宽，能够有效降低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) $，其中$ \left|V\right|=N+M, \left|E\right|=L $。对于无向图$ G $，节点$ V $对应云计算数据中心的一个节点，每条边$ E $代表一个全双工链路。

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

2.2.1 数学模型

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

在不损失通用性的情况下，假设Coflow $ {C}_{i} $包含关于流$ {C}_{i} $的所有信息，在时间$ {T}_{i} $到达网络时立即开始传输，当时间$ t > {T}_{i} $时，流$ {C}_{i} $被分配到速率$ {r}_{f}^{l}\left(t\right) $的路径上。当$ {r}_{f}^{l}\left(t\right) $为零时，说明此流正等待传输。在此基础上，将调度问题表示为时间$ t $内的优化问题，如式（1）所示：

$ \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}:\sum\limits _{k=1}^{K}{C}_{k}\left(t\right) $

(1)

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

$ \mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t} \; \mathrm{t}\mathrm{o}:\sum\limits _{k=1}^{K}{b}_{k}\left(t\right){p}_{kl}={B}_{l} $

(2)

$ {b}_{k}\left(t\right)=\sum \limits_{k=1}^{{W}_{k}}{\tilde{r}}_{f}^{l}\left(t\right) > 0, \forall {W}_{k} $

(3)

$ {C}_{k}\left(t\right)=\sum \limits_{k=1}^{{W}_{k}}{f}_{i, j}^{k}, k\in K, i, j\in M, \forall i, j, k $

(4)

$ {f}_{i, j}^{{W}_{k}}=\frac{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}{{\tilde{r}}_{f}^{l}\left(t\right)}, \forall f $

(5)

对式（1）进行变换得：

$ \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}:-\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{{\tilde{r}}_{f}^{l}\left(t\right)}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)} $

(6)

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

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

2.2.2 Lagrange优化

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

$ L({\tilde{r}}_{f}^{l}, \lambda , v)={f}_{0}\left({\tilde{r}}_{f}^{l}\right)+\sum \limits_{i=1}^{{W}_{k}}{\lambda }_{{}_{i}}{f}_{i}\left({\tilde{r}}_{f}^{l}\right)+\sum \limits_{j=1}^{L}{\nu }_{j}{h}_{j}\left({\tilde{r}}_{f}^{l}\right)=\left(-\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{\lambda }_{{}_{i}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}\right){\tilde{r}}_{f}^{l}\left(t\right)-\sum \limits_{j=1}^{L}{\nu }_{j}{B}_{j} $

(7)

$ \begin{array}{l}g(\lambda , v)=\underset{r\in D}{\mathrm{i}\mathrm{n}\mathrm{f}}L({\tilde{r}}_{f}^{l}, \lambda , v)=\underset{r\in D}{\mathrm{i}\mathrm{n}\mathrm{f}}\left({f}_{0}\left({\tilde{r}}_{f}^{l}\right)+\sum \limits_{i=1}^{{W}_{k}}{\lambda }_{{}_{i}}{f}_{i}\left({\tilde{r}}_{f}^{l}\right)+\sum \limits_{j=1}^{L}{\nu }_{j}{h}_{j}\left({\tilde{r}}_{f}^{l}\right)\right)=\\ \underset{r\in D}{\mathrm{i}\mathrm{n}\mathrm{f}}\left(\left(-\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{\lambda }_{{}_{i}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}\right){\tilde{r}}_{f}^{l}\left(t\right)-\sum \limits_{j=1}^{L}{\nu }_{j}{B}_{j}\right)\end{array} $

(8)

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

$ g(\lambda , v)\le {p}^{\mathrm{*}} $

(9)

设$ (\tilde{r}, \lambda , v) $为原问题的一个可行解，如式（10）所示：

$ L(\tilde{r}, \lambda , v)={f}_{0}\left(\tilde{r}\right)+\sum \limits_{i=1}^{{W}_{k}}{\lambda }_{{}_{i}}{f}_{i}\left(\tilde{r}\right)+\sum \limits_{j=1}^{L}{\nu }_{j}{h}_{j}\left(\tilde{r}\right)\le {f}_{0}\left(\tilde{r}\right) $

(10)

因此，$ g(\lambda , v)=\underset{r\in D}{\mathrm{i}\mathrm{n}\mathrm{f}}L({\tilde{r}}_{f}^{l}, \lambda , v)\le L(\tilde{r}, \lambda , v)\le {f}_{0}\left(\tilde{r}\right) $。每个可行解$ \tilde{r} $都满足$ g(\lambda , v)\le {f}_{0}\left(\tilde{r}\right) $，如式（11）所示：

$ g(\lambda , v)=\left\{\begin{array}{l}\begin{array}{c}-\sum \limits_{j=1}^{L}{\nu }_{j}{B}_{j}, -\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{\lambda }_{{}_{i}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}=0\end{array}\\ \begin{array}{c}-\infty , -\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{\lambda }_{{}_{i}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}\ne 0\end{array}\end{array}\right. $

(11)

虽然式（11）成立，但是当$ g(\lambda , v)=-\mathrm{\infty } $时，对偶函数的意义不大。只有当$ \lambda \ge 0 $且$ (\lambda , v)\in \mathrm{d}\mathrm{o}\mathrm{m}\mathrm{g} $时，即$ g(\lambda , v)\ne -\mathrm{\infty } $时，对偶函数才能给出$ {p}^{\mathrm{*}} $的一个非平凡下界，满足$ \lambda \ge 0 $及$ (\lambda , v)\in \mathrm{d}\mathrm{o}\mathrm{m}\mathrm{g} $的$ (\lambda , v) $是对偶可行的。

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

$ \begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\;g(\lambda , v)=\left\{\begin{array}{l}-\sum \limits_{j=1}^{L}{\nu }_{j}{B}_{j}, -\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{\lambda }_{{}_{i}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}=0\\ -\infty , -\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{\lambda }_{{}_{i}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}\ne 0\end{array}\right.\\ \begin{array}{cc}\mathrm{s}.\mathrm{t}.& \lambda \ge 0\end{array}\end{array} $

(12)

该问题可以等价为：

$ \begin{array}{l}\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}-\sum \limits_{j=1}^{L}{\nu }_{j}{B}_{j}\\ \mathrm{s}.\mathrm{t}.\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{\nu }_{j}{p}_{kl}-\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}\ge 0\end{array} $

(13)

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

$ \nabla {f}_{0}\left({\tilde{r}}^{l}\right)+\sum \limits_{i=1}^{{W}_{k}}{{\lambda }_{{}_{i}}}^{*}\nabla {f}_{i}\left({\tilde{r}}^{l}\right)+{\sum \limits_{j=1}^{L}{{\nu }_{j}}^{\mathrm{*}}\nabla h}_{j}\left({\tilde{r}}^{l}\right)=0 $

(14)

显然，必存在$ ({\lambda }^{\mathrm{*}}, {v}^{\mathrm{*}}) $使得下式成立：

$ \begin{array}{l}-\sum \limits_{k=1}^{K}\sum \limits_{w=1}^{{W}_{k}}\frac{1}{{S}_{k}\left(t\right)+{d}_{f}\left(t\right)}-\sum \limits_{i=1}^{{W}_{k}}\sum \limits_{1}^{k}{{\lambda }_{{}_{i}}}^{\mathrm{*}}+\sum \limits_{j=1}^{L}\sum \limits_{1}^{k}\sum \limits_{1}^{k}{{\nu }_{j}}^{\mathrm{*}}{p}_{kl}=0\\ -\sum \limits_{i=1}^{{W}_{k}}{{\lambda }_{{}_{i}}}^{\mathrm{*}}\le 0, \sum \limits_{j=1}^{l}{\nu }_{j}\left(\sum \limits_{1}^{k}\sum \limits_{1}^{k}{p}_{kl}\tilde{r}\left(t\right)-{B}_{j}\right)=0\end{array} $

(15)

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

2.2.3 Lyapunov优化

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

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

$ \mathrm{M}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\sum \limits_{l=1}^{L}\left(\frac{1}{\beta }\right)\mathrm{l}\mathrm{n}(1+\beta {r}_{f}^{l}(t\left)\right) $

(16)

$ \mathrm{s}.\mathrm{t}.\sum \limits_{i\in N\left(l\right)}{r}_{f}^{l}\left(t\right)\le {B}_{l}\text{，}\forall l\in \{\mathrm{1, 2}, \cdots , L\} $

(17)

$ \beta =\frac{{S}_{k}}{{W}_{k}}, k\in K, {r}_{f}^{l}\in [0, {\tilde{r}}^{l}], \forall l\in \{\mathrm{1, 2}, \cdots , L\} $

(18)

$ {\varphi }_{i}\left({r}_{f}^{l}\right)=\left(\frac{1}{\beta }\right)\mathrm{l}\mathrm{n}(1+\beta {r}_{f}^{l}) $

(19)

其中：$ {\tilde{r}}^{l} $为流最大流速；$ \mathrm{l}\mathrm{n}(1+\beta {r}_{f}^{l}(t\left)\right) $为严格的凸函数；$ \beta {r}_{f}^{l} $为优先级系数，即瓶颈因子。虚拟队列中Coflow流的优先级与$ \beta $相关，即Coflow流发送的数据越大，其数据本身也就越大，并且其宽度越小时，优先级越高。$ {r}_{f}^{l} $是Coflow流的流速，流速状态直接表示链路的拥塞情况，因此，流速$ {r}_{f}^{l} $对虚拟队列中Coflow流的优先级的影响极为关键。虚拟队列如式（20）所示：

$ {Q}_{l}(t+1)=\mathrm{m}\mathrm{a}\mathrm{x}\left[{Q}_{l}\left(t\right)+\sum \limits_{l\in L\left(l\right)}{r}_{f}^{l}\left(t\right)-{B}_{l}, 0\right] $

(20)

其中：$ {Q}_{l}\left(t\right) $为虚拟队列的长度，其与分配Coflow流的流速$ {r}_{f}^{l} $及链路带宽$ {B}_{l} $直接相关。

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

$ \underset{t\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{E\left\{Q\left(t\right)\right\}}{t}=0 $

(21)

Lyapunov函数如式（22）所示：

$ L\left(Q\left(t\right)\right)=\frac{1}{2}\sum \limits_{i}^{N}{Q}_{i}^{2}\left(t\right) $

(22)

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

$ \Delta \left(Q\left(t\right)\right)=E\left(L\left(Q(t+1)\right)-L\left(Q\left(t\right)\right)\left|Q\right(t)\right) $

(23)

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

$ -V{\varphi }_{i}\left({r}_{f}^{l}\right(t\left)\right)+\Delta \left(Q\left(t\right)\right) $

(24)

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

$ -V{\varphi }_{i}\left({r}_{f}^{l}\right(t\left)\right)+\Delta \left(Q\left(t\right)\right)\le \alpha -V{\varphi }_{i}({r}_{f}^{l}{\left(t\right))}_{}+ \\ \sum \limits_{i}^{N}{Q}_{i}(t)\left({r}_{f}^{l}\left(t\right)-{B}_{l}\right) $

(25)

其中：$ \alpha $为最差情况值的上界。$ \alpha $值是有限的，由于集合$ \chi $被假定为连续的，因此对于每个时间间隙有$ \alpha \ge \sum \limits_{1}^{N}({r}_{f}^{l}-{B}_{l}{)}^{2} $。在式（20）两边同时平方，可以得到如下不等式：

$ {\left[{Q}_{l}(t+1)\right]}^{2}\le {\left[{Q}_{l}\left(t\right)\right]}^{2}+{\left[{r}_{f}^{l}\left(t\right)-B\left(t\right)\right]}^{2}- \\ 2{Q}_{l}\left(t\right)\left(B\left(t\right)-{r}_{f}^{l}\left(t\right)\right) $

(26)

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

$ \frac{\sum \limits_{l}^{N}\left({\left[{Q}_{l}(t+1)\right]}^{2}-{\left[{Q}_{l}\left(t\right)\right]}^{2}\right)}{2}\le \\ \frac{\sum \limits_{l}^{N}\left({\left[{r}_{f}^{l}\left(t\right)-{B}_{l}\left(t\right)\right]}^{2}\right)}{2}-\sum \limits_{l}^{N}{Q}_{l}\left(t\right)\left({B}_{l}\left(t\right)-{r}_{f}^{l}\left(t\right)\right) $

(27)

因此，Drift-plus-penalty算法的输入是监控队列$ {Q}_{1}\left(t\right), {Q}_{2}\left(t\right), \cdots , {Q}_{L}\left(t\right) $，输出是每个流期望流速$ {r}_{f}^{l}\left(t\right)=\left({r}_{1}^{l}\right(t), {r}_{2}^{l}(t), \cdots , {r}_{f}^{l}(t\left)\right) $，算法步骤如下：

1）对于时隙$ t $，网络控制器监控队列$ {Q}_{1}\left(t\right), $ $ {Q}_{2}\left(t\right), \cdots , {Q}_{L}\left(t\right) $，选择$ r\left(t\right)=\left({r}_{1}^{l}\right(t), {r}_{2}^{l}(t), \cdots , {r}_{f}^{l}(t\left)\right)\in \chi $，使式（28）最小化：

$ \begin{array}{c}{\rm{minimize}} -V\sum \limits_{i=1}^{N}{\varphi }_{i}\left({r}_{f}^{l}\right(t\left)\right)+\sum \limits_{l=1}^{L}{Q}_{l}\left(t\right)\left[\sum \limits_{f\in N\left(l\right)}{r}_{f}^{l}\left(t\right)\right]\end{array} $

(28)

2）通过式（20）更新虚拟队列；

3）更新平均变量：

$ \overline{{r}_{f}^{l}}\left(t\right)=\frac{1}{t+1}\sum \limits_{\tau =0}^{t}{r}_{f}^{l}\left(\tau \right)=\overline{{r}_{f}^{l}}\left(t\right)\left(\frac{t}{t+1}\right)+{r}_{f}^{l}\left(t\right)\left(\frac{1}{t+1}\right) $

(29)

给定时间间隙$ t $，通过搜寻$ {r}_{f}^{l}\left(t\right)\in \chi $使得$ {r}_{f}^{l}\left(t\right) $最小，使用最小化$ {r}_{f}^{l}\left(t\right) $来更新下一个时隙的队列值$ {Q}_{1}(t+1), {Q}_{2}(t+1), \cdots , {Q}_{L}(t+1) $，得特解：

$ {r}_{l}^{\mathrm{*}}\left(t\right)={\left[ {V1/\beta \left( {{U_l}\left( t \right) - 1} \right)} \right]}_{0}^{{r}_{\mathrm{m}\mathrm{a}\mathrm{x}}}, {U}_{i}\left(t\right)=\sum \limits_{l=1}^{L}{Q}_{l}\left(t\right) $

(30)

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所示。

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

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

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

算法2  Bamq算法

输入   $ B, Q, A, {f}_{k}^{w}, l $

输出   $ {\tilde{r}}_{f}^{l}\left(t\right) $

1./*Coflow调度机制*/

2.初始化$ \mathrm{\sigma } $/*初始化链路拥塞阈值$ \mathrm{\sigma } $ */

3.for i←1 to I do

4 update

5./*利用Lagrange优化调度*/

6.while（$ {\mathrm{Q}}_{\mathrm{i}} $）

7.初始化$ {\mathrm{f}}_{\mathrm{i}}= < {\mathrm{f}}_{\mathrm{k}}^{\mathrm{w}}, {\mathrm{W}}_{\mathrm{k}}, {\mathrm{S}}_{\mathrm{k}}\left(\mathrm{t}\right), {\mathrm{d}}_{\mathrm{f}}\left(\mathrm{t}\right) > $

8.计算Coflow完成时间$ \mathrm{T} $

9.通过梯度下降求解式（15），得到每个流的期望速率$ {\tilde{\mathrm{r}}}_{\mathrm{f}}^{\mathrm{l}}\left(\mathrm{t}\right) $

10.if$ \left({\tilde{\mathrm{r}}}_{\mathrm{f}}^{\mathrm{l}}\right(\mathrm{t}) > \mathrm{\sigma }{\tilde{\mathrm{b}}}_{\mathrm{l}}, \mathrm{l}\in \mathrm{L}) $/*判断链路是否拥塞*/

11.$ {\mathrm{F}}_{\mathrm{i}}={\mathrm{F}}_{\mathrm{i}}-{\mathrm{f}}_{\mathrm{i}} $，break

12.Let $ (\mathrm{A}\leftarrow {\mathrm{F}}_{\mathrm{i}})^({\mathrm{Q}}_{\mathrm{i}}\leftarrow {\mathrm{Q}}_{\mathrm{i}}-{\mathrm{F}}_{\mathrm{i}}) $

13.end while

14./*利用Lyapunov优化调度*/

15.Let $ {\mathrm{F}}_{\mathrm{i}}={\mathrm{F}}_{\mathrm{i}}+{\mathrm{f}}_{\mathrm{i}} $

16.通过DPP解式（30）

17.得到每个流的最终速率$ {\tilde{\mathrm{r}}}_{\mathrm{f}}^{\mathrm{l}}\left(\mathrm{t}\right) $

18.update $ (\mathrm{A}\leftarrow {\mathrm{F}}_{\mathrm{i}})^({\mathrm{Q}}_{\mathrm{i}}\leftarrow {\mathrm{Q}}_{\mathrm{i}}-{\mathrm{F}}_{\mathrm{i}}) $

19.end for

注$ \mathrm{\sigma } $表示链路拥塞因子，A表示已发送队列。

3 模拟实验

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

3.1 实验设置 3.1.1 调度模型实验环境

CoflowSim是基于Java语言的开源调度器，已经实现了多种Coflow调度机制，如Varys、Aalo，被广泛应用于Coflow领域。本文在单机模拟下进行实验，CoflowSim模拟器部署环境具体为：Intel^®Core^TMi7-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所示。

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信息不包含流速、吞吐量等信息，因此需要使用开源网络模拟器，模拟链路状况。

NS-3（Network Simulator）是一个用于Internet系统的离散事件网络模拟器，用于面向对象编程C++开发的开源项目。NS-3模拟器抽象出几个核心概念，即节点是连接到网络的最基本实体，包括用于应用程序、协议和网络设备的容器类。网络系统是分配MAC地址，以及配置节点的协议栈。基于这些特点，NS-3模拟器简化了api的繁琐工作，用于构建各种类型的仿真场景。NS-3模拟器部署环境为：Ubuntu16.04.7 LTS、ns-allinone-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提高了链路利用率。

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

3.2.2 吞吐量

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

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

3.2.3 结果分析

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

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

$ {\rho }_{X, Y}=\frac{\mathrm{c}\mathrm{o}\mathrm{v}(X, Y)}{{\sigma }_{X}{\sigma }_{Y}} $

(31)

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

从表 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的前提下，能够增大吞吐量，并且提高链路利用率。下一步将利用光电路交换机制优化流量调度，并结合边缘技术提高核心互联网络的带宽利用率。