All-Match Based Complete Redundancy Removal for Packet Classifiers in TCAMs
All-Match Based Complete Redundancy Removal for Packet Classifiers in TCAMs
复制标题
DOI：
10.1109/infocom.2008.31
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
A. Liu;C. Meiners;Yun Zhou
中科院分区：
文献类型：
--
作者：
A. Liu;C. Meiners;Yun Zhou
包分类是Internet上许多网络服务（如防火墙包过滤、流量计费）的核心机制。使用三元内容可寻址存储器（TCAMs）来执行高速分组分类已经成为事实上的工业标准。TCAMs通过将数据包与所有三进制编码的分类规则并行比较，在恒定时间内对数据包进行分类。尽管tcam速度快，但也存在众所周知的区间膨胀问题。由于分组分类规则的字段通常指定为间隔，因此将这些规则转换为与TCAM兼容的规则可能会导致规则数量的爆炸式增长。如果tcam容量大，这不是问题。不幸的是，tcam的容量非常有限，更多的规则意味着tcam的功耗和热量消耗更多。更糟糕的是，随着互联网上部署的服务数量的增加，包分类器中的规则数量也在迅速增加。通过去除包分类器中的冗余规则，可以解决TCAMs的区间扩展问题。这种等效的转换可以显著减少包分类器所需的TCAM条目的数量。我们在实际包分类器上的实验表明，通过去除冗余规则，TCAM条目的数量平均减少了58.2%。本文提出了一种基于全匹配的完全冗余去除算法。这是第一个尝试从全匹配的角度解决首次匹配问题的算法。我们正式证明了我们的冗余去除算法保证生成的包分类器中没有冗余规则。我们在现实生活和合成包分类器上进行了广泛的实验。实验结果表明，我们的冗余去除算法在减少TCAM条目方面是有效的，在运行时间方面是有效的。
Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known interval expansion problem. As packet classification rules usually have fields specified as intervals, converting such rules to TCAM- compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules means more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers have been increasing rapidly with the growing number of services deployed on the internet. The interval expansion problem of TCAMs can be addressed by removing redundant rules in packet classifiers. This equivalent transformation can significantly reduce the number of TCAM entries needed by a packet classifier. Our experiments on real- life packet classifiers show an average reduction of 58.2% in the number of TCAM entries by removing redundant rules. In this paper, we propose an all-match based complete redundancy removal algorithm. This is the first algorithm that attempts to solve first-match problems from an all-match perspective. We formally prove that our redundancy removal algorithm guarantees no redundant rules in resulting packet classifiers. We conducted extensive experiments on both real-life and synthetic packet classifiers. These experimental results show that our redundancy removal algorithm is both effective in terms of reducing TCAM entries and efficient in terms of running time.