Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2004-05-17
2008-07-22
Hsu, Alpus H (Department: 2619)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395320, C707S793000, C709S238000, C711S108000
Reexamination Certificate
active
07403526
ABSTRACT:
Disclosed are, inter alia, methods, apparatus, data structures, computer readable media, mechanisms, and means for partitioning and filtering a search space of particular use for determining a longest prefix match thereon, such as for routing packets. One implementation uses one or more filtering mechanisms to filter portions of a lookup word against a first set of lookup values, such as, but not limited to the value of any corresponding portion of any entry in the search space. A set of possible matching prefixes defined by consecutive matching portions of the lookup word from the highest-order position are determined, and lookup operations are typically performed in parallel on each of these possible matching prefixes to generate a set of matching results (if any), which is typically used to identify the longest matching prefix.
REFERENCES:
patent: 5857196 (1999-01-01), Angle et al.
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5983223 (1999-11-01), Perlman
patent: 6052683 (2000-04-01), Irwin
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6526474 (2003-02-01), Ross
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6564211 (2003-05-01), Andreev et al.
patent: 6570866 (2003-05-01), Murase et al.
patent: 6611832 (2003-08-01), van Lunteren
patent: 6614789 (2003-09-01), Yazdani et al.
patent: 6631419 (2003-10-01), Greene
patent: 6658002 (2003-12-01), Ross et al.
patent: 6717946 (2004-04-01), Hariguchi et al.
patent: 6728732 (2004-04-01), Eatherton et al.
patent: 6775737 (2004-08-01), Warkhede et al.
patent: 6778530 (2004-08-01), Greene
patent: 6871262 (2005-03-01), Oren et al.
patent: 6947931 (2005-09-01), Bass et al.
patent: 6970971 (2005-11-01), Warkhede et al.
patent: 7002965 (2006-02-01), Cheriton
patent: 7047317 (2006-05-01), Huie et al.
patent: 7089240 (2006-08-01), Basso et al.
patent: 7289979 (2007-10-01), Wilson
patent: 2003/0023581 (2003-01-01), Davis et al.
patent: 2004/0008634 (2004-01-01), Rangarajan et al.
patent: 2004/0030803 (2004-02-01), Eatherton et al.
patent: 2004/0044868 (2004-03-01), Guerrero
patent: 2004/0170172 (2004-09-01), Pullela et al.
patent: 2004/0205229 (2004-10-01), Stojancic
patent: 2004/0230583 (2004-11-01), Testa
patent: 2005/0114602 (2005-05-01), Ngai et al.
patent: 2005/0157712 (2005-07-01), Rangarajan et al.
patent: 2005/0175010 (2005-08-01), Wilson et al.
Suri et al., “Scalable IP Lookup With Fast Updates,” Global Telecommunications Conference, 2001. Globecom '01. vol. 3, pp. 1610-1614.
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.
William N. Eatherton, Hardware-Based Internet Protocol Prefix Lookups, Master's thesis, Sever Institute, Washington University, St. Louis, MO, May 1999, 109 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.
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).
Bonomi Flavio Giovanni
Zou Xu
Cisco Technology Inc.
Hsu Alpus H
The Law Office of Kirk D. Williams
LandOfFree
Partitioning and filtering a search space of particular use... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partitioning and filtering a search space of particular use..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning and filtering a search space of particular use... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3972939