Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Robust distributed routing in dynamical flow networks

Como, Giacomo LU ; Savla, Ketan ; Acemoglu, Daron ; Dahleh, Munther A. and Frazzoli, Emilio (2011) 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 In Proceedings of the IEEE Conference on Decision and Control p.6290-6295
Abstract

Robustness of distributed routing policies is studied 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 constant 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... (More)

Robustness of distributed routing policies is studied 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 constant 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.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
series title
Proceedings of the IEEE Conference on Decision and Control
article number
6161260
pages
6 pages
conference name
2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
conference location
Orlando, FL, United States
conference dates
2011-12-12 - 2011-12-15
external identifiers
  • scopus:84860653761
ISSN
0191-2216
ISBN
9781612848006
DOI
10.1109/CDC.2011.6161260
language
English
LU publication?
yes
id
9a70e88a-e266-4547-ba51-dab383ef811d
date added to LUP
2020-01-29 21:24:45
date last changed
2020-06-03 05:16:42
@inproceedings{9a70e88a-e266-4547-ba51-dab383ef811d,
  abstract     = {<p>Robustness of distributed routing policies is studied 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 constant 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.</p>},
  author       = {Como, Giacomo and Savla, Ketan and Acemoglu, Daron and Dahleh, Munther A. and Frazzoli, Emilio},
  booktitle    = {2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011},
  isbn         = {9781612848006},
  issn         = {0191-2216},
  language     = {eng},
  month        = {12},
  pages        = {6290--6295},
  series       = {Proceedings of the IEEE Conference on Decision and Control},
  title        = {Robust distributed routing in dynamical flow networks},
  url          = {http://dx.doi.org/10.1109/CDC.2011.6161260},
  doi          = {10.1109/CDC.2011.6161260},
  year         = {2011},
}