A new fast packet classification algorithm: RC-FST

A classifier is required to support fairly large database and wire-speed handling with the rapid growth of Internet. The existing classification algorithms (RFC, EGT-PC, HiCuts, HyperCuts) make better time-space tradeoffs, however, while the tradeoffs have been constantly improving, the time taken for a reasonable amount of memory is still too poor for practical deployment. This paper presents a new classification algorithm called RC-FST (rules cuttings-fast search trees) which splits the set of filter rules into several subsets by the hash-compression index table built based on the first 18-bit prefix of IP and constructs fast search trees for each subset. These search trees with smaller-sized filters can be more quickly constructed, optimized and updated, so the rate of search is correspondingly improved. Furthermore, some novel methods for the building of search trees and the partition of filters are described in this paper. RC-FST can provide an order of magnitude improvement over existing classification algorithms and be easily implemented in hardware at line speeds using a pipeline fashion.