EFFICIENT LOOKUP OF TCAM-LIKE RULES IN RAM

摘要

A method for classification includes extracting respective classification keys from a collection of data items and receiving a corpus of rules for matching to the classification keys. At least some of the rules include masked bits in addition to the unmasked bits. Rule patterns are extracted from the corpus, defining different, respective sequences of masked and unmasked bits to which one or more of the rules conform. The rule patterns are grouped into extended rule patterns, such that the respective set of unmasked bits in any rule pattern is a superset of the unmasked bits in the extended rule pattern into which it is grouped. Rule entries corresponding to the rules are computed using the extended rule patterns and are stored in a random access memory (RAM). The data items are classified by matching the respective classification keys to the rule entries in the RAM.

主权项

1. A method for classification, comprising:
extracting, in a decision logic pipeline, respective classification keys from a collection of data items, each classification key comprising a string of bits; receiving a corpus of rules for matching to the classification keys, each rule comprising a respective set of unmasked bits having corresponding bit values, and at least some of the rules comprising masked bits in addition to the unmasked bits; extracting rule patterns from the corpus, each rule pattern defining a different, respective sequence of masked and unmasked bits to which one or more of the rules conform; grouping the rule patterns into extended rule patterns, such that the respective set of unmasked bits in any rule pattern that is grouped into any given extended rule pattern is a superset of the unmasked bits in the given extended rule pattern; computing rule entries corresponding to the rules using the extended rule patterns into which the rule patterns are grouped, and storing the rule entries in a random access memory (RAM); and classifying the data items by matching the respective classification keys to the rule entries in the RAM.