A Memory-efficient Multi-dimensionalHardware-specific Algorithm for PacketClassification

The paper presents a memory-efficientmulti-dimensional hardware-specific algorithm for fastpacket classification. The algorithm builds a decision treein which each leaf node stores a relatively small numberof rules. The maximum number of rules is determined bythe level of a node in the tree and the maximum availablesearching time so that the worst-case classification timecan be bounded. The algorithm allows quick updates andhas relatively small storage requirements. It can be tailoredfor a Field-programmable gate array (FPGA) implementationusing an optimization for the tree and a simplememory management strategy. The results show that thealgorithm can classify about 2.5M packet headers per secondon 50MHz search clock with the worst-case classificationtime Csum = 34 clock cycle and the space complexityO(n).