sigcomm'18--香港科技大学

摘要：

目前DRL（深度强化学习）算法的时延过大，不能直接应用于处理流级别的数据中心流量优化，因为短流在决策未生成之前已经结束了。

基于数据中心的流量分布类型为长尾分布，本文提出了两级DRL系统：周边（PS）和中枢系统（CS）。PS位于终端，收集流信息，在本地为短流作出决策，保证最小时延，但PS的决策还是由CS干预的。CS拥有全局流量信息，为长流作出决策。实验搭建在32个服务器的实验床上，相比现有方法，AuTO将RTT从几周降低到了100毫秒，同时提高了性能。平均FCT也比现有方法降低了48.14%。

简介：

问题：现有TO算法依赖于人工启发式算法，依据为流量负荷，流量大小分布，流量密集度等分量分布状况。存在问题有：1）TO算法的参数设置与真实情况不匹配，造成性能下降。举例：PIAS，pFabric，Aalo。2）已存在的TO启发式算法的RTT太长，以周为单位。因为需要很长的时间收集应用信息，流量数据信息，才能设置启发式算法的相关参数。举例： 部署监测系统，收集足够多的数据分析，设计启发式算法，仿真优化工具寻找合适参数，最后在实验床上测试启发式算法。这一完整的周期很长。

动机：强化学习是机器学习的分支，主要用于决策和动作控制。现有领域在深度学习方面取得了成果：DeepMind的Atari结果，AlphaGo等等。受到这些启发，本文尝试在数据中心TO方面应用DRL工具。一个流调度的小测试验证了单一的集中式TO系统在大规模的数据中心（10的5次方台服务器）中不能满足短流的需求，存在决策速度慢，无用的问题，因此本文才尝试用分层TO架构。

关键：AuTO可扩展的关键将耗时的DRL算法处理与需要快速采取动作的短流处理分开。解决方案为在PS系统采用多级反馈队列（MLFQ）和一组门限值进行流调度。每条新流都是最高优先级，随着发送的字节数增加，优先级会降低。这样，PS系统就会根据本地信息（发送字节数和门限值）对每条流进行快速决策。门限值由CS系统通过DRL算法优化，更新周期会较长。对于长流来说，CS系统会使用另一种DRL算法确定路由，速率和优先级。

实验测试：搭建环境为32台服务器和2台交换机。流量模式为固定的负载和流分布，对比方案为标准的启发式算法（最少工作优先和最小服务优先），训练时间为8小时，平均FCT降低了8.71%。

背景和动机：

介绍了DRL模型，通过小型流调度实验证明现有DRL系统处理时延过长，不能满足数据中心级TO。

AuTO设计：

两级系统：PS运行在终端，为短流做TO决策，CS为长流做决策。

AuTO系统

PS系统：

根据CS下发的一组门限值和流的大小，为流打上不同的优先级标签，从而确保PS系统仅仅根据本地信息就可以为短流作出全局最优决策。分为执行模块和监测模块。

MLFQ-多级优先级反馈队列

执行模块：采用MLFQ（最早在PIAS中出现）为短流分配优先级。优先级字段填充在IP头部的服务类型字段中的DSCP字段中（占6个比特）。这样每条流就可以在终端根据发送的字节数和门限值快速打上相应的优先级标签。这样，长短流自然就分开了，对于长流，CS也可以单独做决策（路由策略，速率限制和优先级）。

监测模块：主要用来收集已完成流的大小、流完成时间。CS根据收集信息更新流分布模型。同时，检测系统也需向CS报告即将到来的长流信息，以便CS及时作出决策。

CS系统：

4队列的AuTO系统示例

CS系统由两种DRL代理（agent）组成：短流代理（sRLA）和长流代理（lRLA）。短流代理解决最小化FCT的问题，使用DDPG算法，用来更新门限值；长流使用PG（策略梯度）算法生成长流的路由、速率、优先级。

DRL理论分析

优化MLFQ门限值：

