Fast and Scalable Conflict Detection for Multi-Dimensional Packet Filters

Packet classification plays an important role in supporting advanced network services, such as firewalls, policy-based routing, security, and quality-of-service (QoS). Routers have to classify incoming packets into different flows according to pre-defined rules, which are also called packet filters. If two or more filters overlap, a conflict may occur and lead to ambiguity in packet classification. Packet classification has attracted a lot of attention due to its importance. However, few studies have been done on conflict detection. In this project, we aim to design a fast and scalable conflict detection algorithm for multi-dimensional packet filters. The key idea behind the proposed algorithm is to divide the detection process into two phases. The first phase uses the tuple space to significantly reduce the number of possible conflicting filters based on the network address fields. By exploring the intrinsic properties of the data structures generated by the rectangle search, a well-known packet classification algorithm, our algorithm is faster and requires less memory space than other existing algorithms. The second phase deals with the remaining fields using a pre-built cross-producting table, which can efficiently detect conflicts between two filters. We will use the synthetic filter databases generated by ClassBench, a packet classification benchmark, to evaluate the performance of the proposed algorithm.

Project ID:PB10108-2288
External Project ID:NSC101-2221-E182-074