Abstract
In this paper, we study the 2-dimensional packet classification problem for a set of conflict-free filters in an IP network. We design a linear space data structure with O(min{logwloglogn, \sqrt {\log n\log \log n}}) query time where n is the number of filters in the router and w is the number of bits in an IP address. This is the first optimal space data structure with poly-logarithmic query time for this problem. Our technique can also be extended to solve the binary dispatching problem arose in object-oriented programming.