User-level Internet tomography and overlay routing

In this thesis, we study methods to detect, localize and overcome performance problems experienced by end-users in communication networks. These problems are extremely difficult to solve when the only available information are end-to-end data. We first consider the simple problem of identifying poorly performing links in a network. Even though end-to-end data do not provide sufficient information to calculate link loss rates exactly, we show that in many settings they provide enough information to identify the lossy links. We introduce an inference technique based on the maximum likelihood inference principle, which handles well noisy measurements and routing changes. We apply our technique to locate lossy links in sensor networks. Compared to wired networks, sensor networks pose two additional challenges for monitoring functions: they support much less probing traffic, and they change their routing topologies much more frequently. A Boolean performance model that requires a small number of probes is therefore particularly suited to sensor networks. We evaluate the performance of our inference algorithm in simulation and on real-network traces. We find that the proposed technique achieves high detection and low false positive rates. In IP networks where the network topology is stable and the number of end-to-end probes is large, we consider a second approach to the Boolean tomography problem where we take multiple measurements of the network to learn the probability that a link is going to be congested. We show that these probabilities can be uniquely identified from a small set of measurements by using properties of Boolean algebra. We can then use the learnt probabilities as priors to find rapidly the congested links at any time, with an order-of-magnitude gain in accuracy over existing algorithms. We validate our results both by simulation and real implementation in the PlanetLab network. Taking multiple snapshots of the network also allows us to calculate link loss rates from end-to-end measurements exactly. This operation is possible despite that the system of equations relating link loss rates with end-to-end loss rates has multiple solutions. The main reasons are that losses due to congestion occur in bursts, hence the loss rates of congested links have high variances. On the contrary, most links on the Internet are un-congested, hence the averages and variances of their loss rates are virtually zero. We first prove that the variances of link loss rates can be uniquely calculated from the covariances of the measured end-to-end loss rates in any realistic topology. After calculating the link variances, we remove the un-congested links with small variances from the first-order moment equations in order to obtain a full-rank linear system of equations, from which we can calculate precisely the loss rates of the remaining congested links. Our proposed solution uses only regular unicast probes and thus is applicable in today's Internet. It is a