Per-Flow Traffic Measurement Through Randomized Counter Sharing
Per-Flow Traffic Measurement Through Randomized Counter Sharing
复制标题
DOI：
10.1109/tnet.2012.2192447
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Tao Li;Shigang Chen;Y. Ling
中科院分区：
文献类型：
--
作者：
Tao Li;Shigang Chen;Y. Ling
流量测量为服务提供商和网络管理员执行容量规划、会计和计费、异常检测和服务提供提供了关键的真实数据。设计在线测量模块的最大挑战之一是最小化每个数据包的处理时间，以跟上现代路由器的线路速度。为了应对这一挑战，我们应该尽量减少每个数据包的内存访问次数，并在片上SRAM中实现测量模块。SRAM的小尺寸要求设计非常紧凑的数据结构来存储每流信息。现有最好的工作，称为计数器编织，每流需要超过4位，每个数据包执行6次或更多的内存访问。在本文中，我们设计了一个快速和紧凑的测量函数来估计所有流的大小。它达到了最佳的处理速度：每个数据包两次内存访问。此外，它提供了合理的测量精度，在一个狭小的空间，计数器辫子不再工作。我们的设计基于一种新的数据编码/解码方案，称为随机计数器共享。该方案允许我们在存储中混合每个流的信息以保持紧凑性，并且在解码时，通过统计去除在其他流的信息混合过程中引入的错误来分离每个流的信息。通过基于真实网络流量轨迹的大量实验，分析并验证了在线流量测量方法的有效性。我们还提出了几种方法来增加流量大小的估计范围。
Traffic measurement provides critical real-world data for service providers and network administrators to perform capacity planning, accounting and billing, anomaly detection, and service provision. One of the greatest challenges in designing an online measurement module is to minimize the per-packet processing time in order to keep up with the line speed of the modern routers. To meet this challenge, we should minimize the number of memory accesses per packet and implement the measurement module in the on-die SRAM. The small size of SRAM requires extremely compact data structures to be designed for storing per-flow information. The best existing work, called counter braids, requires more than 4 bits per flow and performs six or more memory accesses per packet. In this paper, we design a fast and compact measurement function that estimates the sizes of all flows. It achieves the optimal processing speed: two memory accesses per packet. In addition, it provides reasonable measurement accuracy in a tight space where the counter braids no longer work. Our design is based on a new data encoding/decoding scheme, called randomized counter sharing. This scheme allows us to mix per-flow information together in storage for compactness and, at the decoding time, separate the information of each flow through statistical removal of the error introduced during information mixing from other flows. The effectiveness of our online per-flow measurement approach is analyzed and confirmed through extensive experiments based on real network traffic traces. We also propose several methods to increase the estimation range of flow sizes.