皮盼资讯网移动版

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