A Fast Bit-Vector-Based Conflict Detection Algorithm for Packet Classifiers

To support various network services, routers have to classify packets based on header fields and a set of filters. Each filter contains several fields to specify ranges of header values, and an associated action, which specifies how to handle the packet matching the filter. If two filters overlap and the actions defined in the filters conflict, it may lead to a false classification. In this paper, we propose a fast bit-vector-based algorithm for conflict detection. Experimental results show that our algorithm can reduce the average detection time per filter by 22.6% to 77.9% compared to the scalable bit vector (SBV) algorithm.  Moreover, our algorithm does not consume significant extra memory and pre-computation time.