Affordable Access

On distributed robust routing for transportation networks under local information constraints

Publication Date
  • Technology And Engineering
  • Mathematics


Robust Distributed Routing in Dynamical Flow Networks Giacomo Como Ketan Savla Daron Acemoglu Munther A. Dahleh Emilio Frazzoli . Abstract— Robustness of distributed routing policies is stud- ied for dynamical flow networks, with respect to adversarial disturbances that reduce the link flow capacities. A dynamical flow network is modeled as a system of ordinary differential equations derived from mass conservation laws on a directed acyclic graph with a single origin-destination pair and a con- stant inflow at the origin. Routing policies regulate the way the inflow at a non-destination node gets split among its outgoing links as a function of the current particle density, while the outflow of a link is modeled to depend on the current particle density on that link through a flow function. The robustness of distributed routing policies is evaluated in terms of the network’s weak resilience, which is defined as the infimum sum of link-wise magnitude of disturbances under which the total inflow at the destination node of the perturbed dynamical flow network is positive. The weak resilience of a dynamical flow network with arbitrary routing policy is shown to be upper- bounded by the network’s min-cut capacity, independently of the initial flow conditions. Moreover, a class of distributed routing policies that rely exclusively on local information on the particle densities, and are locally responsive to that, is shown to yield such maximal weak resilience. These results imply that locality constraints on the information available to the routing policies do not cause loss of weak resilience. I. INTRODUCTION Flow networks provide a fruitful modeling framework for many applications of interest such as transportation, data, and production networks. They entail a fluid-like description of the macroscopic motion of particles, which are routed from their origins to their destinations via intermediate nodes: we refer to standard textbooks, such as [1], for a thorough treatment. The present pap

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times