Wire Speed Packet Classification Without TCAMS: One More Register (and a Bit of Logic) is Enough

Abstract

Many Internet functions, such as QoS and security, require classification of each packet based on a set of rules. As Internet bandwidth and data transmission rates continue to grow, the available time budget to classify each packet continues to diminish. This poses a serious challenge to the task of wire speed packet classification. In this paper, we propose a new solution to this problem, using a smart rule cache that combines simple hardware and software constucts. The hardware consists of a small on-chip cache, large enough to store just one evolving rule, along with some simple logic to match incoming packets against this stored rule. The software component consists of an algorithm by which this rule in cache continuously evolves in respone to changes in incoming traffic pattern. Using real traffice traces and rule sets from a tier-1 ISP, we evaluate the performance of this smart rule cache. Our results demonstrate that this carefully constructed, evolving rule cached on-chip suffices to achieve a hit ratio in excess of 99.9842%, thus meeting our wire speed classification objectives. Given its negligible cost and good performance, we believe our smart rule cache represents a practical solution that may create significant impact on industry practice.