On rule width and the unreasonable effectiveness of policy verification

Policies, such as routing tables and firewalls, are fundamental components of networking infrastructure. Unfortunately, existing policy verification and optimization algorithms require O(n^d) time, where n is the number of rules (thousands), and d the number of fields (usually <; 10). However, these algorithms perform very well in practice. In this paper, we provide the explanation for this result: n and d are not the only parameters of interest! Through experimental study of our Parallel Next-step Lookup system PaNeL, as well as the FDD and Probe algorithms for policy verification, we clearly demonstrate the importance of our proposed new metric - the “width index”. Some established algorithms (such as FDD, used for structured firewall design) indeed become intractable for policies with poor width index values. We therefore suggest that the “unreasonable effectiveness” of such algorithms for practical policies is possible because such policies have a reasonable width index.