High-Speed Per-Flow Traffic Measurement with Probabilistic Multiplicity Counting
High-Speed Per-Flow Traffic Measurement with Probabilistic Multiplicity Counting
复制标题
DOI：
10.1109/infcom.2010.5461921
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Peter Lieven;Björn Scheuermann
中科院分区：
文献类型：
--
作者：
Peter Lieven;Björn Scheuermann
在当今的高速骨干网络链路上，测量每流量信息已经变得非常具有挑战性。由于计算和成本的限制，在OC-192或OC-768链路上保持精确的每流数据包计数器实际上是不可行的。在今天的路由器中实现的分组采样导致大的近似误差。在这里，我们提出了概率多重计数（PMC），一种新的数据结构，能够占流量的概率。PMC算法非常简单且高度可并行化，因此允许在软件和硬件中有效实现。同时，它提供了非常准确的交通统计数据。我们评估PMC与阿尔蒂和现实世界的交通数据，证明它优于其他方法。
On today's high-speed backbone network links, measuring per-flow traffic information has become very challenging. Maintaining exact per-flow packet counters on OC-192 or OC-768 links is not practically feasible due to computational and cost constrains. Packet sampling as implemented in today's routers results in large approximation errors. Here, we present Probabilistic Multiplicity Counting (PMC), a novel data structure that is capable of accounting traffic per flow probabilistically. The PMC algorithm is very simple and highly parallelizable, and therefore allows for efficient implementations in software and hardware. At the same time, it provides very accurate traffic statistics. We evaluate PMC with both artificial and real-world traffic data, demonstrating that it outperforms other approaches.