摘要

目前已经有大量关于提高数据中心间网络性能的研究[1][2][3][4][5]，但这些已有研究都专注于改善每个数据中心对之间的广域网路径的性能。由于这些方法未能利用存在于地理分布的数据中心上的大量应用层覆盖路径，也未能发现服务器存储转发数据的能力，因而它们是不完备的。而通过覆盖路径的使用，结合对带宽的预测，实时地对数据复制传输进行调度，能够实质性地提高数据中心间数据复制的性能。

关键词： 数据中心 流量调度 预测

一、 引言

如今，越来越多的大型企业在全国各地构建起了自己的数据中心以及跨数据中心域的数据传输平台。但是，连接每个数据中心对的长途链路十分昂贵，因此提高数据中心间链路的利用率能够为企业带来巨大的效益，尤其是随着5G的到来以及传输数据量的急剧膨胀，数据中心间链路利用率的提升更为紧迫，其所带来的效益更为显著。

传统的数据中心间的数据复制方法具有三个局限：

第一，低效的局部适应。现有的非集中式的协议缺少全局视图，这将导致次优的调度和路由决策。每个服务器仅看到可用的数据源（已下载部分文件的服务器）的子集，因此不能利用所有可用的覆盖路径来最大化吞吐量。即使覆盖网络只是部分分散，得到次优性能的现象也会发生[9]。即使每个服务器都有全局视图，单个服务器的本地适应仍然会在覆盖路径上产生潜在的热点和拥塞。

第二，高计算开销。为了得到全局视图并且实现最优的调度协议，现有的集中化的协议都要承受高的计算开销。大多数模型都是超线性的，所以集中化协议的计算开销通常都是指数增长的，这使得这些协议实际上不可行。

第三，固定的带宽分离。固定地分离链路带宽将会导致过度使用带宽或者不能充分使用带宽的现象。理论上，如果我们能够实时地充分利用在线流量所剩的可用带宽，则链路利用率会更稳定。

所以本文提出了基于预测的实时增量调度的方法。

二、 研究背景及现状

在数据中心间进行数据复制的需求急剧增长，为了满足这一需求，百度几年前部署了一个应用层的覆盖网络——Gingko。尽管后来Gingko进行了改良，但它依然基于接收者驱动的非集中化的覆盖多播协议，这类似于在其他覆盖网络（如CDNs和基于覆盖的实时视频流[6][7][8]）中使用的协议。它的基本思路是，当多个数据中心希望从一个源数据中心中请求一个数据文件时，被请求的数据将会经过多阶段的中间服务器传回请求方，其中，每个阶段的发送方选择是由下一阶段的接收者以分散的方式驱动的。

为了提高数据中心间WAN的链路利用率，Google先后提出了B4 WAN[17]以及它的升级版本B4 and After[18]，此外还有支持TE组件的BwE组件。

B4是连接Google全球数据中心的专用WAN，在它提出时，Google在全球的数据中心站点有12个，而到B4 and After提出时，Google的全球数据中心站点已经达到了33个。而且Google也表明，在B4提出之后的5年之内，带宽需求已经增长了100倍，而且会以每9个月翻倍的速度增长。B4 整体采用SDN的结构来实现，SDN能够提供一个运行在商用服务器上的、专用的、基于软件的控制平台，让使用者能对全局状态进行分析，简单地对计划内和计划外的网络变化进行协调。OpenFlow能够搭建SDN的生态系统，Google通过它可以开发多种switch/data平面元素。SDN和OpenFlow将软硬件的发展进行了解耦，使得控制平面的软件更简单，发展更快，同时促使数据平面的硬件能够基于可编程性来发展。此外，使用SDN的结构还有其他优势：新协议的快速迭代；简化的测试环境；通过模拟确定性中央TE服务器而不是尝试分布式协议的异步路由，可以改进TE规划；通过以结构为中心而不是以路由器为中心的WAN视图，可以简化网络管理。由于B4采用了SDN的结构，而且当时没有现有平台可以支持SDN部署，因此Google还定制了自己的交换机硬件。B4主要通过一个集中式的流量工程（TE）算法来为应用分配带宽，实现最大最小公平（max-min fairness），这一方式能够使链路利用率达到接近100%。

