Fast IP route lookup with 16/K and 16/Kc compressed data structures
An advanced data structure allows lookup based upon the most significant 16 bits and the following variable number of K bits of the IP destination address. This 16/K scheme requires less than 2 MB memory to store the whole routing tables of present day backbone routers. A 16/Kc version utilizes bitmaps to compress the table to less than 0.5 MB. For the 16/K data structure each route lookup requires at most 2 memory accesses while the 16/Kc requires at most 3 memory accesses. By configuring the processor properly and developing a few customized instructions to accelerate route lookup, one can achieve 85 million lookups per second (MLPS) in the typical case with the processor running at 200 MHz. Further, the lookup method can be implemented using pipelining techniques to perform three lookups for three incoming packets simultaneously. Using such techniques, 100 MLPS performance can be achieved.
1. 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.
2. The method of claim 1 , wherein the first set of values includes one and two.
3. The method of claim 2 , wherein the configuring steps are performed such that:
the information storage portion of the at least one entry stores one set of next hop and prefix length information when the total number of ones in the bitmap of the at least one entry is one;
the information storage portion of the at least one entry stores two sets of next hop and prefix length information when the total number of ones in the bitmap of the at least one entry is two; and
the information storage portion of the at least one entry stores 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 more than two.
4. A method according to claim 1 , wherein the configuring steps further include:
determining for each entry in a group of entries in the lookup tables, whether a value of the entry is different from a value of a previous entry,
when the entry value is different from the previous entry value, storing a first bit value in a corresponding place in a bitmap corresponding to that group of entries; and
when the entry value is the same as a previous entry value, storing a second bit value different from the first bit value in the corresponding place;
when a number of ones in the bitmap is in a first set of values, storing next hop and prefix length information in an entry storing the bitmap, the next hop and prefix length information corresponding to entries in the bitmap; and
when a number of ones in the bitmap is in a second set of values, storing an index to next hop and prefix length information corresponding to the bitmap information stored in a second data structure in the entry storing the bitmap.
5. The method of claim 1 , wherein K is less than a total number of bits of the IP destination address less a number of bits comprising the segment portion.
6. A method of routing packets including updating a data structure suitable for use in a route lookup system in a communications network, the method comprising:
routing packets using the data structure;
receiving an IP route having an IP address component, prefix length component and next hop component;
checking a group of entries in the data structure indicated by the prefix length component, the group having a size determined by a length of the IP address less the prefix length;
performing a longest match procedure to update the group of entries to have most specific next hop and prefix length information for the group of entries, wherein updating includes determining and storing a variable value K in the data structure, and further including storing next hop and prefix information for certain of the updated group of entries entirely within a 2 K block of entries in another data structure;
wherein checking includes
determining whether a given portion of an entry in the group of entries stores next hop and prefix information, or stores an index to a block of next hop and prefix information in the another data structure; and
obtaining prefix length and next hop information for the entry based on the determination result; and
routing packets using the updated data structure and the another data structure.