Technical Report Number
Packet switched networks such as the Internet require packet classiﬁcation at every hop in order to ap-ply services and security policies to trafﬁc ﬂows. The relentless increase in link speeds and trafﬁc volume imposes astringent constraints on packet classiﬁcation solutions. Ternary Content Addressable Memory (TCAM) devices are favored by most network component and equipment vendors due to the fast and de-terministic lookup performance afforded by their use of massive parallelism. While able to keep up with high speed links, TCAMs suffer from exorbitant power consumption, poor scalability to longer search keys and larger ﬁlter sets, and inefﬁcient support of multiple matches. The research community has responded with algorithms that seek to meet the lookup rate constraint with greater efﬁciency through the use of com-modity Random Access Memory (RAM) technology. The most promising algorithms efﬁciently achieve high lookup rates by leveraging the statistical structure of real ﬁlter sets. Due to their dependence on ﬁlter set characteristics, it is difﬁcult to provision processing and memory resources for implementations that support a wide variety of ﬁlter sets. We show how several algorithmic advances may be leveraged to im-prove the efﬁciency, scalability, incremental update and multiple match performance of CAM-based packet classiﬁcation techniques without degrading the lookup performance. Our approach, Label Encoded Content Addressable Memory (LECAM), represents a hybrid technique that utilizes decomposition, label encoding, and a novel Content Addressable Memory (CAM) architecture. By reducing the number of implementation parameters, LECAM provides a vehicle to carry several of the recent algorithmic advances into practice. We provide a thorough overview of CAM technologies and packet classiﬁcation algorithms, along with a detailed discussion of the scaling issues that arise with longer search keys and larger ﬁlter sets. We also provide a comparative analysis of LECAM and standard TCAM using a collection of real and synthetic ﬁlter sets of various sizes and compositions.
Taylor, David E. and Spitznagel, Edward W., "On using content addressable memory for packet classiﬁcation" Report Number: WUCSE-2005-9 (2005). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7T43RF4