Many measurement systems have been proposed in recent years to shed light on the internal performance of the Internet. Their common goal is to allow distributed applications to improve end-user experience. A common hurdle they face is the need to deploy yet another measurement infrastructure. In this work, we demonstrate that without any new measurement infrastructure or active probing we obtain composite performance estimates from AS-by-AS segments and the estimates are as good as (or even better than) those from existing estimation methodologies that use on-demand, customized active probing. The main contribution of this paper is an estimation algorithm that breaks down measurement data into segments, identifies relevant segments efficiently, and, by carefully stitching segments together, produces delay and path estimates between any two end points. Fittingly, we call our algorithm path stitching. Our results show remarkably good accuracy: error in delay is below 20 ms in 80% of end-to-end paths.

Massively distributed applications are popular in today's Internet. To improve the end-user experience, they require constantly updated information about the network-internal performance characteristics, such as RTT, effective bandwidth, IP hop count, and loss rate. Knowledge of network-internal characteristics allow distributed applications to solve commonly encountered problems, such as nearest neighbor discovery, leader node selection, and optimal distribution tree organization. Today's Internet does not provide any such information, and applications and new services resort often perform their own measurement to obtain necessary information.