Patent ID: 8200686

Claim:
A method for performing a lookup in a hierarchy of nodes to obtain routing information for a packet, comprising: receiving an input key from a header in the packet; using a plurality of state machines comprising at least one processor and a plurality of memory banks to perform a plurality of lookups in parallel; using leading bits from the input key to index an entry in a first level of the hierarchy of nodes, wherein the entry contains either a value or a plurality of fields that specify: a skip-count indicating a number of bits to skip in the key, a skip-value to match against the skipped bits, a pointer to a next node in the hierarchy, and a number of index bits which are used to index the next node; and repeating the following operations until a value is returned or an error is indicated, when the entry includes a value, returning the value to provide the routing information for the packet, and when the entry includes a plurality of fields, skipping the next skip-count bits in the input key, comparing the skipped bits against the skip-value, when the skipped bits do not match the skip-value, indicating a lookup failure, and otherwise, using the next number of index bits from the input key and the pointer to index a next entry in the hierarchy of nodes.