| Data storage and matching employing words wider than width of content addressable memory -> Monitor Keywords |
|
|
  Data storage and matching employing words wider than width of content addressable memoryRelated Patent Categories: Electrical Computers And Digital Processing Systems: Memory, Storage Accessing And Control, Specific Memory Composition, Content Addressable Memory (cam)The Patent Description & Claims data below is from USPTO Patent Application 20060085590. Brief Patent Description - Full Patent Description - Patent Application Claims
FIELD OF THE INVENTION [0001] This invention relates to search apparatus employing a CAM, i.e. a content addressable memory. The object of the invention is to permit the storage and matching of a word which is wider than the width of the CAM. BACKGROUND TO THE INVENTION [0002] A content addressable memory is a memory with a searching facility which allows the comparison of a key simultaneously with all the entries in the memory and therefore in its usual form it can achieve a result, i.e. the detection of a match or partial match with the search key within one clock cycle of the search. The search result is determined by the content of the memory rather than the address of the storage location. It can be used to determine whether a given key is merely a match with a word stored in the memory but more usually it is employed to retrieve data associated with an entry. In particular, the input to a CAM may be, for example a destination address extracted from an addressed data packet which is transmitted using any of the well known protocols, such as TCP/IP. A match of the input key with a stored word yields a match address, i.e. the address of the matching entry; the match address may be used as a pointer into another memory, such as a random access memory (RAM) to retrieve data associated with the entry in the CAM. For example the associated data may be a port number, i.e. a numerical identifier of a transmit port of a switch by which the packet has been received and from which the packet should be forwarded. [0003] Although a CAM is a rapid and versatile hardware search engine, in practice there are limitations on the size of it. For example, as explained later, the (column) lines which convey the digits of the input key to the storage cells and, usually, almost all the (row) match lines which can indicate the location of a match have to be charged and discharged each search cycle, so that the operating speed is limited and the heating effect of the CAM geometrically increases, as the CAM increases in size. [0004] However, in modern network practice the trend is for an increase in the search width. The address width for packets conforming to Internet Protocol version six (`Ipv6`) is 128 bits. Thus the word width is already quite large. Furthermore, a much wider width is necessary if it be desired to conduct a search on, for example a source/destination pair or to employ a CAM in a classification engine. [0005] Accordingly various processes may require that from time to time one may need to search for words that are wider than a CAM can store in a single entry. Such a need is not well met by the provision of a CAM which is as `wide` as one could possibly require: such a CAM would not perform `ordinary` narrower searches efficiently. Much the same applies to the provision of two CAMs; they represent an inefficient means of performing narrower searches and require much additional external control logic and search logic. [0006] There is therefore a need for a search engine based on a single CAM which allows a search for a word that is wider than the width of the CAM. SUMMARY OF THE INVENTION [0007] The present invention is based on partitioning a word into segments, which need to be less than the width of the CAM by at least the number of digits in a coded representation of entry addresses in the CAM, so that for example if there are 2.sup.n possible entries the number of `address` digits will be n. A first segment is stored with a predetermined prefix, which may be all zeroes, in any location that does not match the prefix. The prefix is not specific to the data content of the segment. A second segment is stored with a prefix comprising content corresponding to the location address in which the first segment is stored. [0008] A search for a given word can therefore proceed by partitioning the input word similarly, and applying a first segment of the word with the aforementioned prefix to the CAM. If there is a match, the address of the matching entry is employed as or included in a prefix to the second segment. [0009] For all words or for all words of a given type or length, the predetermined prefix would preferably be the same and is preferably all zeroes to facilitate any conflict with words that are also stored in the CAM and are occupy the full width of the CAM. However the invention does not preclude the use of different prefixes to distinguish between differently classified words or words of different lengths. Moreover both prefixes may include a respective predetermined field indicating whether the associated segment is the first or second segment. [0010] If a bipartite partition is employed, the word thus stored can be up to (2w-2n) digits, where w is the digital width of the CAM. Thereby a word of nearly twice the width of the CAM, since w is normally much greater than n, can be stored and used to address the CAM at the cost of one extra search cycle. For example if w is 128 and n is 12 (corresponding to 2.sup.12 locations), the 128-digit wide CAM would allow storage of words up to 232 digits. [0011] The scheme could be extended to a triple partitioning or more, at the cost of an additional search cycle. BRIEF DESCRIPTION OF THE DRAWINGS [0012] FIG. 1 is a schematic drawing showing a CAM in simplified form. [0013] FIG. 2 is a schematic drawing of a CAM operating according to the invention. [0014] FIG. 3 is a flow diagram illustrating a loading process. [0015] FIG. 4 is a flow diagram illustrating a searching process. DETAILED DESCRIPTION [0016] FIG. 1 of the drawings illustrates in grossly simplified form a content addressable memory 1, omitting for simplicity the circuit components within each cell and also the lines and logic required to insert entries in the memory. The illustrated CAM is only four entries `deep` and each entry has a `width` of only four bits. The CAM has an array of cells 2. For simplicity the means of loading the cells has been omitted but will be well understood by those skilled in the art. A word is loaded into a row of cells in parallel. For the sake of example the four words stored in the CAM are 101x, 0111, 0101 and 0011. the example is that of a ternary CAM, where in addition to storing binary digits (O or 1) a cell can be in a `don't care` state, where is will detect a bit match with either binary digit. Thus the top row of the CAM can produce a match with an input word that is either 1011 or 1010. The use of `don't care` digits is useful in detecting input strings rather than full addresses and is important for internet routing. The invention is applicable to binary CAMs as well as ternary CAMs. [0017] An input word may be located in a temporary register 3. The digits of the input word are shown as a0, a1, a2 and a3. In the construction shown in FIG. 1, each column of cells (which will be compared with the respective digit in the input word) has two column lines which convey a high and low voltage to the cells. Which is which depends on the respective digit. If for example a0 is `1` then the line conveying a0 will be `high` and the line conveying the complement of a0 will be low. [0018] The cells of a row are all coupled to a respective row output line. This is normally `high` at the start of a cycle. If any cell in the row does not detect a match it will pull the row line low. Thus for example if the input word is 0011 all the row output lines except that marked (11). [0019] The output lines have address, herein call match addresses. A binary representation of the address can be obtained by means of an address encoder which converts the signal indicating a match into a word which will have n binary digits where the number of row lines and therefore the number of possible entries is 2.sup.n (or between 2.sup.n-1 and 2.sup.n). In the simple example the rows have addresses 00, 01, 10 and 11. Continue reading... Full patent description for Data storage and matching employing words wider than width of content addressable memory Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Data storage and matching employing words wider than width of content addressable memory patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Data storage and matching employing words wider than width of content addressable memory or other areas of interest. ### Previous Patent Application: Status register to improve initialization of a synchronous memory Next Patent Application: Hybrid hardware and software implementation of transactional memory access Industry Class: Electrical computers and digital processing systems: memory ### FreshPatents.com Support Thank you for viewing the Data storage and matching employing words wider than width of content addressable memory patent info. IP-related news and info Results in 0.13357 seconds Other interesting Feshpatents.com categories: Tyco , Unilever , Warner-lambert , 3m |
||
