A resource-minimalist flow size histogram estimator

ABSTRACT

The histogram of network flow sizes is an important yet difficult metric to estimate in network monitoring. It is important because it characterizes traffic compositions and is a crucial component of anomaly detection methods. It is difficult to estimate because of its high memory and computational requirements. Existing algorithms compute fine grained estimates for each flow size, i.e. 1, 2,... up to the maximum number observed over a finite time interval. Our approach instead relies on the insight that, while many applications require fine grained estimates of small flow sizes, i.e. {1,2,...,k} with a small k, network operators are often only interested in coarse grained estimates of larger flow sizes. Thus, we propose an estimator that outputs a binned histogram of size distributions. Our estimator computes this histogram in O(k³ + log W) operations, where W is the largest flow size of interest to the network operator, while requiring only a few bits of memory per measured flow. This translates into more than 4 fold memory savings and an exponential speedup in the estimator as compared to previous works, greatly increasing the possibility of performing on-line estimation inside a router.

REFERENCES

• 1: Chadi Barakat, Patrick Thiran, Gianluca Iannaccone, Christophe Diot, and Philippe Owezarski. Modeling internet backbone traffic at the flow level. IEEE Transactions on Signal Processing, 51(8):2111--2124, August 2003.
• 2: Graham Cormode , S. Muthukrishnan , Irina Rozenbaum, Summarizing and mining inverse distributions on data streams via dynamic inverse sampling, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: 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]
• 4: Abhishek Kumar , Minho Sung , Jun (Jim) Xu , Ellen W. Zegura, A data streaming algorithm for estimating subpopulation flow size distribution, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 5: Abhishek Kumar , Minho Sung , Jun (Jim) Xu , Jia Wang, Data streaming algorithms for efficient and accurate estimation of flow size distribution, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 6: Yi Lu , Andrea Montanari , Balaji Prabhakar , Sarang Dharmapurikar , Abdul Kabbani, Counter braids: a novel counter architecture for per-flow measurement, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 7: Robert Morris, Counting large numbers of events in small registers, Communications of the ACM, v.21 n.10, p.840-842, Oct. 1978 [doi>10.1145/359619.359627]
• 8: Bruno Ribeiro , Don Towsley , Tao Ye , Jean C. Bolot, Fisher information of sampled packets: an application to flow size estimation, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177083]

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
      Subjects: Nonparametric statistics

General Terms:
Design, Measurement

Keywords:
data stream algorithms, flow size histogram, monitoring systems, sampling methods