Technical Report No. 226 - Abstract

K. A. Mohamed, C. Kupich
An O(n log n) Output-Sensitive Algorithm to Detect and Resolve Conflicts for 1D Range Filters in Router Tables

We present an output-sensitive solution to the offline variant of the conflict detection and resolution problem for a given set of n 1D arbitrary range filters R. This Slab-Detect algorithm is applicable to two popular tie-breaking rules in the event of filter conflicts -- the most-specific tie breaking rule (MSTB), and the highest-priority filter rule (HPF). We are able to detect all conflict situations in R and report an optimal number of O(n) slab-resolves to make the set Rconflict-free. The algorihm achieves a worst-case time complexity of O(n log n) and utilises O(n) space. As a direct follow up to the main lemmata, this article serves to support and strengthen the claims and conjectures of our earlier report with robust experiment proofs from data collected on various simulations running the Slab-Detect algorithm for R on IPv4 and IPv6 settings.