Building a better NetFlow

ABSTRACT

Network operators need to determine the composition of the traffic mix on links when looking for dominant applications, users, or estimating traffic matrices. Cisco's NetFlow has evolved into a solution that satisfies this need by reporting flow records that summarize a sample of the traffic traversing the link. But sampled NetFlow has shortcomings that hinder the collection and analysis of traffic data. First, during flooding attacks router memory and network bandwidth consumed by flow records can increase beyond what is available; second, selecting the right static sampling rate is difficult because no single rate gives the right tradeoff of memory use versus accuracy for all traffic mixes; third, the heuristics routers use to decide when a flow is reported are a poor match to most applications that work with time bins; finally, it is impossible to estimate without bias the number of active flows for aggregates with non-TCP traffic.In this paper we propose Adaptive NetFlow, deployable through an update to router software, which addresses many shortcomings of NetFlow by dynamically adapting the sampling rate to achieve robustness without sacrificing accuracy. To enable counting of non-TCP flows, we propose an optional Flow Counting Extension that requires augmenting existing hardware at routers. Both our proposed solutions readily provide descriptions of the traffic of progressively smaller sizes. Transmitting these at progressively higher levels of reliability allows graceful degradation of the accuracy of traffic reports in response to network congestion on the reporting path.

REFERENCES

• 1: IPMON - packet trace analysis. http://ipmon.sprintlabs.com/packstat/packetoverview.php.
• 2: Personal conversation with Dave Plonka.
• 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: Andy Bierman and Juergen Quittek. Packet sampling (psamp). IETF working group.
• 5: N. Brownlee, C. Mills, and G. Ruth. Traffic flow measurement: Architecture. RFC 2722, October 1999.
• 6: Nevil Brownlee and Dave Plonka. IP flow information export (ipfix). IETF working group.
• 7: J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. In Journal of Computer and System Sciences, volume 18, April 1979.
• 8: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 9: Baek-Young Choi , Jaesung Park , Zhi-Li Zhang, Adaptive random sampling for load change detection, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 10: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 11: 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]
• 12: Nick Duffield , Carsten Lund , Mikkel Thorup, Properties and prediction of flow statistics from sampled packet streams, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637225]
• 13: 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]
• 14: Cristian Estan, Ken Keys, David Moore, and George Varghese. Building a better NetFlow: Technical report, 2004. http://www.caida.org/outreach/papers/2004/tr-2004-03/.
• 15: Cristian Estan , George Varghese , Mike Fisk, Bitmap algorithms for counting active flows on high speed links, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948225]
• 16: 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
• 17: P. Flajolet, On adaptive sampling, Computing, v.43 n.4, p.391-400, 1990 [doi>10.1007/BF02241657]
• 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: Ken Keys, David Moore, Ryan Koga, Edouard Lagache, Michael Tesch, and k claffy. The architecture of CoralReef: an Internet traffic monitoring software suite. In PAM2001. CAIDA, RIPE NCC, April 2001. http://www.caida.org/outreach/papers/2001/CoralArch/.
• 20: Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, ACM SIGCOMM Computer Communication Review, v.26 n.4, p.117-130, Oct. 1996
• 21: Keith McCloghrie and Marshall T. Rose. RFC 1213, March 1991.
• 22: David L. Mills. RFC 1305: Network time protocol (version 3) specification, implementation, March 1992.
• 23: D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N. Weaver. The spread of the sapphire/slammer worm. Technical report, 2003.
• 24: Cisco netflow. http://www.cisco.com/warp/public/732/Tech/netflow.
• 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: Peter Phaal, Sonia Panchen, and Neil McKee. RFC 3176: sFlow, September 2001.
• 27: Dave Plonka, FlowScan: A Network Traffic Flow Reporting and Visualization Tool, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 28: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 29: Sampled NetFlow. http://www.cisco.com/univercd/cc/td/doc/product/software/ios120/120newft/120limit/120s/120s11/12s sanf.htm.

INDEX TERMS

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

General Terms:
Algorithms, Measurement

Keywords:
data summarization, network monitoring, traffic measurement