针对增长了100倍的带宽需求，从99%到99.99%的可靠性要求，以及容量不对称的现象，Google提出了B4 and After。B4的扩展方案是在原有站点附近新增站点，这样将会影响TE优化算法的性能，而且有限的交换机转发表空间将成为瓶颈。因此B4 and After将每一个站点设计为两层的拓扑抽象，底层引入一个称为supernode的结构，这是由商用硅交换芯片构成的标准两层Clos网络，顶层将多个supernode节点连成一个全网状的拓扑。这样一来，通过添加supernode节点便可以实现横向的扩展，通过仅更新需要的supernode便可以实现纵向的扩展，划分为supernode的粒度又能够提高可用性。分层拓扑结构中的容量不对称现象会降低链路可利用的空间，阻碍链路利用率的提升，为了解决这一问题，Google引入了sidelinks的概念。Sidelinks连接每个站点中的supernodes，构成全网状的结构，通过使用sidelinks，中央控制器动态地平衡一个站点中的由WAN链路故障引起的容量不对称。然而，之前的站点级别的TE并不能做到这些，这就需要一个supernode级别的TE来计算sidelinks的容量。但是，仅使用supernode级别的TE，需要进行IP-in-IP的封装，而且不能很好地收敛计算时间，同时还需要更大的交换机转发表来支持。于是，Google采用了分层TE的做法，结合使用站点级别的TE和supernode级别的TE。这样的做法只需要一次封包封装就能够实现站点到站点的传输，而且最短路径的计算成本较低，能够实现可扩展。

三、 动态分离的传输机制

3.1 DC间流量特征分析

对于大型在线服务提供商，一个很重要的数据通信模式是DC（Data Center）间的大量数据复制，在DC间进行数据复制所用的流量占DC间所有流量的主要部分。随着提供商将越来越多的数据中心部署到全球各地，以及海量数据的急剧膨胀，DC间的数据复制需要以一种更加频繁而且高效的方式来进行。

在数据中心间进行数据复制所使用的流量，占据数据中心间总流量的一大部分，同时也占据了每种应用类型总流量的一大部分。基于这样的事实，优化数据中心间数据复制的性能就显得十分重要。

对于数据中心间的数据复制，它们传输的目的地是大部分的数据中心，而不是少数的几个数据中心，而且在传输和传输之间，源数据中心和目的数据中心都有很大的差异。这一现象表明，想要事先配置好所有可能的数据复制请求是不切实际的。因此需要这样一个系统，它能自动地路由和调度所给的任意数据复制传输请求。

数据中心间数据复制的规模通常很大，60%的数据复制的规模超过1TB，而90%的数据复制的规模超过50GB。假定分配给每个DC间数据复制传输的总广域网带宽是几GB每秒，这些传输不是临时的而是持续的，通常最少持续数十秒，则任何优化数据复制传输的方案都必须动态地适应数据传输过程中的任何性能变化。另一方面，这种时间持久性也意味着数据中心间的数据复制传输可以容忍由集中控制机制引起的少量延迟。

3.2 实时增量调度

基于这样的动机，本文提出了一个集中化的近似最优的应用层网络系统，它把数据分成细粒度的单元，通过瓶颈不相交的覆盖链路[10]并行地发送它们，动态地共享带宽。本系统的核心是一个集中化的决策制定算法，它几乎实时地周期性地批量更新覆盖路由决策。通过将路由和决策进行解耦，本系统能够找到最佳的解决方案，同时做出近似实时的更新，得到满意的结果。

为了实现可扩展性，提高对网络动态的响应，广域覆盖网的传统思路在某种程度上依赖于单个节点（或中继服务器）的局部适应[6][9][11][12]，尽管因此会由于缺乏全局视图和协调而达到次优的性能。与此相反，本系统认为，将广域覆盖网的控制完全集中，同时在配置数据中心间的组播时实现近似最优的性能是可行的。概括地说，本系统有一个集中控制器，它周期性地从所有服务器拉取数据传输状态的信息，更新有关覆盖路由的决策，把它们推送到在服务器本地上运行的代理。并且当控制器出现故障或无法访问时，系统会退回到传统的非集中的控制模式。

集中化的系统能够产生接近最优的决策，但同时也会导致很小的更新延迟，因此要考虑在两者之间进行权衡。达到平衡的关键是近似最优的高效的覆盖路由算法，它可以做到几乎实时地更新决策。然而，由于决策空间十分庞大，使用标准路由和线性规划的方法很难得到近似最优的决策，这是实现集中控制的关键问题。

