A calibrated asymptotic framework for analyzing packet classification algorithms on GPUs

Packet classification is a computationally intensive, highly parallelizable task in many advanced network systems like high-speed routers and firewalls. Recently, graphics processing units (GPUs) have been exploited as efficient accelerators for parallel implementation of software packet classifiers. However, due to the lack of a comprehensive analysis framework, none of the conducted studies to date has efficiently exploited the capabilities of the complex memory subsystem of such highly threaded machines. In this work, we combine asymptotic and calibrated analysis frameworks to present a more efficient framework that not only can boost the straightforward design of efficient parallel algorithms that run on different architectures of GPU but also can provide a powerful analysis tool for predicting any empirical result. Comparing analytical results with the experimental findings of ours and other researchers who have implemented and evaluated packet classification algorithms on a variety of GPUs evinces the efficiency of the proposed analysis framework.