Data Streaming Algorithms for Efficient and Accurate Estimation of Flow Size Distribution

Knowing the distribution of the sizes of traffic flows passing through a network link helps a network operator to characterize network resource usage, infer traffic demands, detect traffic anomalies, and accommodate new traffic demands through better traffic engineering.

Previous work on estimating the flow size distribution has been focused on making inferences from sampled network traffic. Its accuracy is limited by the (typically) low sampling rate required to make the sampling operation affordable. In this paper we present a novel data streaming algorithm to provide much more accurate estimates of flow distribution, using a “lossy data structure” which consists of an array of counters fitted well into SRAM. For each incoming packet, our algorithm only needs to increment one underlying counter, making the algorithm fast enough even for 40 Gbps (OC-768) links. The data structure is lossy in the sense that sizes of multiple flows may collide into the same counter. Our algorithm uses Bayesian statistical methods such as Expectation Maximization to infer the most likely flow size distribution that results in the observed counter values after collision. Evaluations of this algorithm on large Internet traces obtained from several sources (including a tier-1 ISP) demonstrate that it has very high measurement accuracy (within 2%).

Our algorithm not only dramatically improves the accuracy of flow distribution measurement, but also contributes to the field of data streaming by formalizing an existing methodology and applying it to the context of estimating the flow-distribution.

Speaker Details

Abhishek is a Ph.D. student in Computer Science at Georgia Institute of Technology. He received the B.Tech. degree in Computer Science and Engineering from Indian Institute of Technology, Delhi. His current research interests include algorithms and mechanisms for high speed traffic monitoring, applications and algorithms for peer-to-peer networks, and Internet scale analysis of worm propagation. He received the Best Student Paper Award at the ACM SIGMETRICS/IFIP Performance joint conference in June, 2004. In the past, he has worked on Mobile Ad-hoc Networks, Active Networks, Active Queuing Mechanisms and on Flow and Congestion Control in Networks.

Date:
Speakers:
Abhishek Kumar
Affiliation:
Georgia Institute of Technology
    • Portrait of Jeff Running

      Jeff Running