Patent ID: 6691171
Filing Date: 2004-02-10
Classification: H04L

Abstract:
A method of searching for a longest prefix match for an address having a number of binary bits among a plurality of entries having different lengths of bits, the entries being associated with a trie having a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K1-bit trie match and at least one trie node for K2-bit trie match, wherein K1 and K2 are two different positive integers, each of the plurality of entries corresponding to one trie node, at least one trie node for L-bit trie match pointing to the first trie unit, and each trie node corresponding to a first, second, third, or fourth type of trie node, the method comprising;splitting the address into at least a first key and a second key, each key including a predetermined number of address bits; determining a first matching node among the first number of trie nodes based on the address bits in the first key; responsive to the first matching node corresponding to the first or second trie node type, selecting the entry corresponding to the first matching node as the longest prefix match for the address; responsive to the first matching node corresponding to the third or fourth trie node type, determining at least one second matching node in the first trie unit based upon the address bits in the second key.