Finding Non Equivalent Classifiers in Boolean Space to Reduce TCAM Usage
Abstract
Finding non equivalent classifiers in Boolean space
Finding Non Equivalent Classifiers in Boolean Space to Reduce TCAM Usage. Packet classification is one of the major challenges today in designing high-speed routers
and firewalls, as it involves sophisticated multi-dimensional searching.
However, TCAMs have limitations of high cost and high power consumption, which ignite the desire to reduce TCAM usage. The other is that there often exists redundancy among rules. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. Unlike previous schemes that compress classifiers by converting the original classifiers to semantically equivalent
classifiers, the BP technique innovatively finds semantically nonequivalent classifiers to achieve compression by performing block-based permutations on the rules represented in Boolean Space.
We have developed an efficient heuristic approach to find permutations for compression
and have designed its hardware implementation by using a field-programmable gate array (FPGA) to preprocess incoming packets.
Conclusion
ermutation (BP) to reduce the number of TCAM entries required to represent a classifier.
The BP technique significantly improves the compression rate under the circumstances where direct logic optimization cannot perform effectively.
The improvement is achieved by performing a series of permutations to change the distribution of rule elements in Boolean Space from sparse to dense, thus allowing more rules to be merged into each TCAM entry.
