A Robust Optimization Approach to Backup Network Design With Random Failures
This paper presents a scheme in which a dedicated backup network is designed to provide protection from random link failures. Upon a link failure in the primary network, traffic is rerouted through a preplanned path in the backup network. We introduce a novel approach for dealing with random link fa...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114608 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1811075128659804160 |
|---|---|
| author | Johnston, Matthew Ryan Lee, Hyang-Won Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Johnston, Matthew Ryan Lee, Hyang-Won Modiano, Eytan H |
| author_sort | Johnston, Matthew Ryan |
| collection | MIT |
| description | This paper presents a scheme in which a dedicated backup network is designed to provide protection from random link failures. Upon a link failure in the primary network, traffic is rerouted through a preplanned path in the backup network. We introduce a novel approach for dealing with random link failures, in which probabilistic survivability guarantees are provided to limit capacity over provisioning. We show that the optimal backup routing strategy in this respect depends on the reliability of the primary network. Specifically, as primary links become less likely to fail, the optimal backup networks employ more resource sharing among backup paths. We apply results from the field of robust optimization to formulate an ILP for the design and capacity provisioning of these backup networks. We then propose a simulated annealing heuristic to solve this problem for large-scale networks and present simulation results that verify our analysis and approach. |
| first_indexed | 2024-09-23T10:00:57Z |
| format | Article |
| id | mit-1721.1/114608 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:00:57Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1146082022-09-26T15:11:57Z A Robust Optimization Approach to Backup Network Design With Random Failures Johnston, Matthew Ryan Lee, Hyang-Won Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Johnston, Matthew Ryan Lee, Hyang-Won Modiano, Eytan H This paper presents a scheme in which a dedicated backup network is designed to provide protection from random link failures. Upon a link failure in the primary network, traffic is rerouted through a preplanned path in the backup network. We introduce a novel approach for dealing with random link failures, in which probabilistic survivability guarantees are provided to limit capacity over provisioning. We show that the optimal backup routing strategy in this respect depends on the reliability of the primary network. Specifically, as primary links become less likely to fail, the optimal backup networks employ more resource sharing among backup paths. We apply results from the field of robust optimization to formulate an ILP for the design and capacity provisioning of these backup networks. We then propose a simulated annealing heuristic to solve this problem for large-scale networks and present simulation results that verify our analysis and approach. National Science Foundation (U.S.) (grant CNS-0626781) National Science Foundation (U.S.) (grant CNS-0830961) United States. Defense Threat Reduction Agency (grant HDTRA1-07-1-0004) United States. Defense Threat Reduction Agency (grant HDTRA-09-1-005) 2018-04-06T23:46:12Z 2018-04-06T23:46:12Z 2014-05 2013-11 2018-04-06T11:44:36Z Article http://purl.org/eprint/type/JournalArticle 1063-6692 1558-2566 http://hdl.handle.net/1721.1/114608 Johnston, Matthew, Hyang-Won Lee, and Eytan Modiano. “A Robust Optimization Approach to Backup Network Design With Random Failures.” IEEE/ACM Transactions on Networking 23, no. 4 (August 2015): 1216–1228. https://orcid.org/0000-0001-8238-8130 http://dx.doi.org/10.1109/TNET.2014.2320829 IEEE/ACM Transactions on Networking Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT Web Domain |
| spellingShingle | Johnston, Matthew Ryan Lee, Hyang-Won Modiano, Eytan H A Robust Optimization Approach to Backup Network Design With Random Failures |
| title | A Robust Optimization Approach to Backup Network Design With Random Failures |
| title_full | A Robust Optimization Approach to Backup Network Design With Random Failures |
| title_fullStr | A Robust Optimization Approach to Backup Network Design With Random Failures |
| title_full_unstemmed | A Robust Optimization Approach to Backup Network Design With Random Failures |
| title_short | A Robust Optimization Approach to Backup Network Design With Random Failures |
| title_sort | robust optimization approach to backup network design with random failures |
| url | http://hdl.handle.net/1721.1/114608 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT johnstonmatthewryan arobustoptimizationapproachtobackupnetworkdesignwithrandomfailures AT leehyangwon arobustoptimizationapproachtobackupnetworkdesignwithrandomfailures AT modianoeytanh arobustoptimizationapproachtobackupnetworkdesignwithrandomfailures AT johnstonmatthewryan robustoptimizationapproachtobackupnetworkdesignwithrandomfailures AT leehyangwon robustoptimizationapproachtobackupnetworkdesignwithrandomfailures AT modianoeytanh robustoptimizationapproachtobackupnetworkdesignwithrandomfailures |