Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-04-29
2004-05-18
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06738862
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a ternary CAM.
2. Related Art
In computer networks for transmitting information, routing devices are used to process incoming messages and to determine the disposition for those messages. Most messages are ultimately forwarded to their destination, using routing information maintained at the router and used in response to routing information contained in a header for the message.
One problem in the known art is that the task of processing incoming messages by the router can take substantial time. Performing additional functions besides forwarding could also increase the amount of processing time. These additional functions can include access control, quality of service features, and implementing other administrative policies. Accordingly, it would be advantageous to reduce the amount of processing time used by the router, so as to be able to route more messages in each unit time.
One known solution is to organize routing information in the router so it can be readily accessed, such as using a tree structure, a trie structure, or a hash table. While these methods of data access are relatively quick, they still take an amount of time that grows with the number of possible different selections. For example, some of these methods take about O(log N) time to perform, where N is the number of possible different selections. When the number of possible different selections is large, this can represent a substantial amount of processing time for each message. These methods of data access also have the drawback that they take variable amounts of time. This makes allocating processing time, queueing space, and other router (or switch) resources more difficult. Accordingly, it would be advantageous to be able to process each message in a known bounded time, such as O(constant) time.
One idea with promise is to use a CAM (content addressable memory) to match key information from each incoming message with a disposition for that message. However, the information used for routing has a great deal of redundancy. Having one entry in the CAM for each possible set of routing information (or even for each set of routing information known to the router), the CAM would need to be unduly large and unwieldy. Accordingly, it would be desirable to have one entry in the CAM stand for multiple sets of routing information.
One known method by which each CAM entry can stand for multiple sets of information is to provide a ternary CAM, that is, one in which each bit entry for matching is either a logical “0,” a logical “1,” or a logical “don't care.” In known ternary CAMs, each entry for matching comprises two bits for each value bit, a first bit to indicate whether the bit need be matched at all, and a second bit to indicate (if matched) to what value the bit must match. However, by providing a mask bit for each value bit (thus, two bits total for each value bit) these known ternary CAMs have a relatively large amount of overhead. This limits the maximum size of the CAM that can be implemented in a selected chip area with a selected manufacturing technology.
Accordingly, it would be desirable to provide a method and system for flexible matching of data in a CAM that does not use the overhead of one mask bit for each matched value bit. This advantage is achieved in an embodiment of the invention in which the entries of the CAM are logically grouped in a set of blocks, each block having a single mask that applies to all entries in the block.
SUMMARY OF THE INVENTION
The invention provides a method and system for flexible matching of data in a CAM that does not use the overhead of one mask bit for each matched value bit. The entries of the CAM are logically grouped in a set of blocks, each block having a single mask that applies to all entries in the block. In a preferred embodiment, each block includes a predetermined number of CAM entries, such as a block of sixteen entries. However, in alternative embodiments, the number of CAM entries for each block could be predetermined to be a different number, or could be dynamically selected with the values that are entered into the CAM.
REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4296475 (1981-10-01), Nederlof et al.
patent: 4491945 (1985-01-01), Turner
patent: 4791606 (1988-12-01), Threewitt et al.
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5319763 (1994-06-01), Ho et al.
patent: 5383146 (1995-01-01), Threewitt
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5450351 (1995-09-01), Heddes
patent: 5515370 (1996-05-01), Rau
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5978885 (1999-11-01), Clark, II
patent: 6000008 (1999-12-01), Simcoe
patent: 6041389 (2000-03-01), Rao
patent: 6047369 (2000-04-01), Colwell et al.
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6181698 (2001-01-01), Hariguchi
patent: 6199140 (2001-03-01), Srinivasan et al.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6389506 (2002-05-01), Ross et al.
patent: 6499081 (2002-12-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-Verlag, 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 and 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.
Bechtolsheim Andreas V.
Ross Mark A.
Cisco Technology Inc.
Namazi Mehdi
The Law Office of Kirk D. Williams
LandOfFree
Block mask ternary CAM does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block mask ternary CAM, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block mask ternary CAM will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225889