难点在于计算最优门限值。之前的工作提供了计算门限值的数据分析，并且建议更新周期为周或月。AuTO的优化目标是在连续的动作空间中寻求一个真实的最优值。将门限值优化问题看做一个DRL问题，用DNN网络模拟复杂的数据中心网络。

将门限值优化转化为M/M/1排队模型：到达时间服从泊松分布，服务时间服从指数分布，先到先服务，队列长度无限制，可加入队列的人数无限。假设流分布的累计密度函数为F(x)，表示流大小不大于x的概率，Li表示给定流在队列Qi中引入的数据包的数量， 则E[Li]≤(αi-αi-1)(1-F (αi-1))。流到达速率为λ，则队列Qi中数据包到达速率为λi=λE[Li ]。假定链路服务速率为μ，则Q1的服务速率为μ，空闲概率为1-ρ1，ρi表示服务被占用的概率。imax (x)表示大小为x 的流的大于x的最小门限值的下标。

队列i的服务速率 数据包在Qi中的逗留时间 T(x) ：大小为x的流的平均FCT

则最小化FCT即可表示为：

最小化FCT数学表达

状态空间：一组已完成流的属性集合。每条流有7个属性：五元组、流大小、流完成时间。100条短流

动作空间：一组MLFQ门限值{αi，t}

反馈函数：前一时刻与当前时刻目标函数的比值。

优化长流：

使用PG算法，优化长流。

动作空间：每条流对应优先级，限速，路径（路径的枚举方式与XPath相同）

状态空间：未结束的流（11条长流）：五元组，优先级；已经结束的流（10条长流）：五元组，流大小，FCT

反馈函数：通过已经结束的流获得。每条已完成流的吞吐量为流大小与流完成时间的比值。则反馈函数设置为两个连续时间所有已完成流的平均吞吐量的比值。

（a）反馈函数  （b）单一流的吞吐量计算公式

系统实现部分：

语言Python2.7，深度学习框架Keras，PS和CS系统是通过RPC接口通信的。

PS系统：

监测模块：在linux内核中实现是最高效的，但现有方案是在流发生器中实现的。一个周期为T秒，MM收集已结束的流（7个属性）（10条长流，100条短流），未结束的流（6个属性）（11条未结束的长流）信息，并将其整合通过RPC接口发送给CS。收集流的个数是由流量负载和采样周期决定的。

执行模块：在linux内核实现。周期性接收CS下发的一组门限值和本地长流的路由、限速、优先级信息。对于短流，用ECMP选路和负载均衡，这样就不需要对每条流进行集中式控制和拥塞控制。对于长流，EM利用相同的linux内核模块为长流打上优先级标签。在限速操作上，使用TCHTB实现。HTB队列“控发不控收”。EM首先建立一个父类的HTB队列，将速率设置为CS指定该节点的总出口带宽。当某条流到达最低优先级队列时，EM通过HTB过滤器匹配流的五元组为其设置CS下发的速率。速率上限为min{原始速率，CS下发的速率的两倍}。

CS系统：

借鉴了SEDA系统架构，分为三块：HTTP请求处理、深度网络学习或处理、回复发送。使用三个进程分别实现，进程之间使用队列，这样避免了Python实现过程中的全局锁问题。超参数（架构，神经网络层数，节点数等）的选择由经验得出。

评估：

1.在固定的流大小分布和流量负载分布情况下，AuTO性能与标准启发式算法相比：平均FCT降低了48.14%

2.当流量特征变化时，AuTO能够适应这种变化吗：四组服务器分别生成不同流大小分布的流量，测试结果为平均流完成时间降低了37.20%

3.AuTO在多长时间内可以应对流量特征变化：四组服务器的流量模式周期性变化，性能稳定，优于标准启发式算法。

4.AuTO的整体性能开销和可扩展性如何：平均10ms就可以完成门限值等更新，传统算法需要几个月或者几周。对于PS系统，CPU利用率和吞吐量的开销也显著下降。