Variable key type search engine and method therefor6901476Abstract A system and method for storing arranged data in a memory, and for extracting the data therefrom, the system including: (a) a random access memory (RAM) including: (i) a first array of cells, the first array having at least two dimensions and having rows and columns, the first array designed and configured to contain a plurality of at least two kinds of key entries, each of the cells having a unique address and being accessible via an input key, each of the kinds of key entries being arranged in monotonic order, and (ii) a second array of cells, the second array having at least two dimensions and having rows and columns, the second array having a plurality of data entries, each of the data entries being associated with a particular one of the key entries, and (b) processing means designed and configured to search, in response to the input key, the plurality of key entries so as to identify a match. Claims 1. A system for storing arranged data in a memory, and for extracting the date therefrom, the system comprising: Description FIELD AND BACKGROUND OF THE INVENTION
In a co-pending application, U.S. patent application Ser. No. 09/779,941, which is incorporated by reference for all purposes as if fully set forth herein, a method and apparatus are disclosed for arranging and storing a set of key entries and a corresponding set of associated data entries in storage areas within a memory device. Each location in the first storage area is assigned a unique index and is associated with the corresponding location to second storage area with the same index. Each key entry represents a range of consecutive values and is denoted herein as Range Key Entry. The range may be represented by its lower or upper boundary. When a key is submitted for search and is found to belong to a range represented by a range key entry, the associated data entry with the same index is extracted from the memory as valid data and a Match signal is issued. If no range is found to contain the submitted key, no valid associated data is retrieved and a No-Match signal is issued. In a co-pending, unpublished PCT Patent Application Serial No. IL01/01 025, which is incorporated by reference for all purposes as if fully set forth herein, RAM-based technology is implemented on an RCAM in a somewhat analogous fashion to the above-described implementation of RAM-based technology on a binary CAM. A method and apparatus are disclosed therein for the high-rate arrangement, storage of ranges of integers, and extraction of data associated with these ranges in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries (representing range boundaries) in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond uniquely to these ranges are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found within an integer range, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array. The RCAM optionally includes a third two-dimensional array, consisting of associated boundary type entries that also correspond uniquely to these ranges and are stored under the same pair of indices. These entries determine the validity of the corresponding ranges. A match signal, "True" or "False", is output accordingly with the retrieved associated data entry to indicate whether the matched range and the associated data are valid or not. The array of associated boundary type entries can be stored in conjunction with that of associated data entries or separately. The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries. The technologies (both Binary CAM and RCAM) disclosed by the above-mentioned applications are characterized by fixed-width key entries. For example, RCAM key entries consisting of 32 bits provide a very efficient way of storing address ranges in Classless Inter Domain Routing (CIDR) used in Internet Protocol Version 4 (IPv4), the currently used IP version. It would, however, be highly desirable and of further advantage to have a device for, and a method of significantly improving the efficiency and flexibility in the storage and key search operations, by enabling the use of key entries with different widths and types to be efficiently stored in contiguous locations. It would be of even further advantage to have such a system and method adapted for the efficient storage of address ranges in the CIDR used in the new IPv6 protocol. SUMMARY OF THE INVENTION The Variable Key Type Search Engine of the present invention is based on a method and apparatus that enable the use of key entries having different widths and types. Each key entry is composed of a pre-selected number of key fields, and each key field consists of two fixed-width fields: a tag field and a key data field. The tag field indicates the number of key fields that are included in the respective key entry and whether the key data field corresponds to a single integer (like a key entry in a Binary CAM) or to a range of integers (like a key entry in an RCAM). The tag field value also determines the sequential order of the key entries in the list or array, so that key entries of different types may be placed in separate, but preferably contiguous, blocks within the key array. The use of classification tags thus provides great efficiency and flexibility in the storage and key search operations in a single array. Using this approach, groups of four 32-bit key data fields can be used for efficient storage of address ranges in CIDR used in the new IPv6 protocol. Thus, according to one aspect of the present invention, there is provided a system for storing arranged data in a memory, and for extracting the data therefrom, the system including: (a) a random access memory (RAM) including: (i) a first array of cells, the first array having at least two dimensions and having rows and columns, the first array designed and configured to contain a plurality of at least two kinds of key entries, each of the cells having a unique address and being accessible via an input key, each of the kinds of key entries being arranged in monotonic order, and (ii) a second array of cells, the second array having at least two dimensions and having rows and columns, the second array having a plurality of data entries, each of the data entries being associated with a particular one of the key entries, and (b) processing means designed and configured to search, in response to the input key, the plurality of key entries so as to identify a match. According to further features in the described preferred embodiments, the at least two kinds of key entries include a range type key entry, each range type key entry corresponding to a particular range and being associated with a particular one of the data entries. According to still further features in the described preferred embodiments, the at least two kinds of key entries include an exact type key entry, each exact type key entry being associated with a particular one of the data entries. According to still further features in the described preferred embodiments, the at least two kinds of key entries include range type key entries of differing length, each of the range type key entries corresponding to a particular range and being associated with a particular one of the data entries. According to still further features in the described preferred embodiments, the at least two kinds of the key entries include exact type key entries of differing length, each of the exact type key entries being associated with a particular one of the data entries. According to still further features in the described preferred embodiments, the at least two kinds of the key entries include a range type key entry and an exact type key entry, each range type key entry corresponding to a particular range and being associated with a particular one of the data entries, each exact type key entry being associated with a particular one of the data entries. According to still further features in the described preferred embodiments, at least two of any of the keys are of differing length. According to still further features in the described preferred embodiments, the range type key entry contains a single range-boundary value. According to still further features in the described preferred embodiments, each of the key entries includes a tag field for differentiating between the kinds of the key entries. According to still further features in the described preferred embodiments, each of the key entries includes at least one key field including a key data field and a tag field for differentiating between the kinds of the key entries, and wherein the processing means are designed and configured to search the plurality of the key entries by adding bits of the tag field to bits of the key data field to form a single binary number. According to still further features in the described preferred embodiments, each of the key entries includes a plurality of key fields including a plurality of key data fields and at least one tag field for differentiating between the kinds of the key entries, and wherein the processing means are designed and configured to search the plurality of the key entries by adding bits of the tag field to bits of the key data fields to form a single binary number. According to still further features in the described preferred embodiments, each of the key entries includes at least one key field including a key data field and a tag field for differentiating between the kinds of the key entries, and wherein the processing means are further designed and configured to add at least one bit of the tag field to bits of the key data field to form a single binary number for use in the search. According to still further features in the described preferred embodiments, each of the key entries includes a tag field for differentiating between the kinds of the key entries, each tag field having a tag field value, and wherein the processing means are further designed and configured to position a particular one of the key entries within the first array, based on the tag field value. According to still further features in the described preferred embodiments, each of the key entries includes a tag field for differentiating between the kinds of the key entries, each tag field having a tag field value, and wherein the processing means include identification means for identifying, within the first array, a row that may contain a match between a particular one of the key entries and the input key, based on the tag field value. According to still further features in the described preferred embodiments, the identification means for identifying a row within the first array include at least one comparator. According to still further features in the described preferred embodiments, the identification means further include a column locator for comparing contents of the row with the input key so as to identify a column containing a match for the input key. According to still further features in the described preferred embodiments, the column locator includes at least one comparator. According to still further features in the described preferred embodiments, the tag field is disposed in relation to the key field such that at least one most significant bit (MSB) position is occupied by at least one bit of the tag field. According to a second aspect of the present invention, there is provided a method for storing arranged data in a memory, and for extracting the data therefrom, the method including the steps of: (a) providing a system including: (i) a random access memory (RAM) including: (A) a first array of cells for storing key entries, the first array having at least two dimensions and having rows and columns, each of the cells having a unique address and being accessible via an input key, and (B) a second array of cells, the second array having at least two dimensions and having rows and columns, the second array having a plurality of data entries, each of the data entries being associated with a particular one of the key entries, and (ii) processing means associated with the RAM, and (b) storing at least a first kind and second kind of the key entries within the first array. According to further features in the described preferred embodiments, the at least a first kind and second kind of key entries are arranged in monotonic order. According to still further features in the described preferred embodiments, the first kind of key entries is arranged in a first block of cells within the first array, and the second kind of key entries is arranged in a second block of cells within the first array. According to still further features in the described preferred embodiments, the blocks of cells are arranged in a substantially contiguous fashion. According to still further features in the described preferred embodiments, the method further includes the step of: (c) searching, in response to the input key, a plurality of key entries so as to identify a match. According to still further features in the described preferred embodiments, the at least one kind of key entries is a range type key entry. According to still further features in the described preferred embodiments, the at least one kind of key entries is an exact type key entry. According to still further features in the described preferred embodiments, the at least one kind of key entries is an exact type key entry. According to still further features in the described preferred embodiments, each of the key entries includes a tag field. According to still further features in the described preferred embodiments, each of the key entries includes a tag field and a key data field, and wherein the searching includes differentiating between the kinds of key entries. According to still further features in the described preferred embodiments, the tag field and the key data field are examined as a single binary number in step (c). According to still further features in the described preferred embodiments, the first kind of key entries is arranged in a first block of cells within the first array, and the second kind of key entries is arranged in a second block of cells within the first array. According to still further features in the described preferred embodiments, the searching includes identifying a matching kind of the key entries using the tag field. According to still further features in the described preferred embodiments, the searching includes identifying a row within the first array in which a key entry matching the input key may be disposed. According to still further features in the described preferred embodiments, the searching includes identifying a row within the first array in which the input key may fall within a particular range associated with a range type key entry. According to still further features in the described preferred embodiments, the searching includes disposing the tag field in relation to the key field such that at least one most significant bit (MSB) position is occupied by at least one bit of the tag field. According to still further features in the described preferred embodiments, the storing of the key entries includes varying a length of the tag field according to a pre-determined criterion, so as to reduce a number of the cells occupied by the tag field. According to still further features in the described preferred embodiments, the method further includes disposing the tag field in a most significant bit (MSB) position. BRIEF DESCRIPTION OF THE DRAWINGS The invention is herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of the preferred embodiments of the present invention only, and are presented in the cause of providing what is believed to be the most useful and readily understood description of the principles and conceptual aspects of the invention. In this regard, no attempt is made to show structural details of the invention in more detail than is necessary for a fundamental understanding of the invention, the description taken with the drawings making apparent to those skilled in the art how the several forms of the invention may be embodied in practice. In the drawings: FIG. 1 is a schematic illustration of a two-dimensional, M-column by N-row, memory array; FIG. 2 is a schematic illustration of key mapping in a conventional RAM of the prior art; FIG. 3 is a schematic illustration of the correspondence between the two-dimensional key list and the associated data list for a binary CAM; FIG. 4 is a schematic illustration of the correspondence between the two-dimensional key list, the associated data list and the associated boundary type list; FIG. 5 illustrates a generic key field and three key entries containing 1, 2 and 4 key fields, respectively; FIG. 6 illustrates width relations of the three key entries provided in FIG. 5; FIG. 7 illustrates a two-dimensional array, partially filled with contiguous blocks of key entries of decreasing width; FIG. 8 provides examples of tag fields in a key entry word and structure of a three-bit tag field; FIG. 9 illustrates step 1 (Row Location) in a Sequential Key Search in a TDA, and FIG. 10 illustrates step 2 (Column Location) in a Sequential Key Search in a TDA. DESCRIPTION OF THE PREFERRED EMBODIMENTS The principles of the variable-key type search system for, and variable-key type search method of, implementing a Random Access Memory (RAM)-Based Binary CAM and a RAM-Based Range Content Addressable Memory (RCAM), according to the present invention, may be better understood with reference to the drawings and the accompanying description. Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not limited in its application to the details of construction and the arrangement of the components set forth in the following description or illustrated in the drawing. The invention is capable of other embodiments or of being practiced or carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting. 1. RAM-Based Binary CAM or RCAM—Basic Concepts One basic concept underlying the RAM-Based Binary CAM or RAM-Based RCAM is maintaining an ordered key list. This means that the key entries are stored in such a way that:
Although the RAM-Based Binary CAM or RCAM may be implemented using any of the alternatives described above, we shall limit our discussion to the following exemplary cases:
FIG. 1 depicts a TDA of M columns by N rows. The rows are sequenced from top to bottom and indexed with an integer index j, where 0≦j≦N-1. The columns are sequenced from left to right and indexed with an integer index i, where 0≦i≦M-1. The occupied key entry locations are shadowed with light gray. The empty locations are blank. A key located in column i and row j has an integer value Ki,j. The lowest key value K0,0 resides in row 0 and column 0. The highest key value KU,V resides in row V and column U. The TDA parameters are: The RAM organization is depicted in FIG. 2. The RAM parameters are: Then, each w-bit wide RAM word contains M key words, that is, The RAM-Based Binary CAM contains two TDAs or lists, a key list and an associated data list. Each key entry Ki,j has a corresponding associated data entry Di,j, as depicted in FIG. 3. Since the Binary CAM stores an ordered list of single integer keys, a key search in results in an exact match and a straightforward access to the corresponding associated data. The RAM-Based RCAM includes additionally an associated boundary type list, where each associated boundary type entry Mi,j corresponds to the key entry Ki,j as shown in FIG. 4. The RCAM stores a list of key entries that represent boundaries of associative ranges, so that a key search results in a matching range, and the retrieval of the associated data and boundary type that corresponds uniquely to this range. The associated boundary type determines the validity of the matching range and the associated data. The entries of the key list, associated data list and associated boundary type list (for an RCAM) are always kept in a compact and sequential form (monotonically increasing or decreasing), and perfect correspondence, by means of efficient Insert and Remove algorithms. 2. Variable Key Type Search Engine—Basic Architecture and Operations One basic component that promotes the flexibility and efficiency of the inventive Variable Key Type Search Engine is a tag field indicator for indicating:
Although the Variable Key Type Search Engine may be implemented in any of the alternatives described above, we shall discuss the following case:
FIG. 5 depicts a generic key field and then three key entries containing 1, 2 and 4 key fields. The data provided in a key entry with several key fields is distributed in the key data fields with the most significant bits (MSBs) in the leftmost key field and the least significant bits (LSBs) in the rightmost key field. The tag fields are identical for all the key fields in the same key entry. The key entry parameters are: FIG. 6 depicts the width relations of three key entries containing 1, 2 and 4 key fields. The width parameters of the key entry and key field are: The width or number of bits of a key field is the sum of the number of bits of its tag and key data fields: The widths of the key field, tag field and key data field, wf, wt and wb, respectively, are fixed. The number of bits in a key entry is a multiple of the number of bits in its key fields: Since the key entries must fill every TDA row (corresponding to a RAM word), the number of bits n of any key entry, except the smallest key entry (for a one key field), must be a multiple of the number of bits of the contiguous smaller key entry, and the sum of bits of all the key entries in every row must equal the RAM word width: ##EQU1## where w is the width of the RAM word, K is the number of key entries in a row and nt is the number of key fields in a specific key entry. If all the key entries in a row have the same number n of key fields, then: Thus, since wkn is a multiple of the number of bits in any key fields, including the largest key entry, the total number of bits in a row is clearly a multiple of the number of bits in the largest key entry. FIG. 7 depicts a TDA partially filled with contiguous blocks of key entries of decreasing width starting with the largest key entries at the first array index (0,0). The key entries in these blocks contain 4, 2 and 1 key fields, and are shown in alternate gray and white colors, and with different filling patterns for the key entries with different widths. The width of each key entry, which depends on the number of key fields integrated in it, is determined by the two more significant bits of the tag field. Since, in this particular example, the values of the RSE key entries are stored in ascending order, the more significant bits of the tag field must be specified so that larger key entries are represented by smaller numbers. (If the TDA were arranged with contiguous blocks of key entries of increasing width, the more significant bits of the tag field would be specified so that smaller key entries are represented by smaller numbers). The LSB of the tag field indicates whether the key data field corresponds to a single integer (leading to an Exact Match in a Binary CAM) or to a range of integers (leading to a Range Match in an RCAM). In this way, the key entries of the same width are grouped according to their type. Within these groups, the key entries are stored in contiguous ascending order according to the values of the key data fields starting from their MSBs. Thus, this tagging method allows, by storing contiguous blocks of key entries in ascending order, a Search operation for lookups, and Insert and Remove operations for the maintenance of the TDA in order, using the same procedures as in RAM-Based Binary CAMs and RAM-Based RCAMs described in PCT Patent Application Serial No. IL01/00458 and PCT Patent Application Serial No. IL01/01025, respectively. In a preferred implementation, the structures of the Associated Data TDA and Associated Boundary Type TDA (for RAM-Based RCAM) correspond identically to that of the Key TDA. In this case, when a key entry is composed of more than one key field, the corresponding associated data entry and the associated boundary type entry (for RAM-Based RCAM) are also composed of the same number of fields; however, these fields contain data only and no tags. All the fields in the associated data and boundary type entry can be used to store data; if only one field suffices, the field corresponding to the more significant bits may be used. If all the key entries in a device are known to have the same length, an alternative implementation may be used with the associated data and associated boundary type entries having each one data field only. The storage of Ipv4 CIDR, Multicast and IPv6 CIDR addresses requires 32, 64 and 128 bits, respectively. Key entries with 1, 2 and 4 key data fields of 32 bits can be used for this purpose. If 32 bits are assigned to the key field and 3 bits to the tag field, then a field key consists of 35 bits, because: Key entries with 1, 2 and 4 field keys, consisting of 35, 70 and 140 bits, respectively, can be used to store Ipv4, Multicast and IPv6 CIDR addresses: In order to fill a TDA row, the RAM word width must be a multiple of the number of bits in the largest key entry, i.e., a multiple of 140. Thus, any RAM having words with a number of bits equal to 140, 280, 420, 560, etc., can serve for this purpose. As an example, a single Range Search Engine (RSE) or multiple RSEs integrated into a single Forwarding Information Base (FIB) implemented with such RAMs can be used to store six key types several key types:
|
Same subclass Same class Consider this | ||||||||||