Fast monitoring of traffic subpopulations

ABSTRACT

Network accounting, forensics, security, and performance monitoring applications often need to examine detailed traces from subsets of flows ("subpopulations"), where the application desires flexibility in specifying the subpopulation (e.g., to detect a portscan, the application must observe many packets between a source and a destination with one packet to each port). However, the dynamism and volume of network traffic on many high-speed links necessitates traffic sampling, which adversely affects subpopulation monitoring: because many subpopulations of interest to operators are low-volume flows, conventional sampling schemes (e.g., uniform random sampling) miss much of the subpopulation's traffic. Today's routers and network devices provide scant support for monitoring specific traffic subpopulations.

This paper presents the design, implementation, and evaluation of FlexSample, a traffic monitoring engine that dynamically extracts traffic from subpopulations that operators define using conditions on packet header fields. FlexSample uses a fast, flexible counter array to provide rough estimates of packets' membership in respective subpopulations. Based on these coarse estimates, FlexSample then makes per-packet sampling decisions to sample proportionately from each subpopulation (as specified by a network operator), subject to an overall sampling constraint. We apply FlexSample to extract subpopulations such as port scans and traffic to high-degree nodes and find that it is able to capture significantly more packets from these subpopulations than conventional approaches.

REFERENCES

• 1: Idle-scanning and Related IPID Games. http://nmap.org/idlescan.html.
• 2: Original posting describing FTP bounce scan. http://nmap.org/hobbit.ftpbounce.txt.
• 3: Arbor Networks. http://www.arbornetworks.com.
• 4: 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]
• 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: G. Cantieni, G. Iannaccone, P. Thiran, C. Barakat, and C. Diot. Reformulating the monitor placement problem: Optimal network-wide sampling. Intel Research Technical Report, Feb. 2006.
• 7: B.-Y. Choi and S. Bhattacharyya. On the Accuracy and Overhead of Cisco Sampled NetFlow. In Proceedings of ACM SIGMETRICS Workshop on Large Scale Network Inference (LSNI), June 2005.
• 8: Kimberly C. Claffy , George C. Polyzos , Hans-Werner Braun, Application of sampling methodologies to network traffic characterization, Conference proceedings on Communications architectures, protocols and applications, p.194-203, September 13-17, 1993, San Francisco, California, United States
• 9: N. Duffield. A Framework for Packet Selection and Reporting. IETF Internet Draft draft-ietf-psamp-framework-12.txt, June 2007.
• 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, 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]
• 12: 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]
• 13: N. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring Link Loss Using Striped Unicast Probes. In Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001.
• 14: 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
• 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: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 17: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 18: 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]
• 19: Y. Huang and J. Pullen. Countering Denial of Service Attacks using Congestion Triggered Packet Sampling and Filtering. In Proceedings of International Conference on Computer Communications and Networks, pages 490--494, 2001.
• 20: InMon sFlow. http://www.inmon.com/technology.
• 21: Juniper traffic sampling and forwarding overview. http://www. juniper.net/techpubs/software/junos/junos71/swconfig71-policy/html/sampling-overview.html.
• 22: 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
• 23: 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
• 24: 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
• 25: 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
• 26: A. Kumar and J. Xu. Sketch Guided Sampling -- Using On-Line Estimates of Flow Size for Adaptive Data Collection. In Proc. IEEE INFOCOM, Barcelona, Spain, Mar. 2006.
• 27: 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
• 28: Harsha V. Madhyastha , Balachander Krishnamurthy, A generic language for application-specific flow sampling, ACM SIGCOMM Computer Communication Review, v.38 n.2, April 2008 [doi>10.1145/1355734.1355736]
• 29: 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]
• 30: G. Maier, R. Sommer, H. Dreger, A. Feldmann, V. Paxson, and F. Schneider. Enriching Network Security Analysis with Time Travel. In Proc. ACM SIGCOMM, Seattle, WA, Aug. 2008.
• 31: Cisco NetFlow. http://www.cisco.com/en/US/products/ps6601/products_ios_protocol_group_home.html.
• 32: Anirudh Ramachandran , Nick Feamster, Understanding the network-level behavior of spammers, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 33: H. Ringberg, A. Soule, and M. Caeser. Behavior Of Bots In Traffic Traces. Technical report, Princeton University, 2008. Number forthcoming.
• 34: L. A. Sanchez, W. C. Milliken, A. C. Snoeren, F. Tchakountio, C. E. Jones, S. T. Kent, C. Partridge, and W. T. Strayer. Hardware Support for a Hash-Based IP Traceback. In Proceedings of DARPA Information Survivability Conference and Exposition (DISCEX), 2001.
• 35: Vyas Sekar , Michael K. Reiter , Walter Willinger , Hui Zhang , Ramana Rao Kompella , David G. Andersen, CSAMP: a system for network-wide flow monitoring, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.233-246, April 16-18, 2008, San Francisco, California
• 36: Haoyu Song , Sarang Dharmapurikar , Jonathan Turner , John Lockwood, Fast hash table lookup using extended bloom filter: an aid to network processing, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 37: George Varghese, Network Algorithmics,: An Interdisciplinary Approach to Designing Fast Networked Devices (The Morgan Kaufmann Series in Networking), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 38: F. Vaskovich. Nmap stealth port scanner. http://www.insecure.org/nmap/index.html, 2002.
• 39: Average spam message size at record low. http://www.virusbtn.com/news/2008/04_03a.xml?rss.
• 40: Report: 95 percent of all email has that spammy smell. http://arstechnica.com/news.ars/post/20071212-report-95-percent-of-all-e-mail-has-that-spammy-smell.html.
• 41: Kuai Xu , Zhi-Li Zhang , Supratik Bhattacharyya, Profiling internet backbone traffic: behavior models and applications, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 42: Bo Yang , Ramesh Karri , David A. McGrew, Divide-and-concatenate: an architecture level optimization technique for universal hash functions, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996733]
• 43: 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
• 44: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 45: Yin Zhang , Sumeet Singh , Subhabrata Sen , Nick Duffield , Carsten Lund, Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028802]
• 46: T. Zseby, M. Molina, N. Duffield, S. Niccolini, and F. Raspall. Sampling and Filtering Techniques for IP Packet Selection, Internet-Draft, draft-ietf-psamp-sample-tech-07.txt, Work in Progress, 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Algorithms, Design, Measurement, Security

Keywords:
counters, flexsample, sampling, traffic statistics, traffic subpopulations