Enhancing network robustness via shielding
We consider shielding critical links to guarantee network connectivity under geographical and general failure models. We develop a mixed integer linear program (MILP) to obtain the minimum cost shielding to guarantee the connectivity of a single SD pair under a general failure model, and exploit geo...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109206 https://orcid.org/0000-0003-3318-2165 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1811069327645868032 |
|---|---|
| author | Hay, David Zhang, Jianan Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Hay, David Zhang, Jianan Modiano, Eytan H |
| author_sort | Hay, David |
| collection | MIT |
| description | We consider shielding critical links to guarantee network connectivity under geographical and general failure models. We develop a mixed integer linear program (MILP) to obtain the minimum cost shielding to guarantee the connectivity of a single SD pair under a general failure model, and exploit geometric properties to decompose the shielding problem under a geographical failure model. We extend our MILP formulation to guarantee the connectivity of the entire network, and use Benders decomposition to significantly reduce the running time by exploiting its partial separable structure. We also apply simulated annealing to solve larger network problems to obtain near-optimal solutions in much shorter time. Finally, we extend the algorithms to guarantee partial network connectivity, and observe significant reduction in shielding cost, especially when the failure region is small. For example, when the failure region radius is 60 miles, we observe as much as 75% reduction in shielding cost by relaxing the connectivity requirement to 95% on a major US infrastructure network. |
| first_indexed | 2024-09-23T08:09:21Z |
| format | Article |
| id | mit-1721.1/109206 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:09:21Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | mit-1721.1/1092062022-09-23T11:17:11Z Enhancing network robustness via shielding Hay, David Zhang, Jianan Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Zhang, Jianan Modiano, Eytan H We consider shielding critical links to guarantee network connectivity under geographical and general failure models. We develop a mixed integer linear program (MILP) to obtain the minimum cost shielding to guarantee the connectivity of a single SD pair under a general failure model, and exploit geometric properties to decompose the shielding problem under a geographical failure model. We extend our MILP formulation to guarantee the connectivity of the entire network, and use Benders decomposition to significantly reduce the running time by exploiting its partial separable structure. We also apply simulated annealing to solve larger network problems to obtain near-optimal solutions in much shorter time. Finally, we extend the algorithms to guarantee partial network connectivity, and observe significant reduction in shielding cost, especially when the failure region is small. For example, when the failure region radius is 60 miles, we observe as much as 75% reduction in shielding cost by relaxing the connectivity requirement to 95% on a major US infrastructure network. 2017-05-19T15:22:09Z 2017-05-19T15:22:09Z 2015-07 2015-03 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-7795-6 http://hdl.handle.net/1721.1/109206 Zhang, Jianan; Modiano, Eytan and Hay, David. “Enhancing Network Robustness via Shielding.” 2015 11th International Conference on the Design of Reliable Communication Networks (DRCN), March 2015, Kansas City, Missouri, Institute of Electrical and Electronics Engineers (IEEE), July 2015 © Institute of Electrical and Electronics Engineers (IEEE) https://orcid.org/0000-0003-3318-2165 https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/DRCN.2015.7148980 2015 11th International Conference on the Design of Reliable Communication Networks (DRCN) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf MIT web domain |
| spellingShingle | Hay, David Zhang, Jianan Modiano, Eytan H Enhancing network robustness via shielding |
| title | Enhancing network robustness via shielding |
| title_full | Enhancing network robustness via shielding |
| title_fullStr | Enhancing network robustness via shielding |
| title_full_unstemmed | Enhancing network robustness via shielding |
| title_short | Enhancing network robustness via shielding |
| title_sort | enhancing network robustness via shielding |
| url | http://hdl.handle.net/1721.1/109206 https://orcid.org/0000-0003-3318-2165 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT haydavid enhancingnetworkrobustnessviashielding AT zhangjianan enhancingnetworkrobustnessviashielding AT modianoeytanh enhancingnetworkrobustnessviashielding |