Acceleration of decision tree searching for IP traffic classification

ABSTRACT

Traffic classification remains a hot research problem, especially when facing new traffic trends and new hardware architectures. We propose a classification tree search method called explicit range search, motivated by the characteristics of machine learning based classification approaches. Our method differs from previously known algorithms such as HiCut and HyperCut in how to cut the ranges within a dimension and how to search within the ranges. By storing explicit marks and performing hardware supported parallel comparison, the explicit range search can reduce the worst-case number of memory accesses from 26 to 5 on a number of realistic rule sets generated from a well-known machine learning algorithm (C4.5). We also describe in this paper the proposed design based on FPGA devices.

REFERENCES

• 1: F. Baboescu, S. Singh, and G. Varghese. Packet classification for core routers: Is there an alternative to cams? In INFOCOM, 2003.
• 2: Florin Baboescu , George Varghese, Scalable packet classification, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.199-210, October 2001
• 3: Laurent Bernaille , Renata Teixeira , Ismael Akodkenou , Augustin Soule , Kave Salamatian, Traffic classification on the fly, ACM SIGCOMM Computer Communication Review, v.36 n.2, April 2006 [doi>10.1145/1129582.1129589]
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: V. Srinivasan , G. Varghese , S. Suri , M. Waldvogel, Fast and scalable layer four switching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.191-202, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 6: Pankaj Gupta , Nick McKeown, Designing and Implementing a Fast Crossbar Scheduler, IEEE Micro, v.19 n.1, p.20-28, January 1999 [doi>10.1109/40.748793]
• 7: P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Proc. Hot Interconnects, 1999.
• 8: P. Gupta and N. McKeown. Algorithms for packet classification. IEEE Network, March 2001.
• 9: Christopher L. Hayes , Yan Luo, DPICO: a high speed deep packet inspection engine using compact finite automata, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323579]
• 10: Thomas Karagiannis , Andre Broido , Michalis Faloutsos , Kc claffy, Transport layer identification of P2P traffic, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028804]
• 11: Thomas Karagiannis , Konstantina Papagiannaki , Michalis Faloutsos, BLINC: multilevel traffic classification in the dark, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 12: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.203-214, Oct. 1998
• 13: T. T. T. Nguyen and G. Armitage. Training on multiple sub-flows to optimise the use of machine learning classifiers in real-world ip networks. In Proc. 31th Conference on Local Computer Networks, Tampa, FL, November 2006.
• 14: T. T. T. Nguyen and G. Armitage. A survey of techniques for internet traffic classification using machine learning. IEEE Communications Surveys and Tutorials, 2008.
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 16: Sumeet Singh , Florin Baboescu , George Varghese , Jia Wang, Packet classification using multidimensional cutting, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863980]
• 17: Snort. http://www.snort.org/, 2003.
• 18: H. Song. Multidimensional cuttings (hypercuts), http://www.arl.wustl.edu/hs1/project/hypercuts.htm.
• 19: V. Srinivasan , S. Suri , G. Varghese, Packet classification using tuple space search, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.135-146, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 20: Salvatore J. Stolfo, Wei Fan, Wenke Lee, Andreas Prodromidis, and Philip K. Chan. Cost-based modeling for fraud and intrusion detection: results fromthe jam project. In DARPA Information Survivability Conference and Exposition, volume 2, pages 130--144, http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html, 2000.
• 21: David E. Taylor, Survey and taxonomy of packet classification techniques, ACM Computing Surveys (CSUR), v.37 n.3, p.238-275, September 2005 [doi>10.1145/1108956.1108958]
• 22: 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]
• 23: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, decision tree, machine learning, traffic classification