To CMP or not to CMP: Analyzing Packet Classification on Modern and Traditional Network Processors

Packet classification is a central component of modern network functionality, yet satisfactory memory usage and overall performance remains an elusive challenge at the highest speeds. The recent emergence of chip multiprocessors and other low-cost, highly parallel processing hardware provides a promising platform on which to realize increased classification performance. In this paper we analyze the performance of packet classification in the context of parallel, shared-memory architectures. We begin with two classic algorithms--Aggregated Bit Vector and HiCuts--and parallelize each of them multiple ways. We discuss the tradeoffs of different architectures in the context of these algorithms, and we evaluate the schemes on both chip multiprocessor (CMP) and symmetric multiprocessor (SMP) hardware. Our experiments show that for CMPs, resource-sharing replaces synchronization scaling as the primary speedup-limiting bottleneck. Further, while SMPs provide more processing power core-for-core, CMPs nevertheless provide the best overall performance when all available execution contexts are employed