Empirical Study of Topology Effects on Diagnosis in Computer Networks

In this paper, we compare the efficiency of fault detection and diagnosis in networks having different topological properties, such as scale-free networks and Erdos-Renyi random graphs. Efficiency measures include both the number of tests (e.g., end-to-end network probes) necessary for diagnosis and the computational complexity of diagnosis. We observe that diagnosis in scale-free networks typically requires significantly larger number of tests than diagnosis in random networks. However, the computational complexity of diagnosis appears to be much lower for scale-free networks since the corresponding Bayesian network models used for probabilistic diagnosis tend to have much lower induced width - a topological parameter controlling the complexity of inference in Bayesian networks. We believe that our observations provide important insights for design and deployment of cost-efficient diagnostic methods in computer networks and distributed systems.