Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2014. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 77-80). / Shielding critical links enhances network robustness and provides a new way of designing robust networks. We first consider shielding critical links to guarantee network connectivity after any failure 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 source-destination (SD) pair under a general failure model, and exploit geographical 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 extend the algorithms to guarantee partial network connectivity, and observe that significantly less shielding is required, especially when the failure region is small. To mitigate the effect of random link failures on network connectivity, we consider increasing the effective min-cut of the network by shielding, where shielded links cannot be contained in effective cuts. For a single SD pair, we develop an efficient algorithm to increase the effective min-cut by one, and develop a MILP with a small number of constraints to increase the effective min-cut by an arbitrary value. Then we extend the MILP to obtain the optimal shielding to increase the effective min-cut for the entire network, which can be used to solve realistic size problems. Finally, we consider shielding critical nodes in random graphs. We demonstrate the importance of high degree nodes in random graphs constructed under the configuration model. The occupancy of higher degree nodes leads to a larger size of the giant component. Moreover, shielding a small fraction of nodes in power law random graphs guarantees the existence of a giant component if the exponent is less than three. / by Jianan Zhang. / S.M.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/93804 |
| Date | January 2014 |
| Creators | Zhang, Jianan, Ph. D. Massachusetts Institute of Technology |
| Contributors | Eytan Modiano., Massachusetts Institute of Technology. Department of Aeronautics and Astronautics., Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 80 pages, application/pdf |
| Rights | 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 |
Page generated in 0.0016 seconds