Data streaming algorithms for estimating entropy of network traffic
Data streaming algorithms for estimating entropy of network traffic
复制标题
DOI：
10.1145/1140277.1140295
复制
发表时间：
2006-06
影响因子：
1.6
通讯作者：
Ashwin Lall;Vyas Sekar;Mitsunori Ogihara;Jun Xu;Hui Zhang
中科院分区：
文献类型：
--
作者：
Ashwin Lall;Vyas Sekar;Mitsunori Ogihara;Jun Xu;Hui Zhang
使用流量分布的熵已经被证明可以帮助各种各样的网络监控应用程序，如异常检测，聚类以揭示有趣的模式和流量分类。然而，在实践中实现这种潜在的好处需要精确的算法，可以在高速链路上运行，具有较低的CPU和内存要求。本文研究了流计算模型中的熵估计问题。我们给出了这个问题的下界，表明无论是近似还是随机化都不能让我们有效地计算熵。我们提出了两种算法随机近似的熵在时间和空间有效的方式，适用于非常高的速度（大于OC-48）的链接。熵估计的第一个算法的灵感来自于与Alon等人的开创性工作的结构相似性。用于估计频率矩，并且我们提供了关于误差和资源使用的强有力的理论保证。我们的第二种算法利用了这样的观察结果，即通过将高频项（或大象）与低频项（或小鼠）分离，可以增强流算法的性能。我们评估我们的算法从不同的部署方案的流量跟踪。
Using entropy of traffic distributions has been shown to aid a wide variety of network monitoring applications such as anomaly detection, clustering to reveal interesting patterns, and traffic classification. However, realizing this potential benefit in practice requires accurate algorithms that can operate on high-speed links, with low CPU and memory requirements. In this paper, we investigate the problem of estimating the entropy in a streaming computation model. We give lower bounds for this problem, showing that neither approximation nor randomization alone will let us compute the entropy efficiently. We present two algorithms for randomly approximating the entropy in a time and space efficient manner, applicable for use on very high speed (greater than OC-48) links. The first algorithm for entropy estimation is inspired by the structural similarity with the seminal work of Alon et al. for estimating frequency moments, and we provide strong theoretical guarantees on the error and resource usage. Our second algorithm utilizes the observation that the performance of the streaming algorithm can be enhanced by separating the high-frequency items (or elephants) from the low-frequency items (or mice). We evaluate our algorithms on traffic traces from different deployment scenarios.