TCAM architecture where content-based search is conductible

Abstract

According to an embodiment of the present invention, there is provided a TCAM architecture in which a content-based search is conductible in such a manner that a search key to be searched for is used as an address of a memory element that makes up a TCAM cell and that an output from the memory element reflects whether a match or a mismatch is found as a result of the search. The memory element may be a look-up table.

Claims

1. A FPGA-based TCAM architecture, wherein: multiple look-up tables are provided; outputs from the look-up table are ANDed through a carry chain, and thus a final match result is output; each of the look-up tables has many bits, as many as the number values that are representable by a search key that is input; “1” is written in a bit for an address corresponding to a value of the search key to be stored; “0” is written in the remaining bits; when the search key to be searched for is input into each of the look-up tables, a bit value for an address corresponding to the value of the search key that is input is output; in a case where “1” is output from all the look-up tables, “1” is output as a final match result; the search for the search key is conducted by having direct access to a bit for the address corresponding to the value of the search key to be searched for; and values stored in the remaining bits in the lookup table, which do not correspond to the address of the search key to be searched for, are updated while at the same time conducting the search for the search key.

2. The FPGA-based TCAM architecture according to claim 1, wherein: in the look-up tables, four 64-bit look-up table RAMs (LUTRAM) have a quad port RAM structure in which three look-up table RAMs, as read ports, implement 18 TCAM bits, and one look-up table RAM functions as a write port.

3. The FPGA-based TCAM architecture according to claim 2, comprising: a log.sub.2D-bit decoder that outputs an update address of the look-up table RAM; a MOD-64 counter that generates and outputs a 6-bit sequence; and a comparator that compares an update word that is a value to be updated, and the 6-bit sequence of the MOD-64 counter, wherein the update word and the 6-bit sequence are consistent with each other in the update address, “1” is recorded in a bit for the update address.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram illustrating a general 4×4 TCAM;

(2) FIG. 2 is a diagram illustrating a TCAM cell having a TCAM architecture according to an embodiment of the present invention;

(3) FIG. 3 is a diagram illustrating a 1×2 TCAM that results from increasing the number of TCAM cells, each being illustrated in FIG. 2, in a width direction;

(4) FIG. 4 is a diagram illustrating a 2×1 TCAM that results from increasing the number of TCAM cells, each being illustrated in FIG. 2, in a depth direction;

(5) FIG. 5 is a diagram illustrating a D×W TCAM that results from increasing the number of TCAM cells, each being illustrated in FIG. 2, in the depth and width directions;

(6) FIG. 6 is a diagram illustrating an example where the 4×4 TCAM in FIG. 1 is realized by employing the TCAM architecture according to the present invention;

(7) FIG. 7 is a diagram illustrating an FPGA-based TCAM architecture according to another embodiment of the present invention;

(8) FIG. 8 is a diagram illustrating Carry Chain Structures of the present invention and

(9) FIG. 9 is a diagram for describing an update logic in the FPGA-based TCAM architecture according to the embodiment of the present invention.

DETAILED DESCRIPTION

(10) Terms that have ordinary meanings, which are currently widely used, were selected as ones that are to be used in the present specification. However, in certain instances, there are also terms that were arbitrarily selected by the inventor. Such terms should be interpreted in light of the specification, instead of literal meanings of such terms.

(11) Preferable embodiments of the present invention will be described in terms of technical configurations with reference to the accompanying drawings.

(12) However, the present invention is not limited to the embodiments that are described here and may be implemented into other embodiments. The same constituent element is given the same reference character throughout the specification.

(13) FIG. 2 is a diagram illustrating a TCAM cell having a TCAM architecture according to an embodiment of the present invention.

(14) With reference to FIG. 2, a TCAM architecture 100 according to the embodiment of the present invention includes one or multiple TCAM cells 110, and, when a search key 13 is input, the CAM cell 110 outputs a match signal or a mismatch signal.

(15) In addition, the TACM cell 110 includes first and second memory elements 111 and 112, and the content of ternary memory is stored, as 2-bit data, in the TACM cell 110.

(16) In addition, the search key 13 is used as an address of each of the first or second memory element 111 or 112, and the content of the first or second memory element is output as a match or mismatch that results from the search.

(17) In addition, the address of the first memory element 111 is “0” and an address of the second memory element 112 is “1”.

