Patent ID: 7706302

Claim:
A routing device comprising: a port for receiving a protocol data unit (PDU); a routing table for storing a plurality of routes in a multi-way trie having a plurality of nodes, the routing table comprising: a first route memory for caching a first set of the plurality of nodes; and a second route memory for caching a second set of the plurality of nodes that is mutually exclusive from the first set of the plurality of nodes; a routing engine in a router for searching the routing table for one of the plurality of routes associated with the PDU; and a route manager in a router for relocating one or more nodes of the second set from the second route memory to the first route memory, such that a utilization count for each of the nodes of the first route memory is higher than each of the nodes of the second route memory and such that said route manager generates a utilization count for one or more nodes assigned to the first route memory and for one or more nodes assigned to the second route memory and compares the utilization count for the one or more nodes assigned to the first route memory with the utilization count for the one or more nodes assigned to the second route memory and if the utilization count of at least one of the one or more nodes in the second route memory exceeds the utilization count of at least one of the one or more nodes in the first route memory, then reassigning the at least one of the one or more nodes in the second route memory to the first route memory.