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 |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/67292 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826209501385064448 |
|---|---|
| author | Johnston, Matthew Ryan Lee, Hyang-Won Modiano, Eytan H. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 amongst 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 largescale networks, and present simulation results that verify our analysis and approach. |
| first_indexed | 2024-09-23T14:23:29Z |
| format | Article |
| id | mit-1721.1/67292 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:23:29Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/672922022-09-29T09:10:07Z 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 Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Modiano, Eytan H. 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 amongst 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 largescale 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) 2011-11-28T15:16:46Z 2011-11-28T15:16:46Z 2011-06 2011-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-9919-9 0743-166X http://hdl.handle.net/1721.1/67292 Johnston, Matthew, Hyang-Won Lee, and Eytan Modiano. “A Robust Optimization Approach to Backup Network Design with Random Failures.” 2011 Proceedings IEEE INFOCOM. Shanghai, China, 2011. 1512-1520. © Copyright 2011 IEEE https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/INFCOM.2011.5934940 2011 Proceedings IEEE INFOCOM 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 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/67292 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 |