Fast and Scalable Conflict Detection for Packet Classifiers

Packet filters provide roles for classifying packets based on header fields. High speed packet classification has received much study. However, the twin problems of fast updates and fast conflict detection have not received much attention. A conflict occurs when two classifiers overlap, potentially creating ambiguity for packets that match both filters. For example, if Rule 1 specifies that all packets going to CNN be rote controlled and Rule 2 specifies that all packets coming from Walmart be given high priority, the roles conflict for traffic from Walmart to CNN. There has been prior work on efficient conflict detection for two dimensional classifiers. However, the best known algorithm for conflict detection for geneml classifiers is the naive O(N2) algorithm of comparing each pair of rules for a conflict. In this paper, we describe an efficient and scalable conflict detection algorithm for the general casethat is significantly faster. For example, for a database of 20,000 roles, our algorithm is 40 times faster. than the naive implementation. Even without considering conflicts, our algorithm also provides a packet classifier with fast updates and fast lookups that can be used for stateful packet filtering.