本系统以集中的方式周期性地（默认为3秒）更新路由和调度决策，每个周期的工作流程如下：

1) 由运行在每个服务器本地的代理确认本地的状态，包括数据块的传输状态（哪些块到来，哪些块未完成），服务器的可用性，磁盘故障，等等。

2) 然后这些数据被包装成一个控制消息，通过代理监视器的高效的消息传递层发送给集中化的控制器。

3) 控制器也从网络监视器接收网络层的数据（延迟敏感型流量的带宽消耗，以及每条数据中心间链路上的利用率）。

4) 一旦接收到来自所有代理和网络监视器的更新信息，控制器就运行集中化的决策制定算法，以得到新的调度和路由决策，并且通过代理监视器的消息传递层将新旧决策间的差异发送给每个服务器本地的代理。

5) 最后，代理为每个数据传输分配带宽，根据控制器的路由和调度决策来进行实际的数据传输。

本系统做了两个额外的优化来使系统的运行更高效：

1) 块的合并。为了减小计算规模，实现更高效的传输，本系统将具有相同源和目的的块合并为一个子任务。这样有两个方面的好处：首先，它显著地减少了每个调度周期中挂起的块，因此减少了集中化的决策制定逻辑的计算开销。其次，它减少了服务器间的并行TCP连接，这些并行的TCP连接会降低链路的利用率和性能。

2) 无阻塞更新。当控制器运行集中化的决策制定算法时，为了防止被决策制定算法阻塞，每个本地代理都使正在进行的数据传输保持活动状态。类似地，控制器也考虑了这一点，它在决策被重新计算的时候预测数据传输状态的变化，并且用这些预测的数据传输状态作为这个集中逻辑的输入。

3.3 在线流量预测

在传统的固定带宽分离的模式中，由于分配给在线流量和离线流量的带宽是固定的，所以即使在线流量很少时，离线流量也不能利用分配给在线流量但目前空闲的带宽，这将导致很低的链路利用率。所以本系统采用了动态带宽分离模式，它能实时地为大量数据传输调整可用带宽，通过不断地预测在线流量和自动地调整调度决策，来充分利用网络带宽。具体来说，本系统根据不同的网络情况来自动调整调度结果：当在线流量到达其峰值时，本系统缩减离线流量拥有的带宽以避免拥堵，当在线流量到达其谷值时，本系统让离线流量使用更多的带宽以充分使用剩余带宽。为了实现这一功能，本系统使用了在线流量预测算法，它能识别服务器带宽使用的变化，触发重调度来调整分配给大量数据传输的带宽。图 1为本系统动态带宽分离的逻辑图。网络监视器读取由代理观察到的traffic值，然后执行一个由EWMA（Exponentially Weighted Moving-Average）[13]和拐点检测算法[14]组成的Sliding-k模块，EWMA负责计算当前周期的流量预测值，拐点检测负责观察历史数据然后判断当前是否有突变出现，使代理监视器平稳而且敏感。

目前有一些基本方法可以检测在线流量变化并动态调整调度的配置，如EWMA、k-Sigma等[15][16]。但这些方法有时候会连续地重配置，甚至在网络很稳定的时候也会如此。因此，在预测可用带宽的时候面临着一个权衡：当我们在参考时更看重最近的数据，预测值将会出现明显的震荡，这将引起不必要的连续重调度；而当我们在参考时更看重历史数据，预测值受近期检测到的拐点的影响就较小，这使得系统对于网络变化不那么敏感。

为解决以上问题，本系统将EWMA[13]和拐点检测算法[14]结合，并且设计了定制的滑动k算法。具体来说，我们为EWMA算法设置了一个上界K，若当前没有拐点，k将被设置为K，而当一个拐点被检测到时，k将被设为0，然后逐渐地增长到K。我们把拐点检测放到网络变化监视器中，实现了定制算法。

在一个调度周期内，网络变化监视器不断地获取服务器吞吐量的一系列代理观察值，这些值在下一个调度周期内被用来预测可用带宽。

3.3.1 EWMA

EWMA即指数加权移动平均法，这一方法可以根据历史观测值来估计当前的值，预测时给观测值的权值随时间呈指数递减，离当前时间越近的数据权重越大。

EWMA的表达式如下：

