Enhancing network robustness via shielding

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Zhang, Jianan, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Eytan Modiano.

• Aeronautics and Astronautics.

Statement dc: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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/93804

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/93804