Toward Accurate and Practical Network Tomography

摘要

The current understanding of the research community is that the accuracy of network performance tomography is significantly influenced by the particular algorithm we choose. We presented early evidence to the contrary: We considered Boolean Inference, and we experimentally showed that the two state-of-the-art Boolean-Inference algorithms perform equally well or very badly, depending on the kind of network topology on which they are applied. Based on these results, we argued that it makes more sense to solve an easier problem than Boolean Inference: infer the probability with which each link is congested (as opposed to which particular links are congested when). Even though Congestion Probability Inference yields less information than Boolean Inference, we argue that, in practice, this information is more useful, because it can be obtained accurately under significantly weaker assumptions (it requires solving a well-posed problem, without making Homogeneity or Independence assumptions).