Network Topology Inference with Partial Path Information and Probabilistic Cascading Failures through Interdependent Networks
Open Access
- Author:
- Holbert, Brett David
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- September 10, 2014
- Committee Members:
- Thomas La Porta, Thesis Advisor/Co-Advisor
- Keywords:
- topology inference
cascading failures
fault propagation - Abstract:
- Network operation and management are reliant upon accurate knowledge of the network topology. In order to carry out these network management tasks the topology must first be obtained, often using probing. However, full knowledge of the topology may neither be known nor easily obtainable due to heterogeneous ownership and configuration of the routers. In these cases, the network must be inferred. We consider two topics highly related to these problems; network inference required to obtain the topology when it is unknown and modeling cascading failures in interdependent networks as a network operation with full knowledge of the topology. In this thesis we first present iTop, an algorithm for topology inference when complete information about a network's topology is not available. We describe how the iTop algorithm processes the partial information that is obtainable to detect the presence of missing network components and then resolve them towards an inferred topology by identifying links which may be the same. Lastly, we show that iTop outperforms pre-existing network inference algorithms both in terms of the metrics of the inferred networks as well as the suitability of the inferred networks for use with a fault diagnosis algorithm. We further investigate the subject of network failures by proposing a probabilistic model to estimate the spread of cascading failures through an interdependent network. We use this model to calculate the estimated network outages over time for a variety of interdependent network structures. These estimations are compared to simulations of failures over the same networks in order to show that the model accurately predicts the cascade with only a small margin of error. Based on the patterns of failure for the different interdependent network structures we provide insight as to how the cascade spreads through different topologies.