Title: Persistent Spread Measurement for Big Network Data Based on Register Intersection,
Abstract: Persistent spread measurement is to count the number of distinct elements
that persist in each network flow for predefined time periods. It has many
practical applications, including detecting long-term stealthy network
activities in the background of normal-user activities, such as stealthy DDoS
attack, stealthy network scan, or faked network trend, which cannot be detected
by traditional flow cardinality measurement. With big network data, one
challenge is to measure the persistent spreads of a massive number of flows
without incurring too much memory overhead as such measurement may be performed
at the line speed by network processors with fast but small on-chip memory. We
propose a highly compact Virtual Intersection HyperLogLog (VI-HLL) architecture
for this purpose. It achieves far better memory efficiency than the best prior
work of V-Bitmap, and in the meantime drastically extends the measurement
range. Theoretical analysis and extensive experiments demonstrate that VI-HLL
provides good measurement accuracy even in very tight memory space of less than
1 bit per flow.