Information retrieval architecture for packet classification
An information retrieval architecture for performing a multi-dimensional search for a lookup value associated with a set of input values, the set of input values organized into one or more fields, the information retrieval architecture including a plurality of classification modules, each classification module storing the lookup values, each lookup value being associated with a set of input values; and a preprocessing module which receives a set of input values and selectively limits search of the plurality of classification modules to a subset of the classification modules.
1. An information retrieval architecture for performing a multi-dimensional search for a lookup value associated with a set of input values, the set of input values organized into one or more fields, the information retrieval architecture comprising:
a plurality of classification modules, each classification module storing the lookup values, each lookup value being associated with a set of input values; and
a preprocessing module which receives a set of input values and selectively limits search of the plurality of classification modules to a subset of the classification modules, the preprocessing module further comprising one or more lookup structures associating input values with a data representation identifying which of the plurality of classification modules to search to retrieve the lookup value associated with the set of input values, the lookup structure further comprising a hashing module that receives the input value and generates a plurality of hashed values from the input value, a first table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value, and a second table storing a plurality of data representations, where the first table is constructed so that the encoded values, obtained from the hashed values generated from an input value, encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value selects a data representation in the second table, the data representation identifying which of the plurality of classification modules to search to retrieve the lookup value.
2. The information retrieval architecture of claim 1 wherein the preprocessing module is arranged to default to a data representation identifying that all of the plurality of classification modules are to be searched for any lookup value associated with input values not found in the lookup structures of the preprocessing module.
3. The information retrieval architecture of claim 2 wherein the preprocessing module uses a single lookup structure for different fields of input values so as to take advantage of a number of unique input values for the different fields of input values.
4. The information retrieval architecture of claim 2 wherein the preprocessing module stores data representations in the lookup structures based on which are more likely to be accessed.
5. The information retrieval architecture of claim 1 wherein the lookup structure is a constant query-time lookup structure.
6. The information retrieval architecture of claim 1 wherein lookup values stored in the classification modules are arranged so as to minimize parallel searches through the plurality of classification modules as selectively limited by the preprocessing module.
7. The information retrieval architecture of claim 1 wherein if an update is made to lookup values stored in the classification modules, an update is conducted to the lookup structure in the preprocessing module.
8. The information retrieval architecture of claim 1 wherein the data representation identifying which of the plurality of classification modules to search to retrieve the lookup value associated with the input value is a bitmap where each bit represents a different classification module.
9. The information retrieval architecture of claim 1 wherein each bit in the data representation is used in identifying which of the plurality of classification modules to search.
10. The information retrieval architecture of claim 1 wherein each lookup structure in the preprocessing module is used for a different field of input values and wherein the data representations from each lookup structure are combined to generate a final data representation identifying which of the plurality of classification modules to search to retrieve the lookup value associated all of the input values in the different fields.
11. The information retrieval architecture of claim 1 wherein the data representation identifying which of the plurality of classification modules to search to retrieve the lookup value associated with the input value is a bitmap where each bit represents a different classification module and wherein the data representations are combined by intersecting the bitmaps.
12. The information retrieval architecture of claim 1 wherein the input values are information in a packet header and wherein the lookup values are packet classification rule identifiers.