Sketching unaggregated data streams for subpopulation-size queries

ABSTRACT

IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing, anomaly detection, inferring traffic demands, configuring packet filters and routing protocols, and more. While queries are posed over the set of flows, the summarization algorithmis applied to the stream of packets. Aggregation of traffic into flows before summarization requires storage of per-flow counters, which is often infeasible. Therefore, the summary has to be produced over the unaggregated stream.

An important aggregate performed over a summary is to approximate the size of a subpopulation of flows that is specified a posteriori. For example, flows belonging to an application such as Web or DNS or flows that originate from a certain Autonomous System. We design efficient streaming algorithms that summarize unaggregated streams and provide corresponding unbiased estimators for subpopulation sizes. Our summaries outperform, in terms of estimates accuracy, those produced by packet sampling deployed by Cisco's sampled NetFlow, the most widely deployed such system. Performance of our best method, step sample-and-hold is close to that of summaries that can be obtainedfrom pre-aggregated traffic.

REFERENCES

• 1: E. Cohen, N. Duffield, H. Kaplan, C. Lund, and M. Thorup. Algorithms and estimators for accurate summarization of Internet traffic. Manuscript, 2007.
• 2: Edith Cohen , Haim Kaplan, Bottom-k sketches: better and more efficient estimation of aggregates, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 3: E. Cohen and H. Kaplan. Sketches and estimators for subpopulation weight queries. Manuscript, 2007.
• 4: Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network, Journal of Computer and System Sciences, v.73 n.3, p.265-288, May, 2007 [doi>10.1016/j.jcss.2006.10.016]
• 5: E. Cohen and H. Kaplan. Summarizing data using bottom-k sketches. Manuscript, 2007.
• 6: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 7: Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating flow distributions from sampled flow statistics, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863992]
• 8: Nick Duffield , Carsten Lund , Mikkel Thorup, Flow sampling under hard resource constraints, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 9: Cristian Estan , Ken Keys , David Moore , George Varghese, Building a better NetFlow, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 11: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 12: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 13: Nicolas Hohn , Darryl Veitch, Inverting sampled traffic, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948235]
• 14: Ken Keys , David Moore , Cristian Estan, A robust system for accurate real-time summaries of internet traffic, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 15: Abhishek Kumar , Minho Sung , Jun (Jim) Xu , Ellen W. Zegura, A data streaming algorithm for estimating subpopulation flow size distribution, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 16: Sriram Ramabhadran , George Varghese, Efficient implementation of a statistics counter architecture, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 17: Devavrat Shah , Sundar Iyer , Balaji Prabhakar , Nick McKeown, Maintaining Statistics Counters in Router Line Cards, IEEE Micro, v.22 n.1, p.76-81, January 2002 [doi>10.1109/40.988692]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Algorithms, Measurement, Performance

Keywords:
IP flows, data streams, sketches, subpopulation size