Network loss tomography using link independence

We address the problem of inferring link loss rates from unicast end-to-end measurements. Different from previous tomographic techniques, we provide a method to partition all links in the network into several subsets-loss inferences can be performed independently among each subset. We also design a approach, based on the independence of links, to infer the loss rates of individual links in each subset with high accuracy. Compared with two previous representative approaches: LIA and Netscope (the most two accurate algorithms as far as we know) by both analytical and experimental tools, our method mainly has the following strengths: 1) Lower cost. Our method only makes use of single measurement (2% of probe cost of previous methods) on each independent path; 2) More accurate. Even in the network with 30% lossy links, our method accurately identifies 96% of the lossy links, with the false positive rate of 3%, which is a great improvement over the existing alternatives; 3) More scalable. Our algorithm runs much faster than previous ones, with bounded inference error, especially for the networks with more lossy links.