Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-08-22
2004-06-01
Elms, Richard (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S230030
Reexamination Certificate
active
06744652
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of memory devices and, in particular, to content addressable memory devices.
BACKGROUND OF THE INVENTION
Networks may contain a collection of computing systems (e.g., clients and servers) that are interconnected by transmission lines to enable the transfer of data between them. A network typically includes multiple access points (e.g., routers and servers) that may switch and/or route data between transmission lines to transfer data from a source to a destination. Data is typically transmitted in the form of packets that are made up of smaller data cells. A packet is a unit of data that is routed between a source and a destination on a packet-switched network. When a file (e.g., e-mail, graphics, etc.) is sent from one place to another on a network, the file is divided into such smaller packets making them more efficient for transmission. The individual packets for a given file may travel different routes throughout networks with each packet containing both data and transmission information associated with the routing of data. As such, a packet may be described as having a payload containing the data, and one or more headers that contain the routing information (e.g., a destination address).
When all the packets have arrived at a destination, they are reassembled into the original file at the receiving end. Such a packet switching scheme is an efficient way to handle transmission on a connectionless network. This is in contrast to a circuit switching scheme where a connection (e.g., a voice connection) requires the dedication of a particular path for the duration of the connection.
A router is a device (e.g., hardware, firmware, software) that determines the next network segment to which a packet should be forwarded towards its destination. A router may be positioned at points within a network or where one network meets another, referred to as a gateway. A router may create and maintain tables of the available routes and their conditions for use with other information to determine the best route for a given packet. Typically, a packet may travel through a number of network points having routers before arriving at its destination.
When a data packet arrives at the input of a router, several lookups may be performed to determine the subsequent handling of the packet, as illustrated in FIG.
1
. The lookups may include, for examples, where to send the packet next (Next Hop), the quality of service requirement (QoS), the Ethernet port address, etc. Consider, for example, a packet arriving at Router-A. Router-A needs to determine whether the packet is destined for local servers connected directly to Router-A, or if the packet should go to the next router on a route (Router-B) to a destination. Additionally, Router-A may assign a priority based on the destination address (DA) and the source address (SA) of the packet.
The packet header may first be parsed or processed to get the values from different fields (e.g., SA, DA, protocol type, QoS, etc) in order to perform the various lookups. A packet classification lookup, for example, may be performed using SA, DA and other relevant fields in the packet header. The Next Hop lookup, for example, may also be performed to determine whether the packet is meant for local servers or for Router-B. If the packet is destined for Router-B, the packet is then put in a queue for Router-B. If the packet is destined for a local server (e.g., Server-1 or Server-2), then a media access control (MAC) lookup is performed to send the packet to the appropriate server. In the preceding example, three lookups are necessary for sending the packet on its way: Packet Classification, Next Hop, and MAC. However, often there are other lookups performed on the packet header, with the number of lookups exceeding five or more.
Routers may use processors and content addressable memory (CAM) devices to perform the various lookups on packets. As opposed to a random access memory (RAM) device, in which information is accessed by specifying a particular memory location address, the data stored in a CAM is accessed by the contents of the data. More specifically, instead of using an address to access a particular memory location, a CAM uses a key that contains a portion of the desired contents of a particular memory cell in the memory device. The CAM can be instructed by a processor to compare the key, also referred to as comparand data (e.g., packet header data) with data stored in its associative memory array, as illustrated in FIG.
2
. The CAM simultaneously examines all of its entries and selects the stored data that matches the key.
When the entire CAM device, or blocks thereof, is searched simultaneously for a match of the stored data with the key comparand data, the CAM device indicates the existence of a match by asserting a match flag. Multiple matches may also be indicated by asserting a multiple match flag. The CAM device typically includes a priority encoder to translate the matched location into a match address or CAM index and outputs this address to a status register so that the matched data may be accessed. The priority encoder may also sort out which matching memory location has the top priority if there is more than one matching entry.
Data may be represented in the form of strings of binary digits (“bits”) having a low (“0”) logic state and a high (“1”) logic state. Different types of CAMs may be used with different data formats. A binary CAM is designed to operate with “0” and “1” states, while a ternary CAM is designed to operate with “0”, “1”, and “don't care” states. The bits may be organized into groups such as a word (e.g., 64 or 72 bits wide) and stored in different segments of a CAM. The keys used for different data fields may have different word sizes, for example, the key for a Classification lookup may be 128 bits wide and the key for a Next Hop lookup may be 32 bits wide.
A router may include multiple CAMs, with each CAM having a different table or, alternatively, a single CAM having multiple blocks for each of the different tables, for performing the different lookups. For example, a router may include a 32 bit wide Next Hop CAM, a 128 bit Classification CAM, and a 48 bit MAC CAM. With routers having multiple CAMs, each of the multiple CAMs are typically connected to common buses that are used to communicate the various keys and other input and output data with each of the CAM devices. Similarly, with routers having a single CAM with multiple blocks, each of the blocks is accessed using common buses. Thus, lookups are typically performed sequentially before a packet is processed (e.g., routed to the next destination or classified). Because the buses are shared with so many input and output functions of all the CAMs or CAM blocks, many clock cycles are required to multiplex data on the bus. This generally limits the search rate and overall throughput of conventional CAM devices. As the number of ports, segments, or devices that are supported by routers and as the number of lookups increase, conventional CAM devices and architectures can undesirably limit the system's overall throughput.
SUMMARY OF THE INVENTION
The present invention pertains to a method and apparatus for concurrent searching of different tables in a content addressable memory array.
In one embodiment, the apparatus includes a plurality of content addressable memory blocks each coupled to a corresponding filter circuit. Each of the filter circuits is configured to receive a common input string and transmit a filtered comparand string as compared information to its content addressable memory block. The filter comparand strings may be compacted.
Other features and advantages of the present invention will be apparent from the accompanying drawings, and from the detailed description.
REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4845668 (1989-07-01), Sano et al.
patent: 4958377 (1990-09-01), Takahashi
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5319762 (1994-06-01), Mayer
patent: 5414704 (1
Khanna Sandeep
Srinivasan Varadarajan
Blakely , Sokoloff, Taylor & Zafman LLP
Hur Jung H.
Netlogic Microsystems Inc.
LandOfFree
Concurrent searching of different tables within a content... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Concurrent searching of different tables within a content..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrent searching of different tables within a content... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3321729