Passive Network Tomography Using Bayesian Inference

In this paper, we investigate the problem of identifying lossy links in the interior of the Internet by passively observing the end-to-end performance of existing traffic between a server and its clients. This is in contrast to the previous work on network tomography (e.g., [1]) that has been based on active probing. The key advantage of a passive approach is that it does not introduce wasteful traffic which might perturb the object of inference, i.e., the link loss rates. Moreover, our techniques depend only on knowing the number of lost and successful packets sent to each client rather than the exact loss sequence required by previous techniques such as [1]. While accuracy of link loss rate inference may consequently suffer, our techniques can still pinpoint the trouble spots in the network (e.g., highly lossy links).

We have developed three techniques for passive network tomography: Random Sampling, Linear Optimization, and Bayesian Inference using Gibbs Sampling. We have evaluated these techniques using simulations and traces gathered at a busy Web server. In this paper, we focus on the Gibbs Sampling technique; more information on the three techniques appears in [3].