Fang Yu, T. V. Lakshman, Martin Austin Motoyama and Randy H. Katz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1388
May 2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1388.pdf

New network applications like intrusion detection systems and packet-level accounting require multi-match packet classification, where all matching filters need to be reported. Ternary Content Addressable Memories (TCAMs) have been adopted to solve the multi-match classification problem due to their ability to perform fast parallel matching. However, TCAM is expensive and consumes large amounts of power. None of the previously published multi-match classification schemes is both memory and power efficient. In this paper, we develop a novel scheme that meets both requirements by using a new Set Splitting Algorithm (SSA). The main idea of SSA is that it splits filters into multiple groups and performs separate TCAM lookups into these groups. It guarantees the removal of at least half the intersections when a filter set is split into two sets, thus resulting in low TCAM memory usage. SSA also accesses filters in the TCAM only once per packet, leading to low power consumption. We compare SSA with two best known schemes: MUD and Geometric Intersectionbased solutions. Simulation results based on the SNORT filter sets show that SSA uses approximately the same amount of TCAM memory as MUD, but yields a 75% to 95% reduction in power consumption. Compared with Geometric Intersection-based solutions, SSA uses 90% less TCAM memory and power at the cost of one additional TCAM lookup per packet.

BibTeX citation:

@techreport{Yu:CSD-05-1388,
    Author = {Yu, Fang and Lakshman, T. V. and Motoyama, Martin Austin and Katz, Randy H.},
    Title = {SSA: A Power and Memory Efficient Scheme to Multi-Match Packet Classification},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2005},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5654.html},
    Number = {UCB/CSD-05-1388},
    Abstract = {New network applications like intrusion detection systems and packet-level accounting require multi-match packet classification, where all matching filters need to be reported. Ternary Content Addressable Memories (TCAMs) have been adopted to solve the multi-match classification problem due to their ability to perform fast parallel matching. However, TCAM is expensive and consumes large amounts of power. None of the previously published multi-match classification schemes is both memory and power efficient. In this paper, we develop a novel scheme that meets both requirements by using a new Set Splitting Algorithm (SSA). The main idea of SSA is that it splits filters into multiple groups and performs separate TCAM lookups into these groups. It guarantees the removal of at least half the intersections when a filter set is split into two sets, thus resulting in low TCAM memory usage. SSA also accesses filters in the TCAM only once per packet, leading to low power consumption. We compare SSA with two best known schemes: MUD and Geometric Intersectionbased solutions. Simulation results based on the SNORT filter sets show that SSA uses approximately the same amount of TCAM memory as MUD, but yields a 75% to 95% reduction in power consumption. Compared with Geometric Intersection-based solutions, SSA uses 90% less TCAM memory and power at the cost of one additional TCAM lookup per packet.}
}

EndNote citation:

%0 Report
%A Yu, Fang
%A Lakshman, T. V.
%A Motoyama, Martin Austin
%A Katz, Randy H.
%T SSA: A Power and Memory Efficient Scheme to Multi-Match Packet Classification
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1388
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5654.html
%F Yu:CSD-05-1388