Title: On the Detection of Policy Conflicts in Interdomain Routing

Authors: Karim Mattar, Samuel Epstein and Ibrahim Matta

Abstract: 

The dynamic policy routing model (DPR) was recently introduced
to explicitly model the dynamics of policy routing. DPR extends
the formalism of the stable paths problem with discrete
synchronous time to capture the propagation of path changes in
any dynamic network using a structure called the causation
chain. In this work, we extend DPR by introducing several novel
structures, namely, causation fences and policy digraphs that
provide further insight into how the dynamics of policy routing
manifest in the network. Using our extensions to DPR, we solve a
fundamental problem: policy conflict detection. We show how the
root cause of any cycle of routing update messages, under any
routing policy configuration, can be precisely inferred as
either a transient route flap or a policy conflict. We also
develop SafetyPulse, a token-based distributed algorithm to
detect policy conflicts in any dynamic network. SafetyPulse has
several novel characteristics, namely, it is privacy preserving,
computationally efficient and provably correct.