Friday, Oct 16, 2009, 11-12
Room # 3315
Eric Torng
Michigan State University 

Title: 
Minimizing TCAM-based Packet Classifiers

Abstract: 

Packet classification is the core mechanism that enables many networking
services on the Internet such as firewall packet filtering and traffic
accounting. Using Ternary Content Addressable Memories (TCAMs) to perform
high-speed packet classification has become the de facto standard in
industry.  TCAMs classify packets in constant time by comparing a packet
with all classification rules of ternary encoding in parallel and using a
priority encoder to identify the first classification rule that matches the
given packet.

Although TCAMs process packets in constant time, TCAMs do suffer from
several limitations. First, TCAMs come in limited capacities. Second, as
TCAMs increase in size, they become slower, more expensive, and consume
large amounts of energy and generate lots of heat. Third, the number of
rules in packet classifiers has been increasing rapidly with the growing
number of services deployed on the internet as well as the increased number
of threats on the internet. Finally, TCAMs suffer from the well-known
prefix expansion problem. As packet classification rules usually have some
fields specified as intervals, converting such rules to TCAM-compatible
rules may result in an explosive increase in the number of rules.

To address the limitations of TCAMs, we develop a variety of methods to fit
packet classifiers into TCAMs more efficiently. One approach, TCAM Razor,
addresses the following problem: given a packet classifier, how can we
generate another semantically equivalent packet classifier that requires
the least number of TCAM entries? Two other approaches, topological
transformation and TCAM SPliT, provide even more compression than TCAM
Razor by exploiting new more efficient architectural designs.

This talk represents joint work with Alex Liu and Chad Meiners in the
Department of Computer Science and Engineering at Michigan State
University. Portions of this work were presented at ICNP 2007 and
Sigmetrics 2009. This work has been funded in part by the National Science
Foundation under Grant Numbers CNS-0716407 and CNS-0916044.

----------------------

Eric Torng is an associate professor and graduate director in the
Department of Computer Science and Engineering at Michigan State
University. He received his B.A. summa cum laude, in computer science, from
Princeton University in 1989, his M.S. in computer science from Stanford
University in 1992, and his Ph.D. in computer science from Stanford
University in 1994. His research interests include algorithms, scheduling,
and networking; and he has published extensively in these areas. He
received the Withrow Teaching Excellence Award for outstanding instruction
in Engineering in 1996 and in 2002, the Michigan State University
Teacher-Scholar Award in 1999, and a National Science Foundation CAREER
award in 1997.