张彤^1,2, 任丰原³, 舒然⁴
1. 南京航空航天大学 计算机科学与技术学院, 南京 211106;
2. 软件新技术与产业化协同创新中心, 南京 210093;
3. 清华大学 计算机科学与技术系, 北京 100084;
4. 微软研究院, 北京 100080
收稿日期：2020-07-20
基金项目：国家自然科学基金面上项目（61872208）
作者简介：张彤(1992-), 女, 副研究员
通讯作者：任丰原, 教授, E-mail: renfy@tsinghua.edu.cn

摘要：数据中心网络作为云计算的关键基础设施，其性能对业务服务质量有至关重要的影响。在当前数据中心多业务并存的条件下，数据中心网络中同时存在截止期限流和非截止期限流。为同时满足2种流的传输需求，该文提出一种基于分布式优化的数据中心网络混流调度（distributed-optimization-based mix-flow scheduling，DOMS）机制。首先对截止期限流和非截止期限流分别定义优化目标和传输约束，将混流调度问题形式化为实时速率分配问题；然后利用问题的对偶分解特性，设计主机与交换机的协同调度结构，分布式求解该问题，设定每条流的传输速率并演化至全局最优解。仿真结果表明，DOMS能有效降低截止期限流的期限错失率和非截止期限流的完成时间。
关键词：数据中心网络混流调度分布式优化截止期限错失率流完成时间
Distributed-optimization-based mix-flow scheduling mechanism for data center networks
ZHANG Tong^1,2, REN Fengyuan³, SHU Ran⁴
1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China;
2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing 210093, China;
3. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
4. Microsoft Research, Beijing 100080, China

