Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-10-09
2004-08-10
Lane, Jack A. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06775737
ABSTRACT:
FIELD OF THE INVENTION
This invention especially relates to performing range lookup operations using associative memory devices, especially in communications and computer systems that employ content-addressable memories; and more particularly, the invention relates to allocating and using range identifiers as input values to content-addressable memories.
BACKGROUND OF THE INVENTION
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for access control lists (ACLs) and forwarding decisions is a demanding part of switch and router design. This packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
One known approach uses binary and/or ternary content-addressable memories to perform packet classification. Ternary content-addressable memories allow the use of wildcards in performing their matching, and thus are more flexible than binary content-addressable memories. These content-addressable memories are expensive in terms of power consumption and space, and are limited in the size of an input word on which a lookup operation is performed as well as the number of entries (e.g., 72, 144, etc.) which can be matched.
Various applications that use packet classification, such as Security Access Control, Quality of Service etc., may use arbitrary ranges of values (such as port numbers or packet length) as one of the classification criteria. For example, a certain operation may be performed on packets have a port range between 80 and 1024. It would be desirable to have a single or limited number of entries in a content-addressable memory than for an entry of each port (e.g., 80, 81, 82, . . . 1024).
One previous known attempt produces a resultant bitmap identifying to which of multiple ranges a certain value resides. Such a device is preprogrammed with a set of ranges and generates an bitmap output with the number of bits being as large as the number of range intervals, which may consume a large number of bits in the content-addressable memories. Needed are new methods and apparatus for performing range operations in relation to content-addressable memories.
SUMMARY OF THE INVENTION
Systems and methods are disclosed for allocating and using range identifiers as input values to content-addressable memories. In one embodiment, each of multiple non-overlapping intervals are identified with one of multiple unique identifiers. An indication of a mapping between the multiple non-overlapping intervals and the multiple unique identifiers is maintained. A particular unique identifier is determined from said multiple unique identifiers based on a value and said multiple non-overlapping intervals. A lookup operation is performed on an associative memory using the particular unique identifier to generate a result.
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: 5956336 (1999-09-01), Loschke 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: 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: 6532516 (2003-03-01), Krishna et al.
patent: 6574701 (2003-06-01), Krishna et al.
patent: 6633953 (2003-10-01), Stark
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, Server 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
Eatherton William N.
Maniyar Shyamsundar N.
Marimuthu Peram
Warkhede Priyank Ramesh
Cisco Technology Inc.
Lane Jack A.
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for allocating and using range... 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 allocating and using range..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for allocating and using range... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3286276