High-speed packet classification using segment tree

Abstract

As the Internet grows into a commercial infrastructure, more and more network services require routers to classify packets based on one or more fields in the header in order to provide QoS differentiation. The biggest challenge for packet classification is to keep the classification time and storage requirements small. We design a fast 2-dimensional packet classification algorithm with small memory requirement. The algorithm draws on computational geometry techniques-segment tree and fractional cascading to achieve logarithmic classification time. For a database of N filters, the proposed algorithm can complete a classification in O(logN) time and the memory requirement is in the order of O(NlogN).