Abstract: Data center networks are key cloud computing infrastructure whose performance critically impacts the quality of service. Currently, data centers have multiple services with both deadline and non-deadline flows. This paper presents a distributed-optimization-based mix-flow scheduling (DOMS) mechanism to meet the transmission requirements of both types of flows. First, the optimization goals and transmission constraints are defined for both kinds of flows and the mixed-flow scheduling problem is formalized as a real-time rate allocation problem. Then, a coordinated scheduling structure is designed for the hosts and switches that leverages the dual decomposition characteristics of the problem. This method uses a distributed solution method to solve the problem with the flow rates evolving to a global optimal solution. Simulations show that this method effectively reduces deadline miss rates for deadline flows as well as flow completion times for non-deadline flows.
Key words: data center network (DCN)mix-flow schedulingdistributed optimizationdeadline miss rate (DMR)flow completion time (FCT)
数据中心(data center, DC)是云计算和在线服务的关键基础设施，在全球范围得到了广泛的部署和应用。在数据中心内部，服务器节点间具有大量通信需求。根据思科系统公司报告^[1]，2016年全球数据中心内部通信流量已达到5.143 ZB，预计到2021年将增长到12.371 ZB。数据中心网络(data center network, DCN)作为连接数据中心服务器的桥梁，需要承载这些持续增长的通信流量，其性能对数据中心业务的服务质量具有至关重要的作用。
当前数据中心中多种业务并存，而不同业务会产生不同模式的流量，因此数据中心网络中传输的是特征需求各异的混合流量^[2]。根据性能目标，流量可分为2类：截止期限流和非截止期限流^[3]。截止期限流主要由面向用户的交互性业务如网页搜索、键值存储、远程调用等^[4]产生。主节点将来自用户的请求分片并逐层分发给下层工作节点，下层工作节点对收到的部分请求进行处理产生部分结果，再逐层汇聚到主节点，形成最终结果返回给用户。在此过程中传输部分请求和结果的流均有严格的截止期限，若未在期限内完成传输，则该部分结果被直接丢弃，会降低最终结果质量且浪费带宽。因此，截止期限流的性能指标为截止期限错失率(deadline miss rate, DMR)。非截止期限流由并行处理、数据备份、管理配置等业务如各类分布式计算模型、虚拟机迁移等^[5]产生。在这些业务中，流量传输主要用于在处理阶段之间传递数据和中间结果及节点数据的备份和更新。非截止期限流没有具体的期限要求，但期望传输尽快完成以加速整个任务运行并提高网络吞吐量。因此，非截止期限流的性能指标为流完成时间(flow complete time，FCT)。
流量调度是优化传输性能的有效方法^[6-7]，具体指设定流量的传输顺序和带宽分配以优化特定效用函数。现有的数据中心网络流量调度机制主要包括Fastpass^[8]、PDQ^[6]、pFabric^[7]、PASE^[9]、PIAS^[10]、pHost^[11]、Karuna^[12]、Aemon^[13]和STAM^[14]等。Fastpass、PDQ、pFabric、PASE、PIAS和pHost均以降低DMR或FCT为目标，采用最早截止期限优先(earliest deadline first, EDF)、最短作业优先(shortest job first, SJF)、最小剩余时间优先(smallest remaining processing time, SRPT)等规则，实现DMR或FCT的降低，但对于混合流量场景缺少针对性。Karuna、Aemon和STAM为混合流调度机制。Karuna通过调节发送窗口大小优先传输截止期限流，保证其在期限内完成的同时最小化对非截止期限流的影响；同时采用SRPT和最低服务优先(least attained service first，LAS)规则传输非截止期限流以降低FCT。Karuna在计算截止期限流窗口大小时采用了过多近似和松弛，导致截止期限的满足不够严格。Aemon在主机端设计了基于紧迫性的拥塞控制协议(urgency-based congestion control protocol，UCP)，在交换机上设计了2层优先级的多级反馈队列。截止期限流随着紧迫性的提高逐渐从低优先级队列移动到高优先级队列，非截止期限流随着累计发送量的增大逐渐从高优先级队列移动到低优先级队列。同级队列中非截止时间流优先于截止时间流。Aemon在流量信息不可知的场景中能有效降低DMR与FCT，但由于反馈队列采用固定阈值，在流量分布不断变化的动态环境中难以实现最优调度。STAM引入了松弛时间的概念，在接收端检测到网络拥塞时计算每条截止期限流在每一轮往返时延(round trip time，RTT)内的松弛时间，并将对应的反馈包插入排队延时满足要求的最低优先级队列中；而非截止期限流则按采用最小累计发送量优先算法填充反馈队列剩余空间。发送端下一轮按反馈包顺序调整流的优先级。STAM缓解了Aemon中固定阈值的适应性问题，但最小累计发送量优先算法未能充分利用流量已知信息，仍无法获得最优性能。
针对上述问题，本文提出了基于分布式优化的数据中心网络混流调度(DOMS)机制。该机制形式化定义了截止期限流和非截止期限流的传输目标和约束，将混流调度问题归约为多目标优化问题；进而通过数据传输和反馈在节点间交互流量和链路信息，分布式求解该问题并分配流传输速率；利用传输目标的互补关系同时提升2种流量传输性能。
1 模型与形式化将包含N台主机、M台交换机和L条链路的数据中心网络抽象为无向图G(V, E)，其中，|V|=N+M, |E|=L。每个节点表示一台主机或交换机，每条边表示一条全双工链路，图的拓扑对应网络拓扑结构。定义链路l的总带宽为B_l。图 1为包含4台主机、7台交换机、16条链路的数据中心网络无向图模型。

图 1 数据中心网络模型

图选项

网络中的每条非截止期限流f可以由三元组＜s_f, d_f, S_f＞定义，s_f、d_f和S_f分别表示流f的发送端、接收端和总大小；截止期限流则由四元组＜s_f, d_f, S_f, D_f＞定义，D_f表示截止期限。
令F_D和F_N分别表示网络中所有截止期限流和非截止期限流的集合。由于截止期限流尺寸较小，通常为一次性到达，因此假设F_D中的每条流f到达网络时，s_f、d_f、S_f和D_f均为可知^[12]。而非截止期限流尺寸分布广泛，且部分应用中数据流的生成和传输同时进行。因此F_N中的流到达时，s_f和d_f均可从应用层获得，但仅部分流的S_f可知。F_D(t)和F_N(t)分别表示时刻t截止期限流和非截止期限流的集合，S_f(t)表示时刻t流f的剩余大小，$\tilde S$_f(t)表示时刻t流f已传输大小，D_f(t)表示时刻t截止期限流f的剩余期限。
定义A_f为流f到达网络的时刻，C_f为流f传输完成的时刻，则流完成时间为C_f-A_f。对于截止期限流，其性能指标$I_{\mathrm{D}}=\frac{\left|\left\{f: f \in F_{\mathrm{D}}, C_{f} \leqslant D_{f}\right\}\right|}{\left|F_{\mathrm{D}}\right|}$；对于非截止期限流，定义性能指标为平均流完成时间，即$I_{\mathrm{N}}=\frac{\sum\limits_{f \in F_{\mathrm{N}}}\left(C_{f}-A_{f}\right)}{\left|F_{\mathrm{N}}\right|}$。对于网络来说，任意时刻t每条链路l所传输流量的总速率都不应超过链路带宽B_l。根据以上目标和约束可将混流调度问题形式化为以下离线优化问题1：

