Wire Speed Packet Classification Without TCAMs: A Few More Registers (And A Bit of Logic) Are Enough

摘要

Packet classification is the foundation of many Internet functions such as QoS and security. A long thread of research has proposed efficient software-based solutions to this problem. Such software solutions are attractive because they require cheap memory systems for implementation, thus bringing down the overall cost of the system. In contrast, hardware-based solutions use more expensive memory systems, e.g., TCAMs, but are often preferred by router vendors for their faster classification speeds. The goal of this paper is to find a 'best-of-bofh-worlds' solution — a solution that incurs the cost of a software-based system and has the speed of a hardware-based one. Our proposed solution, called smart rule cache achieves this goal by using minimal hardware — a few additional registers — to cache evolving rules which preserve classification semantics, and additional logic to match incoming packets to these rules. Using real traffic traces and real rule sets from a tier-1 ISP, we show such a setup is sufficient to achieve very high hit ratios for fast classification in hardware. Cache miss ratios are 2 ～ 4 orders of magnitude lower than flow cache schemes. Given its low cost and good performance, we believe our solution may create significant impact on current industry practice.