Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-09-10
2009-10-27
Robinson, Greta L (Department: 2169)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S238000
Reexamination Certificate
active
07610271
ABSTRACT:
A method and apparatus for searching an electronically stored table of information including a plurality of table entries and facilitating high speed searching of a table to provide a longest matching entry. The table searching method uses at least one memory unit having a table of information including a plurality of data entries. The table of information has a plurality of search keys associated with the plurality of data entries and the plurality of search keys form a tree structure based on a prefix length for each of the search keys. The plurality of search keys are expanded such that each of the plurality of search keys has two lowest level search keys associated therewith that cover a lowest level of the tree structure. A binary search of the lowest level search keys is performed based on a search value to determine a longest prefix match. A data entry of the plurality of data entries is output based on said longest prefix match. The method is also applicable to routing data in an internet router where the routing of data packets depends on address information stored in the table of information.
REFERENCES:
patent: 5278789 (1994-01-01), Inoue et al.
patent: 5390173 (1995-02-01), Spinney et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5423015 (1995-06-01), Chung
patent: 5459717 (1995-10-01), Mullan
patent: 5473607 (1995-12-01), Hausman
patent: 5497485 (1996-03-01), Ferguson et al.
patent: 5499295 (1996-03-01), Cooper
patent: 5524254 (1996-06-01), Morgan et al.
patent: 5555398 (1996-09-01), Raman
patent: 5568477 (1996-10-01), Galand
patent: 5579301 (1996-11-01), Ganson et al.
patent: 5644784 (1997-07-01), Peek
patent: 5652579 (1997-07-01), Yamada et al.
patent: 5696899 (1997-12-01), Kalwitz
patent: 5742613 (1998-04-01), MacDonald
patent: 5748631 (1998-05-01), Bergantino et al.
patent: 5781549 (1998-07-01), Dai
patent: 5787084 (1998-07-01), Hoang et al.
patent: 5790539 (1998-08-01), Chao et al.
patent: 5802052 (1998-09-01), Venkataraman
patent: 5802287 (1998-09-01), Rostoker et al.
patent: 5825772 (1998-10-01), Dobbins et al.
patent: 5828653 (1998-10-01), Goss
patent: 5831980 (1998-11-01), Varma et al.
patent: 5842038 (1998-11-01), Williams et al.
patent: 5845081 (1998-12-01), Rangarajan et al.
patent: 5877187 (1999-03-01), Orjales et al.
patent: 5892922 (1999-04-01), Lorenz
patent: 5898687 (1999-04-01), Harriman et al.
patent: 5909686 (1999-06-01), Muller
patent: 5918074 (1999-06-01), Wright et al.
patent: 5940596 (1999-08-01), Rajan et al.
patent: 5950205 (1999-09-01), Aviani, Jr.
patent: 5987507 (1999-11-01), Creedon et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061351 (2000-05-01), Erimli et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6119196 (2000-09-01), Muller et al.
patent: 6175902 (2001-01-01), Runaldue et al.
patent: 6178414 (2001-01-01), Beckmann et al.
patent: 6185185 (2001-02-01), Bass et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6553002 (2003-04-01), Bremer et al.
patent: 6581106 (2003-06-01), Crescenzi et al.
patent: 6594268 (2003-07-01), Aukia et al.
patent: 6631419 (2003-10-01), Greene
patent: 6658482 (2003-12-01), Chen et al.
patent: 6836771 (2004-12-01), Brown
patent: 6996559 (2006-02-01), Beshai
patent: 7072885 (2006-07-01), Cao et al.
patent: 0312917 (1989-04-01), None
patent: 465090 (1992-01-01), None
patent: 0752796 (1997-01-01), None
patent: 0849917 (1998-06-01), None
patent: 0853441 (1998-07-01), None
patent: 0854606 (1998-07-01), None
patent: 0859492 (1998-08-01), None
patent: 0862349 (1998-09-01), None
patent: 0907300 (1999-04-01), None
patent: WO 94/01828 (1994-01-01), None
patent: WO 98/09473 (1998-03-01), None
patent: WO 99/00938 (1999-01-01), None
patent: WO 99/00939 (1999-01-01), None
patent: WO 99/00944 (1999-01-01), None
patent: WO 99/00945 (1999-01-01), None
patent: WO 99/00948 (1999-01-01), None
patent: WO 99/00949 (1999-01-01), None
patent: WO 99/00950 (1999-01-01), None
patent: WO 99/14906 (1999-03-01), None
patent: WO9900936 (2001-06-01), None
“Queue Management for Shared Buffer and Shared Multi-buffer ATM Switches,” Yu-Sheng Lin et al., Department of Electronics Engineering & Institute of Electronics, National Chiao Tung University, Hsinchu, Taiwan, R.O.C., Mar. 24, 1996, pp. 688-695.
“A 622-Mb/s 8 × 8 ATM Switch Chip Set with Shared Multibuffer Architecture,” Harufusa Kondoh et al., 8107 IEEE Journal of Solid-State Circuits Jul. 28, 1993, No. 7, New York, US, pp. 808-814.
Cao Jun
Ng Eric
Smith Brandon Carl
Broadcom Corporation
Robinson Greta L
LandOfFree
Method and apparatus for performing a binary search on an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing a binary search on an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing a binary search on an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4113782