Algorithms for advanced packet classification with ternary CAMs
Algorithms for advanced packet classification with ternary CAMs
复制标题
DOI：
10.1145/1080091.1080115
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
K. Lakshminarayanan;Anand Rangarajan;S. Venkatachary
中科院分区：
文献类型：
--
作者：
K. Lakshminarayanan;Anand Rangarajan;S. Venkatachary
三值内容可寻址存储器（TCAM）在存储和搜索访问控制列表（Access Control List，ACL）的行业中已获得广泛接受。本文针对TCAM中遇到的两个重要问题：减少值域扩展和多匹配分类，提出了一种新的TCAM扩展算法，该算法通过值域字段来表示TCAM中的值域规则，将一个值域规则映射到多个TCAM条目，从而减少了TCAM的使用率。我们提出了一个新的方案，称为数据库独立的范围预编码（DIRPE），在早期的方法相比，减少了最坏情况下的TCAM条目的数量一个单一的规则映射。DIRPE的工作没有数据库的先验知识，规模时，大量的范围是存在的，并具有良好的增量更新属性。我们的第二个算法解决了在TCAM中找到多个匹配的问题。当搜索时，TCAM返回第一个匹配的条目;然而，新的应用程序需要前几个或所有匹配的条目。我们描述了一种新的算法，称为多匹配使用鉴别器（MUD），发现多个匹配，而不存储任何每搜索状态信息的TCAM，从而使其适合于多线程环境。MUD不会增加所需的TCAM条目数量，因此可以扩展到大型数据库。我们的算法不需要对现有的TCAM进行任何修改，因此相对容易部署。我们使用真实生活和随机数据库的算法进行评估。
Ternary content-addressable memories (TCAMs) have gained wide acceptance in the industry for storing and searching Access Control Lists (ACLs). In this paper, we propose algorithms for addressing two important problems that are encountered while using TCAMs: reducing range expansion and multi-match classification.Our first algorithm addresses the problem of expansion of rules with range fields¿to represent range rules in TCAMs, a single range rule is mapped to multiple TCAM entries, which reduces the utilization of TCAMs. We propose a new scheme called Database Independent Range PreEncoding (DIRPE) that, in comparison to earlier approaches, reduces the worst-case number of TCAM entries a single rule maps on to. DIRPE works without prior knowledge of the database, scales when a large number of ranges is present, and has good incremental update properties.Our second algorithm addresses the problem of finding multiple matches in a TCAM. When searched, TCAMs return the first matching entry; however, new applications require either the first few or all matching entries. We describe a novel algorithm, called Multi-match Using Discriminators (MUD), that finds multiple matches without storing any per-search state information in the TCAM, thus making it suitable for multi-threaded environments. MUD does not increase the number of TCAM entries needed, and hence scales to large databases.Our algorithms do not require any modifications to existing TCAMs and are hence relatively easy to deploy. We evaluate the algorithms using real-life and random databases.