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


Student thesis: Master's Thesis

View graph of relations


  • Ka Chun KWOK

Related Research Unit(s)


Awarding Institution
  • Chung Keung POON (Supervisor)
Award date3 Oct 2006


In this thesis, 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. The two problems can be transformed to the point enclosure problem, which is a well known problem in theoretical computer science. The classic point enclosure problem is to store a set of (hyper-)rectangles in an effective way such that given any query point, the set of rectangles enclosing the query point can be reported quickly. Our research focuses on several variants of this problem in the static case, i.e., to process a static set of packet classification filters. For the 2-dimensional static point-enclosure problem in which the rectangles are conflict-free (i.e. nested), we obtain a linear space data structure that reports the most specific rectangle enclosing a query point in O(Tpred(w, n) + (log log n)²) query time on a Random Access Machine (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 Tpred(w, n) = O(min{log w, log w log log n/log log w ,√ log n/log log n}) is the currently best query time for a linear space static predecessor structure. 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(nTpred(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. Hardware implementation of the above data structures is an important practical issue. This thesis will also study the implementation of several related data structures on a type of hardware called Content Addressable Memory (CAM).

    Research areas

  • Packet switching (Data transmission)