Collaborative measurements of upload speeds in P2P systems
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 timecomplexity 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.
References
[1]
American National Standards Institute. Network and Customer Installation Interfaces-Asymmetric Digital Subscriber Line (ADSL) Metallic Interface, 1998. ANSI T1.413.
[2]
A. Bharambe, J. Douceur, J. Lorch, T. Moscibroda, J. Pang, S. Seshan, and X. Zhuang. Donnybrook: Enabling Large-Scale, High-Speed, Peerto-Peer Games. In Proceedings of SIGCOMM, pages 389-400, August 2008.
[3]
B. Biskupski, R. Cunningham, J. Dowling, and R. Meier. High-Bandwidth Mesh-based Overlay Multicast in Heterogeneous Environments. In Proceedings of ACM AAA-IDEA, October 2006.
[4]
A. Bozdog, R. van Renesse, and D. Dumitriu. SelectCast--A Scalable and Self-Repairing Multicast Overlay Routing Facility. In Proceedings of SSRS, pages 33-42, October 2003.
[5]
Broadband Reports. Broadband reports speed test statistics. http://www.dslreports.com/archive, October 29, 2008.
[6]
Cable Television Laboratories, Inc. Data-Over-Cable Service Interface Specifications (DOCSIS 3.0): MAC and Upper Layer Protocols Interface Specification, January 2009.
[7]
R. Carter and M. Crovella. Measuring bottleneck link speed in packetswitched networks. Performance Evaluation, 27-28:297-318, October 1996.
[8]
Communication Workers of America. Speed Matters: A Report on Internet Speeds in All 50 States. http://www.speedmatters.org/documentlibrary/ sourcematerials/sm_report.pdf, July 2007.
[9]
M. Dischinger, A. Haeberlen, I. Beschastnikh, K. Gummadi, and S. Saroiu. SatelliteLab: Adding Heterogeneity to Planetary-Scale Network Testbeds. In Proceedings of SIGCOMM, pages 315-326, August 2008.
[10]
J. R. Douceur, J. R. Lorch, and T. Moscibroda. Maximizing total upload in latency-sensitive p2p applications. In Proceedings of 19th SPAA, pages 270-279, 2007.
[11]
J. R. Douceur, J.W. Mickens, T. Moscibroda, and D. Panigrahi. Thunder-Dome: Discovering Upload Constraints Using Decentralized Bandwidth Tournaments. In Proceedings of the 5th ACM International Conference on Emerging Networking Experiments and Technologies (CoNext), 2009.
[12]
C. Dovrolis, P. Ramanathan, and D. Moore. Packet-Dispersion Techniques and a Capacity-Estimation Methodology. IEEE/ACM Transactions on Networking, 12(6):963-977, December 2004.
[13]
J. Ghoshal, B. Ramamurthy, and L. Xu. Variable Neighbor Selection in Live Peer-to-Peer Multimedia Streaming Networks. Technical Report TR-UNL-CSE-2007-021, University of Nebraska-Lincoln Department of Computer Science and Engineering, September 2007.
[14]
N. Hu and P. Steenkiste. Evaluations and Characterization of Available Bandwidth Probing Techniques. IEEE Journal on Selected Areas in Communication, 21(6):879-894, August 2003.
[15]
N. Hu and P. Steenkiste. Exploiting Internet Route Sharing for Large Scale Available Bandwidth Estimation. In Proceedings of IMC, pages 187-192, October 2005.
[16]
International Telecommunication Union, Standardization Sector. ITUT Recommendation V.92: Enhancements to Recommendation V.90, November 2000.
[17]
M. Jain and C. Dovrolis. Pathload: A measurement tool for end-toend available bandwidth. In Proceedings of the Passive and Active Measurements Workshop, pages 14-25, March 2002.
[18]
X. Jin, W. Yiu, S. Chan, and Y. Wang. On Maximizing Tree Bandwidth for Topology-Aware Peer-to-Peer Streaming. IEEE Transactions on Multimedia, 9(8):1580-1592, December 2007.
[19]
K. Lai and M. Baker. Nettimer: A Tool for Measuring Bottleneck Link Bandwidth. In Proceedings of USENIX Symposium on Internet Technologies and Systems, pages 123-134, March 2001.
[20]
K. Lakshminarayanan, V. Padmanabhan, and J. Padhye. Bandwidth Estimation in Broadband Access Networks. In Proceedings of IMC, pages 314-321, October 2004.
[21]
Z. Lotker, E. Pavlov, B. Patt-Shamir, and D. Peleg. MST construction in O(log log n) communication rounds. In Proceedings of 15th SPAA, pages 94-100, 2003.
[22]
B. Melander, M. Bjorkman, and P. Gunningberg. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks. In Proceedings of the GLOBECOM, pages 415-420, November 2000.
[23]
R. Motwani and P. Raghavan. Randomized Algorithms.
[24]
V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, and R. Baraniuk. Multifractal cross traffic estimation. In Proceedings of ITC Specialist Seminar on IP Traffic Measurement, September 2000.
[25]
V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell. pathChirp: Efficient Available Bandwidth Estimation for Network Paths. In Proceedings of the Passive and Active Measurement Workshop, March 2003.
[26]
J. Rosenberg, R. Mahy, P. Matthews, and D. Wing. Session Traversal Utilities for NAT (STUN). RFC 5389, October 2008.
[27]
N. Spring, L. Peterson, A. Bavier, and V. Pai. Using PlanetLab for network research: myths, realities, and best practices. SIGOPS Operating Systems Review, 40(1):17-24, January 2006.
[28]
J. Strauss, D. Katabi, and F. Kaashoek. A Measurement Study of Available Bandwidth Estimation Tools. In Proceedings of IMC, pages 39-44, October 2003.
[29]
WebSiteOptimization.com. Average Web Page Size Triples Since 2003. http://www.websiteoptimization.com/speed/tweak/average-web-page/.
Recommendations
Redesigning multi-channel P2P live video systems with View-Upload Decoupling
In current multi-channel P2P live video systems, there are several fundamental performance problems including exceedingly-large channel switching delays, long playback lags, and poor performance for less popular channels. These performance problems ...
On incentivizing upload capacity in P2P-VoD systems: Design, analysis and evaluation
Free riding has long been a serious problem in peer-to-peer (P2P) systems due to the selfish behavior of individual users. To conquer this problem, a key design issue of the P2P systems is to appropriately incentivize users to contribute resources. In ...
Public Domain P2P File-Sharing Networks Measurements and Modeling
ICISP '06: Proceedings of the International Conference on Internet Surveillance and ProtectionSince P2P file-sharing networks became extremely popular between Internet users, many researchers have tried to model those P2P networks. This article deals with the modeling of public domain P2P filesharing networks in terms of some parameters such as ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2010
2990 pages
ISBN:9781424458363
Publisher
IEEE Press
Publication History
Published: 14 March 2010
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024