Algorithms and estimators for accurate summarization of internet traffic
Algorithms and estimators for accurate summarization of internet traffic
复制标题
用于准确汇总互联网流量的算法和估算器
DOI：
10.1145/1298306.1298344
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
E. Cohen;N. Duffield;Haim Kaplan;C. Lund;M. Thorup
IP网络中流量的统计摘要是网络操作的核心，用于恢复任意流子群体的流量信息。因此，考虑到路由器的资源限制，收集最准确和信息量最大的摘要非常重要。Cisco的采样NetFlow基于将采样数据包流聚合为流，是部署最广泛的此类系统。
我们观察到两个来源的效率低下，在目前的方法。首先，使用单个参数（采样率）来控制存储器和处理/访问速度的利用率，这意味着必须根据瓶颈资源来设置该参数。其次，无偏估计量适用于实际上通过在测量周期期间不均匀地使用资源而收集的汇总（来自测量周期的较早部分的信息根本不被收集，并且在执行采样率自适应时利用或丢弃较少的计数器）。
我们开发的算法可以通过均匀、更有效地利用可用资源来收集更多信息的摘要。我们的方法的核心是一个新的推导无偏估计，使用这些更多的信息计数。我们展示了如何有效地计算这些估计量，并通过分析证明它们优于以前的方法（在所有数据包流和子群体上具有较小的方差）。上级。对Pareto分布和IP流数据的模拟表明，新的摘要提供了更准确的估计。我们提供了一个实施设计，可以有效地部署在路由器。
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on the traffic of arbitrary subpopulations of flows. It is therefore of great importance to collect the most accurate and informative summaries given the router's resource constraints. Cisco's sampled NetFlow, based on aggregating a sampled packet stream into flows, is the most widely deployed such system.
We observe two sources of inefficiency in current methods. Firstly, a single parameter (the sampling rate) is used to control utilization of both memory and processing/access speed, which means that it has to be set according to the bottleneck resource. Secondly, the unbiased estimators are applicable to summaries that in effect are collected through uneven use of resources during the measurement period (information from the earlier part of the measurement period is either not collected at all and fewer counter are utilized or discarded when performing a sampling rate adaptation).
We develop algorithms that collect more informative summaries through an even and more efficient use of available resources. The heart of our approach is a novel derivation of unbiased estimators that use these more informative counts. We show how to efficiently compute these estimators and prove analytically that they are superior (have smaller variance on all packet streams and subpopulations) to previous approaches. Simulations on Pareto distributions and IP flow data show that the new summaries provide significantly more accurate estimates. We provide an implementation design that can be efficiently deployed at routers.