Patent ID: 7111071

Claim:
A network router comprising: an input switch; an output switch; a controller, the controller comprising a plurality of look-up engines, the look-up engines receiving look-up requests in a round robin fashion; and a memory for storing data for access by a longest prefix match program, the program comprising: a data structure stored in the memory, the data structure including information used by the longest prefix match program and including: at least one first table at a root, the at least one first table comprising entries indexed according to a first portion of an Internet Protocol (IP) address span and maintaining links to a first set of nodes containing a first set of trie tables corresponding to less significant portions of the IP address span, the entries of the at least one first table not including links to route entries, each table of the first set of trie tables configured to be indexed according to address bits in the corresponding IP address span of that trie table to locate an indexed trie entry, the indexed trie entry including a corresponding route pointer and a corresponding trie pointer; and at least one second table at the root, the at least one second root table comprising entries indexed according to a second portion of the IP address span, each entry of the at least one second root table including a corresponding route pointer and a corresponding trie pointer, at least some of the entries having corresponding trie pointers pointing to entries in a second set of trie tables at a second set of nodes; computer instructions that, when executed, cause the look-up engines to traverse in parallel the first table at the root and its linked first set of trie tables, and the second table at the root and its linked second set of trie tables.