Memory-Efficient 5D Packet Classification At 40 Gbps

Packet classification is one of the most important enabling technologies for next generation network services. Even though many multi-dimensional classification algorithms have been proposed, most of them are precluded from commercial equipments due to their high memory requirements. In this paper, we present an efficient packet classification scheme, called Bloom Based Packet Classification (B2PC). B2PC comprises of an innovative 5-field search algorithm that decomposes multifield classification rules into internal single field rules which are combined using multi-level Bloom filters. The design of B2PC is optimized for the common case based on analysis of real world classification databases. The hardware implementation of this scheme handles 4K rules by involving only 530KB of memory for its data structures, while it supports network streams at a rate of 15Gbps even in the worst case, and more than 40Gbps in the average case. This system covers 1.3 mm in a 0.18mum CMOS technology. We show that given a certain memory budget and silicon cost, the B2PC is the most efficient hardware-based approach to the classification problem.