Network Recovery after an Ambiguous Massive Failure
Open Access
Author:
Hayes, Seamus Brock
Area of Honors:
Computer Engineering
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Thomas F. LaPorta, Thesis Supervisor Chitaranjan Das, Thesis Honors Advisor
Keywords:
network engineering recovery computer failure
Abstract:
This thesis addresses the problem of finding the minimum cost set of repairs to perform on a destroyed communications network in order to support mission critical services. The work presented here is an expansion on the work done by N. Bartolini, S. Ciavarella, T. La Porta, and S. Silvestri in their paper Network recovery after massive failures. Their paper defines a polynomial time heuristic, called Iterative Split and Prune (ISP) that solves for the minimum cost set of repairs to be performed on a known disruption by recursively dividing the problem. We propose a new heuristic, k-Hop Iterative Split and Prune, which can solve for the minimum cost set of repairs when the exact structure of the network disruption is not known. We performed extensive simulations by varying the demand intensity, the number of demands, and the strength of the disruption. We find that the additions to the new k-Hop ISP enable it to perform well when the pattern of the destruction in partially unknown. The number of network elements that truly need repairing found by k-Hop ISP with partial knowledge is similar to the number of elements determined by ISP with full knowledge of the disruption.
