Accurately estimating all link-level properties of a large network has proven to be very difficult. The measurements used for these estimates require significant collaboration from all endpoints on the network, significantly reducing their applicability for large scale Internet measurements. We present a scalable approach using a small number of hosts without collaboration from existing routers and minimal collaboration between the hosts. Our approach is based on adaptive sampling. Initially, each host probes a set of receivers at a low frequency. When packet losses are detected, the sampling rate increases. By detecting correlations between time series and combining them with information about network connectivity, the host identifies a set of suspected lossy routers. Hosts then communicate with each other, combining evidence to identify routers with high packet loss. Our experiments show that using a relatively small set of hosts and receivers, we can gather sufficient evidence to identify a small number of routers that cause most of the packet loss in a geographically diverse sample of the Internet. We deployed our method for one month on 68 PlanetLab nodes. As a result of that deployment, we identified 128 routers of the ~4,500 accounting for 87% of the observed packet loss.
The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, firstname.lastname@example.org.
[ Search ]