TCAM-based not logic

Abstract

A NOT logic circuit is provided comprising: one or more memory devices; wherein a first memory address location of the one or more memory devices stores first content data, wherein the first content data includes a first ternary value and a corresponding first priority value, wherein the first ternary value includes a continuous sequence of X-state values that represent a first range of non-X ternary values; wherein a second memory address of the one or more memory device stores second content data that includes a second ternary value and a corresponding second priority value, wherein the second ternary value includes a continuous sequence of non-X state values represent a non-X ternary value that is within the first range of non-X ternary values; an interface is coupled to receive a ternary value from a processing device; comparator circuitry operable to compare a received ternary key with the outputted first ternary value and to compare the received ternary key with the outputted second ternary value; priority encoder logic operable to, return the outputted first priority value on a condition that the received ternary key matches the first ternary value and the received ternary key does not match second ternary value, and return the outputted second priority value on a condition that the received ternary key matches the first ternary value and that the received ternary key matches the second ternary value; and detection logic operable to send a return to the processing device on a condition of a return of the first priority value.

Claims

1. A NOT logic circuit comprising: one or more memory devices; wherein a first memory address location of the one or more memory devices stores first content data, wherein the first content data includes a first ternary value and a corresponding first priority value, wherein the first ternary value includes a continuous sequence of X-state values that represent a first range of non-X ternary values; wherein a second memory address of the one or more memory device stores second content data that includes a second ternary value and a corresponding second priority value, wherein the second ternary value includes a continuous sequence of non-X state values represent a non-X ternary value that is within the first range of non-X ternary values; an interface is coupled to receive a ternary value from a processing device; comparator circuitry operable to compare a received ternary key with the outputted first ternary value and to compare the received ternary key with the outputted second ternary value; priority encoder logic operable to, return the outputted first priority value on a condition that the received ternary key matches the first ternary value and the received ternary key does not match second ternary value, and return the outputted second priority value on a condition that the received ternary key matches the first ternary value and that the received ternary key matches the second ternary value; and detection logic operable to send a return to the processing device on a condition of a return of the first priority value.

2. The NOT logic circuit of claim 1 further including: the detection logic operable to send no priority value to the processing device on a condition that of a return of the second priority value.

3. The NOT logic circuit of claim 1 further including: memory control logic operable to cause output of the first content data from the first memory address location and to cause output of the second content data from the second memory address location.

4. A method to use one or more memory devices to perform a NOT logic function comprising: storing first content data at a first memory address location of the one or more memory devices, wherein the first content data includes a first ternary value and a corresponding first priority value, wherein the first ternary value includes a continuous sequence of X-state values that represent a first range of non-X ternary values; storing second content data at a second memory address of the one or more memory device stores, wherein the second content data includes a second ternary value, wherein the second ternary value includes a continuous sequence of non-X state values represent a non-X ternary value that is within the first range of non-X ternary values; receiving a ternary value from a processing device; using a comparator circuit to compare a received ternary key with the stored first ternary value; using the comparator circuit to compare the received ternary key with the stored second ternary value; sending the stored first priority value to the processing device on a condition that the received ternary key matches the first ternary value and the received ternary key does not match second ternary value.

5. The method of claim 4 further including: sending no priority value to the processing device on a condition that the received ternary key matches the first ternary value and the received ternary key matches second ternary value.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) In the drawings, which are not necessarily drawn to scale, like numerals may describe similar components in different views. Like numerals having different letter suffixes may represent different instances of similar components. Some embodiments are illustrated by way of example, and not limitation, in the figures of the accompanying drawings in which:

(2) FIG. 1 is an illustrative drawing representing a first example TCAM storing ternary values in a first example pattern.

(3) FIG. 2 is an illustrative drawing representing a second example TCAM storing ternary values in a second example pattern.

(4) FIG. 3 is an illustrative drawing representing a third example TCAM storing a first example compressed ternary value pattern to represent multiple ternary values.

(5) FIG. 4 is an illustrative an illustrative drawing representing a fourth example TCAM that stores multiple partial X state sequences to provide a compressed representation of range of ternary values.

(6) FIG. 5 is an illustrative drawing showing an example network device in accordance with some embodiments.

(7) FIG. 6 is an illustrative drawing representing an example content data record that includes a key and an associated priority values searched based upon the key.

(8) FIG. 7 is an illustrative drawing representing an example information structure stored in a memory device that associates priority values with ports.

(9) FIG. 8 is an illustrative drawing showing an example TCAM system.

