# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 2 Related Work
### Conflict Detection for 5D Filters  
[PERSON] et al. [6] first defined the source IP address and destination IP address fields as 2D prefix fields and introduced the notion of 2D filter conflict. Two filters, \(F\) and \(G\), are in conflict if and only if one of the following conditions holds:\(F[1]\) is a prefix of \(G[1]\) and \(G[2]\) is a prefix of \(F[2]\), or
2. \(G[1]\) is a prefix of \(F[1]\) and \(F[2]\) is a prefix of \(G[2]\). \(F[1]\) and \(G[1]\) indicate the first prefix field of \(F\) and \(G\), respectively, whereas \(F[2]\) and \(G[2]\) indicate the second prefix field of \(F\) and \(G\), respectively. [PERSON] et al. proposed the _FastDetect_ algorithm [6] using the Grid-of-Trie and a switch pointer [24] for 2D conflict detection. All conflicting filter pairs can be reported in \(O(nW+S)\) time, where \(W\) is the length of the longest prefix and \(S\) is the number of conflicting filter pairs. The memory requirement of the _FastDetect_ algorithm is \(O(nW)\). When the _FastDetect_ algorithm is extended for 5D conflict detection, for non-prefix fields, [PERSON] et al. assumed the port fields of a filter must be either an exact value or a wildcard, while the protocol field of a filter must be one of the following: transmission control protocol (TCP), user datagram protocol (UDP), or a wildcard. In case a filter whose protocol field is a wildcard, the filter will be replicated three times: once with the protocol field set to TCP, once to UDP, and once to the special value OTHER. Finally, the filter sets are divided into sets of TCP, UDP, and OTHER according to the protocol values, thus ensuring that filters in different sets do not conflict [6]. Based on these assumptions, the number of filters that require comparison during conflict detection can be reduced and it does not require extra auxiliary information. However, filter replication caused by the aforementioned method will consume considerable memory space. In addition, the port and protocol field values can only be exact values or a wildcard, and clearly this does not conform to a practical application. [PERSON] and [PERSON] [7] proposed the scalable bit vector (SBV) conflict detection algorithm based on the bit vector (BV) scheme [25] and the aggregated bit vector scheme [26]. They proposed to use compressed binary tries (each field bit requires the use of a trie) and \(n\) bit vectors to determine dynamically whether new filters conflict with the original filter sets in \(O(nW)\) time. Their proposed algorithm can detect all conflicts with \(O(knW)\) time and \(O(kn^{2})\) space, where \(k\) indicates the number of fields in a filter. In the study [7], all the non-prefix fields are converted into the prefix fields by using the method described in [26] during 5D conflict detection; this method causes many filter replications and requires considerable memory space. [PERSON] and [PERSON] [10] proposed 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 remains costly in terms of memory requirements due to the high cost of the auxiliary information used to compare the range fields. [PERSON] et al. [27] proposed a compact bit vector (CBV) conflict detection algorithm to improve the constructed matching tries of the SBV algorithm. In the CBV algorithm, they proposed a redundancy reduction scheme and exploited the covering and potential conflict relationships between filters to significantly reduce the number of filters that must be involved in the construction of matching tries. The CBV algorithm then further merged the redundant match nodes in each matching trie by adopting an upward merging approach. Finally, the highly compact matching tries were built to represent the relationships between filters. However, the CBV algorithm does not consider the case where the non-prefix field is represented as an ambiguity range.