| The Internet consists of thousands of autonomous systems (ASes). Each AS represents an Internet Service Provider or the network of a large organization, that is managed independently. The Border Gateway Protocol is the policy routing protocol of choice for connecting these ASes, while allowing them to set their routing policies independently. Routing policies (or path preferences) determine how a path to a particular destination is chosen out of a candidate set of paths. This flexibility in configuring routing policies comes at the cost of stability, where ASes may have conflicting policies causing them to continually advertise new routing updates for extended periods of time.;We introduce a theoretical framework for policy routing dynamics (i.e., how path changes propagate in the network) that is based on the specifics of routing update mechanisms. Unlike existing models, our Dynamic Policy Routing (DPR) model introduces several structures that capture how path changes propagate in any network under dynamic topology and path preference changes. We demonstrate the utility of DPR by applying it to three problems: minimizing routing dynamics, detecting policy conflicts, and deriving properties of safe (i.e., convergent) routing dynamics.;For minimizing routing dynamics we formulate the Routing Dynamics Minimization Problem (RDMP) which solves a graph optimization problem. RDMP aims to minimize the longest possible sequence of routing update messages in a dynamic network by changing the path preferences of nodes. We show that solving RDMP in general is NP-Hard and under restrictions can be solved in polynomial time.;For detecting policy conflicts we prove that the root cause of any cycle of routing update messages can be precisely inferred as either transient or potentially persistent due to the existence of a policy conflict. We then develop SafetyPulse, a token-based distributed algorithm, to detect policy conflicts in a dynamic network.;For deriving properties of safe routing dynamics we establish three properties that provide insight into which ASes can directly induce route changes in one another, and how cycles of routing updates can be manifested in the network. We then develop InterferenceBeat, a token-based distributed algorithm, to check adherence to these properties. |
