Full match (FM) search algorithm implementation for a network processor
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.
-
Citations
24 Claims
-
1-13. -13. (canceled)
-
14. A computer readable medium containing a plurality of data structures for finding a match for a variable length search key, comprising:
-
a pattern or 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; and
a plurality of leaves wherein each leaf is an address location for the result of a search wherein said direct table is one of said plurality of data structures that is first accessed in conducting the search. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24-45. -45. (canceled)
Specification