Patent ID: 8472350

Claim:
A network element, to be coupled to a network, configured to receive packets from other network elements of the network, process those packets, and maintain an internet protocol (IP) address lookup table within a bank aware multi-bit trie (mtrie), the bank aware mtrie being a tree data structure utilized to store and maintain an IP address lookup table that associates destination addresses of packets with next hops of the packets, the network element comprising: a plurality of network interfaces configured to receive packets from other network elements of the network, each packet comprising a destination IP address; a processor coupled to the plurality of network interfaces and configured to: process the received packets, and determine a forwarding interface for one or more of the received packets; a memory coupled to the processor configured to store the bank aware mtrie; a memory control module coupled to the processor and coupled to the memory comprising a plurality or memory banks, the memory control module configured to: identify the plurality of memory banks present in the memory, identify one or more mtrie blocks in one or more mtrie levels in the bank aware mtrie, wherein each mtrie block is to be an array of mtrie nodes each associated with one or the one or more mtrie levels; store each of the one or more mtrie blocks in one of the plurality of memory banks, wherein all mtrie nodes for a given mtrie block are to be stored in the same memory bank only; store a stride length and a pointer to another mtrie block in one or more mtrie nodes; store a forwarding interface identifier in one or more mtrie nodes; and for each subsequent mtrie level: ensure that each of the mtrie blocks in that mtrie level is stored in one of the plurality of memory banks other than the memory bank that stores mtrie blocks of an immediately previous mtrie level.