(18) If the content of the ternary memory “0”, that is, in a case where a value of “0” has to be stored in the first and second memory elements 111 and 112, “1” is stored in the first memory element 111, and “0” is stored in the second memory element 112. In a case where the content of the ternary memory is “1”, “0” is stored in the first memory element 111, and “1” is stored in the second memory element 112. In a case where the content of the ternary memory is “X” (don't care), “1” is stored in each of the first memory element 111 and the second memory element 112.

(19) In an example in FIG. 2, “1” is stored in the first memory element 111, and “0” is stored in the second memory element 112. Thus, the content of the ternary memory is “0”.

(20) In addition, in a case where “0” is input as the search key 13, a value of “1” for the first memory element 111 is output, and this corresponds to a match signal.

(21) However, in a case where “1” is input as the search key 13, a value of “0” for the second memory element 112 is output, and thus the result is output as a mismatch signal.

(22) That is, the TCAM cell 110 according to the embodiment of the present invention outputs a signal stored in an address, with the search key 13 as the addresses of the first and second memory elements 111 and 112. This provides the advantage of outputting a match result without a separate comparative circuit or architecture.

(23) FIG. 3 is a diagram illustrating a 1×2 TCAM 200 that results from increasing the number of TCAM cells, each being illustrated in FIG. 2, in a width direction.

(24) The 1×2 TCAM 200 results from increasing the number of TCAM cells in order to perform parallel processing in a case where the search key 13 that is input is multiple bits long. Outputs from first and second TCAM cells 110 and 120 are sequentially AND-cascaded. Thus, the result is output as a match vector that is a final match or mismatch signal.

(25) Specifically, the output from the first TCAM cell 110 is AND-cascaded with “1” by a first AND gate 210. The output from the second TCAM cell 120 is AND-cascaded with the output from the first AND gate 210 by a second AND gate 220. Thus, a final match vector is output.

(26) That is, in a case where all outputs from the TCAM cells in the width direction are match signals, the match vector is output as a match signal.

(27) FIG. 4 is a diagram illustrating a 2×1 TCAM 300 that results from increasing the number of TCAM cells, each being illustrated in FIG. 2, in a depth direction.

(28) The 2×1 TCAM 300 results from arranging TCAM cells 110 and 130 in the vertical direction. The same search key is input into each of the TCAM cells 110 and 130. As a result, each of the TCAM cells 110 and 130 outputs a match signal or a mismatch signal.

(29) FIG. 5 is a diagram illustrating a D×W TCAM that results from increasing the number of TCAM cells, each being illustrated in FIG. 2, in the depth and width directions.

(30) The same search key is input into TCAM cells 420 arranged in the depth direction, and outputs from TCAM cells 410 arranged in the width direction are sequentially AND-cascaded. Thus, a match vector is output.

(31) FIG. 6 is a diagram illustrating an example 500 where the 4×4 TCAM in FIG. 1 is realized by employing the TCAM architecture according to the present invention. In a case where the search key 13, that is, “1100”, is input, it is seen from FIG. 6 that a match signal is output in a match vector [2]. The match signal is provided to the priority encoder. The priority encoder outputs a match address.

(32) FIG. 7 is a diagram illustrating an FPGA-based TCAM architecture according to another embodiment of the present invention. With reference to FIG. 7, the FPGA-based TCAM architecture (hereinafter referred to as “TCAM architecture”) according to the embodiment of the present invention is a TCAM architecture that is designed on the basis of a Field-Programmable Gate Array (FPGA).

(33) Generally, a static random access memory (SRAM)-based TCAM suffers from longer update latencies and has to suspend search operations during an update process. This makes the search operations infeasible in applications that require high-frequency updates.

(34) However, the present invention is directed to a dynamically re-configurable TCAM design on FPGAs. Distributed RAM resources in FPGAs are exploited by configuring look-up table RAMs (LUTRAMs) available in SliceM type logic slices as quad-port RAM.

(35) Contemporary FPGA devices include configurable logic blocks (CLBs), programmable interconnect elements, clock distribution networks, block RAMs, digital signal processing slices, and external input/output blocks. The CLBs available on FPGA include two types of slices, “L” type slice and “M” type slice.

(36) In addition, an FPGA slice includes four 6 input look-up tables (6 input LUTs).

(37) In addition, the “M” type slice called SliceM can be configured as a look-up table RAM (LUTRAM) as well as a function generator for implementing logic, and the “L” type slice called SliceL can be configured as a function generator for implementing logic, not as a look-up table RAM.

(38) In addition, the RAM constructed using the look-up table RAMs of SLice M is known as distributed RAM.

(39) A TCAM architecture 1000 according to another embodiment of the present invention includes four 64-bit look-up table RAMs 1100, 1200, 1300, and 1400 of SliceM. Three look-up table RAMs 1100, 1200, 1300 (a look-up table RAM A, a look-up table RAM B, and a look-up table RAM C), as read ports, implements 18 TCAM bits, and the remaining look-up table RAM 1400 (a look-up table D) is used as a write port.

(40) In addition, the four look-up table RAMs 1100, 1200, 1300, and 1400 share a common write address port. Four distinct bits are written to the look-up table RAMs using data in ports DIA, DIB, DIC, and DID. A write address is applied to the look-up table RAM D using an ADDRD port.

(41) In addition, at the same time, address ports of the look-up table RAM A 1100, the look-up table RAM B 1200 and the look-up table RAM C 1300 are available for read. This structure makes a quad-port RAM with three read ports and with one write port.

(42) In addition, each of the look-up table RAM A 1100, the look-up table RAM B 1200, and the look-up table RAM C 1300 has many bits, as many as the number of values that are representable by the search key (TCAM word).

(43) In addition, the look-up table RAM A 1100, the look-up table RAM B 1200, and the look-up table RAM C 1300 implement an 18-bit TCAM word 20. A TCAM word 21 that is input into the look-up table RAM A 1100, a TCAM word 22 that is input into the look-up table RAM B 1200, and a TCAM word 23 that is input into the look-up table RAM C 1300 are each implemented as a 6-bit TCAM word.

(44) In addition, the 6-bit TCAM word can represent 64 values. Thus, the look-up table RAM A 1100, the look-up table RAM B 1200, the look-up table RAM C 1300 are each made up of a 64-bit memory element.

(45) For example, as illustrated in FIG. 7, in the look-up table RAM A 1100, “1” is written only in the most significant bit b.sub.63 in order to implement a TCAM word, that is, “111111”, and “0” is written in the remaining bits. In addition, in order to implement a TCAM word, that is, “000000x”, in the look-up table RAM B 1200, “1” is written in the least significant bit b.sub.0 in order to implement a TACM word, that is “000000”, “1” is written in the second least significant bit b in order to implement a TCAM word, that is, “000001”, and “0” is written in the remaining bits.

(46) In addition, in order to implement “000xxx”, in the look-up table RAM C 1300, “1” is written in 8 bits (“000000” to “000111” are implemented) starting with the least significant b.sub.0, and “0” is written in the remaining bits.

(47) That is, in the look-up table RAM A 1100, the look-up table RAM B 1200, the look-up table RAM C 1300, “1” is written in a bit that corresponds to a value of the search key, and “0” is written in bits that do not correspond to the value of the search key.

(48) Then, when search keys to be searched for are input in parallel into the look-up table RAMs A, B, and C 1100, 1200, and 1300, direct access to the bit for the address corresponding to the value of the search key is made, and thus a match result can be outputted.

(49) In addition, outputs from the look-up table RAMs A, B, and C 1100, 1200, and 1300 are ANDed through a carry chain 1500. Thus, a final match result is output.

(50) In addition, in order to transfer the match result to a next slice (a slice that is connected in the width direction), the look-up table RAM D 1400 permanently initializes all bits to a logic value of “1”.

(51) In addition, the TCAM architecture can be extended with connections in the width direction and the depth direction.

(52) On the other hand, in the TCAM architecture according to the present invention, direct access to an address of a look-up table RAM corresponding to the value of the search key is made, and a result indicating whether a match or a mismatch is found is output. Thus, values stored in the remaining bits that do not correspond to the value of the search key can be updated while at the same time conducting the search.

(53) FIG. 8 is a diagram illustrating Carry Chain Structures of the present invention. With reference to FIG. 8, the CLBs are the main logic implementation resources on FPGA. A CLB element on FPGAs contains several slices. Each slice on CLBs has an independent carry chain structure. The carry chain on a slice is hardwired and can be connected to the carry chain of the slices belonging to the same column in the next CLBs. Thus multiple slices sharing the same column are cascaded by connecting through carry chains as shown in FIG. 8.

(54) To this end, as illustrated in FIG. 9, an update logic 2000 may be included. The update logic 2000 includes a log.sub.2D-bit decoder 2100, a MOD-64 counter 2200, and comparators 2300, 2310, and 2320.

(55) The log.sub.2D-bit decoder 2100 decodes and outputs an update address, and selects a row of a look-up table RAM implementing a TCAM word for write.

(56) In all cycles, the MOD-64 counter 2200 generates and outputs a new 6-bit sequence (from “000000” to “111111”).

(57) The comparators 2300, 2310, and 2320 each compare a TCAM word for update and the 6-bit sequence that is generated in the MOD-64 counter 2200, and, if a match is found, records a logical value of “1” in the corresponding update address.

(58) That is, during an update process, the remaining blocks are available for search operations, thereby allowing dynamic updates.

(59) The present invention is not limited to the embodiments of the present invention, which are described above with reference to the drawings. It is apparent to a person of ordinary skill in the art that various amendments and alterations are possible within the scope that does not depart from the nature and gist of the present invention.