Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-10-10
2006-10-10
Corrielus, Jean M. (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C370S401000, C370S356000
Reexamination Certificate
active
07120630
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.
REFERENCES:
patent: 5121495 (1992-06-01), Nemes
patent: 5418947 (1995-05-01), Hsu et al.
patent: 5546390 (1996-08-01), Stone
patent: 5594899 (1997-01-01), Knudsen et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5815737 (1998-09-01), Buckland
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: 5940396 (1999-08-01), Rochberger
patent: 5946676 (1999-08-01), Iggulden
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 5978795 (1999-11-01), Poutanen et al.
patent: 6161144 (2000-12-01), Michels et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6347085 (2002-02-01), Kelly
patent: 6396842 (2002-05-01), Rochberger
patent: 6404752 (2002-06-01), Allen et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6456625 (2002-09-01), Itoi
patent: 6522632 (2003-02-01), Waters et al.
patent: 6553002 (2003-04-01), Bremer et al.
patent: 6560640 (2003-05-01), Smethers
patent: 6789116 (2004-09-01), Sarkissian et al.
patent: 6836771 (2004-12-01), Brown
patent: 2001/0043602 (2001-11-01), Brown
patent: 0 520 116 (1991-06-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
Willibald Doeringer, Gunter Karjoth and Mehdi Nassehi—“Routing on Longest-Matching Prefixes” IEEE/ACM Transactions on Networking (TON), vol. 4, Issue 1, Feb. 1996, pp. 86-97.
Masanori Uga & Kohei Shiomoto—“A Fast and Compact Longest Match Prefix Look-up Method Using Pointer Cache for Very Long Network Address” IEEE, CCN, Oct. 11-13, 1999, pp. 595-602.
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).
Bass Brian Mitchell
Calvignac Jean Louis
Heddes Marco C.
Maragkos Antonios
Patel Piyush Chunilal
Cockburn Joscelyn G.
Corrielus Jean M.
Ly Anh
LandOfFree
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.
Profile ID: LFUS-PAI-O-3619982