Return to search

Enhancing network robustness via shielding

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.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/93804
Date January 2014
CreatorsZhang, Jianan, Ph. D. Massachusetts Institute of Technology
ContributorsEytan Modiano., Massachusetts Institute of Technology. Department of Aeronautics and Astronautics., Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.
PublisherMassachusetts Institute of Technology
Source SetsM.I.T. Theses and Dissertation
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Format80 pages, application/pdf
RightsM.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.0022 seconds