Department of Computer Science & Engineering

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.

Pre-2018 CSE ID: CS2007-0891