Network protection with service guarantees
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/82471 |
| _version_ | 1826196118490316800 |
|---|---|
| author | Kuperman, Gregory |
| author2 | Eytan Modiano. |
| author_facet | Eytan Modiano. Kuperman, Gregory |
| author_sort | Kuperman, Gregory |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2013. |
| first_indexed | 2024-09-23T10:21:29Z |
| format | Thesis |
| id | mit-1721.1/82471 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:21:29Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/824712019-04-12T20:45:43Z Network protection with service guarantees Kuperman, Gregory Eytan Modiano. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Aeronautics and Astronautics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2013. This electronic version was submitted and approved by the author's academic department as part of an electronic thesis pilot project. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from department-submitted PDF version of thesis. Includes bibliographical references (p. 167-174). With the increasing importance of communication networks comes an increasing need to protect against network failures. Traditional network protection has been an "all-or-nothing" approach: after any failure, all network traffic is restored. Due to the cost of providing this full protection, many network operators opt to not provide protection whatsoever. This is especially true in wireless networks, where reserving scarce resources for protection is often too costly. Furthermore, network protection often does not come with guarantees on recovery time, which becomes increasingly important with the widespread use of real-time applications that cannot tolerate long disruptions. This thesis investigates providing protection for mesh networks under a variety of service guarantees, offering significant resource savings over traditional protection schemes. First, we develop a network protection scheme that guarantees a quantifiable minimum grade of service upon a failure within the network. Our scheme guarantees that a fraction q of each demand remains after any single-link failure, at a fraction of the resources required for full protection. We develop both a linear program and algorithms to find the minimum-cost capacity allocation to meet both demand and protection requirements. Subsequently, we develop a novel network protection scheme that provides guarantees on both the fraction of time a flow has full connectivity, as well as a quantifiable minimum grade of service during downtimes. In particular, a flow can be below the full demand for at most a maximum fraction of time; then, it must still support at least a fraction q of the full demand. This is in contrast to current protection schemes that offer either availability-guarantees with no bandwidth guarantees during the down-time, or full protection schemes that offer 100% availability after a single link failure. We show that the multiple availability guaranteed problem is NP-Hard, and develop solutions using both a mixed integer linear program and heuristic algorithms. Next, we consider the problem of providing resource-efficient 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. Finally, we study the problem of providing protection against failures in wireless networks subject to interference constraints. Typically, protection in wired networks is provided through the provisioning of backup paths. This approach has not been previously considered in the wireless setting due to the prohibitive cost of backup capacity. However, we show that in the presence of interference, protection can often be provided with no loss in throughput. This is due to the fact that after a failure, links that previously interfered with the failed link can be activated, thus leading to a "recapturing" of some of the lost capacity. We provide both an ILP formulation for the optimal solution, as well as algorithms that perform close to optimal. by Gregory Kuperman. Ph.D. 2013-11-18T20:39:38Z 2013-11-18T20:39:38Z 2013 2013 Thesis http://hdl.handle.net/1721.1/82471 862119271 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 174 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Kuperman, Gregory Network protection with service guarantees |
| title | Network protection with service guarantees |
| title_full | Network protection with service guarantees |
| title_fullStr | Network protection with service guarantees |
| title_full_unstemmed | Network protection with service guarantees |
| title_short | Network protection with service guarantees |
| title_sort | network protection with service guarantees |
| topic | Aeronautics and Astronautics. |
| url | http://hdl.handle.net/1721.1/82471 |
| work_keys_str_mv | AT kupermangregory networkprotectionwithserviceguarantees |