Network protection with guaranteed recovery times using recovery domains
We consider the problem of providing network protection that guarantees the maximum amount of time that flow can be interrupted after a failure. This is in contrast to schemes that offer no recovery time guarantees, such as IP rerouting, or the prevalent local recovery scheme of Fast ReRoute, which...
| 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/81413 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826208651908481024 |
|---|---|
| author | Kuperman, Gregory Modiano, Eytan H. |
| author2 | Lincoln Laboratory |
| author_facet | Lincoln Laboratory Kuperman, Gregory Modiano, Eytan H. |
| author_sort | Kuperman, Gregory |
| collection | MIT |
| description | We consider the problem of providing network protection that guarantees the maximum amount of time that flow can be interrupted after a failure. This is in contrast to schemes that offer no recovery time guarantees, such as IP rerouting, or the prevalent local recovery scheme of Fast ReRoute, which often over-provisions resources to meet recovery time constraints. To meet these recovery time guarantees, we provide a novel and flexible solution by partitioning the network into failure-independent “recovery domains”, where within each domain, the maximum amount of time to recover from a failure is guaranteed. We show the recovery domain problem to be NP-Hard, and develop an optimal solution in the form of an MILP for both the case when backup capacity can and cannot be shared. This provides protection with guaranteed recovery times using up to 45% less protection resources than local recovery. We demonstrate that the network-wide optimal recovery domain solution can be decomposed into a set of easier to solve subproblems. This allows for the development of flexible and efficient solutions, including an optimal algorithm using Lagrangian relaxation, which simulations show to converge rapidly to an optimal solution. Additionally, an algorithm is developed for when backup sharing is allowed. For dynamic arrivals, this algorithm performs better than the solution that tries to greedily optimize for each incoming demand. |
| first_indexed | 2024-09-23T14:09:17Z |
| format | Article |
| id | mit-1721.1/81413 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:09:17Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/814132022-10-01T19:30:48Z Network protection with guaranteed recovery times using recovery domains Kuperman, Gregory Modiano, Eytan H. Lincoln Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Kuperman, Gregory Modiano, Eytan H. We consider the problem of providing network protection that guarantees the maximum amount of time that flow can be interrupted after a failure. This is in contrast to schemes that offer no recovery time guarantees, such as IP rerouting, or the prevalent local recovery scheme of Fast ReRoute, which often over-provisions resources to meet recovery time constraints. To meet these recovery time guarantees, we provide a novel and flexible solution by partitioning the network into failure-independent “recovery domains”, where within each domain, the maximum amount of time to recover from a failure is guaranteed. We show the recovery domain problem to be NP-Hard, and develop an optimal solution in the form of an MILP for both the case when backup capacity can and cannot be shared. This provides protection with guaranteed recovery times using up to 45% less protection resources than local recovery. We demonstrate that the network-wide optimal recovery domain solution can be decomposed into a set of easier to solve subproblems. This allows for the development of flexible and efficient solutions, including an optimal algorithm using Lagrangian relaxation, which simulations show to converge rapidly to an optimal solution. Additionally, an algorithm is developed for when backup sharing is allowed. For dynamic arrivals, this algorithm performs better than the solution that tries to greedily optimize for each incoming demand. National Science Foundation (U.S.) (NSF grant CNS-1017800) National Science Foundation (U.S.) (grant CNS-0830961) United States. Defense Threat Reduction Agency (grant HDTRA-09-1-005) United States. Defense Threat Reduction Agency (grant HDTRA1-07-1-0004) United States. Air Force (Air Force contract # FA8721-05-C-0002) 2013-10-17T16:32:01Z 2013-10-17T16:32:01Z 2013-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-5946-7 978-1-4673-5944-3 978-1-4673-5945-0 0743-166X INSPEC Accession Number: 13682042 http://hdl.handle.net/1721.1/81413 Kuperman, Greg, and Eytan Modiano. “Network protection with guaranteed recovery times using recovery domains.” In 2013 Proceedings IEEE INFOCOM, 14-19 April 2013, Turin, Italy. pp.692-700. Institute of Electrical and Electronics Engineers, 2013. https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/INFCOM.2013.6566855 2013 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 | Kuperman, Gregory Modiano, Eytan H. Network protection with guaranteed recovery times using recovery domains |
| title | Network protection with guaranteed recovery times using recovery domains |
| title_full | Network protection with guaranteed recovery times using recovery domains |
| title_fullStr | Network protection with guaranteed recovery times using recovery domains |
| title_full_unstemmed | Network protection with guaranteed recovery times using recovery domains |
| title_short | Network protection with guaranteed recovery times using recovery domains |
| title_sort | network protection with guaranteed recovery times using recovery domains |
| url | http://hdl.handle.net/1721.1/81413 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT kupermangregory networkprotectionwithguaranteedrecoverytimesusingrecoverydomains AT modianoeytanh networkprotectionwithguaranteedrecoverytimesusingrecoverydomains |