Resilient distributed routing in dynamical flow networks

Resilience has become a key issue in complex networked systems. Applications are of wide range and include complex infrastructure systems, such as data, transportation and power networks, as well as social, economic and financial networks. This seminar will focus on resilience properties of distributed routing in dynamical flow networks. We focus on routing policies that are constrained on using only local information on the current state of the system. Disturbances are modeled as (possibly adversarial) reductions of the link flow capacities. These models allow for the possibility of cascading failures, as small local perturbations propagate through the network and local actions aimed at mitigating them can increase the vulnerability of other parts of the network. A class of maximally robust distributed policies is characterized and it is shown that, if the routing policies are allowed to use local information only from the links immediately downstream, then the resilience is in general strictly smaller than the min-cut capacity of the network, while there is no such gap if flow control is allowed using local information also from the links immediately upstream. Potential applications to urban traffic control will be discussed.