从上式可以看出，观测值的权值随着时间呈指数式下降。给近期观测值较大的权重是因为它对预测值有较大的影响，更能反应近期变化的趋势。

3.3.2 贝叶斯在线拐点检测算法

为了同时保证稳定性以及对网络变化的敏感程度，预测模块引入贝叶斯拐点检测算法。

该算法使用消息传递算法计算当前“运行”长度或自上一个变化点以来的时间的概率分布。

该算法在单变量时间序列上以在线方式执行贝叶斯拐点检测。核心思想是在每个新数据点到达时递归计算“运行长度”的后验概率。运行长度定义为自上次更改点发生以来的时间。

3.3.2 Sliding-k

在对序列进行预测时，若EWMA的参数α设置得很小，意味着给久远一些的历史观测值的权重更大，预测结果会更加平稳，但对于突发的抖动不够灵敏，若α很大，意味着给近期观测值的权重越大，预测结果就会越灵敏，但是预测值会出现波动，引起连续的重配置（如果预测结果跟上一周期的预测值相差不大，则无需重新配置状态信息，减小更新压力）。所以本系统采用了Sliding-k的方式，即当前无拐点时就给久远一些的观测值更大的权重，以保证预测结果的平滑，而一旦检测出拐点，就给近期观测值更大的权重，保证预测结果的灵敏、准确。

其主要步骤如下：

1） 贝叶斯拐点检测算法计算当前周期为拐点的概率。

2） 通过将上一步得出的概率值与我们设定好的阈值对比，判断当前周期是否为拐点。

3） 如果当前周期为拐点，则EWMA的输入序列的窗口大小为1，也就是EWMA输入序列仅包含上一周期的观测值，且参数α设置为1，即预测时仅参考上一周期的观测值，之后每经过一个周期α值减小0.1，直到α值降低到我们指定的稳定值（如0.6）。

4） 如果当前周期非拐点，则EWMA的输入序列为上一个拐点出现时到上一周期这段时间内的一系列观测值。

5） EWMA根据输入的序列值和α值预测当前周期的值，输出到调度模块。

Sliding-k根据拐点检测的结果动态地调整预测方式，使得在无拐点时能够保证预测结果的平滑，而有突发拐点时又能灵敏地响应，做出准确的预测。

四、 实验评估

我们在实验中对比了固定带宽分离与我们动态带宽分离的方案。主要是在系统中固定刚性流量和弹性流量的比值来模拟静态带宽分离的效果，而我们的系统则可以动态地预测当前周期的刚性流量需求的大小，然后将剩下的空闲带宽都分配给弹性流量。

如图 2所示，实验结果中，蓝线代表了刚性流量占总带宽的百分比，黑线代表固定带宽分离方案下总的带宽利用率（刚性流量和弹性流量占总带宽的百分比），红线代表本系统方案下的总的带宽利用率。从图中可以看到，为刚性流量与弹性流量设置固定的比值2:3时，弹性流量最多只能使用完属于自己的总带宽的60%，尽管刚性流量远未使用完分配给它的总带宽的40%，弹性流量也不能去借用这部分空闲流量，这就造成了带宽的浪费。其中，图中黑线与蓝线形状相似是因为弹性流量在每周期内都使用了60%的带宽（其上限），也就是说黑线是蓝线往上平移了60%，这与我们的设想是一致的。

为了验证Sliding-k方法的预测效果，我们随机生成了分段的带“毛刺”的序列，首先使用EWMA对刚性流量进行预测，当α设置为0.3、0.5、0.9时预测效果分别如图 3图 4图 5所示，其中黑线代表真实值，红线代表预测值，可以看到α值为0.3时预测结果比较平滑但不够准确，特别是在拐点出现的时间点上，而α为0.9时预测值十分接近真实值，但这样的预测效果比较抖动，会引起频繁的重配置，增加更新压力，而α为0.5时，虽然拐点处的预测值不十分贴近真实值，但是能够兼顾预测平滑和预测灵敏这两点需求。

由于想要实现预测值足够平滑，且在拐点处的预测足够灵敏准确，因此要将拐点检测和EWMA结合使用，也就是本文提出的Sliding-k方法。当EWMA的参数值设置为0.3时，使用Sliding-k方法得到的预测效果如图 6，对比α同样为0.3但仅使用EWMA方法的预测效果（图 3）可以发现，Sliding-k能够弥补EWMA的不足，使拐点出现时的预测效果更加准确，而当α设置为0.5时，Sliding-k预测效果更好，如预测效果在无拐点时平滑，而在有拐点时敏感且准确，达到了预期的预测效果。

