Confident estimation for multistage measurement sampling and aggregation

ABSTRACT

Measurement, collection, and interpretation of network usage data commonly involves multiple stage of sampling and aggregation. Examples include sampling packets, aggregating them into flow statistics at a router, sampling and aggregation of usage records in a network data repository for reporting, query and archiving. Although unbiased estimates of packet, bytes and flows usage can be formed for each sampling operation, for many applications it is crucial to know the inherent estimation error. Previous work in this area has been limited mainly to analyzing the estimator variance for particular methods, e.g., independent packet sampling. However, the variance is of limited use for more general sampling methods, where the estimate may not be well approximated by a Gaussian distribution.

This motivates our paper, in which we establish Chernoff bounds on the likelihood of estimation error in a general multistage combination of measurement sampling and aggregation. We derive the scale against which errors are measured, in terms of the constituent sampling and aggregation operations. In particular this enables us to obtain rigorous confidence intervals around any given estimate. We apply our method to a number of sampling schemes both in the literature and currently deployed, including sampling of packet sampled NetFlow records, Sample and Hold, and Flow Slicing. We obtain one particularly striking result in the first case: that for a range of parameterizations, packet sampling has no additional impact on the estimator confidence derived from our bound, beyond that already imposed by flow sampling.

REFERENCES

• 1: Noga Alon , Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating arbitrary subset sums with few probes, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065209]
• 2: Daniela Brauckhoff , Bernhard Tellenbach , Arno Wagner , Martin May , Anukool Lakhina, Impact of packet sampling on anomaly detection metrics, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177101]
• 3: Cisco. White paper - netflow services and applications. http://www.cisco.com/warp/public/cc/pd/iosw/ioft/neflct/tech/napps_wp.htm.
• 4: Kimberly C. Claffy , George C. Polyzos , Hans-Werner Braun, Application of sampling methodologies to network traffic characterization, ACM SIGCOMM Computer Communication Review, v.23 n.4, p.194-203, Oct. 1993
• 5: Edith Cohen , Nick Duffield , Haim Kaplan , Carsten Lund , Mikkel Thorup, Sketching unaggregated data streams for subpopulation-size queries, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265566]
• 6: Edith Cohen , Nadav Grossaug , Haim Kaplan, Processing top k queries from samples, Proceedings of the 2006 ACM CoNEXT conference, December 04-07, 2006, Lisboa, Portugal [doi>10.1145/1368436.1368446]
• 7: N. Duffield. (Ed.) A Framework for Packet Selection and Reporting. Internet Draft, June 2007. Work in Progress.
• 8: N. Duffield and M. Grossglauser. Trajectory Sampling with Unreliable Reporting. In INFOCOM, 2004.
• 9: Nick Duffield , Carsten Lund, Predicting resource usage and estimation accuracy in an IP flow measurement collection infrastructure, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948228]
• 10: Nick Duffield , Carsten Lund , Mikkel Thorup, Charging from sampled network usage, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505232]
• 11: 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
• 12: Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating flow distributions from sampled flow statistics, IEEE/ACM Transactions on Networking (TON), v.13 n.5, p.933-946, October 2005 [doi>10.1109/TNET.2005.852874]
• 13: N. Duffield, C. Lund, and M. Thorup. Optimal combination of sampled network measurements. In Proc. 5th ACM SIGCOMM Internet Measurement Workshop (IMC), page to appear, 2005.
• 14: N. Duffield, C. Lund, and M. Thorup. Sampling to estimate arbitrary subset sums. Technical Report cs.DS/0509026, Computing Research Repository (CoRR), 2005. http://arxiv.org/abs/cs.DS/0509026. Preliminary journal version of {11}.
• 15: N. G. Duffield , Matthias Grossglauser, Trajectory sampling for direct traffic observation, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.280-292, June 2001 [doi>10.1109/90.929851]
• 16: 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
• 17: 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
• 18: 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
• 19: D. Horvitz and D. Thompson. A generalization of sampling without replacement from a finite universe. J. Amer. Statist. Assoc., 47, 663--685 1952.
• 20: J. Jedwab, P. Phaal, and B. Pinna. Traffic estimation for the largest sources in a network, using packet sampling with limited storage. Technical Report HPL-92-3, HP Laboratories, Bristol, March 1992. url: http://www.hpl.hp.com/techreports/92/HPL-92-35.html.
• 21: Theodore Johnson , S. Muthukrishnan , Irina Rozenbaum, Sampling algorithms in a stream operator, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066159]
• 22: 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
• 23: R. R. Kompella and C. Estan. The power of slicing in internet flow measurement. In Proc. ACM Internet Measurement Conference, Berkeley, CA, October 2005.
• 24: Jianning Mai , Chen-Nee Chuah , Ashwin Sridharan , Tao Ye , Hui Zang, Is sampled data sufficient for anomaly detection?, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177102]
• 25: P. Phaal , S. Panchen , N. McKee, InMon Corporation's sFlow: A Method for Monitoring Traffic in Switched and Routed Networks, RFC Editor, 2001
• 26: J. Reeves and S. Panchen. Traffic monitoring with packet-based sampling for defense against security threats. In Proceedings of Passive and Active Measurement Workshop (PAM 2002), Fort Collins, CO, USA, March 25-26 2002.
• 27: Mario Szegedy, The DLT priority sampling is essentially optimal, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132539]
• 28: M. Szegedy and M. Thorup. On the variance of subset sum estimation. Technical Report cs.DS/0702029, Computing Research Repository (CoRR), 2007. http://arxiv.org/abs/cs.DS/0702029.
• 29: Mikkel Thorup, Confidence intervals for priority sampling, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 30: J. Turian and I. D. Melamed. Computational challenges in parsing by classification. In HLT-NAACL Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing, New York, NY, 2006.
• 31: T. Zseby. Deployment of sampling methods for sla validation with non-intrusive measurements. In Proceedings of Passive and Active Measurement Workshop (PAM 2002), Fort Collins, CO, USA, March 25-26 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

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

General Terms:
Measurement, Theory

Keywords:
confidence intervals, estimation, network measurement, sampling