Highly Compact Virtual Active Counters for Per-flow Traffic Measurement
Highly Compact Virtual Active Counters for Per-flow Traffic Measurement
复制标题
DOI：
10.1109/infocom.2018.8485804
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
You Zhou;Yian Zhou;Shigang Chen;Youlin Zhang
中科院分区：
文献类型：
--
作者：
You Zhou;Yian Zhou;Shigang Chen;Youlin Zhang
Ahstract-Per-flow流量测量是网络大数据时代的一个基础性问题，已经被广泛应用于许多应用中，包括容量规划、异常检测、负载均衡、流量工程等。为了跟上现代网络设备的线路速度（例如，路由器），通常通过使用片上高速缓存（例如SRAM）来实现每流测量在线模块以最小化每分组处理时间，但是片上SRAM昂贵且尺寸有限，这对流量测量提出了重大挑战。作为回应，最近的研究是面向设计高度紧凑的数据结构，近似估计，可以提供概率保证每流测量。被称为计数器树（CT）的现有技术在存储器消耗中要求每个流至少2位，并且在处理时间中要求每个分组多于2次存储器访问。在本文中，我们提出了一种新颖的设计高度紧凑和高效的计数器架构，称为虚拟主动计数器估计（VAC），它实现了更快的处理速度（平均每个数据包略多于1个内存访问），并提供更准确的测量结果比CT在相同的分配内存。此外，VAC即使在存储器空间非常紧张的情况下（每个流小于1位，甚至每个流的五分之一位）也可以表现良好。理论分析和基于真实的网络迹线的实验证明了VAC的上级性能。
Ahstract-Per-flow traffic measurement is a fundamental problem in the era of big network data, and has been widely used in many applications, including capacity planning, anomaly detection, load balancing, traffic engineering, etc. In order to keep up with the line speed of modern network devices (e.g., routers), per-flow measurement online module is often implemented by using on-chip cache memory (such as SRAM) to minimize per-packet processing time, but on-chip SRAM is expensive and limited in size, which poses a major challenge for traffic measurement. In response, much recent research is geared towards designing highly compact data structures for approximate estimation that can provide probabilistic guarantees for per-flow measurement. The state of art, called Counter Tree (CT), requires at least 2 bits per flow in memory consumption and more than 2 memory accesses per packet in processing time. In this paper, we propose a novel design of a highly compact and efficient counter architecture, called Virtual Active Counter estimation (VAC), which achieves faster processing speed (slightly more than 1 memory access per packet on average) and provides more accurate measurement results than CT under the same allocated memory. Moreover, VAC can perform well even with a very tight memory space (less than 1 bit per flow or even one fifth of a bit per flow). Theoretical analysis and experiments based on real network traces demonstrate the superior performance of VAC.