Abstract:
A method and device for arranging and storing data in a memory and for extracting the data from the memory in response to an input key, the method including the steps of: (a) providing a device including: (i) a memory having a plurality of module pairs, each of the module pairs having: (A) a key module including a first array of cells, the first array having at least two dimensions and having rows and columns, the first array containing a plurality of keys, each of the cells having a unique address and being accessible via an input key, the keys within each of the key modules being arranged in monotonic order, and (B) an associated data module including 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, associated with the keys, wherein the memory is designed and configured such that each of the data entries is associated with a particular one of the keys, and (ii) processing means, and (b) performing a processing operation, using the processing means on each the key module in parallel.

Description:
FIELD AND BACKGROUND OF THE INVENTION  
         [0001]    The present invention relates to the field of Content Addressable Memory (CAM) and, more particularly, to a system for, and method of, implementing a RAM-Based Binary CAM and a RAM-Based Range Content Addressable Memory (RCAM).  
           [0002]    Conventional memory arrays such as Random Access Memories (RAMs) store and retrieve data units indexed by their address.  
           [0003]    Content Addressable Memories (CAMs) are associative memories that contain Key Entries and Associated Data Entries that uniquely correspond to the Key Entries. A CAM stores the key entries and the associated data entries at any available location and retrieves the Associated Data for any key that is submitted to be searched in the CAM.  
           [0004]    A Binary CAM stores an ordered list of single integer key entries and a corresponding list of their associated data. An RCAM stores instead a list of key entries that represent range boundaries and a list of associated data that correspond uniquely to these ranges. A key search in a Binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range. The RCAM also stores a list of associated boundary type entries that determine the validity of the corresponding ranges. This list can be stored in conjunction with the list of associated data or in a separate array.  
           [0005]    A successful approach to utilizing RAM-based technology on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00458, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage and extraction of data 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 in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond to these key entries are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array and a match signal, “True” or “False”, is also output with the retrieved associated data entry to indicate whether the associated data is valid or not. 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 arrays of the key entries and their associated data are kept in perfect sequence by Insert and Remove algorithms.  
           [0006]    The main innovations introduced by this technology include:  
           [0007]    Surrounding the RAM structure with search logic in the RAM periphery: The number of comparator units is proportional to the RAM periphery length rather than to the RAM area. This results in dramatic savings in the amount of comparator logic, while keeping the memory cell extremely efficient in density and speed. The CAM implementation overhead is typically less than 15%. Therefore, the CAM density obtained with this method is asymptotically close to the comparable size in RAM technology.  
           [0008]    Fast Search Algorithm: The surrounding logic in conjunction with the RAM structure performs searches with the same throughput as a comparable RAM, and twice the latency. (Theoretically, single clock latency may be accomplished, but pipelining may yield a better throughput and a similar latency if measured on absolute time scale (nano-seconds).  
           [0009]    Continuous “Housekeeping” Procedure: Unlike CAMs of the prior art, these CAM devices keep the “house in order”. That is, the deletion of keys does not leave “holes” in the list, which would otherwise require “housekeeping” operations on the managing processor section. Similarly, the addition of new keys keeps the list in a perfect sequence. This “housekeeping” procedure takes longer than the search, but is much faster than required by the system. The overhead associated with the Key List update is significantly shorter when compared with the time taken by the processor to do the housekeeping. This superior performance is due to the efficient RAM and Insert/Remove hardware architecture, which execute very time-efficient algorithms.  
           [0010]    In my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00595, 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.  
           [0011]    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.  
           [0012]    A successful approach to utilizing RAM-based technology on an RCAM in a similar way that on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/01025, which is incorporated by reference for all purposes as if fully set forth herein. 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.  
           [0013]    The RCAM 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.  
           [0014]    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.  
           [0015]    In many cases, the relatively slow speed of the Insert and Remove operations hampers the performance of the system. It would, therefore, be highly advantageous to have a system for, and a method of significantly improving the speed of the Insert and Remove algorithms, while maintaining the arrays of the key entries and their associated data in perfect sequence.  
         SUMMARY OF THE INVENTION  
         [0016]    The present invention relates to a device for binary CAMs and for RCAMs having multiple module content addressable memories, and a method of utilizing the device.  
           [0017]    According to the teachings of the present invention there is provided, a method for arranging and storing data in a memory and for extracting the data from the memory in response to an input key, the method including the steps of: (a) providing a device including: (i) a memory having a plurality of module pairs, each of the module pairs having: (A) a key module including a first array of cells, the first array having at least two dimensions and having rows and columns, the first array containing a plurality of keys, each of the cells having a unique address and being accessible via an input key, the keys being arranged in monotonic order, and (B) an associated data module including 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, associated with the keys, wherein the memory is designed and configured such that each of the data entries is associated with a particular one of the keys, and (ii) processing means, and (b) performing a processing operation, using the processing means on each key module in parallel.  
           [0018]    According to yet another aspect of the present invention there is provided a multiple module device for storing arranged data in a memory, and for extracting the data therefrom, the device including: (a) a memory having a plurality of module pairs, each of the module pairs having: (i) a key module including a first array of cells, the first array having at least two dimensions and having rows and columns, the first array containing a plurality of keys, each of the cells having a unique address and being accessible via an input key, the keys within each of the key modules being arranged in monotonic order, and (ii) an associated data module including 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, associated with the keys, wherein the memory is designed and configured such that each of the data entries is associated with a particular one of the keys, and (b) processing means designed and configured to search, in response to the input key, the plurality of keys within each key module, so as to identify a match.  
           [0019]    According to further features in the described preferred embodiments, the keys within each key module define a module value span, and the first modules are arranged in monotonic order with respect to each module value span.  
           [0020]    According to still further features in the described preferred embodiments, the multiple module device further includes: (c) sorting means for arranging the keys in monotonic order within the first array.  
           [0021]    According to still further features in the described preferred embodiments, the memory includes a memory selected from the group of memories consisting of: SRAM, DRAM, CCD, ROM, EPROM, E 2 PROM, Flash-memory, and Magnetic-media.  
           [0022]    According to still further features in the described preferred embodiments, the memory is a random access memory (RAM).  
           [0023]    According to still further features in the described preferred embodiments, each of the associated data entries has a unique pair of row and column indices for association with a unique pair of row and column indices of a particular one of the keys.  
           [0024]    According to still further features in the described preferred embodiments, the keys represent range boundary information.  
           [0025]    According to still further features in the described preferred embodiments, the multiple module device further includes range validity information for each of the range boundary information, the range validity information stored within the memory.  
           [0026]    According to still further features in the described preferred embodiments, the range boundary information is a single range-boundary value.  
           [0027]    According to still further features in the described preferred embodiments, the range validity information is disposed in the first array, each range validity information corresponding to a particular single range-boundary value.  
           [0028]    According to still further features in the described preferred embodiments, the range validity information is stored in a separate array.  
           [0029]    According to still further features in the described preferred embodiments, the range validity information is disposed in the second array, each range validity information corresponding to a particular one of the associated data entries.  
           [0030]    According to still further features in the described preferred embodiments, each key module includes a first register for holding a first key and a second register for holding a last key, the first key and the last key representing extreme values of the module value span, wherein the first register and the second register are designed and configured to produce register output signals.  
           [0031]    According to still further features in the described preferred embodiments, each key module includes at least one comparator for comparing an index of a key having an extreme value of the module value span with an index of a key disposed in a last position of the key module.  
           [0032]    According to still further features in the described preferred embodiments, the processing means include: i) a row locator containing at least a first comparator, for comparing contents of an end column of the first array with the input key.  
           [0033]    According to still further features in the described preferred embodiments, the processing means further include: ii) a column locator containing at least a second comparator, for comparing contents of the row with the input key.  
           [0034]    According to still further features in the described preferred embodiments, each of the module pairs further includes: (iii) a tristate buffer operatively connected to the key module and to the associated data module.  
           [0035]    According to still further features in the described preferred embodiments, each of the module pairs further includes an associated boundary type module.  
           [0036]    According to still further features in the described preferred embodiments, the associated boundary type module is operatively connected to a tristate buffer.  
           [0037]    According to still further features in the described preferred embodiments, the output of the tristate buffer is enabled by a match signal received from the key module.  
           [0038]    According to still further features in the described preferred embodiments, the device further includes an associated boundary type module including a third array of cells, the third array having at least two dimensions, and a plurality of data entries containing range validity information, each of the data entries associated with a particular one of the keys.  
           [0039]    According to still further features in the described preferred embodiments, the processing operation includes a Search operation.  
           [0040]    According to still further features in the described preferred embodiments, the processing operation includes an Insert operation.  
           [0041]    According to still further features in the described preferred embodiments, the processing operation includes a Remove operation.  
           [0042]    According to still further features in the described preferred embodiments, the processing operation includes an Update operation.  
           [0043]    According to still further features in the described preferred embodiments, the processing operation includes a comparing operation.  
           [0044]    According to still further features in the described preferred embodiments, the plurality of keys includes range boundary information, and the comparing operation includes comparing a value of the input key with the range boundary information to determine a particular range to which the input key belongs.  
           [0045]    According to still further features in the described preferred embodiments, a row or column containing the range boundary information is selected by the following steps: (i) performing a comparison between the range boundary information and the input key to produce a result, and (ii) identifying a row or column in which the result undergoes a change in inequality status.  
           [0046]    According to still further features in the described preferred embodiments, the method further includes the step of: (iii) selecting the row or column.  
           [0047]    According to still further features in the described preferred embodiments, the method further includes the steps of: (c) identifying within a particular key module, a row into which a new key should be inserted and selecting the row, and (d) inserting the new key into an insertion location in the particular key module while maintaining the monotonic order within each of the key modules.  
           [0048]    According to still further features in the described preferred embodiments, the identifying in step (c) includes a comparison of the new key with at least one end key of the plurality of keys, the end key disposed in an end column in the particular key module.  
           [0049]    According to still further features in the described preferred embodiments, the identifying in step (c) includes examining all the key modules in parallel.  
           [0050]    According to still further features in the described preferred embodiments, the method further includes the step of: (e) checking, before step (d), that the particular key module is devoid of a key of identical value to the new key.  
           [0051]    According to still further features in the described preferred embodiments, the method further includes the step of: (e) identifying a column index for the new range boundary value by performing a comparison of the new range boundary value with the range boundary information disposed in the row.  
           [0052]    According to still further features in the described preferred embodiments, the maintaining of the monotonic order is achieved by shifting a content of each cell disposed after the insertion location respectively, by one position, thereby completely filling at least a portion of the first array with the keys.  
           [0053]    According to still further features in the described preferred embodiments, the data associated with the new key is inserted into the associated data module of the module pair containing the particular key module.  
           [0054]    According to still further features in the described preferred embodiments, the method further includes the steps of: (c) identifying within a particular key module of the key modules, a row containing a key for removing, and selecting the row, and (d) removing the requisite key from a removal location in the particular key module while maintaining monotonic order within each of the key modules.  
           [0055]    According to still further features in the described preferred embodiments, the method further includes the steps of: (c) identifying within a particular key module, a key that needs to be removed, and selecting the row, and (d) removing this key from a removal location in the particular key module while maintaining monotonic order within each of the key modules. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0056]    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.  
         [0057]    In the drawings:  
         [0058]    [0058]FIG. 1 is a schematic illustration of a 2-Dimensional M-column by N-row memory array;  
         [0059]    [0059]FIG. 2 is a schematic illustration of the correspondence between the 2-Dimensional key list and the associated data list for a binary CAM;  
         [0060]    [0060]FIG. 3 is a schematic illustration of the correspondence between the 2-Dimensional key list, the associated data list and the associated boundary type list for an RCAM;  
         [0061]    [0061]FIG. 4 shows essential components added to the ζ-th key module;  
         [0062]    [0062]FIG. 5 shows essential components added to the ζ-th associated data module;  
         [0063]    [0063]FIG. 6 shows the structuring of a binary CAM from multiple modules;  
         [0064]    [0064]FIG. 7 shows the structuring of an RCAM with additional associated boundary type modules;  
         [0065]    [0065]FIG. 8 a  is a search algorithm flowchart for a single module in a binary CAM;  
         [0066]    [0066]FIG. 8 b  is a search algorithm flowchart for multiple modules in a binary CAM of the present invention, in which the search procedure is performed concurrently on all the modules;  
         [0067]    [0067]FIG. 9 a  is a search algorithm flowchart for a single module in an RCAM;  
         [0068]    [0068]FIG. 9 b  is a search algorithm flowchart for multiple modules in an RCAM of the present invention, in which the search procedure is performed concurrently on all the modules;  
         [0069]    [0069]FIG. 10 a  is a flowchart for the search algorithm preceding an insert or remove procedure for a single module in a binary CAM or RCAM;  
         [0070]    [0070]FIG. 10 b  is a flowchart for the search algorithm preceding an insert or remove procedure for a multiple-moduled binary CAM or RCAM of the present invention, in which the search procedure is performed concurrently on all the modules;  
         [0071]    [0071]FIG. 11 a  is a flowchart of the insert algorithm for a single module in a binary CAM or RCAM;  
         [0072]    [0072]FIG. 11 b  is a flowchart of the insert algorithm for a multiple-moduled binary CAM or RCAM of the present invention, in which the insert procedure is performed concurrently on all the modules;  
         [0073]    [0073]FIG. 12 a  is a flowchart of the remove algorithm for a single module in a binary CAM or RCAM, and  
         [0074]    [0074]FIG. 12 b  is a flowchart of the remove algorithm for a multiple-moduled binary CAM or RCAM of the present invention, in which the insert procedure is performed concurrently on all the modules. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0075]    The present invention relates to a device for binary CAMs and for RCAMs having multiple module content addressable memories, and a method of utilizing the device.  
         [0076]    The principles and operation of the multiple module content addressable memories of the present invention may be better understood with reference to the drawings and the accompanying description.  
         [0077]    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.  
         [0078]    In my co-pending, unpublished PCT Patent Application Serial No. IL01/00458 and in my co-pending, unpublished PCT Patent Application Serial No. IL01/01025, methods are described for implementing a Binary CAM and an RCAM, respectively, using a RAM structure surrounded by search logic in the RAM periphery. The above-referenced applications also teach the running of a fast Search algorithm, and the maintaining of key lists and their associated data in perfect sequence by efficient Insert and Remove algorithms.  
         [0079]    The multiple module implementations of the present invention are based on a method of interconnection of multiple Binary CAM or RCAM modules into a single Binary CAM or RCAM device, respectively. This method allows the division of the Binary CAM or RCAM structure into partial modules, each containing a small number of rows. As described hereinbelow, the Insert and Remove throughputs are inversely proportional to the number of rows in the CAM or RCAM. Thus, the use of the smaller partial modules significantly speeds up the Insert and Remove operations in these devices.  
         [0080]    The main concepts and principles of operation of the RAM-Based RCAM are very similar to those of the RAM-Based Binary CAM. The main difference is that whereas the Binary CAM stores an ordered list of single integer keys and a corresponding list containing associated data, the RCAM stores a list of key entries that represent boundaries of associative ranges and a list containing associated data that correspond uniquely to these ranges. A key search in a Binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range.  
         [0081]    The RCAM also stores a list of associated boundary type entries that determine the validity of the corresponding ranges. This list can be stored in conjunction with the list of associated data or in a separate array.  
         [0082]    Another difference between the Binary CAM and the RCAM is reflected in different (although quite similar) Search procedures for the two devices, which yield similar throughput performance. The Insert and Remove operations are practically identical for both devices. Thus, concerning the efficiency of operation and throughput, there are no basic differences between the two devices, and whatever is written below for the RAM-Based Binary CAM holds for the RAM-Based RCAM, unless indicated otherwise.  
         [0083]    Throughput Considerations  
         [0084]    It was demonstrated in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00458 that the Search throughput is independent of the Binary CAM dimensions and is given by the following formula:  
         f   S     =     1   T                           
 
         [0085]    where  
         [0086]    f S  is the search throughput, and  
         [0087]    T is the clock cycle time.  
         [0088]    The above-mentioned patent application also discloses a method for quick insertion and removal of keys and their associated data from the CAM. It was shown therein that the Insert and Remove operations require a time of approximately:  
         t E =t R ≅2·( N+ 1)· T+t   S ,  
         [0089]    where  
         [0090]    t E  is the Insert time,  
         [0091]    t R  is the Remove time,  
         [0092]    t S  is the Search time for Insert or Remove operations,  
         [0093]    N is the number of rows in a block.  
         [0094]    For a large number of rows, N&gt;&gt;1, and a relatively short Search time compared to the Insert or Remove time, 2·(N+1)·T&gt;&gt;t S , the above formula becomes:  
         f   E     =       f   R     ≅       1     2   ·   N       ·     f   S                               
 
         [0095]    This formula demonstrates that although the Search throughput is independent of the Binary CAM dimensions, the Insert and Remove throughputs are inversely proportional to the number of rows in the CAM.  
         [0096]    Although the search speed is the most important parameter, it is clear that the speed performance in the insertion and removal of keys and associated data in the Binary CAM (plus associated boundary type entries in the RCAM) becomes the limiting factor for large CAM configurations.  
         [0097]    The invention disclosed herein is designed to speed up the Insert and Remove operations. This is achieved by breaking down the Binary CAM (or RCAM) structure into smaller modules, each containing a small number of rows. These modules are integrated to form the Key List and Associated Data List (along with the Associated Boundary Type List in the RCAM).  
         [0098]    Since all the modules perform Insert or Remove operations simultaneously, the time required to perform an Insert or Remove operation in a Binary CAM (or RCAM) is the same as that required for a single module, so it is determined by the number of rows in a module rather than the total number of rows in the Binary CAM (or RCAM).  
         [0099]    [0099]FIG. 1 depicts a TDA composed 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 K 0,0  resides in row 0 and column 0. The highest key value K U,V  resides in row V and column U.  
         [0100]    The RAM-Based Binary CAM contains two TDAs or lists, Key List and Associated Data List. Each key entry Ki,j has a corresponding Associated Data entry Di,j as depicted in FIG. 2. Since the Binary CAM stores an ordered list of single integer keys, a successful key search results in an exact match and a straightforward access to the corresponding associated data.  
         [0101]    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. 3. 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.  
         [0102]    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 (monotonously increasing or decreasing), and perfect correspondence, by means of consistent Insert and Remove algorithms.  
         [0103]    An Insert operation starts with a search for the location index of the key to be inserted in the Key List. In a Binary CAM, the key and the associated data having this index are then inserted in the Key List and the Associated Data List, respectively. In an RCAM, in addition, the associated boundary type entry having the same index is inserted in the Associated Boundary Type List.  
         [0104]    Similarly, a Remove operation starts with a search for the location index of the key to be removed from the Key List. Then, the key and the associated data having this index are removed from the Binary CAM. In an RCAM, the associated boundary type entry having the same index is removed as well.  
         [0105]    These principles must be preserved when the Binary CAM and the RCAM are implemented using multiple modules; that is, a key listed with a certain index in any module, must have a corresponding associated data entry (and also an associated boundary type entry for an RCAM) listed with the same index in the same module.  
         [0106]    Multiple-module deployment while preserving these principles implies the ability to transfer, to an adjacent module, keys and their associated data (plus associated boundary type entries for RCAM systems) that are disposed in the boundary locations of each module, during both Insert and Remove operations:  
         [0107]    Insert operation. When a key is inserted in a certain location in any module, all the keys having a larger value must be shifted one location forward. If the module is fully occupied, the highest-index key and the associated data corresponding to this key (along with the boundary type entry for an RCAM system) are shifted one location forward, which is the first location in the succeeding module.  
         [0108]    Remove operation. When a key is deleted at a certain location in any module, all the keys having a larger value must be shifted one location backward. If the module is fully occupied, the highest-index key and the associated data corresponding to this key (along with the boundary type entry for an RCAM system) are replaced by a key and the associated data (along with the boundary type entry) shifted from the first location in the succeeding module.  
         [0109]    The module operation depends on the condition of its adjacent modules. Therefore, each module must be continuously informed whether the adjacent modules are fully occupied or entirely empty.  
         [0110]    The Key List, Associated Data List and Associated Boundary Type List (for an RCAM) are each implemented using partial modules containing a small number of rows. These modules are termed Key Modules, Associated Data Modules and Associated Boundary Type Modules. The Binary CAM (or RCAM) is thus broken down into the two types of modules (or three for the RCAM) defined above. The modules of the same type are integrated to form the Key List and the Associated Data List (and for the RCAM, the Associated Boundary Type List).  
         [0111]    The modules of each type are arranged in sequence, so that, in reference to any module labeled ζ, the preceding module (ζ−1) contains smaller keys (i.e., keys having smaller values), whereas the succeeding module (ζ+1) contains larger keys.  
         [0112]    [0112]FIG. 4 depicts the essential components added to the ζ-th Key Module in the Binary CAM, according to the present invention. The components added to the Key Module are:  
         [0113]    K 0,0   ζ  Register: This register ( 301 ) holds K 0,0   ζ , the first key in the module, as a separate, readily accessible value. The K 0,0   ζ  value is available as the register output signal and is labeled K min   ζ  because it is the minimum key value stored in the ζ-th module. K min   ζ  is used when performing a Remove operation in a preceding module (that holds smaller keys) and is loaded to the highest location in this module. The register value is updated during an Insert or Remove operation via the K min   ζ  line when the first row in the module is updated.  
         [0114]    K U,V   ζ  Register: This register ( 302 ) holds K U,V   ζ , the last key in the module, as a separate, readily accessible value. The K U,V   ζ  value is available as the register output and labeled K max   ζ  because it is the maximum key value stored in the ζ-th module. K max   ζ  is used when performing an Insert operation in this module, and is loaded to the first position of the succeeding module (that holds larger keys) whenever the ζ-th module is full (U=M−1 and V=N−1). The register value is updated during an Insert or Remove operation via the K in   ζ  line when the V-th row in the module is updated.  
         [0115]    Up/Down Counter: This counter ( 303 ) holds the location index of the current highest key in the module. After Reset, this counter holds an “All Ones” value. The first Insert operation actively performed in the module results in the counter wrap-around and in “All Zeros” state, pointing to row 0 and column 0 (U=0 and V=0). The ζ least significant output bits of the counter constitute the column index number U, whereas the φ most significant output bits constitute the row index number V.  
         [0116]     ζ−1&lt;log 2  M≦ζ, where M is the number of columns and Σ is a positive integer, and  
         [0117]     φ−1&lt;log 2  N≦φ, where N is the number of rows and φ is a positive integer.  
         [0118]     The Up/Down Counter is increased by 1 when the Insert signal Ins ζ  is “1” and is decreased by 1 when the Remove signal Rmv ζ  is “1”.  
         [0119]     The Set signal is generated when the module is reset and the Up/Down counter is emptied. This happens when the Up/Down Counter is “All Zeros” and then Rmv ζ  becomes “1”.  
         [0120]    Em (Empty Flag) Flip-Flop: This flip-flop ( 304 ) indicates that the module is empty (Em ζ =“1”) when it is set to “1”; this takes place when the Set signal is “1”. The flip-flop is reset to “0” when the first active Insert signal Ins ζ  becomes “1”.  
         [0121]    U and V Comparators: These pair of comparators ( 305  and  306 ) compare the index of the largest key (U,V) of the module with the index of the last position (M−1, N−1) of the module. If U=M−1 and V=N−1, the comparators indicate that the module is full.  
         [0122]    Fl (Full) Gate: This AND gate ( 307 ) indicates that the module is full (Fl ζ =“1”) when the comparators show that the module is full and the Em flip-flop indicates that the module is not empty (Em ζ =“0”). This last signal is necessary to rule out an Fl ζ =“1” indication when the Up/Down Counter holds an “All Ones” value (after Reset) and yet the module is empty.  
         [0123]     The input signals applied to the Key Module are:  
         [0124]    The Ins ζ  signal is “1” whenever there is an Insert operation and the new key is inserted in this module or in any of the succeeding modules (that hold larger keys).  
         [0125]    The Rmv ζ  signal is “1” whenever there is a Remove operation and the key is removed from this module or from any of the succeeding modules (that hold larger keys).  
         [0126]    The K in   ζ  signal is applied to the K 0,0   ζ  register during an Insert or Remove operation when the first row in the module is updated and to the K U,V   ζ  register when the last row value is updated.  
         [0127]    [0127]FIG. 5 shows the essential components added to the ζ-th Associated Data Module (and also to the ζ-th Type List Module). Since the operations performed in this module correspond to those performed in the Key Module, it is synchronized and controlled by the same control signals as the Key Module. When the Key List inserts and deletes keys, the Associated Data List simultaneously inserts and deletes the corresponding associated data entries. Module chaining requires the boundary values to be readily available. These values are kept in two special registers:  
         [0128]    D 0,0   ζ  Register: This register holds the first key entry D 0,0   ζ  in the Associated Data Module, as a separate, readily accessible value. The D 0,0   ζ  value is available on the register output and is labeled Δ min   ζ  because it is the minimum key value stored in the ζ-th module. The D 0,0   ζ  value (Δ min   ζ ) is used when performing a Remove operation in a preceding module (that holds smaller keys) and is loaded to the highest location of this module. The register value is updated during an Insert or Remove operation via the D in   ζ  line when the first row is updated.  
         [0129]    D U,V   ζ  Register: This register holds the highest key entry D U,V   ζ  in the module, as a separate, readily accessible value. The D U,V   ζ  value is available on the register output and is labeled Δ max   ζ  because it is the maximum key value stored in the ζ-th module. The D U,V   ζ  value (Δ max   ζ ) is used when performing an Insert operation in this module, and is loaded to the first position of the succeeding module (that holds larger keys) whenever the ζ-th module is full (U=M−1 and V=N−1). The register value is updated during an Insert or Remove operation via the D in   ζ  line when the V-th row in the module is updated.  
         [0130]    The Associated Boundary Type Module (in the Associated Boundary Type List of an RCAM) is substantially identical to the Associated Data Module and may be understood by referring to FIG. 5 and to the associated description provided hereinabove.  
         [0131]    Multi-Module Binary CAM and RCAM Architectures  
         [0132]    A Binary CAM contains two arrays or lists, a Key List and an Associated Data List, each array consisting of P modules designated Key Modules and Associated Data Modules, respectively, as described hereinabove. An RCAM contains, additionally, P modules designated Associated Boundary Type Modules. Alternatively, the Associated Boundary Type data can be stored within the Key Modules or within the Associated Data Modules, as disclosed in my co-pending, unpublished PCT Patent Application Serial No. IL01/01025.  
         [0133]    Each Key List, Associated Data List and Associated Boundary Type List is a 2-dimensional array having M columns and N rows.  
         [0134]    The total amount of Key List entries in the CAM (or RCAM) is:  
         
       C=P·M·N  
     
         [0135]    where C is defined as the CAM capacity.  
         [0136]    [0136]FIG. 6 illustrates how to structure a Binary CAM from multiple Key and Associated Data Modules. An RCAM is structured in a similar way with additional Associated Boundary Type Modules that are identical and connected in parallel to the Associated Data Modules). The Associated Boundary Type Modules are shown in FIG. 7.  
         [0137]    The added components required for each Binary CAM (or RCAM) module to enable this module to perform Search, Insert and Remove operations in an independent fashion and concurrently with the other modules are described in conjunction with FIGS.  8 - 12  hereinbelow.  
         [0138]    Each module ζ in the Key List (excluding Key_Module 0 ) receives as inputs the maximum value stored in the preceding module (ζ−1), K max   ζ−1  and the signal Fl ζ−1  that indicates whether this module is full. Each module ζ (excluding Key_Module P−1 ) also receives the minimum key value stored in the succeeding module (ζ+1), K min   ζ−1 , and the signal Em ζ+1  that indicates whether this module is empty.  
         [0139]    The Fl P−1  signal of the last module (which holds the largest keys) also indicates whether the last module is full. If the last module is full, then all the CAM entries are occupied and the entire CAM is full:  
         Full CAM ≡Fl P−1    
         [0140]    The Em 0  signal of the first module (which holds the smallest keys) indicates whether this first module is empty. If the first module is empty, then the entire CAM is empty.  
         Empty CAM ≡Em 0    
         [0141]    Each module ζ in the Associated Data List (except for AD_Module 0 ) receives the last value stored in the preceding module (ζ−1), D max   ζ−1 . Each module ζ (excluding AD_Module P−1 ) also receives the minimum associated data value stored in the succeeding module (ζ+1), D min   ζ+1 .  
         [0142]    In an RCAM, each module ζ in the Associated Boundary Type List (except for AB_Module 0 ) receives the last value stored in the preceding module (ζ−1), M max   ζ−1 . Each module ζ (excluding AB_Module P−1 ) also receives the minimum boundary type value stored in the succeeding module (ζ+1), M min   ζ+1 .  
         [0143]    Whenever a submitted key is searched in the entire Binary CAM or RCAM, each module in the Key List performs its Search operation independently and concurrently with the other modules. The Search operation starts by comparing the submitted key with the first and last key entries of each Key Module, and then proceeds to search within the specific module that may include the submitted key. If the searched key is listed in the Binary CAM or is contained in a range in the RCAM, it will only be found in one module, say the i-th module, and only this module will issue a match signal M i =“1” (0≦i&gt;P−1) and the location index of the searched key.  
         [0144]    The location index is used to retrieve the respective associated data from module AD_Module k  in the Associated Data List. This data is sent to the corresponding Tristate Buffer TB i . The TB i  buffer output is enabled by the respective match signal M i . Since the match signal of only one module is active, only one Tristate buffer output is enabled on the Data bus and issues the respective associated data. If there is no match, none of the modules will issue a match signal.  
         [0145]    The Binary CAM (or RCAM) provides the associated data that corresponds to the searched key according to the following formula:  
       Data   =         ⋃     i   =   0         P   -   1              M   i     ·     AD   i                               
 
         [0146]    In a Binary CAM, the match signal is given by the following formula:  
         Match   CAM     =         ⋃     i   -   0         P   -   1            M   i                             
 
         [0147]    In an RCAM, the boundary type entry is obtained in a procedure similar to that used for getting the associated data. The location index issued by the k-th module where the searched key is found is used to retrieve the boundary type from module AB_Module i  in the Associated Data List. The respective Tristate Buffer TBi, enabled by the match signal M i , issues the corresponding boundary type entry.  
         [0148]    The RCAM match signal provides the boundary type that corresponds to the searched key according to the following formula:  
         Match   CAM     =         ⋃     i   -   0         P   -   1              M   i     ·     AB   i                               
 
         [0149]    Thus, the RCAM match signal depends on the boundary type, which determines the validity of the range that contains the searched key. (The main properties and operations of key ranges have been described in my co-pending, unpublished PCT Patent Application Serial No. IL01/01025).  
         [0150]    If Match CAM =“0” or Match RCAM =“0” (no match), the associated data of the Binary CAM or RCAM has no meaning. In this case, the Data output is tristated.  
         [0151]    [0151]FIG. 8 a  and FIG. 9 a  show flowcharts of Search algorithms for a single i-th module in a Binary CAM and an RCAM, respectively.  
         [0152]    The i-th Key Module is first checked for emptiness. If it is empty (Em i =“1”), the Search is terminated except for handling the output of the match signal Mi and the associated data.  
         [0153]    If the module is not empty, a search is performed as described, for the Binary CAM, in my co-pending, unpublished PCT Patent Application Serial No. IL01/00458. If the Search operation is successful, it results in a match, M i =“1”, which indicates a meaningful associated data value AD i  in the Associated Data Module. For the RCAM, a successful search also yields a meaningful boundary type value AB i . This search is described in detail in my co-pending, as yet unpublished U.S. patent application Ser. No. 09/779,941, which is incorporated by reference for all purposes as if fully set forth herein.  
         [0154]    The Search operation in the i-th module is completed with the output of the M i , AD i  and AB i  values.  
         [0155]    [0155]FIG. 8 b  shows the search performed concurrently in all the P modules of the Binary CAM using the algorithm depicted in FIG. 8 a . The Data and Match signals correspond to those of the individual module that contains the searched key. They are obtained by summing up the results of the Search operation performed in all the modules according to the following formulas:  
       Data   =         ⋃     i   =   0         P   -   1              M   i     ·     AD   i                   Match   CAM     =         ⋃     i   -   0         P   -   1            M   i                               
         [0156]    [0156]FIG. 9 b  shows the search performed concurrently in all the P modules of the RCAM using the algorithm depicted in FIG. 9 a . In an RCAM, the Data signal is obtained in the same way as for the Binary CAM. However, the Match signal corresponds to the boundary type of the individual module that contains the searched key, and is obtained using the following sum-up formula:  
         Match   RCAM     =         ⋃     i   -   0         P   -   1              M   i     ·     AB   i                                 
         [0157]    Prior to the key insertion/removal, a Search procedure is performed independently and concurrently in all the Key Modules. The Search procedure starts by comparing the submitted key with the first and last key entries of each Key Module, and then proceeds to search within the specific module that may include the submitted key. The Search procedure determines the position index of the submitted key to be inserted or removed, provided that these operations are allowed. Key insertion is allowed only if the key is not included in the i-th Key Module, whereas key removal is possible only if it is already included in the module (M Exact “1”).  
         [0158]    [0158]FIG. 10 a  shows the flowchart for the Search algorithm for a single i-th module in a Binary CAM or an RCAM. This algorithm is not performed independently but as a part of the Insert or Remove operation.  
         [0159]    If the Search operation precedes an Insert operation and is successful, it provides the position index for the key insertion, and issues the signal M Exact =“0”, which indicates that the submitted key was not previously included in the i-th module. If the Search operation preceding a Remove operation is successful, it provides the position index for the key removal, and issues the signal M Exact =“1”, which indicates that the submitted key was already included in the i-th module.  
         [0160]    [0160]FIG. 10 b  shows the search performed concurrently in all the P modules of the Binary CAM or RCAM using the algorithm depicted in FIG. 10 a.  The overall Match signal is obtained by summing-up the results of the Search operation performed in all the modules according to the following formulas:  
       Match   =         ⋃     i   -   0         P   -   1            M   Exact   i                               
         [0161]    A successful Insert operation can only take place in Match=“0”, meaning that that the submitted key was not previously included in the entire Binary CAM or RCAM. On the other hand, a successful Remove operation must result in Match=“1”, which indicates that the submitted key was already included.  
         [0162]    [0162]FIG. 11 a  shows the flowchart for the Insert operation for a single i-th module in the Binary CAM or RCAM.  
         [0163]    The first module (i=0) ( 1001 ) does not have a preceding module, so that the respective Insert operation circumvents all the steps dealing with the preceding module. However, the first module is usually implemented in the same way as all the succeeding modules by defining the nonexistent preceding module (i=−1) to be full with zeros, so that Fl −1 =“1”, Em −1 =“0” and K max   −1 =0. Then, the Insert algorithm shown in FIG. 11 a  can be simplified, because it does not have to deal separately with the first module.  
         [0164]    The key inserted in any i-th module for i&gt;0 (succeeding the first module) may be either the submitted key (as described in my PCT Patent Application Serial No. IL01/00458), or, alternatively, the largest key in the preceding module (i−1), K max   i=1 .  
         [0165]    The Insert algorithm first checks whether key insertion is relevant for the i-th module. If this module is empty (Em i =“1”) ( 1002 ) and the preceding module (i−1) is not full (Fl i=1 =“0”) ( 1003 ), then the submitted key can only be inserted (if at all) in the preceding module. Assuming that the i-th module is not empty (Em i =“0”) or that the preceding module is full (Fl i =“1”), the submitted key may be inserted in the i-th module provided that it is larger than the highest key value in the preceding module (Key&gt;K max   i−1 ) ( 1004 ) but smaller than the highest key value in the i-th module (Key&lt;K max   i−1 ) ( 1005 ). If the i-th module is full (Fl i =“1”) (1006), then, after the insertion, its largest key K max   i  will be shifted out of this module and inserted in the lowest location (0,0) of the succeeding module (i+1). If the i-th module is not full (Fl i =“0”), then the submitted key will be inserted here ( 1007 ) even if it is larger than its highest key value (Key&gt;K max   i ). Note that the submitted key can be inserted in the i-th module only if the previous Insert location search results in M Exact   i =“0” (no exact match), meaning that the key is not included in this module; otherwise, the Insert operation will not be executed. This search procedure is part of the Insert algorithm.  
         [0166]    If the submitted key is smaller than the largest key in the preceding module (Key&lt;K max   i−1 ) (in step  1004 ) and the preceding module is full (Fl i−1 =“1”) (in step 1003), then the submitted key will be inserted in the preceding module and K max   i−1  will be shifted out and inserted in the lowest location (0,0) of the i-th module ( 1008 ).  
         [0167]    The Insert operation can take place if and only if Match CAM =“0”, meaning that the key to be inserted is not included in the Key List. If the Search operation results in Match CAM =“1”, then the key to be inserted is already included in the Key List, the insertion attempt is considered an error and the Insert operation will not be executed.  
         [0168]    [0168]FIG. 11 b  shows the Insert operation performed concurrently in all the modules of the Binary CAM or RCAM using the algorithm depicted in FIG. 11 a.    
         [0169]    The Insert time is approximately  
           t   E ≅2·( N   m +1)· T+t   S    
         [0170]    where N m  is the number of rows in a single module.  
         [0171]    It can be seen that  
           t   E &lt;&lt;2·( P·N   m +1)· T+t   S    
         [0172]    which is the Insert execution time for a Binary CAM implemented using one undivided array.  
         [0173]    [0173]FIG. 12 a  shows the flowchart for the Remove operation for a single i-th module in the Binary CAM or RCAM.  
         [0174]    The key removed from the i-th module may be either the submitted key (as described in my PCT Patent Application Serial No. IL01/00458), or alternatively the smallest key in the module, K min   i .  
         [0175]    The Remove algorithm first checks whether key removal is relevant for the i-th module. The Remove operation is possible only if the module is not empty (Em i =“0”) (step  1101 ). If the submitted key lies between the lowest and highest key values stored in the i-th module (K min   i &lt;Key≦K max   i ) (steps  1102  and  1103 ), it will be removed from the module (step  1104 ).  
         [0176]    If the submitted key is larger than the highest key value (Key&gt;K max   i ), it can only be removed (if at all) from the succeeding module. Note that the submitted key can be removed from the i-th module only if the previous Remove location search results in M Exact   i =“1” (exact match), meaning that the key is included in this module; otherwise, the Remove operation will not be executed. This search procedure is part of the Remove algorithm.  
         [0177]    If the submitted key is smaller than the lowest value stored in the i-th module (Key&lt;K min   i ) in step  1103 , then the submitted key will be removed from the preceding module (i−1) and K min   i  will be removed from the i-th module and shifted to the highest location (M−1, N−1) in the preceding module (step  1105 ).  
         [0178]    A Remove operation can take place if and only if M CAM =“1”, meaning that the key to be removed is included in the Key List. If the Search operation results in M CAM =“0”, then the key to be removed is not included in the Key List, the removal attempt is considered an error, and the Remove operation will not be executed.  
         [0179]    [0179]FIG. 12 b  shows the Remove operation performed concurrently in all the modules of the Binary CAM or RCAM using the algorithm depicted in FIG. 12 a . The Remove execution time is approximately:  
           t   R ≅2·( N   m +1)· T+t   S    
         [0180]    where N m  is the number of rows in a single module.  
         [0181]    It can be seen that  
           t   R &lt;&lt;2·( P·N   m +1) ·T+t   S    
         [0182]    which is the Remove execution time for a Binary CAM implemented using one undivided array.  
         [0183]    The associated data corresponding to a key included in the Key List can be modified using an Insert operation. However, this is better performed by means of an explicit Update command that states that the key is already listed and must be updated. This command is preferable because it takes only one or two clock cycles on top of the previous Search operation, as compared to the Insert operation, which takes much longer.  
         [0184]    In an RCAM, the Update command is used to modify the Associated Data List and the Associated Boundary Type List for a specific key in the Key List, without changing the number of keys in the Key List. This operation is generally necessary when an overlapping range (for example, an IPv4 CIDR Address) is inserted in or removed from the RCAM. A special algorithm determines whether it is necessary to insert or remove one or more keys, and also whether the boundary type and the associated data entries corresponding to the keys change as a consequence. Usually, the potential insertion or removal of keys following the insertion or removal of an overlapping range is accompanied by the update of the corresponding boundary type and associated data entries.  
         [0185]    As used herein in the specification and in the claims section that follows, the term “module value span” refers to a span or stretch of values in a key module. The module value span is bounded by keys having “extreme values”. Thus, for a module containing 9 keys having the values of 3, 7, 38, 47, 88, 89, 93, 102, and 114, the module value span is from 3 to 114, and the extreme values of the keys in the module are 3 and 114.  
         [0186]    As used herein in the specification and in the claims section that follows, the term “monotonic order” and the like, in relation to a single key module, refer to one or more rows in an array in which the key values are in ascending order or in descending order.  
         [0187]    As used herein in the specification and in the claims section that follows, the term “row” refers to a first line of cells in an array, and the term “column” refers to a second line of cells in an array, the second line of cells being disposed in perpendicular fashion to the first line of cells. For the sake of convenience, all rows in the Figures are horizontal, and all the columns are vertical.  
         [0188]    Although the invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, it is intended to embrace all such alternatives, modifications and variations that fall within the spirit and broad scope of the appended claims. All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention.