Hit result register file used in a CAM

[0002] 1. Field of the Invention

[0003] This invention relates to content addressable memories.

[0004] 2. Related Art

[0005] A CAM (content addressable memory) is sometimes used in a computer system or device for storing and retrieving information. CAMs have the advantage that they can rapidly link associated data with known tags; it is thus possible to perform rapid lookup of the associated data once the tag is known. Known CAMs include comparison circuits for matching an input tag with each tag recorded in the CAM, so as to determine which if any of the row or lines in the CAM matches the tag. If the input tag matches one or more tags recorded in the CAM, the CAM returns a matching entry (or an index thereof), also called a “hit.”

[0006] In some known CAMs additional processing is performed on the value associated with the matching entry, such as to compare that associated value with a set of selected parameters and possibly validate or invalidate the associated value in response to those selected parameters. In the known art, special purpose circuits perform the additional processing, such as any compare-and-invalidate operations that may be desired.

[0007] A first problem in the known art is that special purpose circuits add complexity and take additional space on the chip in which the CAM is implemented. This limits the size of CAM that can be implemented in any chip of a pre-selected size, or limits the complexity or functionality of the special purpose circuits to be used with the CAM.

[0008] A second problem in the known art is that once the circuits embodying special purpose functions are embedded in the chip, they are fixed for that chip, and cannot generally be altered if new special purpose functions are desired.

[0009] A third problem in the known art is that circuits embodying special purpose functions do not always take the same amount of time to operate. This presents a drawback, in that operation of the CAM cannot be assured to take less time than the maximum time for any one of those special purpose functions. Where one or more special purpose function is a management function for clearing entries in the CAM, the time taken by that special purpose function can be quite large. This has a substantial effect on design of systems that include such a CAM.

[0010] Some known CAMs include a single status register for recording an index value for a result of the match. While this has the general advantage of providing the index value for later use by circuitry or a processor, it has the drawback that the status register would be overwritten by a next CAM operation, and so would be inefficient to attempt to use for generalized operations on the CAM. In practice, special logic is required because the status register is not useful.

[0011] Accordingly, it would be desirable to provide a technique for performing additional processing on CAM hit results, in which the additional processing does not add to the complexity or size of the CAM chip, in which the additional processing can be altered after manufacture of the CAM chip, and in which the additional processing does not delay other operations of the CAM. This advantage is achieved in an embodiment of the invention in which the CAM hit results are presented as indices into the CAM and sent to a hit result register file. The contents of the hit result register file can be processed by other hardware or software coupled to the CAM.

[0012] The invention provides a method and system for performing additional processing on CAM hit results, in which the additional processing does not add to the complexity or size of the CAM chip, can be altered after manufacture of the CAM chip, and does not delay other operations of the CAM. The CAM hit results returned from the CAM array and sent to a hit result register file where they are stored. The contents of the hit result register file can be processed by other hardware or software coupled to the CAM array. In a preferred embodiment, the index associated with the CAM input tag can be accessed using the hit result register file and a register indirect operation. In a preferred embodiment, the index associated with the CAM input tag can be used for CAM management functions in conjunction with (such as in parallel or pipelined) other CAM functions.

[0013] FIG. 1 shows a block diagram of a system including a CAM array and a hit result register file.

[0014] FIG. 2 shows a process flow diagram for a method of operating a system including a CAM array and a hit result register file, so as to perform additional processing on CAM hit results.

[0015] In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. Those skilled in the art would recognize after perusal of this application that embodiments of the invention can be implemented using general or special purpose processors, or other circuits, adapted to particular process steps and data structures described herein. Implementation of the process steps and data structures described herein would not require undue experimentation or further invention.

[0016] FIG. 1 shows a block diagram of a system including a CAM array and a hit result register file.

[0017] A system 100 includes a CAM (content addressable memory) array 110, a HRRF (hit result register file) 120, and a processor 130.

[0018] Content Addressable Memory

[0019] The CAM array 110 is disposed for receiving an input tag 140 at a first CAM input 111. The CAM array 110 includes a set of CAM entries 112, each including a tag value that might or might not match the input tag 140. (The CAM entries 112 can also include additional information, such as a data value associated with the tag value, management information for selected CAM entries related to operation of the CAM array 110, or other information.) The CAM array 110 is disposed for providing, in response to the input tag 140, an index value 113 of an entry matching the input tag 140 at a first CAM output 114.

[0020] As described below, in a preferred embodiment, the CAM array 110 is disposed for matching a set of input tags 140 of differing sizes. Thus, (for example), the CAM array 110 can be presented with an input tag 140 that is 40 bits wide, 72 bits wide, 144 bits wide, or 288 bits wide. The CAM array provides at the first CAM output 114 (in addition to the index value 113) an input tag width 115 that indicates the width of the input tag 140 that the CAM array 110 matched to produce that index value 113.

[0021] The first CAM output 114 is coupled to the HRRF 120 at a designated HRRF input 121. The HRRF 120 includes a set of HRRF entries 122, each of which is disposed for storing one selected index value 113. The HRRF 120 is disposed for receiving the index value 113 of the first CAM output 114 and for storing that index value 113 at a selected one of its HRRF entries 122.

[0022] The CAM array 110 is also disposed for receiving an input index value 113, an input entry value 116, and an input operation code 117 at a second input 118. In this context, the index value 113 specifically relates to a hit result. Similar to a random-access memory, the input operation code 117 can instruct the CAM array 110 to read from or to write to the CAM entry 112 designated by the input index value 113. The CAM array 110 responds to the input index value 113 and the input operation code 117 by reading from or writing to the designated CAM entry 112. The input entry value 116 is used when the CAM array 110 responds by writing to the designated CAM entry 112.

[0023] For example, the CAM array 110 can be instructed using the second CAM input 118 to insert data into a first selected CAM entry 112, to clear a second selected CAM entry 112, or to readout a third selected CAM entry 112. In a preferred embodiment, a portion of a selected CAM entry 112 can be altered by writing to a selected portion of a selected CAM entry 112 in the CAM array 110.

[0024] The second CAM output 119 may be coupled to the processor 130 at a first processor input 131. The processor 130 includes a local memory 132 disposed for recording information possibly including index values 113 and entry values 116. The processor 130 is disposed for receiving the entry value 112 (if read from the CAM array 110) at the second CAM output 119 and for recording that entry value 112 in its local memory 132.

[0025] Hit Result Register File

[0026] The HRRF 120 is disposed for receiving an input index value 113 (and selected additional information, such as a tag width value 115) from the first CAM output 114, at a first HRRF input 121. The HRRF 120 records the input index value 113 in one of its HRRF entries 122. Each HRRF entry 122 thus points to a selected CAM entry 112 (it is possible for two or more HRRF entries 122 to point to the same CAM entry 112).

[0027] In a preferred embodiment, the HRRF 120 includes eight HRRF entries 122. However, in alternative embodiments, the HRRF 120 can include more or fewer HRRF entries 122 (such as four HRRF entries 122, twelve HRRF entries 122, or sixteen HRRF entries 122). There is no particular requirement that the number of HRRF entries 122 must be a power of two.

[0028] The HRRF 120 is also disposed for receiving an input HRRF entry number 123 at a second HRRF input 125. In response to the input HRRF entry number 123, the HRRF 120 provides the CAM index value 113 recorded in the designated HRRF entry 122 at a first HRRF output 124.

[0029] Processor

[0030] The processor 130 is disposed for sending the HRRF entry number 123 from a first processor output 134 to the second HRRF input 125. The processor 130 is also disposed for receiving the CAM index value 113 recorded in the designated HRRF entry 122, from the first HRRF output 124 at a second processor input 133. In a preferred embodiment, the HRRF 120 is coupled to the processor 130 in a similar manner as a memory, so that the processor 130 can read or write HRRF entries 122 in similar manner as a memory. However, there is no particular requirement that the coupling between the HRRF 120 and the processor 130 be so generic.

[0031] The first HRRF output 124 is also coupled to the second CAM input 118, to provide the CAM index value 113 recorded in the designated HRRF entry 122 to the CAM array 110. When the processor 130 directs the HRRF 120 to provide that CAM index value 113 to the CAM array 110, the processor 130 also provides the entry value 116 to write (if a write operation is desired) and the operation code 117, at the second CAM input 118.

[0032] The processor 130 is thus able to perform a register indirect operation using one of the HRRF entries 122 as a pointer to a designated CAM entry 112. For example, the processor 130 can designate an HRRF entry number 123, a selected entry value 116 to write, and an operation code 117 designating a write operation. The processor 130 would thus write the selected entry value 116 to the CAM entry 112 whose index value 113 is recorded in the designated HRRF entry 122.

[0033] The processor 130 is thus able to read from and write to the CAM array 110 using the index values 113 which the CAM 110 provided in response to input tags 140. The CAM 110 is thus coupled to the processor 130 in similar manner as a memory, so that the processor 130 can read or write CAM entries 112 in similar manner as a memory. Thus, the processor 130 can obtain the actual CAM entries 112 that the CAM array 110 presented as matching the input tag 140, including their tag values and any additional information that might be present for those CAM entries 112.

[0034] Although it is desirable that the coupling between the CAM array 110 and the processor 130 is so generic, in alternative embodiments the coupling may be less generic while still providing functionality adequate to at least some of the purposes described below. Accordingly, such alternative embodiments are within the scope and spirit of the invention.

[0035] As noted above, the CAM array 110 responds to the index values 113 at the second CAM input 118, by presenting associated CAM entries 112 (when the processor operation is to read them), or other information (when the processor operation is otherwise) at a second output 119. The second CAM output 119 is coupled to the processor 130 at a first processor input 131.

[0036] Although in a preferred embodiment, the processor 130 provides the index value referring to an entry in the HRKF 120, and the HRRF 120 acts similarly to a random-access memory, alternative embodiments may be otherwise. In at least some alternative embodiments, the HRRF 120 may operate as a queue (such as a FIFO queue), and so select HRRF entries 122 for storage of index values 113 in a round robin manner. Queues are known in the art of computer science. In such alternative embodiments, the HRRF 120 would include a head pointer (not shown) and a tail pointer (not shown) for the queue.

[0037] Parallel or Pipelined Operation

[0038] The CAM array 110, the HRRF 120, and the processor 130 operate in a pipelined manner, so as to process in conjunction or in parallel a sequence of input tags 140 and a sequence of operations on the CAM array 110 by the processor 130. Pipeline processing is known in the art of computer architecture. Operational bandwidth of the CAM array 110 is thus shared among operations for differing purposes. In a preferred embodiment, these differing purposes include lookup operations for routing packets, and read/write operations for altering the contents of the CAM array 110.

[0039] In operation of the CAM array 110, each input tag 140 presented to the CAM 110 at the first CAM input 111 causes the CAM 110 to provide a responsive input index value 113 at the first CAM output 114.

[0040] Similarly, in operation of the HRRF 120, each responsive index value 113 presented by the CAM array 110 at the first HRRF input 121 causes the HRRF 120 to record that index value 113 in an HRRF entry 122. In conjunction or in parallel, each input HRRF entry number 123 presented by the processor 130 at the second HRRF input 125 causes the HRRF 120 to provide the index value 113 recorded in that designated HRRF entry 122 at a first HRRF output 124.

[0041] The processor 130 can thus operate in conjunction or in parallel with the CAM array 110 and the HRRF 120, directing the CAM 110 to perform random-access memory read/write operations interleaved with its associative memory lookup operations. In an alternative embodiment, the CAM 110 performs these operations in parallel with its associative memory lookup operations. Because the processor 130 can read and write the CAM array 110 (indirectly), the processor 130 can perform any computable operation on the contents of the CAM 110. Thus, the CAM 110 does not need specialized circuitry for any operation other than lookup and read/write operations. Moreover, processor 130 performs its operations under software control, so those operations are dynamically alterable.

[0042] CAM Management

[0043] The pipeline technique is well suited to management of the CAM array 110 for lookup operations for forwarding or other information about packets or cells in a router or switch. In a preferred embodiment, each input packet or cell includes information for lookup, using the input tag 140 as a lookup value and using the CAM array 110 as a constant-speed lookup table. The information to be looked up can be for forwarding, for access control, for quality of service, or for other management functions.

[0044] The CAM array 110 is managed by the processor 130 to assure that the CAM entries 112 are responsive to actual network topology and current administrative policies. This management arrangement is particularly useful because routing tables and administrative policies can change dynamically. The processor 130 provides management functions for entering CAM entries 112 into the CAM array 110 when they are new or clearing CAM entries 112 from the CAM array 110 when they are obsolete. Moreover, the CAM array 110 also performs lookup operations for routing as packets or cells are received and are directed for forwarding or other administrative processing.

[0045] The pipeline technique is also well suited to management of the CAM array 110 for interspersing lookup operations with management operations. By recording the index values 113 presented by the CAM 110 from its lookup operations, the HRRF 120 provides a buffering function for that information. Accordingly, lookup operations can occur at the full speed of the CAM array 110, without waiting to determine if the result of any lookup operation prompts the processor 130 to alter the contents of the CAM array 110 or to otherwise interrupt the processing of packets.

[0046] Example Complex Operation

[0047] For example, if the processor 130 desires to perform an operation on the CAM array 110 such as “clear all entries for a selected VLAN,” the processor 130 can perform the following sub-operations in sequence.

[0048] First, the processor 130 presents an input tag 140 to the CAM array 110 to lookup entries for the selected VLAN. In a preferred embodiment, the CAM array 110 includes a ternary CAM with a global mask for at least some of the CAM entries 112. The processor 130 sets the mask so that the selected VLAN is the only unmasked part of each CAM entry 112, and presents the input tag 140 for the selected VLAN.

[0049] Second, the CAM array 110 responds to the input tag 140 for the selected VLAN by presenting an index value 113 for one (it does not matter which one) of its CAM entries 112 for the selected VLAN. The CAM array 110 presents that index value 113 to the HRRF 120, which records that index value 113 in a selected HRRF entry 122 (designated by an HRRF entry number 123).

[0050] The processor 130 monitors the hit result 126 (not shown) resulting from the lookup operation, and determines if that hit result 126 (not shown) indicates that no such entry was found. If so, there are no more entries for the selected VLAN, and the operation “clear all entries for a selected VLAN” is complete.

[0051] Third, the processor 130 performs a register-indirect write to that selected HRRF entry 122 indicated by HRRF entry number 123 (that is, the same HRRF entry number 123 as previously described) if there is a hit. In this event, the processor 130 directs the CAM array 110 to write a designated entry value 116 to that corresponding CAM entry 112. The designated entry value 116 clears the CAM entry 112, which generated the match with the selected VLAN, thus clearing one of the (possibly many) CAM entries 112 for the selected VLAN.

[0052] FIG. 2 shows a process flow diagram for a method of operating a system including a CAM array and a hit result register file, so as to perform additional processing on CAM hit results.

[0053] A method 200 is performed by the system 100, including the CAM array 110, the HRRF 120, and the processor 130. Although the method 200 is described serially, the steps of the method 200 can be performed by separate elements of the system 100 in conjunction or in parallel, whether asynchronously, in a pipelined manner, or otherwise. There is no particular requirement that the method 200 be performed in the particular order in which this description lists the steps, except where so indicated.

[0054] In a preferred embodiment, as noted above, the CAM array 110, the HRRF 120, and the processor 130 operate in a pipelined manner, so as to process a sequence of input tags 140 and a sequence of operations on the CAM array 110 by the processor 130, with operational bandwidth of the CAM 110 thus being shared.

