Show simple item record

dc.contributor.authorMattar, Karimen_US
dc.contributor.authorEpstein, Samuelen_US
dc.contributor.authorMatta, Ibrahimen_US
dc.date.accessioned2011-10-20T04:51:50Z
dc.date.available2011-10-20T04:51:50Z
dc.date.issued2009-01-30
dc.identifier.citationMattar, Karim; Epstein, Sam; Matta, Ibrahim. "Foundational Theory for Understanding Policy Routing Dynamics", Technical Report BUCS-TR-2009-001, Computer Science Department, Boston University, January 30, 2009. [Available from: http://hdl.handle.net/2144/1724]
dc.identifier.urihttps://hdl.handle.net/2144/1724
dc.description.abstractIn this paper we introduce a theory of policy routing dynamics based on fundamental axioms of routing update mechanisms. We develop a dynamic policy routing model (DPR) that extends the static formalism of the stable paths problem (introduced by Griffin et al.) with discrete synchronous time. DPR captures the propagation of path changes in any dynamic network irrespective of its time-varying topology. We introduce several novel structures such as causation chains, dispute fences and policy digraphs that model different aspects of routing dynamics and provide insight into how these dynamics manifest in a network. We exercise the practicality of the theoretical foundation provided by DPR with two fundamental problems: routing dynamics minimization and policy conflict detection. The dynamics minimization problem utilizes policy digraphs, that capture the dependencies in routing policies irrespective of underlying topology dynamics, to solve a graph optimization problem. This optimization problem explicitly minimizes the number of routing update messages in a dynamic network by optimally changing the path preferences of a minimal subset of nodes. The conflict detection problem, on the other hand, utilizes a theoretical result of DPR where the root cause of a causation cycle (i.e., cycle of routing update messages) can be precisely inferred as either a transient route flap or a dispute wheel (i.e., policy conflict). Using this result we develop SafetyPulse, a token-based distributed algorithm to detect policy conflicts in a dynamic network. SafetyPulse is privacy preserving, computationally efficient, and provably correct.en_US
dc.description.sponsorshipNational Science Foundation (CISE/CCF 0820138, CISE/CSR 0720604, CISE/CNS 0524477, CNS/ITR 0205294, CISE/EIA RI #0202067)en_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2009-001
dc.titleFoundational Theory for Understanding Policy Routing Dynamicsen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record