(10) FIG. 9 is an illustrative drawing of an example a priority encoding to select among priority values for return.

(11) FIG. 10 is an illustrative drawing representing an example first example configuration of the TCAM system to perform an if NOT logic function.

(12) FIG. 11 is an illustrative drawing representing an example second example second configuration of the TCAM system to perform an if NOT logic function.

DETAILED DESCRIPTION

(13) Network Device:

(14) FIG. 5 is an illustrative drawing showing an example network device 500. The network device 500 can include one or more integrated circuit (IC) devices, a larger device, such as a router or switch, or a combination of these. In some implementations, the network device 500 is a network routing device. In some implementations, the network r device 500 is coupled with a computing machine 580 within a network communications apparatus. The computing machine 580 can include multiple processor circuits 581 coupled to non-transitory memory 582 that includes instructions 583 to configure the computing machine 580 to perform operations described herein. In some implementations, the network device 500 is a network communications apparatus and includes the computing machine 580. The network device 500 can be coupled with a computer network, such as a local area network (LAN) or a wide area network (WAN), and processes data packets that comprise ordered sequences of binary data values.

(15) The network device 500 includes a processing device 510, which receives the packets or portions of packets on an input port or interface 520. In some implementations, the processing device 510 comprises a network processor. The processing device 510 parses incoming packet information to identify relevant data fields that provide information for handling network operations, such as routing and forwarding. The processing device 510 can be coupled with a TCAM-based search engine 540, hereinafter referred to as the “TCAM system” 540, which assists in determining appropriate actions to take in response to receipt of packets over a network. The processing device 510 extracts information from the packets, referred to as key information 560. The key information is used to identify rules that determine appropriate actions to take in response to the received packets. The key information represents data bits within a packet that indicate packet information such as network addresses or portions thereof, port numbers, other header and trailer information, or combinations thereof, for example. The processing device 510 can generate key information, also referred as a “key”, that includes ternary value bits, which can have any of three states, logic 0, logic 1, or X (“don't care”), to represent the binary bits extracted from a packet. In general, ternary value bits within a key that represent a logic value 0 or a logic value 1 contribute to identifying a rule that determines an action to take based upon a packet represented by the key, and ternary value bits within a key that represent an X state do not contribute to identifying a rule that determines an action take based upon the packet represented by the key.

(16) The processing device 510 sends ternary key information 560 to the TCAM system 540, which stores rules associated with such key information that indicate corresponding action to take. In an example processing device 510 the rules include priority values that indicate output ports to use to output packets received by the processing device 510. More particularly, in response to receipt of key information 560 corresponding to a packet, the TCAM system 540 returns one or more corresponding priority value rules 570 identified using the key information 560. Based upon a returned priority value, the processing device 510 determines an output port from among output ports 530.sub.1-530.sub.m on which to forward packet information, for example. Alternatively, the processing device 510 may determine to drop a received packet. The network processor 540 may determine to drop a packet if the TCAM system 540 determines that there is no match for a received key, for example. The TCAM system 540 includes one or more memory devices to store keys in association with corresponding priority values 570. Matches between previously stored keys and keys provided by the processing device 510, in response to received packets, are searched to identify priority values to use to route or switch the received packets.

(17) FIG. 6 is an illustrative drawing representing an example content data record, stored in a memory device, that includes a key and an associated priority value searched based upon the key.

(18) FIG. 7 is an illustrative drawing representing an example information structure 702 stored in a memory device 704 at the processing device 510 that associates numerical priority values with output ports 530.sub.1-530.sub.m described below. The example information structure 702 comprises a table data structure that orders the priority values in a numerically ascending order. An exception priority value, having a numerical value indicated as “max”, is not associated with a port and instead is handled as an exception as described more fully below. In an example processing device 510, the exception priority value sets a predetermined threshold value that is the largest numerical magnitude of all priority values associated with ports.

(19) TCAM System

(20) FIG. 8 is an illustrative drawing showing an example TCAM system 540 is implemented using algorithmic TCAM in accordance with some embodiments. The TCAM system 540 includes an input interface 810 on which a ternary key is received, multiple memory modules 870.sub.0-870.sub.15, storage control logic circuitry 824, a priority block 875, and detection circuit 880. The example TCAM system 540 includes sixteen memory device modules 870.sub.0-870.sub.15, which comprise corresponding memory devices 830.sub.0-830.sub.15. The input interface 810 includes a buffer circuit (not shown) to temporarily store a received ternary key. However, the number of memory device modules employed in a TCAM system 540 (e.g., one, two, four, eight, sixteen, etc.) can vary with implementation. The memory devices 830.sub.0-830.sub.15 can include integrated circuit RAM memory devices of various types, such Static RAM (SRAM), Dynamic RAM (DRAM), Synchronous DRAM (SDRAM), Flash RAM, etc. For example, each memory device 830.sub.0-830.sub.15 can be a 512×256 RAM. In addition, each of memory devices 830.sub.0-830.sub.15 can have an associated output buffer circuit 840.sub.0-840.sub.15 and comparator circuit 850.sub.0-850.sub.15. The memory devices 830.sub.0-830.sub.15 and their associated buffers 840.sub.0-840.sub.15 and comparators 850.sub.0-850.sub.15 operate as memory device modules 870.sub.0-870.sub.15.

(21) The memory control logic 824 controls access to the memory devices 830.sub.0-830.sub.15. During a write operation, the memory control logic 824 determines a memory location at which to store a ternary value and an associated priority value. Different ternary values and corresponding priority values can be written to the same segment within different memory devices. For example, a memory segment can consist of one or more wordlines. A first ternary value and a corresponding first priority value may be written to a wordline1 835.sub.0 in the first memory device 830.sub.0; a second ternary value and a corresponding second priority value may be written to a wordline1 835.sub.1 in the second memory device 830.sub.1; and a sixteenth ternary value and corresponding sixteenth priority value may be written to a wordline1 835.sub.15 in a sixteenth memory device 830.sub.15.

(22) During a read operation, the memory control logic 824 can simultaneously access multiple memory locations within two or more of the memory the devices 830.sub.0-830.sub.15 to search for a match with a received ternary key value. More particularly, during a read operation, the memory controller 824 causes read access of content data from common memory segments, e.g., wordline1, at one or more of the memory devices. Corresponding output buffer circuits 840.sub.0-840.sub.15 receive content data output by the one or more memory devices. The content data includes stored ternary values and corresponding priority value information written previously to the accessed memory segments of the one or more memory devices. Corresponding comparators 850.sub.0-850.sub.15 compare stored ternary values output to corresponding buffers 840.sub.0-840.sub.15 with a ternary key value received at the input interface 810 and provide signals on corresponding match lines M.sub.0-M.sub.15, indicating whether a match is detected. For example, a first comparator 850.sub.0 provides a match signal on a first match line M.sub.0 indicating whether there is a match between a received ternary key value and a ternary value that is output from memory segment 835.sub.0 to the output to buffer circuit 840.sub.0. On a condition that a match is determined, a priority value output to buffer circuit 840.sub.0 is provided to the detection circuit 880. Thus, a priority value portion of the content data at memory segment 835.sub.0 is provided on output line O.sub.0 to the detection circuit 880 on a condition that the stored ternary value portion of the content data stored at memory segment 235.sub.0 matches the received key value. Conversely, on a condition that there is not a match between a received ternary key value and a ternary value that is output from memory segment 835.sub.0 then the priority value portion of the content data at memory segment 835.sub.0 is not provided on output line O.sub.0 to the detection circuit 880.

(23) Similarly, a second comparator 850.sub.1 provides a match signal on a second match line M.sub.1 indicating whether there is a match between a received ternary key value and a ternary value that is output from memory segment 835.sub.1 to the output to buffer circuit 840.sub.1. On a condition that a match is determined, a priority value output to buffer circuit 840.sub.1 is provided to the detection circuit 880. Thus, a priority value portion of the content data at memory segment 835.sub.1 is provided on output line O.sub.1 to the detection circuit 880 on a condition that the stored ternary value portion of the content data stored at memory segment 235.sub.1 matches the received key value. Conversely, on a condition that there is not a match between a received ternary key value and a ternary value that is output from memory segment 835.sub.1 then the priority value portion of the content data at memory segment 835.sub.1 is not provided on output line O.sub.1 to the detection circuit 880.

(24) FIG. 9 is an illustrative drawing of an example a priority encoder process 900 performed using a priority encoder block 875 used to select among priority values provided on one or more of output lines in response comparison matches. One or more logic circuits are configured to implement operations of the priority block 875. Operation 902 receives one or more priority values provided on one or more output lines O.sub.0-O.sub.15 corresponding to one or matches determined using comparators 850.sub.0-850.sub.15. In response to a simultaneous read from multiple common memory segments, e.g., 835.sub.0-835.sub.15. It will be appreciated that more than one stored ternary value may match a search key value. Decision operation 904 determines whether there is a single received priority value. On a condition that there is a single priority value, operation 906 selects the received priority value and provides the selected priority value for return to the processing device 510. On a condition that there is more than one received priority value, decision operation selects the priority value having the largest magnitude and provides the selected priority value for return to the processing device 510.

(25) Referring again to FIG. 8, the detection circuit 880 determines whether a priority value provided for return meets an exception condition. An example detection circuit 880 includes digital detector logic that compares a magnitude of a priority value provided for return with a threshold value “max” to determine whether there is a match indicating that the returned priority value is an exception value. An example detection circuit 880 includes a digital comparison circuit 882 to compare a magnitude of the priority value provided for return with a threshold magnitude value that is greater than a magnitude of every other priority value stored within the one or more memory devices 830.sub.0-830.sub.15. That is, the “max” magnitude 706 indicated in FIG. 7. On a condition that a priority value provided for return meets the threshold exception condition, the detection circuit 880 block returns of the priority value to cause no return of the priority value to the processing device 510. An example detection circuit 880 includes a switch 884 that opens to block the priority value on a condition that a priority value provided for return meets the exception. On a condition that a priority value provided for return does not meet the threshold exception condition, the detection circuit 880 does not block or cause a no return of a priority value to the processing device 510. An example processing device 510 that receives no return priority value in response to a read performed based upon key value provided by the processing device 510 and may drop a message associated with the key value.

(26) TCAM-Based NOT Logic:

(27) FIG. 10 is an illustrative drawing representing a first example configuration of the TCAM system 540 to perform an if NOT logic function. More specifically, the first memory device 830.sub.0 stores the example compressed continuous ternary value pattern XXX and the corresponding first priority value P1 at memory segment 835.sub.0. The second memory device 830.sub.1 stores the example exception ternary value AAA and a corresponding second priority value P2 at memory segment 835.sub.1. For compactness of disclosure in this example, it is assumed that the first and second memory devices 830.sub.0, 830.sub.1 each store only three ternary values per memory segment 835.sub.0, 835.sub.1 and that the received key value also includes only three ternary values. Moreover, details of the TCAM system 540 will be understood from the explanation with reference to FIG. 8 and are not repeated.

(28) In the first example configuration the TCAM system 540 is configured to perform the logic function: if a received ternary key value is NOT AAA, then use a priority value P1. The compressed continuous ternary value pattern XXX defines a continuous range of ternary values. The XXX ternary value pattern is referred to as continuous because there are no non-X state (i.e. ternary logic state 0 or ternary logic 1 state) values intervening between any X values in the continuous sequence. The compressed ternary value pattern represents a continuous sequence of ternary values, 000-111. The exception ternary value AAA is a value included within the defined range 000-111.

(29) The first memory device 830.sub.0 stores the example compressed continuous ternary value pattern XXX and the corresponding first priority value P1 at memory segment 835.sub.0. The second memory device 830.sub.1 stores the example exception ternary value AAA and a corresponding second priority value P2 at memory segment 835.sub.1. For compactness of disclosure in this example, it is assumed that the first and second memory devices 830.sub.0, 830.sub.1 each store only three ternary values per memory segment 835.sub.0, 835.sub.1 and that the received key value also includes only three ternary values.

(30) The first priority value P1 comprises a numerical value having a magnitude. The second priority value P2 also comprises a numerical value having a magnitude. The second priority value is also referred to herein as an exception priority value. The second priority value P2 has a magnitude that is larger than a magnitude of the first priority value P1. As explained above, in an example TCAM system 540, the second priority value P2 has the largest magnitude out of all priority values stored in the TCAM system 540.

(31) As explained above with reference to FIG. 8, the read control logic 824 can cause a simultaneous search at memory segment 835.sub.0 of memory device 830.sub.0 and at memory segment 235.sub.1 of memory device 230.sub.1 and comparators 850.sub.0, 840.sub.1 may simultaneously check for respective matches between a search key provided at interface 810 and respective ternary values stored at memory segments 835.sub.0, 835.sub.1. One or more priority values can be provided on corresponding output lines O.sub.0-O.sub.15 in response to corresponding matches between stored ternary values and a key value received at the input 810. The priority block selects a priority value to provide for return to the processing device 510. The detection circuit determines whether to cause no return of a priority value provided for return.

(32) On a condition that a key value received at input 810 is received having a ternary value AAA, then the received key value will match both the stored value XXX and the stored value AAA. The first comparator 850.sub.0 determines a key match with the ternary value XXX stored at memory device 830.sub.0 at the memory segment 835.sub.0 that also stores the first priority value P1. The second comparator 850.sub.1 determines a key match with the ternary value AAA stored at memory device 230.sub.1 at the memory segment 835.sub.1 that also stores the second priority value P2. The priority block 875 causes the second priority value P2 to be provided for return to the processing device 510. Since the second/exception priority value P2 equals the exception value (max), the detection circuit 880 causes no return of the second priority value P2.

(33) Conversely, on a condition that a key value received at input 810 has a ternary value other than AAA, then the received key value will match only the stored value XXX.

(34) The first comparator 850.sub.0 determines a key match with the ternary value XXX stored at memory device 830.sub.0 at the memory segment 835.sub.0 that also stores the first priority value P1. The second comparator 850.sub.1 determines no key match with the ternary value AAA stored at memory device 830.sub.1 at the memory segment 835.sub.1 that also stores the first priority value P2. The priority block 875 causes the first priority value P1 to be provided for return to the processing device 510. The first memory device 830.sub.0 outputs only the first priority value P1. The priority block 875 causes the first priority value P1 to be provided for return to the processing device 510. Since the first priority value P12 does meet the exception condition, the detection circuit 880 does not causes no return of the first priority value P1.

(35) Thus, it will be appreciated that only two ternary values need be stored and that only two comparisons are required to determine whether a received key value does not match a designated key value within a continuous range of key values. One comparison determines that the received key value matches the sequence of X states that span the range. A second comparison determines whether the received key value also matches a designated exception value, e.g., AAA, within the range of the X-state sequence. The match with the X state range identifies a first priority value that can be used to specify a rule, e.g., to specify an output port to use to send a message, and a match with the exception value can be used to negate the rule, e.g., to specify that a message should not be sent for a received key that matches a designated exception value. Moreover, it will be appreciated that a received key can represent a network address, a protocol or a combination thereof, for example.

(36) FIG. 11 is an illustrative drawing representing a second example configuration of the TCAM system 540 to perform an if NOT logic function. The example NOT logic function determines in this example determines whether a condition NOT 1023.sub.10 is met. Details of the TCAM system 540 will be understood from the explanation with reference to FIG. 8 and are not repeated. The first memory device 830.sub.0 stores a ternary value that includes a continuous X state ternary value pattern 0000000XXXXXXXXX which matches any value less than 1024.sub.10 and a corresponding first priority value P1, at memory segment 835.sub.0. The second memory device 830.sub.1 stores an example exception value 0000000111111111 (i.e., 1023.sub.10) and a corresponding second/exception priority value P2, at memory segment 835.sub.1. The TCAM system 540, in the second configuration, performs a function, if NOT 0000000111111111, then return the first priority value P1. In this example, the exception value is 0000000111111111 (1023.sub.10). Also, in this example the second priority value P2 is set to be a largest possible priority value magnitude out of all priority value magnitudes used in the processing device 510.

(37) On a condition that a search value 1023.sub.10 (i.e., 0000000111111111) is received (i.e., the NOT condition is met), the detection circuit 880 causes no return of a priority value. Thus, the detection circuit 880 indicates a match between a received search value and the exception value 0000000111111111 in response to a return the second priority value P2.

(38) Conversely, on a condition of receiving any search value less than 1024.sub.10, other than 1023.sub.10 (i.e., the NOT condition is not met) then detection circuit 880 returns the first priority value P1 to the processing device 510. Thus, the detection circuit 880 indicates a match between a received search value and the continuous X state ternary value pattern 0000000XXXXXXXXX in response to a return the first priority value P1. The above description is presented to enable any person skilled in the art to make and use ternary content addressable memory to perform a NOT logic operation. Various modifications to the examples will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. For example, although an algorithmic TCAM is disclosed in detail herein, the principles of the invention also apply to cell based TCAM. In the preceding description, numerous details are set forth for the purpose of explanation. However, one of ordinary skill in the art will realize that the invention might be practiced without the use of these specific details. In other instances, well-known processes are shown in block diagram form in order not to obscure the description of the invention with unnecessary detail. Identical reference numerals may be used to represent different views of the same or similar item in different drawings. Thus, the foregoing description and drawings of embodiments in accordance with the present invention are merely illustrative of the principles of the invention. Therefore, it will be understood that various modifications can be made to the embodiments by those skilled in the art without departing from the spirit and scope of the invention, which is defined in the appended claims.