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

• US 6,947,931 B1
• Filed: 04/06/2000
• Issued: 09/20/2005
• Est. Priority Date: 04/06/2000
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Choules, Jack
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/544,992
• Time in Patent Office: 1,993 Days
• Field of Search: 707 1- 10, 707100-1041, 370/352, 370/389, 370/408, 370/428, 370/432, 370/392, 711/216
• US Class Current: 1/1
• 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. A method for determining a longest prefix match for a variable length search key by a computer processing device, comprising:

reading an input key as a search string;

using the N most significant bits of the input key as an address to index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

reading the next branch contents if the pointer does not point to the leaf of the corresponding search tree and comparing the prefix represented by the next branch with the input key to find a distinguishing bit position;

reading a leaf pattern when the leaf of a corresponding search tree is reached and comparing the leaf pattern with the input key to determine if the leaf pattern matches the input key; and

returning the longest prefix match found for the input key to a requesting application.

2. The method for determining the longest prefix match of claim 1 wherein the table representing a plurality of root nodes of search trees contains 2^N entries.

3. The method for determining the longest prefix match of claim 1 wherein the computer processing device is a network processor.

4. The method for determining the longest prefix match of claim 1 wherein the contents of the next branch of the corresponding search tree points to another next branch.

5. The method for determining the longest prefix match of claim 1 wherein the contents of the next branch points to the leaf of the corresponding search tree.

6. The method for determining the longest prefix match of claim 1 wherein the contents of the next branch points to both a bird and to another next branch of the corresponding search tree.

7. The method for determining the longest prefix match of claim 6 wherein the bird represents a special type of leaf that represents a partial prefix match of the input key.

8. The method for determining the longest prefix match of claim 7 wherein the bird is placed on a bird stack along with an associated bit position.

9. The method for determining the longest prefix match of claim 8 further comprising testing the bird stack to determine if it is full.

10. The method for determining the longest prefix match of claim 9 further comprising, if the bird stack is not full, reading the contents of the next branch of the corresponding search tree.

11. The method for determining the longest prefix match of claim 9 further comprising, if the bird stack is full, flushing the bird stack.

12. The method for determining the longest prefix match of claim 11 wherein flushing the bird stack comprises the acts of:

reading the contents of the birds from a memory location;

comparing the input key with the pattern stored in the contents of the bird memory location;

determining a distinguishing position which represents a first bit at which the bird pattern and the input key differ;

selecting the bird with the largest bit number that does not exceed the distinguishing position to keep in the bird stack; and

removing all other birds in the bird stack.

13. The method for determining the longest prefix match of claim 1 further comprising terminating the search for the longest prefix match when the bit number of the next branch exceeds the length of the input key.

14. A computer readable medium containing a plurality of data structures for finding a longest prefix match for a variable length search key, comprising:

an input key that is to be searched;

a direct table that stores a first address location for a search tree;

a plurality of pattern search control blocks that each represent a branch in the search tree;

at least one bird representing a partial match of the input key; and

a plurality of leaves wherein each leaf is an address location for the result of a search.

15. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 further comprising a lookup definition table that manages a tree search memory.

16. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 15 wherein the lookup definition table comprises entries that define a physical memory that the tree resides in, a size of the key and leaf, and a type of search to be performed.

17. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 15 wherein the lookup definition table is implemented in a plurality of memories.

18. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 wherein a format for a direct table entry includes at least one of a search control block;

a next pattern address that point to a next pattern search control block;

a leaf control block address that points to a leaf or result;

a next bit or bits to test; and

a direct leaf.

19. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 18 wherein the direct leaf is stored directly in a direct table entry and includes a search control block and a pattern to be compared to a search key.

20. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 wherein a format for a pattern search control block includes at least one of a search control block;

a next pattern address that point to a next pattern search control block;

a leaf control block address that points to a leaf or result; and

a next bit or bits to test.

21. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 wherein a leaf data structure includes at least one of a leaf chaining pointer;

a prefix length;

a pattern to be compared to the search key; and

variable user data.

22. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 wherein a pattern search control block is inserted in the search tree at a position where the leaf patterns differ.

23. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 wherein a pattern search control block has a shape defined by a width of one and a height of one and is stored in a memory that has a line length of at least 64 bits.

