Full match (FM) search algorithm implementation for a network processor

• US 7,120,630 B2
• Filed: 08/28/2003
• Issued: 10/10/2006
• 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): Corrielus, Jean M.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US10/650,397
• Publication Number:
  US 20050177552A1
• Time in Patent Office: 1,139 Days
• Field of Search: 707 2- 5, 707100-1041, 707/6, 370/389, 370/392, 370/335, 370/395, 370/401, 370/356
• US Class Current: 1/1
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• 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 a full match between a search pattern and a pattern stored in a leaf of the search tree. A key is input, a hash function is performed on the key, a direct table (DT) is accessed, and a tree is walked through pattern search control blocks (PSCBs) until reaching a leaf. The search mechanism uses a set of data structures that can be located in a few registers and regular memory, and then used to build a Patricia tree structure that can be manipulated by a relatively simple hardware macro. Both keys and corresponding information needed for retrieval are stored in the Patricia tree structure. The hash function provides an n->n mapping of the bits of the key to the bits of the hash key.

Claims

1. A computer system comprising:

a computer readable medium containing a plurality of data structures, for finding a match for a variable length search key, said data structure including;

a first pattern;

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

a plurality of pattern search control blocks wherein pattern search control block represents a branch in the search tree;

a plurality of leaves wherein each leaf is an address location for storing predefined information relative to said first pattern; and

a search tree engine to correlate the first pattern with information stored in selected ones of the plurality of data structures and forward the predefined information found in a leaf included in the selected ones of the plurality of data structure if a match occurs between the first pattern and a second pattern stored in said leaf wherein a format for the direct table includes at least one of the search control block including a next pattern address points to a next pattern search control block, a leaf control block address points to one of the plurality of leaves, a next bit or bits to test and a direct leaf.

2. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 1 further comprising a lookup definition table that manages a tree search memory.

3. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 2 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.

4. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 2 wherein the lookup definition table is implemented in a plurality of memories.

5. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 1 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.

6. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 1 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.

7. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 1 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.

8. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 1 wherein a pattern search control block is inserted in the search tree at a position where the leaf patterns differ.

9. A computer system comprising a computer readable medium containing a plurality of data structures for finding the match of claim 1 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 36 bits.