A fast string search algorithm for deep packet classification

摘要

In this paper, we propose a string search algorithm that requires reduced time complexity. It also requires a small amount of memory, and shows better performance than any other algorithm for deep packet classification based on their payload data. The proposed algorithm is based on Boyer-Moore algorithm but requires a much reduced number of operations. In addition, our algorithm's memory requirement is lower than Boyer-Moore algorithm without sacrificing its speed. We have done time complexity analysis and verified its time complexities through extensive numerical simulations. These simulations show that our algorithm's performance is better for long text, long pattern, and large alphabet set and even its worst case time complexity linearly depends on the length of the text.