100005: Efficient TCAM-based Packet Classification Using Multiple Lookups and Classifier Semantics
Case ID:
TEC2010-0005
Web Published:
7/21/2014
Description:
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.
Description
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:
App Type |
Country |
Serial No. |
Patent No. |
File Date |
Issued Date |
Expire Date |
For Information, Contact:
Raymond Devito
Technology Manager
Michigan State University - Test
517-355-2186
devitora@msu.edu