Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Collaborative Measurements of Upload Speeds in P2P Systems

John Douceur, James Mickens, Thomas Moscibroda, and Debmalya Panigrahi

Abstract

In this paper, we study the theory of collaborative upload bandwidth measurement in peer-to-peer environments. A host can use a bandwidth estimation probe to determine the bandwidth between itself and any other host in the system. The problem is that the result of such a measurement may not necessarily be the sender’s upload bandwidth, since the most bandwidth restricted link on the path could also be the receiver’s download bandwidth. In this paper, we formally define the bandwidth determination problem and devise efficient distributed algorithms. We consider two models, the free-departure and no-departure model, respectively, depending on whether hosts keep participating in the algorithm even after their bandwidth has been determined. We present lower bounds on the time complexity of any collaborative bandwidth measurement algorithm in both models. We then show how, for realistic bandwidth distributions, the lower bounds can be overcome. Specifically, we present O(1) and O(log log n)-time algorithms for the two models. We corroborate these theoretical findings with practical measurements on a implementation on PlanetLab.

Details

Publication typeProceedings
Published inProceedings of INFOCOM
PublisherIEEE Communications Society
> Publications > Collaborative Measurements of Upload Speeds in P2P Systems