$\begin{array}{c}\min w_{\mathrm{D}} I_{\mathrm{D}}+w_{\mathrm{N}} I_{\mathrm{N}}, \\\text { s. t. } \int_{t=A_{f}}^{C_{f}} r_{f}(t) \mathrm{d} t \geqslant S_{f}, \forall f \in F_{\mathrm{D}} \cup F_{\mathrm{N}};\end{array}$

(1)

$\sum\limits_{f \in F_{l}(t)} r_{f}(t) \leqslant B_{l}, \quad \forall l \in E, t \geqslant 0;$

(2)

$r_{f}(t) \geqslant 0, \forall f \in F_{\mathrm{D}} \cup F_{\mathrm{N}}, t \geqslant 0 ;$

(3)

$r_{f}(t)=0, \forall f \in F_{\mathrm{D}} \cup F_{\mathrm{N}}, 0 \leqslant t \leqslant A_{f}.$

(4)

目标函数中，w_D和w_N分别为截止期限流和非截止期限流的权重，旨在平衡I_D与I_N数量级的差距，使得单位带宽对二者的增量相等，保证调度决策只取决于流量和网络状态而非目标函数定义引入的数量差距。F_l(t)表示时刻t通过链路l的所有流集合，约束式(1)保证了每条流在其完成时间内真正完成传输，约束式(2)阐明链路带宽限制，约束式(3)阐明分配速率非负，约束式(4)规定了流到达之前速率为0。可知问题1是一个长时间尺度的多目标优化问题，为调度机制设计提供了目标和解空间约束，所有针对混合流量的调度机制都应在问题1的解空间内寻找可行解。
2 DOMS方案设计2.1 问题分解问题1为离线调度问题，需要网络中传输的所有流量信息，既包括已到达流量也包括未来流量。然而实际的数据中心流量调度问题是在线问题，每一时刻只有已到达网络的流量信息可知，未到达的流量信息不可知；且数据中心网络中流数众多，结合时间维度会导致变量数目过大，难以求解。为设计实际可行的在线调度机制，首先需要对问题1在时间上进行分解。定义以下问题2为求解问题1在时刻t可行解的问题快照：

$\begin{array}{l}\max \sum\limits_{f \in F_{\mathrm{N}}^{1}(t)} \frac{r_{f}(t)}{S_{f}(t)}+\sum\limits_{f \in F_{\mathrm{N}}^{0}(t)} \frac{r_{f}(t)}{\widetilde{S}_{f}(t)}, \\\text { s.t. } r_{f}(t) \geqslant \frac{S_{f}(t)}{D_{f}(t)}, f \in F_{\mathrm{D}}(t) ;\end{array}$

(5)

$\sum\limits_{f \in F_{l}(t)} r_{f}(t) \leqslant B_{l}, \quad \forall l \in E ;$

(6)

$r_{f}(t) \geqslant 0, \quad \forall f \in F_{\mathrm{D}}(t) \cup F_{\mathrm{N}}(t).$

(7)

