research-article

Improving peer-to-peer performance through server-side scheduling

Authors:

Fabián E. Bustamante,

Peter A. Dinda,

Dong LuAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 26, Issue 4

Article No.: 10, Pages 1 - 30

https://doi.org/10.1145/1455258.1455260

Published: 19 December 2008 Publication History

Abstract

We show how to significantly improve the mean response time seen by both uploaders and downloaders in peer-to-peer data-sharing systems. Our work is motivated by the observation that response times are largely determined by the performance of the peers serving the requested objects, that is, by the peers in their capacity as servers. With this in mind, we take a close look at this server side of peers, characterizing its workload by collecting and examining an extensive set of traces. Using trace-driven simulation, we demonstrate the promise and potential problems with scheduling policies based on shortest-remaining-processing-time (SRPT), the algorithm known to be optimal for minimizing mean response time. The key challenge to using SRPT in this context is determining request service times. In addressing this challenge, we introduce two new estimators that enable predictive SRPT scheduling policies that closely approach the performance of ideal SRPT. We evaluate our approach through extensive single-server and system-level simulation coupled with real Internet deployment and experimentation.

References

[1]

Adya, A., Bolosky, W. J., Castro, M., Cermak, G., Chaiken, R., Douceur, J. R., Howell, J., Lorch, J. R., Theimer, M., and Wattenhofer, R. P. 2002. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In Symposium on Operating Systems Design and Implementation.

Digital Library

[2]

Almeida, J., Dabu, M., Manikutty, A., and Cao, P. 1998. Providing differentiated quality-of-service in Web hosting services. In Proceedings of the 1st Workshop on Internet Server Performance (WISP).

[3]

aMule. 2004. aMule homepage. http://www.amule.org.

[4]

Bansal, N. and Harchol-Balter, M. 2001. Analysis of SRPT scheduling: Investigating unfairness. In the Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS).

Digital Library

[5]

Bernstein, D. S., Feng, Z., Levine, B. N., and Zilberstein, S. 2003. Adaptive peer selection. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS).

[6]

Bhagwan, R., Tati, K., Cheng, Y.-C., Savage, S., and Voelker, G. M. 2004. Totall recall: System support for automated availability management. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI). 337--350.

Digital Library

[7]

Box, G. E. P., Jenkins, G. M., and Reinsel, G. 1994. Time Series Analysis: Forecasting and Control, 3rd ed. Prentice Hall.

Digital Library

[8]

Brockwell, P. J. and Davis, R. A. 2002. Introduction to Time Series and Forecasting, 2nd ed. Springer, New York.

[9]

Bustamante, F. E. and Qiao, Y. 2003. Friendships that last: Peer lifespan and its role in P2P protocols. In Proceedings of the 8th International Workshop on Web Content and Caching Distribution.

[10]

Bux, W. 1983. Analysis of a local-area bus system with controlled access. IEEE Trans. Comput. 32, 8, 760--763.

Digital Library

[11]

CacheLogic. 2005. P2P in 2005. http://www.cachelogic.com/research/index.php.

[12]

Chun, B.-G., Dabek, F., Haeberlen, A., Sit, E., Weatherspoon, H., Kaashoek, M. F., Kubiatowicz, J., and Morris, R. 2006. Efficient replica maintenance for distributed storage systems. In Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

[13]

Cox, L. P. and Noble, B. D. 2003. Samsara: Honor among thieves in peer-to-peer storage. In Proceedings of the 19th ACM Symposium on Operating System Principles (SOSP).

Digital Library

[14]

Crovella, M., Frangioso, R., and Harchol-Balter, M. 1999. Connection scheduling in Web servers. In Proc. of the 3rd USENIX Symposium on Internet Technologies and Systems (USITS).

Digital Library

[15]

Dabek, F., Kaashoek, M. F., Karger, D., Morris, R., and Stoica, I. 2001. Wide-Area cooperative storage with CFS. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP).

Digital Library

[16]

Deng, S. 1996. Empirical model of WWW document arivals at access links. In Proc. IEEE ICC.

[17]

eDonkey. 2004. About mftp (multisource file transmission protocol). http://www.edonkey2000.com/documentation/mftp.html.

[18]

eMule. 2004. eMule homepage. http://www.emule-project.net.

