Design of a Universal Conflict Detecting Algorithm for Packet Classifiers

For providing advanced network services, such as firewalls, quality-of-service (Qos), and security, routers have to classify packets into different flows according to pre-defined rules, which are also called packets filters. When two or more filters overlap, a conflict may occurs and lead to ambiguity in packet classification. In the past few years, packet classification has attracted a lot of attention, and a number of packet classification algorithms have been proposed. However, few studies have been done on conflict detection. In our previous study, we proposed an efficient conflict detection algorithm for two-dimensional packet filters. In this two-year project, we plan to study this topic in depth and propose a universal conflict detection algorithms for packet filters. There are two kinds of filter conflicts: subset conflict and overlapping conflict. In the first year, we will focus on subset conflicts. By analyzing the conditions that subset conflicts hold, the source IP and the destination IP address fields are first processing using the tuple space. Then, the remaining fields are encoded to speed up the processing. Through a pre-built lookup table, the time required to access the memory and operations can be significantly reduced. In the second year, we will focus on overlapping conflicts, which are more complicated than subset conflicts. By further exploring the conditions that overlapping conflicts hold, the algorithm and the data structures used to detect subset conflicts can be used to detect overlapping conflicts with some modifications. This enable us to design a universal conflict detection algorithm that can detect either subset conflicts or overlapping conflicts, or even both.

Project ID:PB10408-5764
External Project ID:MOST104-2221-E182-005