Reviewer: Ben Wun
Date: 11-17-2005
How would you rate this paper, relative to others we have read? top 25%, but not top 10%
How would you rate your kowledge of the topic of this paper? novice
What problem or issue does the paper address? Why is it important?
This paper proposes an algorithm for organizing data in TCAMs for multi-match packet classification that minimizes the number of lookups, power consumption, and entries used. This is important because packet classification algorithms need to be able to keep up with line speed, but the TCAMs used to accelerate them are expensive and draw a lot of power.
What are the main contributions of the paper and why are they important?
The main contribution of this paper is a set splitting algorithm (SSA) that reduces the number of intersecting rules that need to be inserted in a TCAM while keeping the number of lookups per packet small. The problem of splitting the set is NP hard, but a usable approximation algorithm is given. This results in less power and TCAM space utilization than the existing schemes they compare it to.
How significant are these contributions relative to previous work?
If the MUD and Geometric Intersection algorithms they compare SSA against really are the best solutions out there (I am not familiar enough with this area to say if they are or not), then I think this is a fairly important contribution. MUD can require a large number of lookups, and Geometric Intersection can require a lot of storage space. SSA manages to come very close to MUD in terms of storage requirements when using 4 sets, and requires only 4 lookups in that case (as opposed to a maximum of 20 for MUD), which is not much worse than the 1 required of Geometric Intersection.
Give detailed comments justifying your view of the paper.
When using 4 sets on the SNORT rule set, SSA manages to come close to MUD in terms of storage space and update costs, while requiring a small and deterministic number of lookups per packet. This seems to combine the strengths of MUD and geometric intersection quite nicely.
The authors indicate that there exist TCAMs that would allow them to implement their scheme in current hardware, so it would have been nice to see an evaluation of a working prototype, but this is a minor complaint.