[19]

Gummadi, K. P., Dunn, R. J., Saroiu, S., Gribble, S. D., Levy, H. M., and Zahorjan, J. 2003a. Measurement, modeling, and analysis of a peer-to-peer file-sharing workload. In Proceedings of the 19th ACM Symposium on Operating System Principles (SOSP).

Digital Library

[20]

Gummadi, K. P., Dunn, R. J., Saroiu, S., Gribble, S. D., Levy, H. M., and Zahorjan, J. 2003b. Measurement, modeling and analysis of a peer-to-peer file-sharing workload. In Proceedings of the 19th ACM Symposium on Operating System Principles (SOSP).

Digital Library

[21]

Haeberlen, A., Mislove, A., and Druschel, P. 2005. Glacier: Highly durable, decentralized storage despite massive correlated failures. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

[22]

Harchol-Balter, M., Crovella, M., and Park, S. 1998. The case for SRPT scheduling in Web servers. Tech. Rep. MIT-LCS-TR-767.

[23]

Harchol-Balter, M., Schrder, B., Bansal, N., and Agrawal, M. 2003. Size-Based scheduling to improve Web performance. ACM Trans. Comput. Syst. 21, 2.

Digital Library

[24]

Huebsch, R., Hellerstein, J. M., Lanham, N., Loo, B. T., Shenker, S., and Stoica, I. 2003. Querying the Internet with PIER. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB).

Digital Library

[25]

Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C., and Zhao, B. 2000. Oceanstore: An architecture for global-scale persistent storage. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).

Digital Library

[26]

Lillibridge, M., Elnikety, S., Birrell, A., Burrows, M., and Isard, M. 2003. A cooperative Internet backup scheme. In Proceedings of the USENIX Annual Technical Conference.

Digital Library

[27]

Lu, D., Dinda, P. A., Qiao, Y., Sheng, H., and Bustamante, F. E. 2004. Applications of SRPT scheduling with inaccurate information. In Proceedings of the IEEE/ACM Annual Meeting of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS).

[28]

Lu, D., Sheng, H., and Dinda, P. A. 2004. Size-Based scheduling policies with inaccurate scheduling information. In Proceedings of the IEEE/ACM Annual Meeting of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS).

Digital Library

[29]

Lu, D., Sheng, H., and Dinda, P. A. 2005. Effects and implications of file size/service time correlation on Web server scheduling policies. In Proceedings of the IEEE/ACM Annual Meeting of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS).

Digital Library

[30]

MetaMachine. 2004. eDonkey homepage. http://www.edonkey2000.com.

[31]

Michael J. Freedman, E. F. and Mazières, D. 2004. Democratizing content publication with coral. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

[32]

Mickens, J. W. and Noble, B. D. 2006. Exploiting availability prediction in distributed systems. In Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

[33]

Mutella. 2004. Mutella homepage. http://mutella.sourceforge.net.

[34]

Paxson, V. and Floyd, S. 1995. Wide area traffic: The failure of Poisson modeling. IEEE/ACM Trans. Netw. 3, 3, 226--244.

Digital Library

[35]

Perera, R. 1993. The variance of delay time in queueing system M/G/1 with optimal strategy SRPT. Archiv fur Elektronik und Uebertragungstechnik 47, 2, 110--114.

[36]

Qiao, Y., Lu, D., Bustamante, F., and Dinda, P. 2004. Looking at the server side of peer-to-peer systmes. In Proceedings of the 7th Workshop on Langauges, Compilers and Run-Time Support for Scalable Systems (LCR).

Digital Library

[37]

Ratnasamy, S., Handley, M., Karp, R., and Shenker, S. 2001. Application-Level multicast using content-addressable networks. In Proceedings of the 2nd International Workshop of Network Group Communication (NGC).

Digital Library

[38]

Rhea, S., Geels, D., Roscoe, T., and Kubiatowicz, J. 2004. Handling churn in a DHT. In Proceedings of the USENIX Annual Technical Conference.

Digital Library

[39]

Rowstron, A. and Druschel, P. 2001a. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceedings of the IFIP/ACM Middleware Conference.

Digital Library

[40]

Rowstron, A. I. T. and Druschel, P. 2001b. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proceedings of the Symposium on Operating Systems Principles (SOSP). 188--201.

