A generic language for application-specific flow sampling

ABSTRACT

Flow records gathered by routers provide valuable coarse-granularity traffic information for several measurement-related network applications. However, due to high volumes of traffic, flow records need to be sampled before they are gathered. Current techniques for producing sampled flow records are either focused on selecting flows from which statistical estimates of traffic volume can be inferred, or have simplistic models for applications. Such sampled flow records are not suitable for many applications with more specific needs, such as ones that make decisions across flows

As a first step towards tailoring the sampling algorithm to an application's needs, we design a generic language in which any particular application can express the classes of traffic of its interest. Our evaluation investigates the expressive power of our language, and whether flow records have sufficient information to enable sampling of records of relevance to applications. We use templates written in our custom language to instrument sampling tailored to three different applications--BLINC, Snort, and Bro. Our study, based on month-long datasets gathered at two different network locations, shows that by learning local traffic characteristics we can sample relevant flow records near-optimally with low false negatives in diverse applications

REFERENCES

• 1: Flexible Netflow. http://www.cisco.com/en/US/products/ps6965/products_ios_protocol_option_home.html.
• 2: Netflow input filters. http://www.cisco.com/en/US/products/sw/iosswrel/ps5207/products_feature_guide09186a00801d3108.html.
• 3: Paul Barford , Jeffery Kline , David Plonka , Amos Ron, A signal analysis of network traffic anomalies, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637210]
• 4: C. Cranor, T. Johnson, O. Spatscheck, and V. Shkapenyuk. Gigascope: A stream database for network applications. In IMC, 2003.
• 5: 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]
• 6: Don Carney , Uǧur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Greg Seidman , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Monitoring streams: a new class of data management applications, Proceedings of the 28th international conference on Very Large Data Bases, p.215-226, August 20-23, 2002, Hong Kong, China
• 7: N. Duffield. Sampling for passive Internet measurement: A review. Statistical Science, 19(3):472¿498, 2004.
• 8: N. Duffield. A framework for packet selection and reporting, 2007. IETF draft: psamp-framework-11.
• 9: 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]
• 10: 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]
• 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: N. Duffield, C. Lund, and M. Thorup. Learn more, sample less: Control of volume and variance in network measurement. IEEE Transactions on Information Theory, 51:1756--1775, 2005.
• 13: N. Duffield, C. Lund, and M. Thorup. Optimal combination of sampled network measurements. In IMC, 2005.
• 14: Cristian Estan , Stefan Savage , George Varghese, Automatically inferring patterns of resource consumption in network traffic, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863972]
• 15: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 16: Juniper Networks. Using compound signatures to protect against complex attacks, 2004.
• 17: Thomas Karagiannis , Konstantina Papagiannaki , Michalis Faloutsos, BLINC: multilevel traffic classification in the dark, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 18: 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
• 19: Ramana Rao Kompella , Cristian Estan, The power of slicing in internet flow measurement, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.9-9, October 19-21, 2005, Berkeley, CA
• 20: Balachander Krishnamurthy , Jia Wang, Traffic classification for application specific peering, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637229]
• 21: S. Kundu, S. Pal, K. Basu, and S. Das. Fast classification and estimation of Internet traffic flows. In PAM, 2007.
• 22: Anukool Lakhina , Mark Crovella , Christiphe Diot, Characterization of network-wide anomalies in traffic flows, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028813]
• 23: 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]
• 24: Andrew W. Moore , Denis Zuev, Internet traffic classification using bayesian analysis techniques, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 25: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7 ]
• 26: J. Reves and S. Panchen. Traffic monitoring with packet-based sampling for defense against security threats. InMon Technology Whitepaper, 2002.
• 27: Matthew Roughan , Subhabrata Sen , Oliver Spatscheck , Nick Duffield, Class-of-service mapping for QoS: a statistical signature-based approach to IP traffic classification, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028805]
• 28: Snort. http://www.snort.org.
• 29: Carol Taylor , Jim Alves-Foss, NATE: Network Analysis of Anomalous Traffic Events, a low-cost approach, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico [doi>10.1145/508171.508186]
• 30: Vyas Sekar , Nick Duffield , Oliver Spatscheck , Jacobus van der Merwe , Hui Zhang, LADS: large-scale automated DDOS detection system, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.16-16, May 30-June 03, 2006, Boston, MA
• 31: Nigel Williams , Sebastian Zander , Grenville Armitage, A preliminary performance comparison of five machine learning algorithms for practical IP traffic flow classification, ACM SIGCOMM Computer Communication Review, v.36 n.5, October 2006 [doi>10.1145/1163593.1163596]
• 32: Lihua Yuan , Chen-Nee Chuah , Prasant Mohapatra, ProgME: towards programmable network measurement, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 33: Sebastian Zander , Thuy Nguyen , Grenville Armitage, Automated Traffic Classification and Application Identification using Machine Learning, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.250-257, November 15-17, 2005 [doi>10.1109/LCN.2005.35]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Algorithms, Experimentation, Languages, Measurement

Keywords:
application-specific traffic monitoring, flow sampling, language design