- Author:
Pascal Poupart(Waterloo) Networks, Online flow size prediction, Routing
摘要：
这篇文章发表在ICNP(第26届IEEE国际网络协议会议上)。描述了在计算机网络环境中的数据挖掘的新应用。该应用是关于预测流量大小和检测大象流量（非常大的流量）的问题。流量大小是一个非常重要的统计数据，可用于改进计算机网络中的路由，负载平衡和调度。
流量大小预测特别具有挑战性，因为流量模式不断变化，并且必须实时（毫秒）进行预测以避免延迟。我们描述了如何将这个问题抽象成online的机器学习任务来连续调整流量的变化。
我们基于三个真实流量数据集，评估了基于神经网络,高斯回归和在线贝叶斯的三个现实预测器的准确性。我们还表明了如何使用这种在线预测器来改进网络模拟中的路由（从而降低的流总完成时间。）
引入：
数据中心不断增长的对带宽的需求越来越大，可以通过multiplying多个链路来实现这一需求。一开始这不被认为是一个问题，然而，发现ecmp并不能够合理得分配flow，从而导致某些链路变得拥挤，而某些链路会变得很空闲，导致不公平分配的问题。
这一问题的原因是flow的size变化很剧烈。(几千字节的小老鼠流mice flow到许多千兆字节的大象 elephant flow ）它们占用路径的时间差异很大（毫秒到几小时）
因为大象的流很有可能被分配到同一链路，所以会导致拥塞的问题。
举个例子来说一些启发式 heuristic的算法比如ECMP，直接忽略了流的大小，并且直接平均分配流,会导致拥塞以及负载均衡的问题.流的大小在scheduling的技术上非常重要。因为要找到最小的平均FCT。
举个例子来说，short job first 是一个著名的有效的根据流的大小做的调度技术。
最近的工作证明了对于一些应用预测和推断flow的大小是可行的。Mahout 安装了一个shim layer 在end hosts 来观察那些大象流,通过监测流的超出阈值的socket buffer。更普遍的来说，因为没有一种可行的方法来调整网络end hosts 上的网络堆栈。
很多方法都是在检测到大象流在他们flow了一段时间后，因此他们只允许rerouting 和rescheduling
这种方法不是最理想的，因为拥塞会发生直到大象流被观察到，并且新的路径被选择了。因为Load balancing，大象流的行为会被消弱，来允许最小流没有delay的完成。
我们提出使用数据挖掘，来估计每个流的大小，当它开始观察到大象流，而没有修改任何end host的应用。流大小的估测是基于机器学习的，可以被简单的加入到逻辑中心的控制器中对于SDN网络。这样的估测器可以使用第一个包裹的特征 packet size, header information 以及TCP synchronization 来预测每个flow的size当每个flow开始的时候。
预测的流大小就可以来作为routing和scheduling的模型的输入，提升网络的engineering并且减少流的完成时间。 在这篇工作中，我们描述了怎么使用三个个ml的方法(Gaussian process, Gaussian mixture model 和 Bayesian Moment Matching 和神经网络)来估计每个flow的大小，基于历史数据以及网络的流数据。
这篇paper的结构如下：