Full match (FM) search algorithm implementation for a...

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C707S793000, C707S793000, C707S793000, C707S793000, C370S389000, C370S395430

Reexamination Certificate

active

07139753

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.

REFERENCES:
patent: 5121495 (1992-06-01), Nemes
patent: 5418947 (1995-05-01), Hsu et al.
patent: 5594899 (1997-01-01), Knudsen et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5819291 (1998-10-01), Haimowitz et al.
patent: 5857196 (1999-01-01), Angle et al.
patent: 5893086 (1999-04-01), Schmuck et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6404752 (2002-06-01), Allen et al.
patent: 6671725 (2003-12-01), Noel et al.
patent: 6842443 (2005-01-01), Allen et al.
patent: 2002/0061022 (2002-05-01), Allen et al.
patent: 2004/0049582 (2004-03-01), Noel et al.
patent: 2005/0152369 (2005-07-01), Ambe et al.
patent: 0419889 (1991-04-01), None
patent: 0419889 (1999-03-01), None
patent: 2350534 (2000-11-01), None
patent: 02-260334 (1990-10-01), None
patent: 05-167640 (1993-07-01), None
patent: 10-162013 (1998-06-01), None
patent: 10162013 (1998-06-01), None
patent: 10-257066 (1998-09-01), None
patent: 2002-024293 (2002-01-01), None
patent: 96/00945 (1996-01-01), None
patent: 01/16779 (2001-03-01), None
Kenshin Yamada et al., “Address Resolution Engine for IP Routing”, Technical Report of IEICE, SSE98-72, IN98-53(2), CS98-69(Sep. 1998).
Shingo Ata et al, “Study on Efficient Cache Structures Providing Policy-Based Services in IP Routers”, Technical Report of IEICE, CS99-155, CQ99-78(Feb. 2000).

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Full match (FM) search algorithm implementation for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Full match (FM) search algorithm implementation for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Full match (FM) search algorithm implementation for a... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3640155

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.