Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2006-04-04
2006-04-04
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S005000, C711S103000, C711S170000, C370S236000, C370S389000, C370S392000
Reexamination Certificate
active
07024515
ABSTRACT:
Methods and apparatus are disclosed for use with an associative memory, such as for, but not limited to implementing access control list and quality of service features in a communications or computing device. Multiple lists, such as access control lists, may be manipulated to typically produce a single list of entries with continuation indications, or the lists might be provided from another source. An associative memory is programmed with entries with each entry typically including a corresponding continuation level indication or flag. One or more lookup words are then generated and provided to the associative memory for a particular packet (or other entity) corresponding to the different continuation levels. In one implementation, a modified version of the Order Dependent Merge technique is used to generate the list of entries and to identify the corresponding continuation level or other continuation indication and the corresponding action to be performed for each entry.
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: 5740171 (1998-04-01), Mazzola et al.
patent: 5842040 (1998-11-01), Hughes et al.
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: 6061368 (2000-05-01), Hitzelberger
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
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: 6308218 (2001-10-01), Vasa
patent: 6308219 (2001-10-01), Hughes
patent: 6374326 (2002-04-01), Kansal et al.
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6389506 (2002-05-01), Ross et al.
patent: 6430190 (2002-08-01), Essbaum et al.
patent: 6434662 (2002-08-01), Greene et al.
patent: 6526474 (2003-02-01), Ross
patent: 6535951 (2003-03-01), Ross
patent: 6633866 (2003-10-01), Kishigami
patent: 6718326 (2004-04-01), Uga et al.
patent: 2002/0191605 (2002-12-01), Lunteren et al.
McAuley et al., Mar. 28-Apr. 1, 1993, IEEE, vol. 3, pp. 1382-1391.
Jon P. Wade and Charles G. Sodini, “A Ternary Content Addressable Search Engine,” IEEE Journal of Solid-State Circuits, vol. 24, No. 4, Aug. 1989, pp. 1003-1013.
Teuvo Kohonen, Content-Addressable Memories, 1987, pp. 128-129 and 142-144, Springer-Verlang, New York.
Brian Dipert, ed., “Special-purpose SRAMs Smooth the Ride,” EDN, Jun. 24, 1999, pp. 93-104.
“What is a CAM (Content-Addressable Memory)?,” Application Brief AB-N6, Rev. 2a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Reading Out the Valid LANCAM Memory Entries,” Application Brief AB-N4, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Extending the LANCAM Comparand,” Application Brief AB-N3, Rev. 1.0a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Advantages of CAM in ASIC-Based Network Address Processing,” Application Brief AB-N11, Rev. 1.2a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Virtual Memory Applications of the MU9C1480A LANCAM,” Application Note AN-N3, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 12 pages.
“Using the MU9C1965A LANCAM MP for Data Wider than 128 Bits,” Application Note AN-N19, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 16 pages.
“Fast IPv4 and IPv4 CIDR Address Translation and Filtering Using the MUAC Routing CoProcessor (RCP),” Application Note AN-N25, Rev. 0a, Music Semiconductors, Milpitas, CA, Oct. 1, 1998, 16 pages.
“Using MUSIC Devices and RCPs for IP Flow Recognition,” Application Note AN-N27, Rev. 0, Music Semiconductors, Milpitas, CA, Oct. 21, 1998, 20 pages.
“Wide Ternary Searches Using Music CAMs and RCPs,” Application Note AN-N31, Rev. 0, Music Semiconductors, Milpitas, CA, Apr. 13, 1999, 8 pages.
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.
Lookwood 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,” PODC98, 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).
Chang Chran Ham
Dharwadkar Pranav
Lalgudi Hari
Ruan Yixing
Cisco Technology Inc.
Farrokh Hashem
Sparks Donald
The Law Office of Kirk D. Williams
LandOfFree
Methods and apparatus for performing continue actions using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for performing continue actions using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for performing continue actions using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3607879