# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 2 Related Work  
### Existing Conflict-Detection Algorithms  
A straightforward approach to detecting all filter conflicts is to check every pair of filters in the filter database. This approach does not utilize extra storage to cache additional information and makes it easy to detect conflicts. However, it takes \(O(n^{2})\) time to detect all the conflicts, where \(n\) denotes the number of filters. [PERSON] et al. [3] defined the source IP address and destination IP address fields as 2D prefix fields. They introduced the filter conflict concept and proposed an algorithm for detecting all conflicts in 2D prefix filters. We assume that the filter \(f\) has two prefix fields. Let \(f[1]\) and \(f[2]\) denote the first prefix field and the second prefix field, respectively. Filters \(f\) and \(g\) conflict when any of the following two conditions hold. 1. \(f[1]\) is a prefix of \(g[1]\), and \(g[2]\) is a prefix of \(f[2]\). 2. \(g[1]\) is a prefix of \(f[1]\), and \(f[2]\) is a prefix of \(g[2]\). [PERSON] et al. [3] developed the _FastDetect_ algorithm to perform 2D prefix filter conflict detection using two grid-of-tries and switch pointers [26]. All conflicts can be detected within \(O(nW+S)\) time, where \(n\) is the number of filters, \(W\) is the length of the prefix, and \(S\) is the number of conflict pairs generated by the filters. In addition, the space complexity is \(O(nW)\). When the _FastDetect_ algorithm is extended to 5D conflict detection, the source/destination port and protocol fields are included for comparison. The preset content of non-IP address fields can only be an exact value or a wildcard. This does not conform to practical applications. [PERSON] and [PERSON] [4] proposed the scalable bit vector (SBV) conflict-detection algorithm based on the bit vector (BV) scheme [27] and the aggregated bit vector (ABV) scheme [28]. They used a compressed binary trie in each field. Each node in tries needs to store an \(n\)-bit vector. In a static mode, their proposed algorithms can detect all conflicts with time complexity \(O(knW)\), where \(k\) is the number of fields. In addition, the space complexity is \(O(kN^{2})\). When dealing with 5D conflict detection, the data structure of the three binary tries must be added to process the information of the three non-IP address fields. When the port field is specified by a range, range-to-prefix conversion is required, leading to significant filter duplications that consume large memory space. [PERSON] and [PERSON] [29] established several algorithms that modified the original BV scheme to prevent the defect of massive memory duplication caused by conversion from range to prefix and developed a method for comparing range fields. This allows the algorithm to support 5D conflict detection. However, it still incurs a high cost in memory space. [PERSON] et al. [30] proposed an algorithm to improve the SBV algorithm by reducing the amount of bits required to be read when bit vectors are accessed. They divided all filters into several groups based on prefix fields, and then constructed a conflict matrix to indicate whether two groups were in conflict or not. The experimental results showed that their algorithm reduced the average detection time per filter by up to 77.9%, compared with the SBV algorithm. However, this algorithm focuses on 2D filter databases, and cannot be easily extended to handle 5D filter databases. [PERSON] et al. [31] proposed a compact bit vector (CBV) conflict-detection algorithm to improve the SBV algorithm. First, they proposed a redundancy reduction scheme that explored and exploited the covering and potential conflict relations between filters to significantly reduce the number of filters that must be involved in the construction of matching tries. Second, the CBV algorithm further merged the redundant match nodes in each matching tries by adopting an upward merging approach. Finally, the highly compact matching tries were built to represent the relationships between filters.