100004: A Systematic Non-Prefix Approach to Minimizing Packet Classifiers in TCAMs
Case ID:
TEC2010-0004
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 is another method that takes a given packet
classifier as input and outputs a semantically equivalent packet classifier that
requires fewer TCAM entries. It is a non-prefix classifier that uses two
techniques, bit swapping and bit merging, to identify and merge the rules that
can be combined. Bit Weaving can be used as an alternative to TCAM Razor or in
combination with it.
Other inventions inventions in the suite
include:
* A Systematic Approach
to Minimizing Packet Classifiers in TCAM (090003)
* Efficient TCAM-Based
Packet Classification Using Multiple Lookups and Classifier Semantics
(100005)
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