Server-based Inference of Internet Performance

We investigate the problem of inferring the packet loss characteristics of Internet links using server-based measurements. Unlike much of existing work on network tomography that is based on active probing, we make inferences based on passive observation of end-to-end client-server traffic. We start with a brief analysis of end-to-end packet loss rate over widearea Internet paths, as observed from a busy Web site. We find that the end-to-end packet loss rate correlates poorly with topological distance (i.e., hop count), remains stable for several minutes, and exhibits a limited degree of spatial locality. These findings suggest that passive network tomography would be both interesting and feasible. Our work on passive network tomography focuses on identifying lossy links (i.e., the trouble spots in the network). We have developed three techniques for this purpose based on Random Sampling, Linear Optimization, and Bayesian Inference using Gibbs Sampling, respectively. We evaluate the accuracy of these techniques using both simulations and Internet packet traces. We find that these techniques can identify most of the lossy links in the network with a manageable false positive rate. For instance, simulation results indicate that the Gibbs sampling technique has over 80% coverage with a false positive rate under 5%. Furthermore, this technique provides a confidence indicator on its inference. In the case of Internet traces, validating the inferences is a challenging problem. We present a method for indirect validation, which suggests that the false positive rate is manageable.