Digital Library

[41]

Saroiu, S., Gummadi, K. P., Dunn, R. J., Gribble, S. D., and Levy, H. M. 2002. An analysis of Internet content delivery systems. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI).

Digital Library

[42]

Saroiu, S., Gummadi, P. K., and Gribble, S. D. 2002. A measurement study of peer-to-peer file sharing systems. In Proceedings of the Annual Multimedia Computing and Networking (MMCN).

[43]

Schrage, L. E. 1968. A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 678--690.

Digital Library

[44]

Schrage, L. E. and Miller, L. W. 1966. The queue M/G/1 with the shortest remaining processing time discipline. Oper. Res. 14, 670--684.

Digital Library

[45]

Schroeder, B. and Harchol-Balter, M. 2006. Web servers under overload: How scheduling can help. ACM Trans. Internet Technol. 6, 1 (Feb.).

Digital Library

[46]

Sharman Networks Ltd. 2004. Kazaa homepage. http://www.kazaa.com.

[47]

Stoica, I., Morris, R., Karger, D., Kaashoek, F., and Balakrishnan, H. 2001. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM). 149--160.

Digital Library

[48]

Tang, C. and Dwarkadas, S. 2004. Hybrid global-local indexing for efficient peer-to-peer information retrieval. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

[49]

Timm, N. H. 2002. Applied Multivariate Analysis. Springer, New York.

Digital Library

[50]

Walsh, K. and Sirer, E. G. 2006. Experience with an object reputation system for peer-to-peer filesharing. In Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

[51]

Zhao, B. Y., Kubiatowicz, J., and Joseph, A. D. 2001. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Tech. Rep. UCV/CSD-01-1141, Computer Science Division, University of California, Berkeley, California.

Digital Library

Cited By

Chiu YEun D(2019)On the Performance of Content Delivery under Competition in a Stochastic Unstructured Peer-to-Peer NetworkIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.1521:10(1487-1500)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TPDS.2010.15
Horváth IRazumchik RTelek M(2019)The resampling M/G/1 non-preemptive LIFO queue and its application to systems with uncertain service timePerformance Evaluation10.1016/j.peva.2019.05.001Online publication date: Jun-2019
https://doi.org/10.1016/j.peva.2019.05.001
Wen CLin R(2010)Towards Minimizing Average Finish Time of P2P File Delivery Under Peer LeavingProceedings of the 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing10.1109/3PGCIC.2010.14(55-62)Online publication date: 4-Nov-2010
https://dl.acm.org/doi/10.1109/3PGCIC.2010.14
Show More Cited By

Index Terms

Recommendations

Scheduling a single server in a two-machine flow shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence ...
Peer-to-peer multimedia applications
MM '06: Proceedings of the 14th ACM international conference on Multimedia

In both academia and industry, peer-to-peer (P2P) applications have attracted great attention. Peer-to-peer file sharing applications, such as Napster, Gnutella, Kazaa, BitTorrent, Skype and PPLive, have witnessed tremendous success among end users. And ...
Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 26, Issue 4

December 2008

98 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/1455258

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 December 2008

Accepted: 01 September 2008

Revised: 01 July 2007

Received: 01 June 2006

Published in TOCS Volume 26, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
740
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chiu YEun D(2019)On the Performance of Content Delivery under Competition in a Stochastic Unstructured Peer-to-Peer NetworkIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.1521:10(1487-1500)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TPDS.2010.15
Horváth IRazumchik RTelek M(2019)The resampling M/G/1 non-preemptive LIFO queue and its application to systems with uncertain service timePerformance Evaluation10.1016/j.peva.2019.05.001Online publication date: Jun-2019
https://doi.org/10.1016/j.peva.2019.05.001
Wen CLin R(2010)Towards Minimizing Average Finish Time of P2P File Delivery Under Peer LeavingProceedings of the 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing10.1109/3PGCIC.2010.14(55-62)Online publication date: 4-Nov-2010
https://dl.acm.org/doi/10.1109/3PGCIC.2010.14
Chen YJana RStern DWei BYang MSun HDyaberi J(2010)ZebroidMultimedia Systems10.1007/s00530-010-0184-y16:3(199-214)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1007/s00530-010-0184-y

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents