摘要 |
A method and apparatus for generating a data structure for classifying an Internet Protocol packet. The data structure generation method may include creating a level-2 table with a plurality of bins for storing therein classification rules and using a first hashing data to derive a hash key 1 from a classification rule to point at, or to designate, an entry of a level-1 table, and populating the entry with a pointer to the level-2 table. The method may further comprise populating a bin in the level-2 table with the classification rule, which bin is pointed at, or designated, by a hash key 2 that is derived from the rule by using a second hashing data contained in the entry. The method may further include searching the data structure for a classification rule by driving from the packet a hash key 1 to point at, or for designating, an entry of level-1 table to obtain a pointer to a level-2 table and hashing data to generate a hash key 2 to point at, or for designating, a bin in the level-2 table, where a classification rule suitable for the packet may be found.
|