High-performance Packet Classification Algorithm for Many-core and Multithreaded Network

Packet classification is crucial for the Internet to provide more value-added services and guar-anteed quality of service. Besides hardware-based solutions, many software-based classification algorithms have been proposed. However, classifying at 10 Gbps speed or higher is a challenging problem and it is still one of the performance bottlenecks in core routers. In general, classification algorithms face the same challenge of balancing between high classification speed and low mem-ory requirements. This paper proposes a modified recursive flow classification (RFC) algorithm, Bitmap-RFC, which significantly reduces the memory requirements of RFC by applying a bitmap compression technique. To speed up classifying speed, we exploit the multithreaded architectural features in various algorithm development stages from algorithm design to algorithm implementa-tion. As a result, Bitmap-RFC strikes a good balance between speed and space. It can significantl