We present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes. netCSI consists of two parts: a hypotheses generation algorithm, and a ranking algorithm. When constructing the hypothesis list of potential causes, we make novel use of positive and negative symptoms to improve the precision of the results. In addition, we propose pruning and thresholding along with a dynamic threshold value selector, to reduce the complexity of our algorithm. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and demonstrate an average gain of 128 percent in accuracy for realistic topologies.

Full knowledge of the routing topology of the Internet is useful for a multitude of network management tasks. However, the full topology is often not known and is instead estimated using topology inference algorithms. Many of these algorithms use Traceroute to probe paths and then use the collected information to infer the topology. We perform real experiments and show that, in practice, routers may severely disrupt the operation of Traceroute and cause it to only provide partial information. We propose iTop, an algorithm for inferring the network topology when only partial information is available. iTop constructs a virtual topology, which overestimates the number of network components, and then repeatedly merges links in this topology to resolve it toward the structure of the true network. We perform extensive simulations to compare iTop to state-of-the-art inference algorithms. Results show that iTop significantly outperforms previous approaches and its inferred topologies are within 5% of the original networks for all considered metrics. Additionally, we show that the topologies inferred by iTop significantly improve the performance of fault localization algorithms when compared with other approaches.

We propose a greedy algorithm, Cluster-MAX-COVERAGE (CMC), to efficiently diagnose large-scale clustered failures. We primarily address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100 percent accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. When there are fewer positive and negative symptoms at a reporting node, CMC performs much better than existing algorithms. We also propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both independent and clustered failures. During a series of failures that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

In this paper, we study the problem of selecting paths to improve the performance of network tomography applications in the presence of network element failures. We model the robustness of paths in network tomography by a metric called expected rank. We formulate an optimization problem to cover two complementary performance metrics: robustness and probing cost. The problem aims at maximizing the expected rank under a budget constraint on the probing cost. We prove that the problem is NP-Hard. Under the assumption that the failure distribution is known, we propose an algorithm called RoMe with guaranteed approximation ratio. Moreover, since evaluating the expected rank is generally hard, we provide a bound which can be evaluated efficiently. We also consider the case in which the failure distribution is not known, and propose a reinforcement learning algorithm to solve our optimization problem, using RoMe as a subroutine. We run a wide range of simulations under realistic network topologies and link failure models to evaluate our solution against a state-of-the-art path selection algorithm. Results show that our approaches provide significant improvements in the performance of network tomography applications under failures.

In this paper, we propose an algorithm to efficiently diagnose large-scale clustered failures. The algorithm, Cluster-MAX-COVERAGE (CMC), is based on greedy approach. We address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100% accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. Furthermore, we propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both kinds of failures, i.e., independent and clustered. During a series of failues that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

In this paper we present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes in the network. netCSI consists of two parts: hypotheses generation algorithm, and ranking algorithm. When constructing the hypotheses list of potential causes, we make novel use of the positive and negative symptoms to improve the precision of the results. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and achieve an average gain of 128\% in accuracy for realistic topologies.

Network coding has been proposed as an alternative to the conventional store-and-forward routing paradigm for data delivery in networks. When deployed in a multi-rate wireless network, network coding has to interact with rate adaptation. When multicasting packets (a requirement of network coding) in a multi-rate IEEE 802.11 wireless network, one must use care when selecting the transmission rate to use. We refer to this problem as rate selection. We analyze the performance of network coding for a small set of scenarios representative of common topologies in a network that lead to coding opportunities. Based on this analysis, we present our Network Coding aware Rate Selection (NCRS) algorithm which takes into account transmission rates used for unicast links to all multicast targets. Simulation results show that in a multi-hop wireless network, network coding with NCRS achieves up to 24% more gain over routing than network coding with other rate selection algorithms.