Twodimensional packet classification and filter conflict resolution in the internet
互聯網二維包封分類及過濾規則衝突之調解
Student thesis: Master's Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution  

Supervisors/Advisors 

Award date  3 Oct 2006 
Link(s)
Permanent Link  https://scholars.cityu.edu.hk/en/theses/theses(802b614b617f4161b87a5ba4ff6a87ec).html 

Other link(s)  Links 
Abstract
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 2dimensional static pointenclosure problem in which the rectangles are conflictfree (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 polylogarithmic query time for this problem. In practice, network filters often contain very few conflicts but are not completely conflictfree. Fortunately, conflicts can be resolved by adding conflictresolving filters. Moreover, practical filters often possess another slightly different nesting property which we called 1nestedness. We present an algorithm to resolve conflicts in a set of 1nested 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 conflictresolved 1nested 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).
 Packet switching (Data transmission)