Longest prefix match (LPM) algorithm implementation for a network processor

• US 20050144553A1
• Filed: 01/28/2005
• Published: 06/30/2005
• Est. Priority Date: 04/06/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Calvignac, Jean Louis, Siegel, Michael Steven, Verplanken, Fabrice Jean, Heddes, Marco C., Patel, Piyush Chunilal, Maragkos, Antonios, Bass, Brian Mitchell
• Granted Patent: US 7,383,244 B2
• Time in Patent Office: Days
• US Class Current: 715/231
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Novel data structures, methods and apparatus for finding the longest prefix match search when searching tables with variable length patterns or prefixes. To find the exact match or the best matching prefix, patterns have to be compared a bit at a time until the exact or first: match is found. This requires “n” number of comparisons or memory accesses to identify the closest matching pattern. The trees are built in such a way that the matching result is guaranteed to be a best match, whether it is an exact match or a longest prefix match. Using the trail of all the birds and associated prefix lengths enables determination of the correct prefix result from the trail. By construction, the search tree provides the best matching prefix at or after the first compare during walking of the trail or tree.

Claims

1. An apparatus fabricated on a semiconductor substrate for determining a longest prefix match for a variable length search key, comprising:

an embedded processor complex including a plurality of protocol processors and an internal control point processor that provide frame processing;

a plurality of hardware accelerator co-processors accessible to each protocol processor and providing high speed pattern searching, data manipulation, and frame parsing;

a plurality of programmable memory devices that store a plurality of data structures that represent at least one search tree, wherein the data structures include a direct table, a pattern search control block, a bird and a leaf; and

an control memory arbiter that controls the access of each protocol processor to the plurality of memory devices.

2. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 1 further comprising a tree search engine that operates in parallel with protocol processor execution to perform tree search instructions including memory reads and writes and memory range checking.

3. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 1 wherein the plurality of memory devices further comprises at least one of internal static random access memory, external static random access memory, and external dynamic random access memory.

4. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 1 wherein the control memory arbiter manages control memory operations by allocating memory cycles between the plurality of protocol processors and the plurality of memory devices.

5. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 1 wherein each protocol processor comprises a primary data buffer, a scratch pad data buffer and control registers for data store operations.

6. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 1 further comprising a hash box component that performs a no hash function on the search key with a resulting hashed key being equal to the search key.

7. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 1 further comprising a programmable search key register and a programmable hashed key register.

8. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 7 further comprising a programmable color key register to enable sharing a single table data structure among a plurality of independent search trees.

9. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 8 wherein the contents of the color register, if enabled, are appended to the hash output to produce a final hashed key.

10. The apparatus fabricated on a semiconductor substrate for determining the longest prefix match of claim 8 wherein if the color register is not enabled, an equivalent number of zeros are appended to the hash output to produce a final hashed key.

11. A data structure for use in database comprising:

(a) a table having a plurality of entries wherein at least one entry includes a first field in which a first leaf bit pattern is stored, a second field in which a bit value indicating the Next Bit to Test (NBT) is stored and a third field in which a Next Pointer Address (NPA) is stored; and

(b) at least one Pattern Search Control Block (PSCB) operatively coupled to the at least one entry, said PSCB including two entries with each entry being structured with fields identical to those listed in (a).

12. The data structure of claim 11 wherein the entries in the PSCB are stacked.

13. The data structure of claim 11 wherein the fields in (a) are serially concatenated forming a line.

14. The data structure of claim 11 wherein the bit value points to a bit in a data stream that is being correlated against the database.

15. The data structure of claim 14 wherein the value of the bit in the data stream determines which one of the two entries to follow in correlating the data stream with the database.

16. A method to correlate a search string against a database comprising the acts of:

(a) providing the database having data structure including a table with N entries N>

1, at least one entry including a first field in which a first leaf bit pattern is stored, a second field in which a bit value is stored and a third field in which a Next Pointer Address (NPA) is stored; and

b. at least one Pattern Search Control Block (PSCB) operatively coupled to the at least one entry, said PSCB including two entries with each entry being structured with fields substantially similar to those listed in (a);

using M bits of the search string as an address to index into the at least one entry; and

reading the entry to determine what action next to pursue in correlating the search string with the database.

17. The method of claim 16 further including the acts of if the entry only points to an end leaf, read the pattern recorded in the end leaf;

comparing the pattern with the search string; and

returning the pattern to a requesting application as the longest prefix match found.

18. The method of claim 16 further including the acts of if the entry points to a first leaf and a first branch,

recording the pattern stored in the first leaf in a stack;

reading the information stored in the first branch;

if the information stored in the first branch points to another leaf and another branch,

recording the pattern stored in the another leaf in the stack;

reading the information stored in the another branch;

repeating the preceding two acts until the last leaf in the corresponding tree is reached;

comparing the pattern recorded in the last leaf with the search string to find a distinguishing bit position;

using the distinguishing bit position to access the stack; and

selecting one of the entries thereon as the longest prefix match found for said input key.