[0055] At a flow point 210, the CAM array 110 is ready to receive an input tag 140 at the first CAM input 111 and an input index value 113, a designated entry value 116, and an operation code 117, at the second CAM input 118.

[0056] Matching Input Tag

[0057] A first sequence of steps relates to matching the input tag 140 at the first CAM input 111.

[0058] At a step 211, the CAM array 110 receives the first input tag 140 at the first CAM input 111.

[0059] At a step 212, the CAM array 110 attempts to match the input tag 140 against tag values stored in its tag array. If the CAM array 110 is able to match the input tag 140, it generates a responsive index value 113. If the CAM array 110 is not able to match the input tag 140, it generates a hit result 126 which indicates that there was no match (a miss). As part of this step, the CAM array 110 provides the responsive index value 113 at the first CAM output 114.

[0060] At a step 213, the HRRF 120 receives the responsive index value 113, the hit result 126 (indicating either a hit or a miss) and the tag width value 115, at the first HRRF input 121.

[0061] At a step 214, the HRRF 120 records the responsive index value 113, the hit result 126 (indicating either a hit or a miss) and the tag width value 115, in a selected HRRF entry 122.

[0062] The method 200 continues with the flow point 210, the CAM array 110 matching input tags 140 according to this first sequence of steps continually.

[0063] Performing Read/Write

[0064] A second sequence of steps, performed in conjunction or in parallel with the first sequence of steps, relates to performing the read/write operation designated by the processor 130 at the second CAM input 111.

[0065] At a step 221, the CAM array 110 receives the input index value 113, the designated entry value 116, and the operation code 117, at the second CAM input 118.

[0066] At a step 222, performed in conjunction or in parallel, the CAM array 110 reads data from (for a read operation) or writes data to (for a write operation) the CAM entry 112 designated by the input index value 113.

[0067] The method 200 continues with the flow point 210, the HRRF 120 receiving and recording index values 113 according to this second sequence of steps continually.

[0068] Operating Processor

[0069] A third sequence of steps, performed in conjunction or in parallel with the first sequence of steps, relates to the processor 130 performing management operations for the CAM array 110.

[0070] At a step 231, the processor 130 receives a processor instruction that references the HRRF 120. For example, the processor instruction can include a register indirect operation, so as to use a HRRF entry 122 to point to an entry in the CAM array 110.

[0071] At a step 232, the processor 130 executes the processor instruction that references the HRRF 120. To perform this step, the processor 130 presents an input HRRF entry number 123 to the HRRF 120 at the second HRRF input 125.

[0072] At a step 233, the HRRF 120 receives the input HRRF entry number 123 from the processor 130, and provides the CAM index value 113 recorded in the designated HRRF entry 122.

[0073] The method 200 continues with the flow point 210, the processor encountering and performing instructions according to this third sequence of steps continually.

[0074] Network Routing

[0075] In a preferred embodiment, the invention is used to perform operations using network routing information, such as found and used in a router or a switch. The CAM array 110 operates in this environment as a constant-speed lookup table, which is also capable of performing multiple lookup operations in parallel or in a pipelined manner.

[0076] The CAM entries 112 each include a tag value, which corresponds to a destination address (in a packet switched system) or a virtual circuit (in a circuit switched system). The tag value can also comprise a mask in embodiments in which the CAM array 110 includes a ternary CAM.

[0077] The CAM entries 112 each also include an index value 113, which corresponds to a pointer to a set of routing information in another memory. In a preferred embodiment, the routing information can include one or more of, or some combination of, the following.

[0078] Forwarding information, such as indicating an output interface to which to forward the packet. The output interface information can be responsive to a tag value constructed in response to at least a portion of a packet header, such as a destination address or port value, a source address or port value, a protocol type, a multicast indicator (indicating for example whether the packet is unicast or multicast), or a type of service indicator (indicating for example whether the packet is voice traffic or otherwise).

