Bitmap algorithms for counting active flows on high-speed links

ABSTRACT

This paper presents a family of bitmap algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high-speed link. Such counting can be used to detect DoS attacks and port scans and to solve measurement problems. Counting is especially hard when processing must be done within a packet arrival time (8 ns at OC-768 speeds) and, hence, may perform only a small number of accesses to limited, fast memory. A naive solution that maintains a hash table requires several megabytes because the number of flows can be above a million. By contrast, our new probabilistic algorithms use little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we replaced the port-scan detection component of the popular intrusion detection system Snort with one of our new algorithms. This reduced memory usage on a ten minute trace from 50 to 5.6 MB while maintaining a 99.77% probability of alarming on a scan within 6 s of when the large-memory algorithm would. The best known prior algorithm (probabilistic counting) takes four times more memory on port scan detection and eight times more on a measurement application. This is possible because our algorithms can be customized to take advantage of special features such as a large number of instances that have very small counts or prior knowledge of the likely range of the count.

REFERENCES

• 1: [1] Cisco Offers Wire-Speed Intrusion Detection. 2000 [Online]. Available: http://www.nwfusion.com/reviews/2000/1218rev2.html
• 2: 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]
• 3: [3] C. Estan, The bmpcount library of flow counting algorithms. [Online]. Available: http://ial.ucsd.edu/bitmaps/
• 4: Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: 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]
• 6: [6] C. Estan, G. Varghese, and M. Fisk, Bitmap algorithms for counting active flows on high speed links Comput. Sci. Eng. Dept., Univ. California, San Diego, Tech. Rep. 0738, 2003.
• 7: [7] W. Fang and L. Peterson, "Inter-as traffic patterns and their implications," in Proc. IEEE GLOBECOM, Dec. 1999, vol. 3, pp. 1859-1868.
• 8: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 9: [9] Fyodor, "Remote OS detection via TCP/IP stack fingerprinting," Phrack, vol. 54, Dec. 1998.
• 10: 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
• 11: [11] K. Keys, D. Moore, R. Koga, E. Lagache, M. Tesch, and K. Claffy, "The architecture of Coralreef: An internet traffic monitoring software suite," presented at the Workshop on Passive and Active Measurements (PAM2001), Amsterdam, The Netherlands, Apr. 2001.
• 12: [12] A. Kumar, J. Xu, J. Wang, O. Spatschek, and L. Li, "Space-code Bloom filter for efficient per-flow traffic measurement," in Proc. IEEE INFOCOM , Mar. 2004, pp. 1762-1773.
• 13: Ratul Mahajan , Steven M. Bellovin , Sally Floyd , John Ioannidis , Vern Paxson , Scott Shenker, Controlling high bandwidth aggregates in the network, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.62-73, July 2002 [doi>10.1145/571697.571724]
• 14: [14] M. Durand and P. Flajolet, "Loglog counting of large cardinalities," presented at the Eur. Symp. Algorithms (ESA), Budapest, Hungary, Sep. 2003.
• 15: [15] CAIDA analysis of Code Red. 2001 [Online]. Available: http://www. caida.org/analysis/security/code-red/
• 16: [16] Cisco Netflow. [Online]. Available: http://www.cisco.com/warp/ public/732/Tech/netflow
• 17: [17] LFAP: Lightweight Flow Accounting Protocol, Riverstone Networks. [Online]. Available: http://www.riverstonenet.com/technology/ac-counting_for_profitability.shtml
• 18: 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
• 19: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 20: Stuart Staniford , James A. Hoagland , Joseph M. McAlerney, Practical automated detection of stealthy portscans, Journal of Computer Security, v.10 n.1-2, p.105-136, 2002
• 21: [21] S. Venkataraman, D. Song, P. B. Gibbons, and A. Blum, "New streaming algorithms for fast detection of superspreaders," presented at the Network and Distributed Systems Symp. (NDSS), San Diego, CA, Feb. 2005.
• 22: Kyu-Young Whang , Brad T. Vander-Zanden , Howard M. Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems (TODS), v.15 n.2, p.208-229, June 1990 [doi>10.1145/78922.78925]

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Management, Performance

Keywords:
counting distinct elements, traffic measurements