100005: Efficient TCAM-based Packet Classification Using Multiple Lookups and Classifier Semantics


Packet classification enables many networking services on the Internet, such as firewall packet filtering and traffic accounting. Using Ternary Content Addressable Memory (TCAM) chips to perform high-speed packet classification has become the de facto standard in industry. TCAM chips classify packets by comparing a packet with the full suite of classification rules in ternary encoding, the comparison being done in parallel.

Unfortunately, TCAMs have limitations of relatively small capacity, high power consumption & heat generation, and high cost. The well-known, range-expansion problem exacerbates these limitations by significantly decreasing the limited capacity of TCAMs as each classifier rule typically has to be converted into multiple TCAM rules.

Traditional packet classification looks at five fields: source and destination IP addresses, source and destination port numbers, and protocol type. New Internet services and new security threats are leading to more complex rule sets. Along with the increasing adoption of IPv6, the size and width growth of packet classifiers puts more demand on TCAM capacity.


Michigan State University has developed a suite of algorithms to enable the optimal use of TCAM chips. This invention moves away from the idea that packet classification should be performed by a single, slow lookup in a single, large TCAM table. Instead, it classifies packets using several fast lookups in several small TCAM tables and includes algorithms that transform a traditional single lookup TCAM table into multiple, small TCAM tables. Multiple Lookups encompasses a set of technologies that can be used to provide the efficiencies of multiple lookups, including algorithms for multiple sequential lookups, pipelined-lookup, and packing.

Other inventions inventions in the suite include:

* A Systematic Approach to Minimizing Packet Classifiers in TCAM (090003)

* A Systemic Nonprefix Approach to Minimizing Packet Classifiers in TCAMs (100004)

IP Protection Status

Patent pending

Patent Information:

For Information, Contact:

Raymond DeVito
Technology Manager
Michigan State University - Test