Three Different Designs for Packet Classification

Abstract: If we analyze real life filter sets (classifiers) and also packet classification requirements, it seems that distribution of rule scope is non-uniform and in some sub spaces is denser inside the total space of classifiers. These features guided us to add "cut point heuristic " to HiCuts, one of the most efficient algorithms and resulted in two new optimized designs for HiCuts, named B-HiCuts and Hist. Also one of the hardware based and fast solution for classification is use of TCAM memory to implement classifiers, but TCAMs are expensive and are not efficient for range fields. The third approach in this paper introduces a hybrid scheme to do a part of search on prefix fields in TCAM and then to check other fields, the search process will be traversed to RAM section in the second level. Synthetic classifiers are made by ClassBench and used to simulate and evaluate performance of proposed designs. The most specifications of proposed methods are balancing of decision trees and reducing the consumed memory for B-HiCuts and Hist and also solving range to prefix conversion and multi match classification problems in the last proposed design