Method and apparatus for packet switching

摘要

A method for performing packet lookups is provided. Packets (which each have a body and a header) are received and parsed to parsing headers. A hash function is applied to each header, and each hashed header is compared with a plurality of binary rules stored within a primary table, where each binary rule is a binary version of at least one ternary rule from a first set of ternary rules. For each match failure with the plurality of rules, a secondary table is searched using the header associated with each match failure, where the secondary table includes a second set of ternary rules.

主权项

1. An apparatus comprising:
a lookup memory having a primary table and a secondary table, wherein the secondary table includes a first set of ternary rules, and wherein the primary includes a set of binary rules, and wherein each binary rule is a binary version of at least one ternary rule from the first set of ternary rules; and a search engine that is coupled to the lookup memory, wherein the search engine includes:
an controller that is configured to receive data words; andhash logic that is coupled to lookup memory and the controller, wherein the hash logic is configured to perform a binary search of the primary table to determine whether each data word matches at least one of the binary rules, and wherein, if there is a failed match by hash logic and primary table, the search engine is configured to perform a ternary search of the secondary table to determine whether the data word associated with the failed match matches at least one of the ternary rules from a second set of ternary rules.