Technical Report Number
TCAMs are the most popular practical approach to high performance packet classiﬁca-tion, but they suﬀer from ineﬃcient handling of range matches; the standard approach of rule replication can result in a 2-6x increase in TCAM words needed, for typical ﬁrewall databases. We describe three CMOS implementations of a range check circuit to address this problem; the most eﬃcient of these designs allows classiﬁcation on the standard IPv4 5-tuple with only a 46% increase in transistor count, rather than relying on rule replication. By avoiding replication, the overall transistor count required is only 24% to 78% of the stan-dard TCAM design, for real ﬁlter databases used in this study; power dissipation is reduced similarly. Also, range check support greatly simpliﬁes creation and maintenance of the TCAM contents, since there is now a one-to-one correspondence between ﬁlters and TCAM entries. Additionally, we show how to construct a more versatile device using range-check sub-ﬁelds that can be chained together as needed.
Spitznagel, Edward W., "CMOS Implementations of a Range Check Circuit" Report Number: WUCSE-2004-39 (2004). All Computer Science and Engineering Research.