Packet classification is the core mechanism that enables many networking devices, such as routers and firewalls, to perform services such as packet filtering, virtual private networks (VPNs), network address translation (NAT), quality of service (QoS), load balancing, traffic accounting and monitoring, differentiated services (Diffserv), etc. The essential problem is to compare each packet with a list of predefined rules, which we call a packet classifier, and find the first (i.e., highest priority) rule that the packet matches. Table 1 below shows an example packet classifier of three rules. The format of these rules is based upon the format used in access control lists (ACLs), such as those found on Cisco routers. In this disclosure, the terms packet classifiers, ACLs rule lists, and lookup tables are used interchangeably.
TABLE 1An example packet classifierSourceDest.Pro-Ac-RuleSource IPDest. IPPortPorttocoltionr11.2.3.0/24162.168.0.1[1.65534][1.65534]TCPacceptr21.2.11.0/192.168.0.1[1.65534][1.65534]TCPaccept24r3*****dis-card
Hardware-based packet classification using Ternary Content Addressable Memories (TCAMs) is now the de facto industry standard. TCAM-based packet classification is widely used because Internet routers need to classify every packet on the wire. Although software based packet classification has been extensively studied, these techniques cannot match the wire speed performance of TCAM-based packet classification systems.
As a traditional random access memory chip receives an address and returns the content of the memory at that address, a TCAM chip works in a reverse manner. That is, it receives content and returns the address of the first entry where the content lies in the TCAM in constant time (i.e., a few clock cycles). Exploiting this hardware feature, TCAM-based packet classifiers store a rule in each entry as an array of 0's, 1's, or *'s (don't-care values). A packet header (i.e., a search key) matches an entry if and only if their corresponding 0's and 1's match. Given a search key to a TCAM, the hardware circuits compare the key with all its occupied entries in parallel and return the index (or the content, depending on the chip architecture and configuration,) of the first matching entry.
Although TCAM-based packet classification is currently the de facto standard in industry, TCAMs do have several limitations. First, TCAM chips have limited capacity. The largest available TCAM chip has a capacity of 36 megabits (Mb). Smaller TCAM chips are the most popular due to the other limitations of TCAM chips stated below. Second, TCAMs require packet classification rules to be in ternary format. This leads to the well-known range expansion problem, i.e., converting packet classification rules to ternary format results in a much larger number of TCAM rules, which exacerbates the problem of limited capacity TCAMs. In a typical packet classification rule, the three fields of source and destination IP addresses and protocol type are specified as prefixes (e.g., 1011****) where all the *s are at the end of the ternary string, so the fields can be directly stored in a TCAM. However, the remaining two fields of source and destination port numbers are specified in ranges (i.e., integer intervals such as [1, 65534]), which need to be converted to one or more prefixes before being stored in a TCAM. This can lead to a significant increase in the number of TCAM entries needed to encode a rule. For example, 30 prefixes are needed to represent the single range [1, 65534], so 30×30=900 TCAM entries are required to represent the single rule r1 in Table 1. Third, TCAM chips consume lots of power. The power consumption of a TCAM chip is about 1.85 Watts per Mb. This is roughly 30 times larger than a comparably sized SRAM chip. TCAMs consume lots of power because every memory access searches the entire active memory in parallel. That is, a TCAM is not just memory, but memory and a (very fast) parallel search system. Fourth, TCAMs generate lots of heat due to their high power consumption. Fifth, a TCAM chip occupies a large footprint on a line card. A TCAM chip occupies 6 times (or more) board space than an equivalent capacity SRAM chip. For networking devices such as routers, area efficiency of the circuit board is a critical issue. Finally, TCAMs are expensive, costing hundreds of dollars even in large quantities. TCAM chips often cost more than network processors. The high price of TCAMs is mainly due to their large die area, not their market size. Power consumption, heat generation, board space, and cost lead to system designers using smaller TCAM chips than the largest available. For example, TCAM components are often restricted to at most 10% a of an entire board's power budget, so a 36 Mb TCAM may not be deployable on all routers due to power consumption reasons.
While TCAM-based packet classification is the current industry standard, the above limitations imply that existing TCAM-based solutions may not be able to scale up to meet the future packet classification needs of the rapidly growing Internet. Specifically, packet classifiers are growing rapidly in size and width due to several causes. First, the deployment of new Internet services and the rise of new security threats lead to larger and more complex packet classification rule sets. While traditional packet classification rules mostly examine the five standard header fields, new classification applications begin to examine addition fields such as classifier-id, protocol flags, ToS (type of service), switch-port numbers, security tags, etc. Second, with the increasing adoption of IPv6, the number of bits required to represent source and destination IP address will grow from 64 to 256. The size and width growth of packet classifiers puts more demand on TCAM capacity, power consumption, and heat dissipation.
To address the above TCAM limitations and ensure the scalability of TCAM-based packet classification, the TCAM-based classifier compression problem has been studied; that is, given a packet classifier, efficiently generate a semantically equivalent packet classifier that requires fewer TCAM entries. Note that two packet classifiers are (semantically) equivalent if and only if they have the same decision for every packet. TCAM-based classifier compression helps to address the limited capacity of deployed TCAMs because reducing the number of TCAM entries effectively increases the fixed capacity of a chip. Reducing the number of rules in a TCAM directly reduces power consumption and heat generation because the energy consumed by a TCAM grows linearly with the number of ternary rules it stores. Finally, TCAM-based classifier compression lets us use smaller TCAMs, which results in less power consumption, less heat generation, less board space, and lower hardware cost.
Several prior TCAM-based classifier compression schemes have been developed. While these techniques vary in effectiveness, they all suffer from one fundamental limitation: they only produce prefix classifiers, which means they all miss some opportunities for compression. Therefore, it is desirable to provide a new TCAM-based classifier compression scheme that is not limited to producing prefix classifiers.
This section provides background information related to the present disclosure which is not necessarily prior art.