Patent ID: 7515588

Claim:
A method, comprising: receiving a packet at a network device, the packet including a destination address; indexing into a table using a portion of the destination address to locate an entry in the table associated with the portion of the destination address; deriving a pool index associated with the portion of the destination address to identify a pool of trie blocks from among a plurality of pools of trie blocks located in a same memory unit, wherein each trie block comprises a plurality of trie entries, each trie entry comprising a next-hop pointer and a next-trie pointer to reference trie entries located in the pool of trie blocks including the next-hop pointer and the next-trie pointer; navigating the entry and the pool of trie blocks that is identified to find a next-hop for the packet; examining the plurality of pools of trie blocks to find an under-utilized pool; splitting the under-utilized pool into a first pool of trie blocks and a second pool of trie blocks; and adding a second entry to the table indexed by a portion of a second destination address, a second pool index associated with the portion of the second destination address to correspond to the second pool of trie blocks.