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

• US 20050076010A1
• Filed: 08/28/2003
• Published: 04/07/2005
• Est. Priority Date: 04/06/2000
• Status: Active Grant

• Current Assignee: Antonios Maragkos, Brian Mitchell Bass, Fabrice Jean Verplanken, Jean Louis Calvignac, Marco C. Heddes, Michael Steven Siegel, Piyush Chunilal Patel
• Original Assignee: Antonios Maragkos, Brian Mitchell Bass, Fabrice Jean Verplanken, Jean Louis Calvignac, Marco C. Heddes, Michael Steven Siegel, Piyush Chunilal Patel
• 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,139,753 B2
• Time in Patent Office: Days
• 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. The data structure that is used to store the hash key and the related information in the tree is called a leaf. Each leaf corresponds to a single key that matches exactly with the input key. The leaf contains the key as well as additional information. The length of the leaf is programmable, as is the length of the key. The leaf is stored in random access memory and is implemented as a single memory entry. If the key is located in the direct table then it is called a direct leaf.

Claims

1-23. -23. (canceled)

24. An apparatus fabricated on a semiconductor substrate for determining a full 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 programable 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 and a leaf; and

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

25. The apparatus fabricated on a semiconductor substrate for determining the full match of claim 24 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.

26. The apparatus fabricated on a semiconductor substrate for determining the full match of claim 24 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.

27. The apparatus fabricated on a semiconductor substrate for determining the full match of claim 24 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.

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

29. The apparatus fabricated on a semiconductor substrate for determining the full match of claim 24 further comprising a hash box component that performs a geometric hash function on the search key.

30. The apparatus fabricated on a semiconductor substrate for determining the full match of claim 24 further comprising a programmable search key register and a programable hashed key register.

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

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

33. The apparatus fabricated on a semiconductor substrate for determining the full match of claim 31 wherein if the color register is not enabled, appending an equivalent number of zeros to the hash output to produce a final hashed key.

34-45. -45. (canceled)