 |
Center for Nonlinear Studies |
Network flow provides a compelling framework to model a variety of infrastructure networks. The celebrated max-flow min-cut theorem yields a framework to quantify robustness of network flow to disruptions in terms of the underlying graph structure and link capacities. However, such a procedure assumes a static framework, and centralized computation and control. In this talk, we present a dynamical framework for network flows, where the dynamics is driven by mass and flow conservation, link capacity constraints and distributed routing policies on the nodes. The resulting dynamics exhibit forward and backward cascading effects, which are qualitatively different than standard percolation, epidemic or interacting particle models. We utilize tools from monotone dynamical systems to study stability of such dynamical network flows under a variety of routing architectures. We then study robustness of the network to, possibly adversarial, disturbance processes that reduce link capacities. The margin of stability is defined as the smallest among the magnitudes of all disturbance processes under which the network looses its capability to transfer flow. We present exact computation of this margin under several scenarios.
Host: Misha Chertkov