Acceleration of decision tree searching for IP traffic classification
Authors:
Open Access
- 6 November 2008
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 40-49
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.Keywords
Funding Information
- Division of Computer and Network Systems (CNS 0709001)
This publication has 17 references indexed in Scilit:
- DPICO2007
- A preliminary performance comparison of five machine learning algorithms for practical IP traffic flow classificationACM SIGCOMM Computer Communication Review, 2006
- Traffic classification on the flyACM SIGCOMM Computer Communication Review, 2006
- Survey and taxonomy of packet classification techniquesACM Computing Surveys, 2005
- BLINCACM SIGCOMM Computer Communication Review, 2005
- Cost-based modeling for fraud and intrusion detection: results from the JAM project2002
- Scalable packet classificationACM SIGCOMM Computer Communication Review, 2001
- Algorithms for packet classificationIEEE Network, 2001
- Designing and implementing a fast crossbar schedulerIEEE Micro, 1999
- High-speed policy-based packet forwarding using efficient multi-dimensional range matchingACM SIGCOMM Computer Communication Review, 1998