Online Spread Estimation with Non-duplicate Sampling
Online Spread Estimation with Non-duplicate Sampling
复制标题
DOI：
10.1109/infocom41043.2020.9155525
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Yu-E. Sun;He Huang;Chaoyi Ma;Shigang Chen;Yang Du;Qingjun Xiao
中科院分区：
文献类型：
--
作者：
Yu-E. Sun;He Huang;Chaoyi Ma;Shigang Chen;Yang Du;Qingjun Xiao
高速网络中的逐流传播测量具有许多实际应用。这是一个比传统的单流粒度测量更困难的问题。大多数先前的工作是基于草图，重点是减少其空间需求，以适应片上缓存存储器。这种设计允许以线路速率执行测量，但它必须接受与用于扩展查询的昂贵计算（不适合在线操作）和用于小流的扩展估计中的大误差的折衷。本文利用基于在实践中常见的片上/片外模型的新的扩展估计器设计来补充现有技术。新的估计器支持在线查询在真实的时间，并产生传播估计有更好的精度。通过将流量数据存储在片外存储器中，我们的新设计面临着高效非重复采样的关键技术挑战。我们提出了一个两阶段的解决方案，片上/片外的数据结构和算法，这不仅是有效的，而且高度可配置的各种概率性能保证。基于真实的互联网流量轨迹的实验结果表明，与现有技术相比，该方法将平均相对和绝对误差降低了一个数量级左右，并且在小流量的流分类中实现了空间效率和准确率效率。
Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real time and produces spread estimation with much better accuracy. By storing traffic data in off-chip memory, our new design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. The experiment results based on real Internet traffic traces show that our estimator reduces the mean relative and absolute error by around one order of magnitude, and achieves both space-efficiency and accuracy-efficiency in flow classification for small flows compared to the prior art.