On the Detection of Policy Conflicts in Interdomain Routing
MetadataShow full item record
Citation (published version)Mattar, Karim; Epstein, Samuel; Matta, Ibrahim. "On the Detection of Policy Conflicts in Interdomain Routing", Technical Report BUCS-TR-2010-009, Computer Science Department, Boston University, April 27, 2010. [Available from: http://hdl.handle.net/2144/3788]
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.