皮盼资讯网移动版

在对序列进行预测时，若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.