Full match (FM) search algorithm implementation for a network processor
First Claim
1. A computer system comprising an apparatus fabricated on a semiconductor substrate, the apparatus comprising:
- an embedded processor complex including a plurality of protocol processors and an internal control point processor that provides frame processing;
a plurality of hardware accelerator co-processors coupled to the embedded processor complex, wherein the plurality of hardware accelerator co-processors are accessible to each protocol processor and provide high speed pattern searching, data manipulation, and frame parsing;
a plurality of memory devices coupled to the embedded processor complex, wherein the plurality of memory devices store a plurality of data structures that represent at least one search tree, wherein the data structures include a table comprising a plurality of entries, wherein at least one entry stores a leaf, and wherein the at least one leaf comprises a pattern corresponding to a search key containing an address; and
a control memory arbiter coupled to the plurality of protocol processor, wherein the control memory arbiter controls the access of each protocol processor to the plurality of memory devices, wherein the table stored in the plurality of memory devices is utilized to match the pattern with the search key.
0 Assignments
0 Petitions
Accused Products
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.
67 Citations
10 Claims
-
1. A computer system comprising an apparatus fabricated on a semiconductor substrate, the apparatus comprising:
-
an embedded processor complex including a plurality of protocol processors and an internal control point processor that provides frame processing; a plurality of hardware accelerator co-processors coupled to the embedded processor complex, wherein the plurality of hardware accelerator co-processors are accessible to each protocol processor and provide high speed pattern searching, data manipulation, and frame parsing; a plurality of memory devices coupled to the embedded processor complex, wherein the plurality of memory devices store a plurality of data structures that represent at least one search tree, wherein the data structures include a table comprising a plurality of entries, wherein at least one entry stores a leaf, and wherein the at least one leaf comprises a pattern corresponding to a search key containing an address; and a control memory arbiter coupled to the plurality of protocol processor, wherein the control memory arbiter controls the access of each protocol processor to the plurality of memory devices, wherein the table stored in the plurality of memory devices is utilized to match the pattern with the search key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
Specification