On resilience of distributed routing in networks under cascade dynamics
We consider network flow over graphs between a single origin-destination pair, where the network state consists of flows and activation status of the links. The evolution of the activation status of a link is given by an irreversible transition that depends on the saturation status of that link and...
| 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/96936 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 |
| _version_ | 1826211940986257408 |
|---|---|
| author | Savla, Ketan Como, Giacomo Dahleh, Munther A. Frazzoli, Emilio |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Savla, Ketan Como, Giacomo Dahleh, Munther A. Frazzoli, Emilio |
| author_sort | Savla, Ketan |
| collection | MIT |
| description | We consider network flow over graphs between a single origin-destination pair, where the network state consists of flows and activation status of the links. The evolution of the activation status of a link is given by an irreversible transition that depends on the saturation status of that link and the activation status of the downstream links. The flow dynamics is determined by activation status of the links and node-wise routing policies under the flow balance constraints at the nodes. We formulate a deterministic discrete time dynamics for the network state, where the time epochs correspond to a change in the activation status of the links, and study network resilience towards disturbances that reduce link-wise flow capacities, under distributed routing policies. The margin of resilience is defined as the minimum, among all possible disturbances, of the link-wise sum of reductions in flow capacities, under which the links outgoing from the origin node become inactive in finite time. We propose a backward propagation algorithm to compute an upper bound on the margin of resilience for tree-like network topologies with breadth at most 2, and show that this bound is tight for trees with the additional property of having depth at most 2. |
| first_indexed | 2024-09-23T15:13:49Z |
| format | Article |
| id | mit-1721.1/96936 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:13:49Z |
| publishDate | 2015 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/969362022-09-29T13:30:19Z On resilience of distributed routing in networks under cascade dynamics Savla, Ketan Como, Giacomo Dahleh, Munther A. Frazzoli, Emilio Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Engineering Systems Division Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Dahleh, Munther A. Frazzoli, Emilio We consider network flow over graphs between a single origin-destination pair, where the network state consists of flows and activation status of the links. The evolution of the activation status of a link is given by an irreversible transition that depends on the saturation status of that link and the activation status of the downstream links. The flow dynamics is determined by activation status of the links and node-wise routing policies under the flow balance constraints at the nodes. We formulate a deterministic discrete time dynamics for the network state, where the time epochs correspond to a change in the activation status of the links, and study network resilience towards disturbances that reduce link-wise flow capacities, under distributed routing policies. The margin of resilience is defined as the minimum, among all possible disturbances, of the link-wise sum of reductions in flow capacities, under which the links outgoing from the origin node become inactive in finite time. We propose a backward propagation algorithm to compute an upper bound on the margin of resilience for tree-like network topologies with breadth at most 2, and show that this bound is tight for trees with the additional property of having depth at most 2. 2015-05-08T14:27:00Z 2015-05-08T14:27:00Z 2013-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-5717-3 978-1-4673-5714-2 978-1-4799-1381-7 0743-1546 http://hdl.handle.net/1721.1/96936 Savla, Ketan, Giacomo Como, Munther A. Dahleh, and Emilio Frazzoli. “On Resilience of Distributed Routing in Networks Under Cascade Dynamics.” 52nd IEEE Conference on Decision and Control (December 2013). https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 en_US http://dx.doi.org/10.1109/CDC.2013.6761081 Proceedings of the 52nd IEEE Conference on Decision and Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Other univ. web domain |
| spellingShingle | Savla, Ketan Como, Giacomo Dahleh, Munther A. Frazzoli, Emilio On resilience of distributed routing in networks under cascade dynamics |
| title | On resilience of distributed routing in networks under cascade dynamics |
| title_full | On resilience of distributed routing in networks under cascade dynamics |
| title_fullStr | On resilience of distributed routing in networks under cascade dynamics |
| title_full_unstemmed | On resilience of distributed routing in networks under cascade dynamics |
| title_short | On resilience of distributed routing in networks under cascade dynamics |
| title_sort | on resilience of distributed routing in networks under cascade dynamics |
| url | http://hdl.handle.net/1721.1/96936 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 |
| work_keys_str_mv | AT savlaketan onresilienceofdistributedroutinginnetworksundercascadedynamics AT comogiacomo onresilienceofdistributedroutinginnetworksundercascadedynamics AT dahlehmunthera onresilienceofdistributedroutinginnetworksundercascadedynamics AT frazzoliemilio onresilienceofdistributedroutinginnetworksundercascadedynamics |