Robust Network Routing under Cascading Failures
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 c...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99950 https://orcid.org/0000-0002-1470-2148 |
| _version_ | 1826207452969828352 |
|---|---|
| author | Savla, Ketan Como, Giacomo Dahleh, Munther A. |
| author2 | Massachusetts Institute of Technology. Institute for Data, Systems, and Society |
| author_facet | Massachusetts Institute of Technology. Institute for Data, Systems, and Society Savla, Ketan Como, Giacomo Dahleh, Munther A. |
| author_sort | Savla, Ketan |
| collection | MIT |
| description | 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 identify sufficient conditions on network parameters under which the upper bound is tight under an appropriate routing policy. Our analysis relies on making connections between network parameters and monotonicity in network state evolution under proposed dynamics. |
| first_indexed | 2024-09-23T13:49:53Z |
| format | Article |
| id | mit-1721.1/99950 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:49:53Z |
| publishDate | 2015 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/999502022-09-28T16:27:59Z Robust Network Routing under Cascading Failures Savla, Ketan Como, Giacomo Dahleh, Munther A. Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Dahleh, Munther A. 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 identify sufficient conditions on network parameters under which the upper bound is tight under an appropriate routing policy. Our analysis relies on making connections between network parameters and monotonicity in network state evolution under proposed dynamics. 2015-11-20T15:24:20Z 2015-11-20T15:24:20Z 2014-11 2014-11 Article http://purl.org/eprint/type/JournalArticle 2327-4697 http://hdl.handle.net/1721.1/99950 Savla, Ketan, Giacomo Como, and Munther A. Dahleh. “Robust Network Routing Under Cascading Failures.” IEEE Trans. Netw. Sci. Eng. 1, no. 1 (January 1, 2014): 53–66. https://orcid.org/0000-0002-1470-2148 en_US http://dx.doi.org/10.1109/TNSE.2014.2373358 IEEE Transactions on Network Science and Engineering Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Savla, Ketan Como, Giacomo Dahleh, Munther A. Robust Network Routing under Cascading Failures |
| title | Robust Network Routing under Cascading Failures |
| title_full | Robust Network Routing under Cascading Failures |
| title_fullStr | Robust Network Routing under Cascading Failures |
| title_full_unstemmed | Robust Network Routing under Cascading Failures |
| title_short | Robust Network Routing under Cascading Failures |
| title_sort | robust network routing under cascading failures |
| url | http://hdl.handle.net/1721.1/99950 https://orcid.org/0000-0002-1470-2148 |
| work_keys_str_mv | AT savlaketan robustnetworkroutingundercascadingfailures AT comogiacomo robustnetworkroutingundercascadingfailures AT dahlehmunthera robustnetworkroutingundercascadingfailures |