Boolean Inference makes it possible to observe the congestion status of end-to-end paths and infer, from that, the congestion status of individual network links. In principle, this can be a powerful monitoring tool, in scenarios where we want to monitor a network without having direct access to its links. We consider one such real scenario: a Tier-1 ISP operator wants to monitor the congestion status of its peers. We show that, in this scenario, Boolean Inference cannot be solved with enough accuracy to be useful; we do not attribute this to the limitations of particular algorithms, but to the fundamental difficulty of the Inference problem. Instead, we argue that the "right" problem to solve, in this context, is compute the probability that each set of links is congested (as opposed to try to infer which particular links were congested when). Even though solving this problem yields less information than provided by Boolean Inference, we show that this information is more useful in practice, because it can be obtained accurately under weaker assumptions than typically required by Inference algorithms and more challenging network conditions (link correlations, non-stationary network dynamics, sparse topologies).

Network tomography establishes linear relationships between the characteristics of individual links and those of end-to-end paths. It has been proved that these relationships can be used to infer the characteristics of links from end-to-end measurements, provided that links are not correlated, i.e., the status of one link is independent from the status of other links.

We present Netscope, a tomographic technique that infers the loss rates of network links from unicast end-to-end measurements. Netscope uses a novel combination of first- and second-order moments of end-to-end measurements to identify and characterize the links that cannot be (accurately) characterized through existing practical tomographic techniques. Using both analytical and experimental tools, we show that Netscope enables scalable, accurate link-loss inference: in a simulation scenario involving 4000 links, 20% of them lossy, Netscope correctly identifies 94% of the lossy links with a false positive rate of 16%-a significant improvement over the existing alternatives. Netscope is robust in the sense that it requires no parameter tuning, moreover its advantage over the alternatives widens when the number of lossy links increases. We also validate Netscope's performance on an "Internet tomographer" that we deployed on an overlay of 400 PlanetLab nodes.