Robust distributed routing in dynamical flow networks
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 acycl...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2013
|
| Online Access: | http://hdl.handle.net/1721.1/82597 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0003-0908-7491 |
| _version_ | 1826197753068257280 |
|---|---|
| author | Como, Giacomo Savla, Ketan D. Acemoglu, Daron 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 Como, Giacomo Savla, Ketan D. Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio |
| author_sort | Como, Giacomo |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:52:54Z |
| format | Article |
| id | mit-1721.1/82597 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:52:54Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/825972022-09-27T15:39:05Z Robust distributed routing in dynamical flow networks Como, Giacomo Savla, Ketan D. Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio 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. Como, Giacomo Frazzoli, Emilio 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. National Science Foundation (U.S.) (NSF EFRI-ARES grant number 0735956) 2013-11-26T19:32:41Z 2013-11-26T19:32:41Z 2011-12 2011-03 Article http://purl.org/eprint/type/JournalArticle 978-1-61284-801-3 978-1-61284-800-6 978-1-4673-0457-3 978-1-61284-799-3 INSPEC Accession Number: 12590061 http://hdl.handle.net/1721.1/82597 Como, Giacomo, Ketan Savla, Daron Acemoglu, Munther A. Dahleh, and Emilio Frazzoli. “Robust distributed routing in dynamical flow networks.” In IEEE Conference on Decision and Control and European Control Conference, 12-15 Dec. 2011, Orlando, Fla., 6290-6295. Institute of Electrical and Electronics Engineers, 2011. 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.2011.6161260 Proceedings of the 2011 50th IEEE Conference on Decision and Control and European Control Conference 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 arXiv |
| spellingShingle | Como, Giacomo Savla, Ketan D. Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio Robust distributed routing in dynamical flow networks |
| title | Robust distributed routing in dynamical flow networks |
| title_full | Robust distributed routing in dynamical flow networks |
| title_fullStr | Robust distributed routing in dynamical flow networks |
| title_full_unstemmed | Robust distributed routing in dynamical flow networks |
| title_short | Robust distributed routing in dynamical flow networks |
| title_sort | robust distributed routing in dynamical flow networks |
| url | http://hdl.handle.net/1721.1/82597 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 robustdistributedroutingindynamicalflownetworks AT savlaketand robustdistributedroutingindynamicalflownetworks AT acemogludaron robustdistributedroutingindynamicalflownetworks AT dahlehmunthera robustdistributedroutingindynamicalflownetworks AT frazzoliemilio robustdistributedroutingindynamicalflownetworks |