New directions in traffic measurement and accounting

ABSTRACT

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow) which log periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of "heavy hitters" accounts for a large share of traffic. Our paper introduces a paradigm shift for measurement by concentrating only on large flows --- those above some threshold such as 0.1% of the link capacity.We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, which take a constant number of memory references per packet and use a small amount of memory. If $M$ is the available memory, we show analytically that the errors of our new algorithms are proportional to $1/M$; by contrast, the error of an algorithm based on classical sampling is proportional to $1/\sqrtM$, thus providing much less accuracy for the same amount of memory. We also describe further optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.

REFERENCES

• 1: J. Altman and K. Chu. A proposal for a flexible service plan that is attractive to users and internet service providers. In IEEE INFOCOM, April 2001.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: N. Brownlee, C. Mills, and G. Ruth. Traffic flow measurement: Architecture. RFC 2722, Oct. 1999.
• 4: N. G. Duffield , M. Grossglauser, Trajectory sampling for direct traffic observation, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.271-282, August 28-September 01, 2000, Stockholm, Sweden
• 5: 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]
• 6: C. Estan and G. Varghese. New directions in traffic measurement and accounting. Tech. Report 699, UCSD CSE, Feb. 2002.
• 7: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 8: W. Fang and L. Peterson. Inter-as traffic patterns and their implications. In IEEE GLOBECOM, Dec. 1999.
• 9: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.257-270, August 28-September 01, 2000, Stockholm, Sweden
• 10: W. Feng et al. Stochastic fair blue: A queue management algorithm for enforcing fairness. In IEEE INFOCOM, April 2001.
• 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: J. Huber. Design of an OC-192 flow monitoring chip. UCSD Class Project, March 2001.
• 13: Jeffrey K. MacKie-Mason , Hal R. Varian, Pricing the Internet, Public access to the Internet, MIT Press, Cambridge, MA, 1995
• 14: R, Mahajan et al. Controlling high bandwidth aggregates in the network. http://www.aciri.org/pushback/, July 2001.
• 15: D. Moore. http://www.caida.org/analysis/security/code-red/.
• 16: Cisco NetFlow http://www.cisco.com/warp/public/732/Tech/netflow.
• 17: R. Pan et al. Approximate fairness through differential dropping. Tech. report, ACIRI, 2001.
• 18: David A. Patterson , John Hennessy, Computer Organization and Design, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 19: S. Subramanya Sastry , Rastislav Bodík , James E. Smith, Rapid profiling via stratified sampling, Proceedings of the 28th annual international symposium on Computer architecture, p.278-289, June 30-July 04, 2001, Göteborg, Sweden
• 20: S. Shenker , D. Clark , D. Estrin , S. Herzog, Pricing in computer networks: reshaping the research agenda, ACM SIGCOMM Computer Communication Review, v.26 n.2, p.19-43, April 1996 [doi>10.1145/231699.231703]
• 21: Smitha , Inkoo Kim , A. L. Narasimha Reddy, Identifying Long-Term High-Bandwidth Flows at a Router, Proceedings of the 8th International Conference on High Performance Computing, p.361-371, December 17-20, 2001
• 22: K. Thomson, G. Miller, and R. Wilder. Wide-area traffic patterns and characteristics. In IEEE Network, December 1997.

INDEX TERMS

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

General Terms:
Algorithms, Measurement

Keywords:
identifying large flows, network traffic measurement, on-line algorithms, scalability, usage based accounting