Fast IP route lookup with configurable processor and compressed routing table

• US 6,888,838 B1
• Filed: 02/09/2001
• Issued: 05/03/2005
• Est. Priority Date: 11/16/2000
• Status: Active Grant

• Current Assignee: Tensilica Incorporated
• Original Assignee: Tensilica Incorporated
• Inventors: Ji, Hongbin, Srinivasan, Rangarajan
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): SHAH, CHIRAG G
• Application Number:
  US09/780,895
• Time in Patent Office: 1,544 Days
• Field of Search: 370389-392, 370/428, 370/472, 370/474, 370/412, 370/429, 370400-401, 709/245, 709/238
• US Class Current: 370/401
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A novel compression method uses bitmaps to reduce the memory storage requirement of routing table information to about 3 MB. The data structure can be used for both route lookup and update. It does not require a separate data structure to be used for route update. A fast route lookup method is also disclosed. An efficient update method supports incremental route update. Through configuring a processor properly and developing a few customized instructions specifically for route lookup, the system can achieve more than 10 million lookups per second (MLPS) at 200 MHz. Using a configurable processor for route lookup/update provides more flexibility and extensibility which supports different data structures and lookup/update methods to meet application specific needs. The data structure and lookup method can be implemented in pure hardware in a pipelined fashion to achieve approximately 100 MLPS.

Claims

1. A computer-readable storage medium configured to store a data structure comprising:

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; and

a second lookup table having at least one entry, each entry in the at least one entry storing next hop and prefix length information;

wherein;

the at least one entry in the first lookup table is indexable by a first portion of an IP destination address, and 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 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;

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 not one of the given set of values;

the first set of values includes one and two;

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.

2. A method of storing information in the data structure of claim 1, the method comprising:

determining for each entry in a group of entries in a data structure, 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.

3. A method of looking up a route and processing a data packet in a communications network, the method comprising:

receiving a data packet from the communications network;

extracting an IP address from a header of the packet;

obtaining a segment and an offset of the IP address;

using the segment to index an entry of the first lookup table;

computing a total number of ones in an bitmap of the indexed entry;

when the total number of ones is in a given set of values, obtaining next hop and prefix information from the information storage portion of the entry;

when the total number of ones is not in the given set of values,

using the offset to index a bit in the bitmap of the indexed entry,

determining a number of ones from the beginning of the bitmap to the indexed bit,

using the number of ones to the indexed bit to index an entry in a second lookup table,

checking a marker bit of the entry in the second lookup table,

if the marker bit is zero, obtaining next hop information and prefix length information for the IP adds from the remaining bits of the entry in the second lookup table,

if the maker bit is one,

using the remaining bits of the entry in the second lookup table to index to a block of entries in a second data structure,

within the block of entries in the second data structure, using the offset to index to a particular entry, and

obtaining next hop and prefix length information from the indexed entry in the second data structure; and

using the next hop and prefix length information to forward a packet associated with the IP address to another location on a communications network.

4. The method of claim 3, wherein:

using the segment to index the entry in the first lookup table is done using a processor having an instruction which causes the processor to load an entry from the first lookup table using the segment;

computing a total number of ones in a bitmap of the indexed entry is done using an instruction of the processor which computes a total number of ones in the bitmap;

obtaining next hop and prefix information from the information storage portion of the entry is done using an instruction of the processor which extracts next hop and prefix length information from the first lookup table;

determining a number of ones from the beginning of the bitmap to the index bit is done using an instruction of the processor which computes a number of leading ones from a most significant bit to a current bit in a bitmap;

using the number of ones to the indexed bit to index an entry in a second lookup table is done using an instruction of the processor which computes the index into the second lookup table; and

obtaining next hop and prefix length information from the second lookup table is done using an instruction of the processor which gets next hop and prefix length information from the second lookup table.

5. The method of claim 3, wherein the method is performed on a configurable processor.

6. The method of claim 5, wherein the configurable processor includes custom instructions for performing the method.

7. A method of updating a data structure suitable for use in a route lookup system in a communications network, the method comprising:

receiving an IP route having an IP address component, prefix length component and next hop component;

when the prefix length component has a value less than a first predetermined value,

determining whether an entry of an NHPL table in the data structure needs to be updated based on values of the prefix length and next hop components, and

updating the entry of the NHPL table based on the determination;

when the prefix length component has a value greater than or equal to a second predetermined value,

identifying an entry in the data structure which matches the prefix length and next hop information,

determining whether the prefix length component in the address component is more specific than that stored in the entry, and whether the next hop component in the address component is different from a next hop component in the entry, and

updating the entry based on the determination; and

when the prefix length component is neither less than the first value nor greater than or equal to the second predetermined value,

determining entries in the data structure matching the prefix length component,

determining bits in a bitmap of the entries matching the prefix length component,

for each matching bit, determining whether the prefix length component is more specific than prefix length information associated with that bit and whether the next hop component is different from next hop information associated with that bit, and

updating an entry in the data structure corresponding to that based on the determination.