截止期限流对完成期限的硬性要求直接由约束式(1)定义，即任意时刻每条截止期限流的带宽分配需保证其在剩余期限内完成；对于非截止期限流，大小已知和未知的流采用不同调度规则有利于充分利用流量已知信息。令F_N¹(t)和F_N⁰(t)分别表示时刻t网络中大小已知和未知的非截止期限流集合，即F_N(t)=F_N¹(t)∪F_N⁰(t)。对于F_N¹(t)中的流，SRPT规则能够有效降低流完成时间^[7]，体现在目标函数第1项：S_f(t)为时刻t流f的剩余大小，而最大化$\sum\limits_{f \in F_{\mathrm{N}}^{1}(t)} \frac{r_{f}(t)}{S_{f}(t)}$会驱动调度机制为剩余传输时间更少的流分配更多带宽。对于F_N⁰(t)中的流，由于剩余大小不可知无法直接采用SRPT。而LAS规则令每条流的优先级随累计发送量的增加而降低，短流在高优先级即可完成，长流在发送一定数据之后优先级降低，在长时间尺度上近似SRPT，在流大小未知的情况下有利于降低FCT。目标函数第2项中$\tilde S$_f(t)为时刻t流f已发数据量，最大化$\sum\limits_{f \in F_{\mathrm{N}}^{0}(t)} \frac{r_{f}(t)}{\widetilde{S}_{f}(t)}$会驱动调度机制为当前累计发送量更少的流分配更多带宽。F_N¹(t)和F_N⁰(t)中流的优先级是交错的，取决于S_f(t)与$\tilde S$_f(t)的大小关系。问题2中优化变量只包括时刻网络中流的分配速率r_f(t)，相比问题1大幅降低了求解复杂度。
2.2 总体框架由于数据中心规模庞大，且流量的到达和离开非常频繁，采用集中式调度会引入极大的通信、计算开销和延时，在实际运行中会大幅降低流量传输性能，并不现实。因此DOMS采用分布式调度结构，在主机与交换机之间交互流量和网络状态信息，分配流量速率，协作求解问题2。
问题2中，只有约束式(2)耦合了多个r_f(t)。因此问题2具备对偶分解特性，即将式(2)放松后每条流可独立优化且不会对其他流产生影响。全局最优解即为每条流速率最优解的集合，因此每台主机均可独立优化以自身为发送端的流。令流f的效用为$U_{f}\left(r_{f}(t)\right)=I_{\left\{f \in F_{\mathrm{N}}^{1}(t)\right\}} \frac{r_{f}(t)}{S_{f}(t)}+I_{\left\{f \in F_{\mathrm{N}}^{0}(t)\right\}} \frac{r_{f}(t)}{\widetilde{S}_{f}(t)}$, 则目标函数可表示为$\sum\limits_{f \in F_{\mathrm{N}}(t)} U_{f}\left(r_{f}(t)\right)$，问题2可看作网络效用最大化问题。首先构造问题2的Lagrange函数为

$\begin{array}{c}L(r, \lambda)=\sum\limits_{f \in F_{\mathrm{N}}(t)} U_{f}\left(r_{f}(t)\right)- \\\sum\limits_{l \in L} \lambda_{l}\left(\sum\limits_{f \in F_{l}(t)} r_{f}(t)-B_{l}\right),\end{array}$

即将约束条件式(2)写入目标函数进行放松，λ_l为链路l带宽约束的Lagrange乘子，表示链路l的拥塞程度。令λ_l≥0，则以L(r, λ)为目标函数会驱动每条链路的总分配速率不超过链路总带宽，并消除了耦合约束式(2)。因此，放松后每条流可独立求解。对偶函数g(λ)为L(r, λ)对所有r_f(t)取最小值：

$g(\lambda)=\inf \limits_{r} L(r, \lambda)$

可知g(λ)为$\sum\limits_{f \in F_{\mathrm{N}}(t)} U_{f}(t)$最小值的上界。求解g(λ)对所有λ_l的最小值即为求解$\sum\limits_{f \in F_{\mathrm{N}}(t)} U_{f}\left(r_{f}(t)\right)$的最小上界。由于问题2为凸优化问题且所有约束条件均为仿射的，问题2满足强对偶性，$\sum\limits_{f \in F_{\mathrm{N}}(t)} U_{f}\left(r_{f}(t)\right)$的最大值即为g(λ)的最小值。考虑分布式调度要求，将对偶问题分解为一个主问题和多个子问题。每个子问题对应一条非截止期限流f，在λ_l固定的情况下求解令L(r, λ)取最小值的r_f^*(t)：

$\begin{array}{c}\max U_{f}\left(r_{f}(t)\right)-r_{f}(t) \sum\limits_{l \in L(f)} \lambda_{l}, \\\text { s.t. } r_{f}(t) \geqslant 0.\end{array}$

