Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2007-12-25
2007-12-25
Lane, Jack (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S108000, C709S238000
Reexamination Certificate
active
10328639
ABSTRACT:
Methods and apparatus are disclosed for longest common prefix based caching. An information space is partitioned into multiple subsets such that a particular subset including a particular prefix also includes all longer prefixes beginning with the particular prefix in the information space. A primary control unit typically maintains the information space and all of the subsets, and selectively distributes some or all of the subsets to basic control units, and each of basic control units does not necessarily receive the same group of subsets. In addition, the group of subsets maintained by a particular basic control unit may change during operation, typically to increase the likelihood that a particular basic control unit will contain the needed subset. When a particular basic control unit does not have the needed subset, it typically sends to the primary control unit, a request for a lookup result, for the primary control unit to process the packet or other information, or for the primary control unit to send the corresponding subset.
REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4296475 (1981-10-01), Nederlof et al.
patent: 4791606 (1988-12-01), Threewitt et al.
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5088032 (1992-02-01), Bosack
patent: 5319763 (1994-06-01), Ho et al.
patent: 5339076 (1994-08-01), Jiang
patent: 5383146 (1995-01-01), Threewitt
patent: 5404482 (1995-04-01), Stamm et al.
patent: 5428565 (1995-06-01), Shaw
patent: 5440715 (1995-08-01), Wyland
patent: 5450351 (1995-09-01), Heddes
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: 5684954 (1997-11-01), Kaiserswerth et al.
patent: 5721889 (1998-02-01), Namba
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5802567 (1998-09-01), Liu et al.
patent: 5809501 (1998-09-01), Noven
patent: 5829004 (1998-10-01), Au
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5848416 (1998-12-01), Tikkanen
patent: 5852569 (1998-12-01), Srinivasan et al.
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: 5956336 (1999-09-01), Loschke et al.
patent: 5978885 (1999-11-01), Clark, II
patent: 6000008 (1999-12-01), Simcoe
patent: 6018524 (2000-01-01), Turner et al.
patent: 6041389 (2000-03-01), Rao
patent: 6047369 (2000-04-01), Colwell et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6067574 (2000-05-01), Tzeng
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6115716 (2000-09-01), Tikkanen et al.
patent: 6134135 (2000-10-01), Andersson
patent: 6137707 (2000-10-01), Srinivasan et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6175513 (2001-01-01), Khanna
patent: 6181698 (2001-01-01), Hariguchi
patent: 6199140 (2001-03-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: 6240003 (2001-05-01), McElroy
patent: 6240485 (2001-05-01), Srinivasan et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6246601 (2001-06-01), Pereira
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: 6307855 (2001-10-01), Hariguchi
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: 6542391 (2003-04-01), Pereira et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6633548 (2003-10-01), Bachmutsky et al.
patent: 6763426 (2004-07-01), James et al.
patent: 6831850 (2004-12-01), Pereira et al.
patent: 6963924 (2005-11-01), Huang et al.
patent: 7114026 (2006-09-01), Khanna
patent: 2002/0131432 (2002-09-01), Bachmutsky et al.
patent: 2003/0005146 (2003-01-01), Miller et al.
patent: 2003/0093616 (2003-05-01), Slavin
patent: 2004/0015752 (2004-01-01), Patella et al.
patent: 2004/0100950 (2004-05-01), Basu et al.
patent: 2004/0105422 (2004-06-01), Sahni et al.
patent: 2005/0262295 (2005-11-01), Nataraj et al.
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-Addressabnle Memory)?,” Application Brief AB-N6, Rev. 2a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Reading Out the Valic 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.
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 Cla
Panigrahy Rina
Saminda De Silva Suran
Sharma Samar
Cisco Technology Inc.
Lane Jack
The Law Office of Kirk D. Williams
LandOfFree
Methods and apparatus for longest common prefix based caching 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 longest common prefix based caching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for longest common prefix based caching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3841657