Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2007-11-20
2007-11-20
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
10165572
ABSTRACT:
Methods and apparatus are disclosed for maintaining and using entries in one or more associative memories. A last bit of a prefix is checked, and based on this result, the entry is placed into one of two classes of associative memory entries. The entry can then be identified within the associative memory by performing a lookup operation using the prefix padded with ones if the last bit of the prefix is zero or with zeros if the last bit is one to fill out the remaining bits of the lookup word. Entries of different classes of entries are typically either stored in different associative memories, or in the same associative memory with each of these entries including a class specific identifier. Among other applications, these entries can be used to locate a prefix and to store a tree data structure in the one or more associative memories.
REFERENCES:
patent: 5088032 (1992-02-01), Bosack
patent: 5319763 (1994-06-01), Ho et al.
patent: 5481540 (1996-01-01), Huang
patent: 5515370 (1996-05-01), Rau
patent: 5528701 (1996-06-01), Aref
patent: 5651099 (1997-07-01), Konsella
patent: 5721899 (1998-02-01), Namba
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5809501 (1998-09-01), Noven
patent: 5829004 (1998-10-01), Au
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5848416 (1998-12-01), Tikkanen
patent: 5884297 (1999-03-01), Noven
patent: 5898689 (1999-04-01), Kumar et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke et al.
patent: 6000008 (1999-12-01), Simcoe
patent: 6018524 (2000-01-01), Turner et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6067574 (2000-05-01), Tzeng
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6115716 (2000-09-01), Tikkanen et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6219748 (2001-04-01), Srinivasan et al.
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6240485 (2001-05-01), Srinivasan et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6285378 (2001-09-01), Duluk, Jr.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6298339 (2001-10-01), Bjornson
patent: 6308219 (2001-10-01), Hughes
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6430190 (2002-08-01), Essbaum et al.
patent: 6434662 (2002-08-01), Greene et al.
patent: 6804744 (2004-10-01), Abbas
Donald R. Morrison, “PATRICIA—Practical Algorithm to Retrieve Information Coded in Alphanumeric,” Journal of the ACM, vol. 15, No. 4, Oct. 1968, pp. 514-534.
Waldvogel et al., “Scalable High Speed IP Routing Lookups,” Proc. SIGCOMM '97, ACM, 1997, pp. 25-36.
Lampson et al., “IP Lookups Using Multiway and Multicolumn Search,” Proc. Infocom 98, Mar. 1998, 24 pages.
V. Srinivasan and George Varghese, “Faster IP Lookups using Controlled Prefix Expansion,” ACM SIGMETRICS Performance Evaluation Review, vol. 26 No. 1, Jun. 1998, p. 1-10.
Stefan Nilsson and Gunnar Karlsson, “Fast Address Look-up for Internet Routers,” Proceedings of IEEE Broadband Communications, Apr. 1998, 12 pages.
William N. Eatherton, Hardware-Based Internet Protocol Prefix Lookups, Master's thesis, Sever Institute, Washington University, St. Louis, MO, May 1999, 109 pages.
Lampson et al., “IP Lookups Using Multiway and Multicolumn Search,” IEEE Transactions on Networking, vol. 7, No. 3, Jun. 1999, pp. 324-334.
Lockwood et al., “Field Programmable Port Extender (FPX) for Distributed Routing and Queuing,” Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays, Feb. 2000, pp. 137-144.
Ruiz-Sanchez et al., “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network Magazine, vol. 15, No. 2, Mar./Apr. 2001, pp. 8-23.
Pankaj Gupta and Nick McKewon, “Algorithms for Packet Classification,” IEEE Network Magazine, vol. 15, No. 2, Mar./Apr. 2001, pp. 24-32.
Iyer et al., “ClassiPI: An Architecture for Fast and Flexible Packet Classification,” IEEE Network Magazine, vol. 15, No. 2, Mar./Apr. 2001, pp. 33-41.
Waldvogel et al., “Scalable High Speed Prefix Matching,” ACM Transactions on Computer Systems, vol. 19, No. 4, Nov. 2001, pp. 440-482.
Devavrat Shah and Pankaj Gupta, “Fast Incremental Updates on Ternary-CAMs for Routing Lookups and Packet Classification,” Proc. Hot Interconnects VIII, Aug. 2000, Stanford. IEEE Micro, vol. 21, No. 1, Jan./Feb. 2001, 9 pages.
Waldvogel et al., “Scalable Best Matching Prefix Lookups,” PODC 98, ACM 1998.
Radia Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, Second Edition, Addison-Wesley, 2000, pp. 347-365.
Pankaj Gupta and Nick McKeown, “Algorithms for Packet Classification,” IEEE Network Special Issue, Mar./Apr. 2001, vol. 15, No. 2, pp. 24-32 (reprint 29 pages).
Srinivasan et al., “Packet Classification Using Tuple Space Search,” ACM Computer Communication Review, 1999. ACM SIGCOMM'99, Sep. 1999 (12 pages).
Srinivasan et al., “Fast and Scalable Layer Four Switching,” ACM Computer Communication Review, 28(4):191-202, 1998. ACM SIGCOMM'98, Sep. 1998 (12 pages).
Stefan Nilsson and Gunnar Karlsson, “IP-Address Lookup Using LC-Tries,” IEEE Journal on Selected Areas in Communications, Jun. 1999 (12 pages).
Panigrahy Rina
Sharma Samar
Cisco Technology Inc.
Dudek Edward J
Kim Matthew
The Law office of Kirk D. Williams
LandOfFree
Assigning prefixes to associative memory classes based on 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 Assigning prefixes to associative memory classes based on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Assigning prefixes to associative memory classes based on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3888718