Two-dimensional packet classification and filter conflict resolution in the internet

In this paper, we study the packet classification problem and the filter conflict resolution problem, both motivated by applications in the routing of packets in an IP network. For the first problem, we focus on the static 2-dimensional conflict-free (i.e., nested) filters. We design a linear space data structure with O(T w (n)+(log∈log∈n)2) query time on a RAM with word size O(w) bits where n is the number of filters in the router, w is the number of bits in an IP address and Tw(n) = O ( min{log w, log w log log n/log log w √log n/log log n}). This is the first optimal space data structure with poly-logarithmic query time for this problem. In practice, network filters often contain very few conflicts but are not completely conflict-free. Fortunately, conflicts can be resolved by adding conflict-resolving filters. Moreover, practical filters often possess another slightly different nesting property which we called 1-nestedness. We present an algorithm to resolve conflicts in a set of 1-nested filters in O(nT w (n)+k) time and linear space, where k is the number of filter pairs in conflict. Furthermore, we show that our data structure for the first problem can be adapted to apply on conflict-resolved 1-nested filters with the same query and space complexities. © 2007 Springer Science+Business Media, LLC.