Advanced

Robust network routing under cascading failures

Savla, Ketan; Como, Giacomo LU and Dahleh, Munther A. (2015) 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 In 2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014) 2015-February. p.2889-2894
Abstract

We propose a dynamical model for cascading failures in single-commodity network flows. In the proposed model, the network state consists of flows and activation status of the links. Network dynamics is determined by a, possibly state-dependent and adversarial, disturbance process that reduces flow capacity on the links, and routing policies at the nodes that have access to the network state, but are oblivious to the presence of disturbance. Under the proposed dynamics, a link becomes irreversibly inactive either due to overload condition on itself or on all of its immediate downstream links. The coupling between link activation and flow dynamics implies that links to become inactive successively are not necessarily adjacent to each... (More)

We propose a dynamical model for cascading failures in single-commodity network flows. In the proposed model, the network state consists of flows and activation status of the links. Network dynamics is determined by a, possibly state-dependent and adversarial, disturbance process that reduces flow capacity on the links, and routing policies at the nodes that have access to the network state, but are oblivious to the presence of disturbance. Under the proposed dynamics, a link becomes irreversibly inactive either due to overload condition on itself or on all of its immediate downstream links. The coupling between link activation and flow dynamics implies that links to become inactive successively are not necessarily adjacent to each other, and hence the pattern of cascading failure under our model is qualitatively different than standard cascade models. The magnitude of a disturbance process is defined as the sum of cumulative capacity reductions across time and links of the network, and the margin of resilience of the network is defined as the infimum over the magnitude of all disturbance processes under which the links at the origin node become inactive. We propose an algorithm to compute an upper bound on the margin of resilience for the setting where the routing policy only has access to information about the local state of the network. For the limiting case when the routing policies update their action as fast as network dynamics, we give sufficient conditions on network parameters under which the upper bound is tight under an appropriate routing policy.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
in
2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014)
volume
2015-February
pages
6 pages
publisher
Institute of Electrical and Electronics Engineers Inc.
conference name
2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
external identifiers
  • Scopus:84931827712
ISBN
9781467360890
DOI
10.1109/CDC.2014.7039833
language
English
LU publication?
yes
id
284be09d-566f-4264-98f3-87b2a96cb8d0
date added to LUP
2016-08-25 19:07:17
date last changed
2016-10-07 15:55:33
@misc{284be09d-566f-4264-98f3-87b2a96cb8d0,
  abstract     = {<p>We propose a dynamical model for cascading failures in single-commodity network flows. In the proposed model, the network state consists of flows and activation status of the links. Network dynamics is determined by a, possibly state-dependent and adversarial, disturbance process that reduces flow capacity on the links, and routing policies at the nodes that have access to the network state, but are oblivious to the presence of disturbance. Under the proposed dynamics, a link becomes irreversibly inactive either due to overload condition on itself or on all of its immediate downstream links. The coupling between link activation and flow dynamics implies that links to become inactive successively are not necessarily adjacent to each other, and hence the pattern of cascading failure under our model is qualitatively different than standard cascade models. The magnitude of a disturbance process is defined as the sum of cumulative capacity reductions across time and links of the network, and the margin of resilience of the network is defined as the infimum over the magnitude of all disturbance processes under which the links at the origin node become inactive. We propose an algorithm to compute an upper bound on the margin of resilience for the setting where the routing policy only has access to information about the local state of the network. For the limiting case when the routing policies update their action as fast as network dynamics, we give sufficient conditions on network parameters under which the upper bound is tight under an appropriate routing policy.</p>},
  author       = {Savla, Ketan and Como, Giacomo and Dahleh, Munther A.},
  isbn         = {9781467360890},
  language     = {eng},
  month        = {02},
  pages        = {2889--2894},
  publisher    = {ARRAY(0xb7cdad0)},
  series       = {2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014) },
  title        = {Robust network routing under cascading failures},
  url          = {http://dx.doi.org/10.1109/CDC.2014.7039833},
  volume       = {2015-February},
  year         = {2015},
}