Robust distributed routing in dynamical networks with cascading failures
We consider a dynamical formulation of network flows, whereby the network is modeled as a switched system of ordinary differential equations derived from mass conservation laws on directed graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the den...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81862 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0003-0908-7491 |
| _version_ | 1826189415004766208 |
|---|---|
| author | Como, Giacomo Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio Savla, Ketan D. |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Como, Giacomo Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio Savla, Ketan D. |
| author_sort | Como, Giacomo |
| collection | MIT |
| description | We consider a dynamical formulation of network flows, whereby the network is modeled as a switched system of ordinary differential equations derived from mass conservation laws on directed graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the density on each link of the network equals the difference between the inflow and the outflow on that link. The inflow to a link is determined by the total flow arriving to the tail node of that link and the routing policy at that tail node. The outflow from a link is modeled to depend on the current density on that link through a flow function. Every link is assumed to have finite capacity for density and the flow function is modeled to be strictly increasing up to the maximum density. A link becomes inactive when the density on it reaches the capacity. A node fails if all its outgoing links become inactive, and such node failures can propagate through the network due to rerouting of flow. We prove some properties of these dynamical networks and study the resilience of such networks under distributed routing policies with respect to perturbations that reduce link-wise flow functions. In particular, we propose an algorithm to compute upper bounds on the maximum resilience over all distributed routing policies, and discuss examples that highlight the role of cascading failures on the resilience of the network. |
| first_indexed | 2024-09-23T08:14:40Z |
| format | Article |
| id | mit-1721.1/81862 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:14:40Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/818622022-09-30T08:31:46Z Robust distributed routing in dynamical networks with cascading failures Como, Giacomo Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio Savla, Ketan D. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Economics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Savla, Ketan D. Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio We consider a dynamical formulation of network flows, whereby the network is modeled as a switched system of ordinary differential equations derived from mass conservation laws on directed graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the density on each link of the network equals the difference between the inflow and the outflow on that link. The inflow to a link is determined by the total flow arriving to the tail node of that link and the routing policy at that tail node. The outflow from a link is modeled to depend on the current density on that link through a flow function. Every link is assumed to have finite capacity for density and the flow function is modeled to be strictly increasing up to the maximum density. A link becomes inactive when the density on it reaches the capacity. A node fails if all its outgoing links become inactive, and such node failures can propagate through the network due to rerouting of flow. We prove some properties of these dynamical networks and study the resilience of such networks under distributed routing policies with respect to perturbations that reduce link-wise flow functions. In particular, we propose an algorithm to compute upper bounds on the maximum resilience over all distributed routing policies, and discuss examples that highlight the role of cascading failures on the resilience of the network. National Science Foundation (U.S.). Office of Emerging Frontiers in Research and Innovation (ARES Grant 0735956) United States. Air Force Office of Scientific Research (Grant FA9550-09-1-0538) 2013-10-30T12:57:57Z 2013-10-30T12:57:57Z 2012-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-2066-5 978-1-4673-2065-8 978-1-4673-2063-4 978-1-4673-2064-1 http://hdl.handle.net/1721.1/81862 Como, Giacomo, Ketan Savla, Daron Acemoglu, Munther A. Dahleh, and Emilio Frazzoli. “Robust distributed routing in dynamical networks with cascading failures.” In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), 7413-7418. Institute of Electrical and Electronics Engineers, 2012. https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0003-0908-7491 en_US http://dx.doi.org/10.1109/CDC.2012.6426170 Proceedings of the 2012 51st IEEE Conference on Decision and Control (CDC) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Como, Giacomo Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio Savla, Ketan D. Robust distributed routing in dynamical networks with cascading failures |
| title | Robust distributed routing in dynamical networks with cascading failures |
| title_full | Robust distributed routing in dynamical networks with cascading failures |
| title_fullStr | Robust distributed routing in dynamical networks with cascading failures |
| title_full_unstemmed | Robust distributed routing in dynamical networks with cascading failures |
| title_short | Robust distributed routing in dynamical networks with cascading failures |
| title_sort | robust distributed routing in dynamical networks with cascading failures |
| url | http://hdl.handle.net/1721.1/81862 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0003-0908-7491 |
| work_keys_str_mv | AT comogiacomo robustdistributedroutingindynamicalnetworkswithcascadingfailures AT acemogludaron robustdistributedroutingindynamicalnetworkswithcascadingfailures AT dahlehmunthera robustdistributedroutingindynamicalnetworkswithcascadingfailures AT frazzoliemilio robustdistributedroutingindynamicalnetworkswithcascadingfailures AT savlaketand robustdistributedroutingindynamicalnetworkswithcascadingfailures |