Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2005-11-29
2005-11-29
Bataille, Pierre-Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130, C711S202000
Reexamination Certificate
active
06970971
ABSTRACT:
Methods and apparatus are disclosed for mapping prefixes and/or values of a hierarchical space to other representations while maintaining the original hierarchy, which may be especially useful in conjunction with associative memories, such as binary and ternary content-addressable memories. In one implementation, a set of prefixes associated with a hierarchical space is received. A new representation of the set of prefixes is developed, such as by using a trie representation, with the new representation maintaining the original hierarchical relationship. This new representation may be an optimized representation selected to reduce or minimize the depth of the trie or some other cost. A set of new prefixes are generated along with a set of lookup values. During processing, a value, such as that included in a packet, is converted to one of the lookup values, which is used to generate a lookup word for use in matching against the new prefixes.
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: 5721889 (1998-02-01), Miller et al.
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: 5956336 (1999-09-01), Loschke et al.
patent: 6000008 (1999-12-01), Simcoe
patent: 6018524 (2000-01-01), Turner et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6067574 (2000-05-01), Tzeng
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: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6181698 (2001-01-01), Hariguchi
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6243667 (2001-06-01), Kerr et al.
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: 6529909 (2003-03-01), Bowman-Amuah
patent: 6717646 (2004-04-01), Park et al.
patent: 6717946 (2004-04-01), Hariguchi et al.
patent: 6775737 (2004-08-01), Warkhede et al.
patent: 2003/0174717 (2003-09-01), Zabarski et al.
patent: WO 01/052063 (2001-07-01), None
Stefan Nilsson and Gunnar Karlsson, “IP-Address Lookup Using LC-Tries,” IEEE Journal on Selected Areas in Communications, Jun. 1999 (12 pages).
Fast IP routing with LC-Tries; achieving gbit/see speed in software, (Internet/Web/Online Service Information); Stefan Nilsson et al.; Dr. Dobb's Journal; Aug. 1998; vol. 23, No. 8, p. 70 (5).
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.
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.
“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.
Bryant Stewart Frederick
Warkhede Priyank Ramesh
Bataille Pierre-Michel
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for mapping prefixes and values of 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 Method and apparatus for mapping prefixes and values of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for mapping prefixes and values of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3508471