五、 结论

传统固定带宽分离的方式会造成这样一种现象，当刚性流量处于谷值的时候，那些预留给它的带宽由于已经被固定地分配给了刚性流量而不能被大量弹性流量充分利用，从而造成数据中心间链路带宽的浪费。而本文使用了动态带宽分离的方式，预测刚性流量的带宽占用情况，在保证延迟敏感型的刚性流量不受影响的条件下将剩余可用的链路带宽容量分配给弹性流量，这种基于预测的增量调度方式可以使链路利用率接近100%，充分地利用了链路带宽。未来可以考虑使用EWMA之外的更好的时间序列预测算法来提高预测效果，使链路利用率更高而且更加稳定。

参考文献

[1] Hong C Y, Kandula S, Mahajan R, et al. Achieving high utilization with software-driven WAN[C]//ACM SIGCOMM Computer Communication Review. ACM, 2013, 43(4): 15-26.

[2] Kumar A, Jain S, Naik U, et al. BwE: Flexible, hierarchical bandwidth allocation for WAN distributed computing[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 1-14.

[3] Savage S, Collins A, Hoffman E, et al. The end-to-end effects of Internet path selection[C]//ACM SIGCOMM Computer Communication Review. ACM, 1999, 29(4): 289-299.

[4] Zhang H, Chen K, Bai W, et al. Guaranteeing deadlines for inter-data center transfers[J]. IEEE/ACM Transactions on Networking (TON), 2017, 25(1): 579-595.

[5] Zhang Y, Xu K, Wang H, et al. Going fast and fair: Latency optimization for cloud-based service chains[J]. IEEE Network, 2017, 32(2): 138-143.

[6] Andreev K, Maggs B M, Meyerson A, et al. Designing overlay multicast networks for streaming[C]//Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures. ACM, 2003: 149-158.

[7] Sripanidkulchai K, Maggs B, Zhang H. An analysis of live streaming workloads on the internet[C]//Proceedings of the 4th ACM SIGCOMM conference on Internet measurement. ACM, 2004: 41-54.

[8] Zhang X, Liu J, Li B, et al. CoolStreaming/DONet: A data-driven overlay network for peer-to-peer live media streaming[C]//Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2005, 3: 2102-2111.

[9] Huang T Y, Johari R, McKeown N, et al. A buffer-based approach to rate adaptation: Evidence from a large video streaming service[C]//ACM SIGCOMM Computer Communication Review. ACM, 2014, 44(4): 187-198.

[10] Datta A K, Sen R K. 1-Approximation algorithm for bottleneck disjoint path matching[J]. Information processing letters, 1995, 55(1): 41-44.

[11] Repantis T, Cohen J, Smith S, et al. Scaling a monitoring infrastructure for the Akamai network[J]. ACM SIGOPS Operating Systems Review, 2010, 44(3): 20-26.

[12] Mukerjee M K, Hong J A, Jiang J, et al. Enabling near real-time central control for live video delivery in CDNs[C]//ACM SIGCOMM Computer Communication Review. ACM, 2014, 44(4): 343-344.

[13] Lucas J M, Saccucci M S. Exponentially weighted moving average control schemes: properties and enhancements[J]. Technometrics, 1990, 32(1): 1-12.

[14] Adams R P, MacKay D J C. Bayesian online changepoint detection[J]. arXiv preprint arXiv:0710.3742, 2007.

[15] Roberts S W. Control chart tests based on geometric moving averages[J]. Technometrics, 1959, 1(3): 239-250.

[16] Lucas J M, Saccucci M S. Exponentially weighted moving average control schemes: properties and enhancements[J]. Technometrics, 1990, 32(1): 1-12.

[17] Jain S, Kumar A, Mandal S, et al. B4: Experience with a globally-deployed software defined WAN[C]//ACM SIGCOMM Computer Communication Review. ACM, 2013, 43(4): 3-14.

[18] Hong C Y, Mandal S, Al-Fares M, et al. B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in google's software-defined WAN[C]//Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. ACM, 2018: 74-87.

分享让更多人看到