24. The computer readable medium containing a plurality of data structures for finding the longest prefix match of claim 14 wherein a pattern search control block has a shape defined by a width of one and a height of two and is stored in a memory of at least 36 bits.

25. A computer readable medium containing a program product for determining a longest prefix match for a variable length search key, comprising:

program instructions that read an input key as a search string;

program instructions that use the N most significant bits of the input key as an address to index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

program instructions that determine if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

program instructions that read the next branch contents if the pointer does not point to the leaf of the corresponding search tree and compare the prefix represented by the next branch with the input key to find a distinguishing bit position;

program instructions that read a leaf pattern when the leaf of a corresponding search tree is reached and compare the leaf pattern with the input key to determine if the leaf pattern matches the input key; and

program instructions that return the longest prefix match found for the input key to the requesting application.

26. The computer program product for determining the longest prefix match of claim 25 wherein the table representing a plurality of root nodes of search trees contains 2^N entries.

27. The computer program product for determining the longest prefix match of claim 25 wherein the contents of the next branch of the corresponding search tree points to another next branch.

28. The computer program product for determining the longest prefix match of claim 25 wherein the contents of the next branch points to the leaf of the corresponding search tree.

29. The computer program product for determining the longest prefix match of claim 25 wherein the contents of the next branch points to both a bird and to another next branch of the corresponding search tree.

30. The computer program product for determining the longest prefix match of claim 29 wherein the bird represents a special type of leaf that is in the middle of a search tree branch.

31. The computer program product for determining the longest prefix match of claim 30 wherein the bird is placed on a bird stack along with an associated bit position.

32. The computer program product for determining the longest prefix match of claim 31 further comprising program instructions that test the bird stack to determine if it is full.

33. The computer program product for determining the longest prefix match of claim 32 further comprising program instructions that read the contents of the next branch of the corresponding search tree if the bird stack is not full.

34. The computer program product for determining the longest prefix match of claim 32 further comprising program instructions that flush the bird stack if the bird stack is full.

35. The computer program product for determining the longest prefix match of claim 34 wherein the act of program instructions that flush the bird stack comprises:

program instructions that read the contents of the birds from a memory location;

program instructions that compare the hashed key with the pattern stored in the contents of the bird memory location;

program instructions that determine a distinguishing position which represents a first bit at which the bird pattern and the hashed key differ;

program instructions that select the bird with the largest bit number that does not exceed the distinguishing position to keep in the bird stack; and

program instructions that remove all other birds in the bird stack.

36. The computer program product for determining the longest prefix match of claim 25 further comprising program instructions that terminate the search for the longest prefix match when the bit number of the next branch exceeds the length of the hashed key.

37. A method for determining a longest prefix match for a variable length search key by a computer processing device, comprising:

reading an input key as a search string;

using N bits of the input key as an address to access a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer;

determining if the pointer in a non-empty table entry points to at least a leaf of the corresponding search tree;

reading a leaf pattern in the leaf;

comparing the leaf pattern with the input key, to determine if the leaf pattern matches the input key, only if the leaf is an end leaf; and

returning the leaf pattern as the longest prefix match found for the input key to a requesting application only if there is an exact match between the leaf pattern and the input key.

38. The method of claim 37 further including:

storing the leaf pattern in a stack if the leaf is not the end leaf of the corresponding tree;

determining other leaves, if any, that are not end leaves of the corresponding tree; and

storing leaf patterns associated with each one of the other leaves in the stack.

39. The method of claim 38 further including retracing a path laid out between the end leaf, other leaves and root node of the corresponding tree to determine the longest prefix match if the leaf pattern in the end leaf does not exactly match the input key.

40. The method of claim 39 wherein the retracing includes correlating the input key with the leaf pattern in the end leaf to determine 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.

41. A method for determining a longest prefix match for a variable length search key by a computer processing device, comprising

(a) reading an input key as a search string;

(b) using the N most significant bits of the input key as an address to index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

(c) determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

(d) reading the next branch contents if the pointer does not point to a leaf of the corresponding search tree;

(e) repeating acts (c) and (d) until a leaf is reached;

reading a leaf pattern when the leaf of a corresponding search tree is reached and comparing the leaf pattern with the input key to determine if the leaf pattern matches the input key; and

returning the leaf pattern as the longest prefix match found for the input key to a requesting application.