Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2008-09-30
2008-09-30
Mofiz, Apu (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
11309160
ABSTRACT:
A lookup is performed using multiple levels of compressed stride tables in a multi-bit Trie structure. An input lookup key is divided into several strides including a current stride of S bits. A valid entry in a current stride table is located by compressing the S bits to form a compressed index of D bits into the current stride table. A compression function logically combines the S bits to generate the D compressed index bits. An entry in a prior-level table points to the current stride table and has a field indicating which compression function and mask to use. Compression functions can include XOR, shifts, rotates, and multi-bit averaging. Rather than store all 2Sentries, the current stride table is compressed to store only 2Dentries. Ideally, the number of valid entries in the current stride table is between 2D−1and 2Dfor maximum compression. Storage requirements are reduced.
REFERENCES:
patent: 5105353 (1992-04-01), Charles et al.
patent: 5276868 (1994-01-01), Poole
patent: 5640551 (1997-06-01), Chu et al.
patent: 5651099 (1997-07-01), Konsella
patent: 5737733 (1998-04-01), Eller
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5813001 (1998-09-01), Bennett
patent: 6067574 (2000-05-01), Tzeng
patent: 6247014 (2001-06-01), Ladwig et al.
patent: 6691131 (2004-02-01), Tikkanen et al.
patent: 6697363 (2004-02-01), Carr
patent: 6782382 (2004-08-01), Lunteren
patent: 6910043 (2005-06-01), Iivonen et al.
patent: 7007101 (2006-02-01), Schwaderer
patent: 7019674 (2006-03-01), Cadambi et al.
patent: 7046175 (2006-05-01), Subramaniam
patent: 2004/0111440 (2004-06-01), Bernard et al.
patent: 2004/0148302 (2004-07-01), McKay et al.
patent: 2004/0148303 (2004-07-01), McKay et al.
patent: 2004/0167923 (2004-08-01), Carr
patent: 2005/0187898 (2005-08-01), Chazelle
Lunteren, “Searching Very Large Routing Tables in Fast SRAM”,Proceedings of the IEEE Global Telecommunications Conference Globecom'01, vol. 3, pp. 1615-1619, San Antonio, Texas, Nov. 2001.
Auvinen Stuart T.
gPatent LLC
Mofiz Apu
Nguyen Thu Nga
X-Engines, Inc.
LandOfFree
Multi-level compressed lock-up tables formed by logical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-level compressed lock-up tables formed by logical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-level compressed lock-up tables formed by logical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3934637