Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience
Original manuscript March 25, 2011
| 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/81860 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0003-0908-7491 |
| _version_ | 1811070275012263936 |
|---|---|
| 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 | Original manuscript March 25, 2011 |
| first_indexed | 2024-09-23T08:33:53Z |
| format | Article |
| id | mit-1721.1/81860 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:33:53Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/818602022-09-30T09:37:15Z Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience 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 Original manuscript March 25, 2011 Robustness of distributed routing policies is studied for dynamical networks, with respect to adversarial disturbances that reduce the link flow capacities. A dynamical 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 total outflow at the origin. Routing policies regulate the way the total outflow at each nondestination 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 dynamical network is called partially transferring if the total inflow at the destination node is asymptotically bounded away from zero, and its weak resilience is measured as the minimum sum of the link-wise magnitude of disturbances that make it not partially transferring. The weak resilience of a dynamical network with arbitrary routing policy is shown to be upper bounded by the network's min-cut capacity and, hence, is independent 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. Fundamental properties of dynamical networks driven by locally responsive distributed routing policies are analyzed in detail, including global convergence to a unique limit flow. The derivation of these properties exploits the cooperative nature of these dynamical systems, together with an additional stability property implied by the assumption of monotonicity of the flow as a function of the density on each link. 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 FA9950-09-1-0538) 2013-10-30T12:34:42Z 2013-10-30T12:34:42Z 2013-01 2012-06 Article http://purl.org/eprint/type/JournalArticle 0018-9286 1558-2523 http://hdl.handle.net/1721.1/81860 Como, Giacomo, Ketan Savla, Daron Acemoglu, Munther A. Dahleh, and Emilio Frazzoli. “Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience.” IEEE Transactions on Automatic Control 58, no. 2 (February 2013): 317-332. 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/tac.2012.2209951 IEEE Transactions on Automatic Control 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) arXiv |
| spellingShingle | Como, Giacomo Acemoglu, Daron Dahleh, Munther A. Frazzoli, Emilio Savla, Ketan D. Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience |
| title | Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience |
| title_full | Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience |
| title_fullStr | Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience |
| title_full_unstemmed | Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience |
| title_short | Robust Distributed Routing in Dynamical Networks - Part I: Locally Responsive Policies and Weak Resilience |
| title_sort | robust distributed routing in dynamical networks part i locally responsive policies and weak resilience |
| url | http://hdl.handle.net/1721.1/81860 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 robustdistributedroutingindynamicalnetworkspartilocallyresponsivepoliciesandweakresilience AT acemogludaron robustdistributedroutingindynamicalnetworkspartilocallyresponsivepoliciesandweakresilience AT dahlehmunthera robustdistributedroutingindynamicalnetworkspartilocallyresponsivepoliciesandweakresilience AT frazzoliemilio robustdistributedroutingindynamicalnetworkspartilocallyresponsivepoliciesandweakresilience AT savlaketand robustdistributedroutingindynamicalnetworkspartilocallyresponsivepoliciesandweakresilience |