[0079] Access control information, such as indicating whether packets are authorized to proceed to the selected destination. The access control information can be responsive to a tag value constructed in response to at least a portion of a packet header, such as those portions of the packet header described with regard to forwarding information.

[0080] Quality of service information, such as indicating what quality of service is demanded or provided for packets (such as committed access rate, traffic latency, or traffic reliability). The quality of service information can be responsive to a tag value constructed in response to at least a portion of a packet header, such as those portions of the packet header described with regard to forwarding information.

[0081] Other administrative information, such as enforcing administrative policies for packet traffic (such as accounting, security control, or usage limitations). The other administrative information can be responsive to a tag value constructed in response to at least a portion of a packet header, such as those portions of the packet header described with regard to forwarding information.

[0082] Compare-and-Invalidate

[0083] One example of a network routing application is when the processor 130 desires to invalidate all entries 112 in the CAM array 110 that relate to a particular route. For example, that route might have been removed from the network topology, or otherwise so altered that corresponding entries should be removed.

[0084] At a flow point 240, the processor 130 identifies a case in which it desires to invalidate all entries 112 in the CAM array 110 that relate to a particular route.

[0085] At a step 241, the processor 130 presents an input tag 140 to the CAM array 110 at the first CAM input 111.

[0086] At a step 242, the CAM array 110 receives the input tag 140 and attempts to match the input tag 140 against tag values stored in its tag array. As noted above, if the CAM array 110 is able to match the input tag 140, it generates a responsive index value 113 at the first CAM output 114. If the CAM array 110 is not able to match the input tag 140, it generates a hit result 126 (a miss), which indicates there was no match, at the first CAM output 114.

[0087] In a preferred embodiment, the CAM array 110 might have more than one CAM entry 112 matching the input tag 140. In this case, the CAM array 110 selects one (in a preferred embodiment, the lowest numbered entry) such entry 112, and generates the responsive index value 113 in response to the selected one entry 112.

[0088] At a step 243, the processor 130 examines the responsive index value 113 and the value of the hit result 126. If value of the hit result 126 indicates miss, there were no entries 112 in the CAM array 110 corresponding to the route to be removed, and the method 200 ends.

[0089] At a step 244, the processor 130 executes a register indirect instruction, using the storage register in the HRRF 120 for the responsive index value 113, to directly access the corresponding entry 112 in the CAM array 110. In a preferred embodiment, to invalidate the entry 112, the processor 130 clears an entry-valid bit (not shown). In alternative embodiments, the processor 130 may clear the entire entry 112.

[0090] The method 200 continues with the flow point 240 to repeat the compare-and-invalidate operation until there are no matching entries 112 in the CAM array 110.

[0091] At a flow point 250, the processor 130 has invalidated all matching entries 112 in the CAM array 110, and is ready to proceed with another operation. The processor 130 knows that further processing is not required because the output of the CAM array 110 no longer indicates a hit.

[0092] Other CAM Management

[0093] The compare-and-invalidate example should serve to illustrate the generalized ability of the processor 130 to provide management functions for controlling CAM entries 112, including entering CAM entries 112 into the CAM array 110 when they are new or clearing CAM entries 112 from the CAM array 110 when they are obsolete.

[0094] Similarly to the compare-and-invalidate example, the processor 130 can determine what portion of its operations it will devote to operations for managing the CAM array 110, and what portion of its operations it will devote to performing routing information lookups using the CAM array 110.

[0095] The invention is applicable not just to routers and switches, but to all CAM systems in which additional processing or pipelining of hit results is desired. More generally, when it is desired to manage the CAM in conjunction or in parallel with using the CAM for lookup purposes, the invention provides for dynamic adjustment of these uses of the CAM. The invention is superior to existing CAM systems in that it allows for that dynamic alteration or selection of CAM data and of processor bandwidth devoted to management of CAM data.

[0096] Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.