Energy-Efficient TCAM Search Engine Design Using Priority-Decision in Memory Technology
Abstract:
Ternary content-addressable memory (TCAM)-based search engines generally need a priority encoder (PE) to select the highest priority match entry for resolving the multiple match problem due to the don’t care (X) features of TCAM. In contemporary network security, TCAM-based search engines are widely used in regular expression matching across multiple packets to protect against attacks, such as by viruses and spam. However, the use of PE results in increased energy consumption for pattern updates and search operations. Instead of using PEs to determine the match, our solution is a three-phase search operation that utilizes the length information of the matched patterns to decide the longest pattern match data. This paper proposes a promising memory technology called priority-decision in memory (PDM), which eliminates the need for PEs and removes restrictions on ordering, implying that patterns can be stored in an arbitrary order without sorting their lengths. Moreover, we present a sequential input-state (SIS) scheme to disable the mass of redundant search operations in state segments on the basis of an analysis distribution of hex signatures in a virus database. Experimental results demonstrate that the PDM-based technology can improve update energy consumption of nonvolatile TCAM (nvTCAM) search engines by 36%–67%, because most of the energy in these search engines is used to reorder. By adopting the SIS-based method to avoid unnecessary search operations in a TCAM array, the search energy reductionis around 64% of nvTCAM search engines. The proposed architecture of this paper analysis the logic size, area and power consumption using Tanner tool.
Existing System:
Regular expression matching algorithms have been implemented in ternary content-addressable memory (TCAM)-based search engines for exploiting their parallel comparison and wildcard search abilities to achieve high speeds. These TCAM-based search engines can be used to monitor patterns spread across multiple packets in a flow, because they run a unique state machine instance for each flow. To check the packet head (IP address/port number/protocol) and payload, the TCAM-based search engine is implemented in firewalls, as shown in Fig. 1. When a new connection is established, it is scanned by the search engine to confirm that it is secure. Then, these packets are forwarded to the host. According to this flow, attacks, such as spam, spyware, worms, and viruses, can be immediately detected for network security because of the parallel and don’t care (X) search abilities of TCAM. Moreover, TCAM-based search designs can be used not only in network security of firewalls but also in broader applications, such as wireless sensor networks, biometrics, face recognition, and vehicle license plate recognition, as shown in Fig. 2.
Figure 1: Firewall router architecture
Unfortunately, TCAM-based search engines need to maintain sorted lists with pattern lengths to resolve multiple matches by the priority encoder (PE). This results in slow update and increases energy consumption in update and search operations. On the other hand, high energy consumption in the TCAM array is really the most critical challenge for TCAM designers, because all entries of the TCAM are searched in parallel comparison, which causes a large amount of power dissipation in match lines (MLs) switching. Therefore, restrictions on the ordering of TCAM arrays and the high energy consumption of search operation are major issues in TCAM-based search engines. Being composed of low-density memory cells, which have high leakage power, is yet another disadvantage of SRAM-based TCAM devices.
Figure 2: TCAM search engine in applications
Disadvantages:
- Power consumption is high
Proposed System:
We propose an energy-efficient TCAM search engine, employing a clever decision-making process in memory technology for search operations without using PEs. A key challenge of this design lies in obtaining a longest pattern length to determine a longest pattern match entry in an arbitrary order.
TCAM Search Engine for Regular Expression Matching:
Fig. 3 shows the details of the TCAM-based search engine architecture for implementing the state machine, which consists of a TCAM array, a PE, and an SRAM array. Each TCAM entry is conceptually partitioned into two fields to represent a pattern that consists of the current state and an input character (hex format). The corresponding data (next state) are stored in the SRAM array at an address computed from the TCAM and PE output. The PE function is composed of a multiple match resolver and match address encoder. It selects the highest priority match entry and encodes this match location into binary format, which is used to retrieve the corresponding data in the SRAM array.
Figure 3: Traditional TCAM-based search engines for regular expressionmatching
In this architecture, each signature has several transitions in the state machine that represents a lot of patterns in TCAM entries. The current state register is initialized to state 0 and the search data of the input buffer are stored in the input register. If there is a matching entry that matches the state and input character in the TCAM array, the PE outputs the index of the matching entry to get the next state information from the SRAM array. The “don’t care (X)” features of TCAM can efficiently reduce data entries, as shown in Fig. 3. On the other hand, multiple entries can be simultaneously matched because don’t care (X) bits, where there is always a match regardless of the search key. Therefore, the PE will output the index of the first matched (high priority) entry. This process is repeated until no pattern needs to be monitored in the packets. If there is no matched entry in the TCAM, the current state register is set to the initial state and an input pointer is advanced to the next input.
Conventional Asymmetric TCAM:
A typical AS-TCAM cell consists of three major components, as shown in Fig. 4. The first component is an 8TXOR-type cell used to compare the stored data with the search data. The second component is used to store a mask bit to indicate whether the status of the TCAM cell is don’t care (X). The third component is the logic that determines the search result based on the ML state of whether pulled down or not, and it is implemented with two nMOS transistors in series and controlled by the mask bit and the XOR result of CAM cell.
Figure 4: Structure of AS-TCAM cell.
Conventional Symmetric TCAM:
Distinct differences between S-TCAM and AS-TCAM include the symmetric cell structure, and the difference is meaning of the cell data and the difference in meaning of the mask bit. Fig. 5 shows that an S-TCAM cell consists of two SRAM cells and four transistors, which are used to store data and compare the stored data with search data, respectively. The four transistors are the necessary evaluation logic to generate the comparison result based on the charge of the ML.
Figure 5: Structure of S-TCAM cell
RCSD-4T2R nvTCAM:
nvTCAMs have been designed to achieve small area and fast/low-power wake-up operations. Fig. 6 shows the circuit scheme for a resistive memory (RRAM)-based nvTCAM comprising two RRAM devices (RT/RB), two comparison transistors (NC/NCB), a write-control transistor (NWC), and an ML-driver transistor (NML). In the standby mode, word line, write-voltage-control and dynamic source line (DSL) are maintained at 0, and the ML is kept at a precharge voltage (VPRE). After the precharging operation, different search data are put on data lines to perform search operations.
Figure 6: Schematic of RCSD-4T2R nvTCAM cell
Advantages:
- Low power consumption
Software implementation:
- Tanner tool