  A fundamental component of networking infras- tructure is the policy, used in
routing tables and firewalls. Accordingly, there has been extensive study of
policies. However, the theory of such policies indicates that the size of the
decision tree for a policy is very large ( O((2n)d), where the policy has n
rules and examines d features of packets). If this was indeed the case, the
existing algorithms to detect anomalies, conflicts, and redundancies would not
be tractable for practical policies (say, n = 1000 and d = 10). In this paper,
we clear up this apparent paradox. Using the concept of 'rules in play', we
calculate the actual upper bound on the size of the decision tree, and
demonstrate how three other factors - narrow fields, singletons, and
all-matches make the problem tractable in practice. We also show how this
concept may be used to solve an open problem: pruning a policy to the minimum
possible number of rules, without changing its meaning.