(8)

而主问题则用来求解令g(λ)最小的所有λ_l：

$\begin{array}{c}\min \sum\limits_{f \in {F_{\rm{N}}}(t)} {{U_f}} \left( {r_f^*\left( {{\lambda ^f}} \right)} \right) - \sum\limits_{l \in L} {{\lambda _l}} \left( {\sum\limits_{f \in {F_l}(t)} {r_f^*} \left( {{\lambda ^f}} \right) - {B_l}} \right),\\{\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \lambda \ge 0.\end{array}$

(9)

其中$\lambda^{f}=\sum\limits_{l \in L(f)} \lambda_{l}(t)$表示流f经过的所有链路拥塞程度之和，r_f^*(λ^f)表示流f子问题的最优解。
子问题由主机直接求解，主问题由交换机和主机联合求解。DOMS的整体框架如图 2所示。发送端发出的流经过一跳或多跳到达接收端。每个数据包经过其路径上的每个交换机时，交换机按发送端计算的速率分配出口链路带宽，并将该链路的拥塞程度λ_l计入数据包头中，由接收端将该信息复制到反馈包头返回发送端，进而由发送端计算该流下一轮的分配速率，进行下一轮迭代。

图 2 DOMS整体框架

图选项

2.3 分布式调度算法定义r_f^max为流f的最大可能发送速率，即发送端网卡速率、瓶颈链路总带宽、接收端接收速率三者中的最小值。在数据包头中增加3个字段，分别用来记录D_f(t)、$\tilde S$_f(t)或$\tilde S$_f(t)、λ^f的值，在ACK包头中增加1个字段用来反馈λ^f。图 3—5的算法1、2、3分别描述了发送端、交换机和接收端的操作。

图 3 算法1

图选项

图 4 算法2

图选项

图 5 算法3

图选项

发送端为以自身发出的流计算发送速率。定义发送端i的接入链路总带宽为B_l(i)，剩余带宽为B_l(i)^′，初始令所有λ_l(0)=0，B_l(i)^′=B_l(i)。在每个发送端截止期限流优先于非截止期限流。将截止期限流按期限从小到大依次分配r_f(t)=min$\left\{\frac{S_{f}(t)}{D_{f}(t)}, B_{l(i)}^{\prime}\right\}$，即r_f(t)取在剩余期限内完成传输所需的最小速率和接入链路剩余带宽两者的最小值。此外，若$\frac{S_{f}(t)}{D_{f}(t)}>r_{f}^{\max }$，则说明截止期限流f已无法在期限内完成传输，此时应中止其传输为其他流让出带宽。每分配一条流的速率或中止一条流传输后即更新B_l(i)^′。在所有截止期限流处理完成后，将所有非截止期限流按S_f(t)(剩余大小已知)或$\tilde S$_f(t)(剩余大小不可知)从小到大依次分配速率。对非截止期限流f，子问题的目标函数是r_f(t)的线性函数，因此最大值在r_f(t)取值范围的端点处取得。若f∈F_N¹(t)，其分配速率为

$r_{f}(t)=\left\{\begin{array}{ll}\min \left\{B_{l(i)}^{\prime}, r_{f}^{\max }\right\}, & \frac{1}{S_{f}(t)} \geqslant \lambda^{f} ; \\0, & \frac{1}{S_{f}(t)}<\lambda^{f} .\end{array}\right.$

若f∈F_N⁰(t)，其分配速率为

$r_{f}(t)=\left\{\begin{array}{ll}\min \left\{B_{l(i)}^{\prime}, r_{f}^{\max }\right\}, & \frac{1}{\widetilde{S}_{f}(t)} \geqslant \lambda^{f} ; \\0, & \frac{1}{\widetilde{S}_{f}(t)}<\lambda^{f} .\end{array}\right.$

每分配一条流速率后即更新B_l(i)^′。在收到接收端返回的ACK包时更新S_f(t)和$\tilde S$_f(t)的值。
交换机负责分配出口链路带宽及维护拥塞程度λ_l。对每条出口链路上的流按截止期限流优先于非截止期限流、截止期限从小到大、S_f(t)或$\tilde S$_f(t)从小到大这三条规则依次排序，在出口链路分配带宽。

$r_{f}^{\text {out }}(t)=\min \left\{B_{l}^{\prime}, r_{f}^{\mathrm{in}}(t)\right\}$

其中：B_l^′为出口链路l的剩余带宽，r_fⁱⁿ(t)为流f进入交换机的速率。每分配一条流速率后即更新B_l^′。进而采用各流的入速率r_fⁱⁿ(t)更新对偶变量λ_l。由于主问题的目标函数g(λ)对所有λ_l均可微，主问题可直接采用梯度下降方法求解。定义τ表示迭代次数，在第(τ+1)轮迭代中，当通过链路l的所有流在第τ轮的速率r_f^out(τ)计算完成后，λ_l更新如下：

$\lambda_{l}(\tau+1)=\left[\lambda_{l}(\tau)-\alpha\left(B_{l}-\sum\limits_{f \in F(l)} r_{f}^{\mathrm{in}}(\tau)\right)\right]_{+}, \forall l.$

其中α表示梯度下降的迭代步长。将更新后的λ_l(τ+1)累加到包头的λ^f中。
接收端将包头中λ^f的值复制到ACK包头中，并按数据包到达的顺序和时刻反馈ACK包。
由于DOMS是在线调度算法，因此除静态时刻的调度策略外还需设计动态环境中的调度行为。当新流到达时，新流的发送端对本地所有流重新排序和分配速率；新流通过的交换机对相应出口链路l上的流重新排序并分配速率，用新的入速率更新λ_l并累加至之后通过的所有数据包头的λ_f中；新流接收端执行λ_f的复制和ACK包的反馈操作。当有流完成传输时，该流的发送端无需重新排序，只需更新接入链路剩余带宽B_l(i)^′，并且对该流之后的流依次重新分配速率；该流通过的交换机只需更新相应出口链路剩余带宽B_l^′，并且对该流之后的流重新分配速率，用新的入速率更新λ_l并累加至之后通过的所有数据包头的λ_f中；接收端无需任何操作。
发送端每当新流到达时需要分别对截止期限流和非截止期限流进行排序，计算复杂度分别为O(|F_D⁽ⁱ⁾|lb|F_D⁽ⁱ⁾|)和O(|F_N⁽ⁱ⁾|lb|F_N⁽ⁱ⁾|)；且针对每条流执行1次判断和最多2次赋值操作，计算复杂度为O(|F_D⁽ⁱ⁾|+|F_N⁽ⁱ⁾|)；因此发送端总的计算复杂度为O(|F_D⁽ⁱ⁾|lb|F_D⁽ⁱ⁾|)+O(|F_N⁽ⁱ⁾|lb|F_N⁽ⁱ⁾|)+O(|F_D⁽ⁱ⁾|+|F_N⁽ⁱ⁾|)；每当流完成时只需要针对当前流进行判断和赋值操作，计算复杂度为O(|F_D⁽ⁱ⁾|+|F_N⁽ⁱ⁾|)。交换机在新流到达时同样需要进行排序和3次赋值，计算复杂度为O(|F_D^(l)|lb|F_D^(l)|)+O(|F_N^(l)|lb|F_N^(l)|)+O(|F_D^(l)|+|F_N^(l)|)，而在流完成时只需执行赋值操作，计算复杂度为O(|F_D^(l)|+|F_N^(l)|)。接收端每接收一个数据包即进行λ^f的复制和ACK包的返回，因此每次操作的计算复杂度为O(1)。可知整体计算复杂度主要与流数和更新频率相关。文^[15]中的测量结果表明，单一主机和交换机上平均并发流数为36，且全网流的平均到达间隔为100 ms，即每台主机或交换机平均每100 ms需要对36条流进行排序和带宽分配。根据不同操作指令所需时钟周期数，在2.4 GHz处理器中每次操作只需1.5 μs左右，计算开销很小。
3 实验与性能评价3.1 实验设置仿真拓扑为数据中心网络常用的叶脊(leaf-spine)网络结构，如图 6所示。整个网络包括3层，由144台主机、12台架顶(top of rack, ToR)交换机和3台聚合(aggregation)交换机组成全连接。每台主机通过10 Gb/s链路与1台架顶交换机相连，每台架顶交换机通过3条40 Gb/s链路与3台聚合交换机相连。同一机架内的RTT值设为50 μs，跨机架的RTT值设为100 μs。

图 6 仿真实验拓扑结构

图选项

仿真流量分别根据网页搜索业务^[15]和数据挖掘业务^[16]生成。网页搜索业务流量既包括传输请求和响应，也包括数据更新的背景流。请求和响应均为短流，设大小为20 kB且标记为截止期限流，截止期限服从5~25 ms的均匀分布；背景流的大小和到达间隔根据文^[15]中的分布随机生成。而数据挖掘业务中超过一半的流小于1 kB，而最大流达到600 MB，将小于1 kB的流标记为截止期限流，截止期限服从流传输时间到2倍传输时间的均匀分布。每台主机作为发送端时，在其他主机中随机选择接收端。为观察DOMS在不同负载条件下的性能，将流到达间隔进行伸缩生成10%~100%的流量负载。
实验采用DMR、平均FCT、99分位FCT和吞吐量作为评价指标，采用混流调度机制Karuna、Aemon和STAM作为参考机制。
3.2 性能评价图 7展示了4种机制在网页搜索(ws)、数据挖掘(dm)两种流量、不同负载下的DMR、平均FCT和99分位FCT。由图 7a可知，网页搜索流量下DOMS取得最小的DMR，相比Karuna和STAM大幅减小，与Aemon接近；而数据挖掘流量下DOMS、Aemon和STAM的DMR非常接近，且明显小于Karuna。Karuna由于将截止期限约束放松为长期的平均速率约束，对截止期限的满足不严格，导致DMR较大；STAM采用M/M/1模型近似队列，对排队时间估计不够准确，导致DMR较大。Aemon虽然取得较小的DMR，但从图 7b和7c中可看出，Aemon中非截止期限流的平均FCT和99分位FCT都是最大的，未平衡好2种流量的带宽分配。此外，在2种流量下DOMS的平均FCT和99分位FCT均小于Aemon和STAM。Karuna将截止期限流的带宽过多分配给非截止期限流，以牺牲DMR为代价取得最小FCT；而DOMS的带宽分配更加平衡，因此平均FCT和99分位FCT略大于Karuna。可以看出，DOMS在保证2种流量带宽均衡的同时DMR和FCT均较小。

图 7 DMR和FCT

图选项

图 8展示了4种机制在不同负载下的吞吐量。可以看出，低负载条件下4种机制的吞吐量差距很小，高负载条件下DOMS吞吐量略低于Karuna和STAM，略高于Aemon。这是因为相比Karuna和STAM，DOMS将更多带宽分配给截止期限流，且根据剩余期限分配带宽虽然为非截止期限流留出更多带宽，但会造成一定的带宽空闲。然而吞吐量最大差距只有2.6%，可见DOMS对吞吐量的影响很小。

图 8 吞吐量

图选项

图 9展示了迭代步长α和网络拓扑对DOMS性能的影响。将图 6中每个机架内的主机数增加为16，机架数减小为9以保持总的主机数不变。令聚合交换机的数量依次从1增加到4，使网络边缘对核心的超量使用率(oversubscription ratio)依次为4:1、2:1、4:3和1:1，依次验证DOMS的性能，同时考察在不同超量使用率下迭代步长的最优取值。由图 9a可知，随着超量使用率的减小，DMR、平均FCT和99分位FCT均有明显降低，并且在超量使用率从4:1减小为2:1时变化最为显著。这是由于核心带宽从不足变为充足，为流量提供了更快的传输和更多调度空间。由图 9b、9c、9d可知，随着α在[10^-10，1]范围内变化，DMR最大波动为0.28%，平均FCT的变化范围为0.16 ms，99分位FCT的变化范围为1.81 ms，可见无论超量使用率如何取值，DOMS对α不敏感，能够通过增大α提高收敛速率。

图 9 参数敏感性

图选项

4 结论本文提出一种基于分布式优化的数据中心网络混流调度(DOMS)机制。该机制分别定义截止期限流与非截止期限流的优化目标和传输约束，将同一网络中的混流调度问题形式化为实时多目标优化问题，然后设计主机与交换机的协同调度结构，分布式地求解该优化问题，设定每条流的传输速率并演化至全局最优解。仿真结果表明，DOMS可以很好地适应流量的动态变化，同时降低截止期限流的期限错失率和非截止期限流的平均及尾部完成时间，有效协调了2种流量对带宽的争用。

参考文献

[1]	Cisco. Cisco global cloud index: Forecast and methodology, 2016-2021[R]. San Jose, USA: Cisco, 2018.
[2]	NOORMOHAMMADPOUR M, RAGHAVENDRA C S. Datacenter traffic control: Understanding techniques and tradeoffs[J]. IEEE Communications Surveys and Tutorials, 2018, 20(2): 1492-1525.
[3]	CHEN L, CHEN K, BAI W, et al. Scheduling mix-flows in commodity datacenters with Karuna[C]//Proceedings of the ACM SIGCOMM 2016 Conference. Florianopolis, Brazil: ACM, 2016: 174-187.
[4]	WILSON C, BALLANI H, KARAGIANNIS T, et al. Better never than late: Meeting deadlines in datacenter networks[C]//Proceedings of the ACM SIGCOMM 2011 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. Toronto, Canada: ACM, 2011: 50-61.
[5]	CHOWDHURY M, ZHONG Y, STOICA I. Efficient coflow scheduling with Varys[C]//ACM SIGCOMM 2014 Conference. Chicago, USA: ACM, 2014: 443-454.
[6]	HONG C Y, CAESAR M, GODFREY P B. Finishing flows quickly with preemptive scheduling[C]//ACM SIGCOMM 2012 Conference. Helsinki, Finland: ACM, 2012: 127-138.
[7]	ALIZADEH M, YANG S, SHARIF M, et al. pFabric: Minimal near-optimal datacenter transport[C]//ACM SIGCOMM 2013 Conference. Hong Kong, China: ACM, 2013: 435-446.
[8]	PERRY J, OUSTERHOUT A, BALAKRISHNAN H, et al. Fastpass: A centralized 'zero-queue' datacenter network[C]//ACM SIGCOMM 2014 Conference. Chicago, USA: ACM, 2014: 307-318.
[9]	MUNIR A, BAIG G, IRTEZA S M, et al. Friends, not foes: Synthesizing existing transport strategies for data center networks[C]//ACM SIGCOMM 2014 Conference. Chicago, USA: ACM, 2014: 491-502.
[10]	BAI W, CHEN L, CHEN K, et al. PIAS: Practical information-agnostic flow scheduling for commodity data centers[J]. IEEE/ACM Transactions on Networking, 2017, 25(4): 1954-1967. DOI:10.1109/TNET.2017.2669216
[11]	GAO P X, NARAYAN A, KUMAR G, et al. pHost: Distributed near-optimal datacenter transport over commodity network fabric[C]//Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies. Heidelberg, Germany: ACM, 2015, 1: 1-12.
[12]	CHEN L, CHEN K, BAI W, et al. Scheduling mix-flows in commodity datacenters with Karuna[C]//Proceedings of the ACM SIGCOMM 2016 Conference. Florianopolis, Brazil: ACM, 2016: 174-187.
[13]	WANG T, XU H, LIU F M. Aemon: Information-agnostic mix-flow scheduling in data center networks[C]//Proceedings of the First Asia-Pacific Workshop on Networking. Hong Kong, China: ACM, 2017: 106-112.
[14]	臧韦菲, 兰巨龙, 胡宇翔. 基于松弛时间与累计发送量的数据中心网络混合流调度机制[J]. 电子学报, 2019, 47(10): 2061-2068. ZANG W F, LAN J L, HU Y X. Slack time and accumulation-based mix-flow scheduling in data center networks[J]. Chinese Journal of Electronics, 2019, 47(10): 2061-2068. DOI:10.3969/j.issn.0372-2112.2019.10.006 (in Chinese)
[15]	ALIZADEH M, GREENBERG A G, DAVID A. M, et al. Data center TCP (DCTCP)[C]//Proceedings of the ACM SIGCOMM 2010 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New Delhi, India: ACM, 2010: 63-74.
[16]	GREENBERG A, HAMILTON J R, JAIN N, et al. VL2: A scalable and flexible data center network[C]//Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication. Barcelona, Spain: ACM, 2009: 51-62.