Patent ID: 7325059

Claim:
A method for an intermediate network node to efficiently lookup routing information associated with a network address, the method comprising: selecting a lookup table from a set of one or more lookup tables in the intermediate network node, each lookup table being associated with a different range of subnet mask lengths, wherein the selected lookup table is associated with the largest subnet mask lengths not yet searched; searching the selected lookup table based on the value of the network address using a bounded number of dependent lookups to locate a memory location of the network address's routing information; if the network address is found in the selected lookup table, providing the memory location of the network address's routing information from the selected lookup table; if the network address is not found in the selected lookup table, then repeating the steps of selecting and searching the selected lookup table, until the memory location of the network address's routing information is found or until all the lookup tables have been searched; if the network address is found in any of the lookup tables, providing the memory location of the network address's routing information from one of the lookup tables; and if the network address is not found in any of the lookup tables, searching an MTRIE for the memory location of the network address's routing information and providing the memory location of the network address's routing information from the MTRIE.