Resilient distributed routing in dynamical flow networks

GSSI-DEWS Maths Seminar
Thursday 22nd May, 15:00 GSSI Main Lecture Room

Dr. Giacomo COMO (Lund Univ.SE)



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 talk will focus on resilience properties of distributed routing in dynamical flow networks. Dynamical flow networks are modeled as ordinary differential equation describing mass conservation with routing policies regulating the way the total outflow at each node gets split among its outgoing links. 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 perturbation 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.