Ternary Content Associated Memories (TCAMs) allow for the masked matching of entries to a search key. Masked matching facilitates search operations common in packet networking. When performing packet processing, masked matching is typically performed in several processing steps to determine next destinations, provide access control of packets into a network, identify traffic source of a packet, and other searching or matching operations. These actions are referred to as rules, which are ideally matched to a particular packet. Prior to performing each of these search operations, a search key is extracted from a packet header through parsing to determine the packet format and header contents.
Both fixed hardware and flexible firmware based solutions are used with firmware based solutions preferred in networks where the protocols used vary over time. Typical flexible implementations make use of programmable processing cores to perform analysis of header segments to determine format and extract values from the header which can be used for searching with a narrow key. Depending upon the specific implementation, performance of firmware-based solutions may be variable with the packet processing rate being non-deterministic. The parsing is required to reduce the width of the search key to something useable with available TCAM implementations. Parsing is also required to determine which fields within the header segment should be selected for the search key with different header segment types requiring different construction of the search key.
Providing TCAM functionality with support for large key widths greater than the number of header bytes of network packets allows the matching of the full header enabling parsing and searching to be performed in a single operation with no complex programming and deterministic performance.
A traditional memory-based TCAM implementation is constructed from bit cells with single bit comparison logic attached to word compare lines with a priority encoder used to indicate which compare line found a match. Such designs consume significant power as all bit cells are simultaneously read on each match operation and all bit locations for the full width of the matching patterns must be present. Additionally, support for features like range matching, longest prefix matching, or inverse matching significantly complicates the design. Finally, memory-based TCAM implementations are implementation technology specific and involve significant effort to port from one semiconductor process node to another as required when embedding TCAM functionality within a packet networking device. In response to the deficiencies of memory-based TCAMs, several algorithmic implementations have been used. Most of these implementations make use of Radix trees, HiCuts, HyperCuts, or other decision tree-try-based based packet classification algorithms for searching of patterns.
Tries are a commonly used method in searching of a data set for matching to an input search key. To perform a search, a tree is traversed as bits from the search key are compared one bit at a time from most significant to least significant bit position. With improvements, they work well for longest prefix matching of keys to the existing dataset as well. Unfortunately, traversal of the tree consumes significant time for long keys, as is required for full packet header matching, as one node of the tree is traversed per bit location in the key. Radix trees or Patricia tries improve upon the latency of searching by combining multiple bits together when they are common to all branches in a given node. However, each of these methods suffers from design challenges when masking is implemented in the search table. When a masked bit, designated as an ‘x’ state by example, is encountered within an entry to the search table, the value must be added to all possible branches of the node where the ‘x’ state is encountered. Many masked bits cause a large increase in the size of the tree. This problem is made worse when considering full packet header matching where many if not most bits of the header are masked.
HiCuts and HyperCuts are useful in dealing with masked bit locations by allowing bits to be selected for traversal of a tree from arbitrary locations within the data values. In packet networking applications where a complete packet header is used as a search key, common bit locations exist within each packet header segment that indicates the packet type and format. HiCuts and HyperCuts enable the use of these known non-masked bits for building and traversal of the search tree. Unfortunately, HiCuts and HyperCuts are not able to support fully nested prefixes that are common in IPv6.
It is therefore desirable to mitigate at least some of the above problems associated with traditional, memory-based TCAM's, thereby providing a system and method for performing masked matching of wide keys against large datasets for packet classification. In particular, it is desirable to provide a system and method for high speed packet matching to a highest precedent rule.