Patent ID: 7274697

Claim:
A method of routing a packet by performing a route lookup based on a received IP destination address, the method comprising: configuring a first lookup table having at least one entry, each of the at least one entry having a bitmap portion and an information storage portion; configuring a second lookup table having at least one entry, each entry in the at least one entry storing next hop and prefix length information; configuring a third lookup table having at least one entry, the at least one entry including a pointer portion and a variable value K; and routing a packet having the received IP destination address using the first, second and third lookup tables, wherein the configuring steps are performed such that each at least one entry of the third lookup table is indexable by a segment portion of the IP destination address, and wherein when there is a route having a prefix matching the index of the at least one entry and a prefix length greater than a predetermined value, the pointer portion includes a pointer that is combined with K bits of the IP destination address following the segment portion to determine an index for the at least one entry in the first lookup table, wherein bits within the bitmap of the at least one entry are indexable by a second portion of the IP destination address, the information storage portion of each of the at least one entry stores next hop and prefix information when the total number of ones in the bitmap of the at least one entry is one of a given set of values, and the information storage portion of each of the at least one entry information pointing to an entry in the second lookup table when the total number of ones in the bitmap of the at least one entry is not one of the given set of values.