You Can Drop But You Can't Hide: K-persistent Spread Estimation In High-speed Networks

He Huang Soochow University, P.R. China
Yue Sun Soochow University, P.R. China
Shaojie Tang University of Texas at Dallas, USA
Shigang Chen University of Florida, USA
Kai Han University of Science and Technology of China, P.R. China
Jing Yuan University of Texas at Dallas, USA
Wenjian Yang Soochow University, P.R. China


Traffic measurement in high-speed networks has many applications in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a new problem called k-persistent spread estimation, which measures persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t can be arbitrarily defined in user queries. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. Yet, it is under-investigated as the prior work only addresses a special case with a questionable assumption. Designing an efficient and accurate k-persistent estimator requires us to use bitwise SUM (instead of bitwise AND typical in the prior art) to join the information collected from different periods. This seemly simple change has fundamental impact on the mathematical process in deriving an estimator, particular over space-saving virtual bitmaps. Based on real network traces, we show that our new estimator can accurately estimate the k-persistent spreads of the flows. It also performs much better than the existing work on the special case of measuring elements that appear in all periods.

You may want to know: