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

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: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 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: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 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: Ranjita Bhagwan , Kiran Tati , Yu-Chung Cheng , Stefan Savage , Geoffrey M. Voelker, Total recall: system support for automated availability management, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.25-25, March 29-31, 2004, San Francisco, California
• 7: George Edward Pelham Box , Gwilym M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 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: W. Bux, Analysis of a Local-Area Bus System with Controlled Access, IEEE Transactions on Computers, v.32 n.8, p.760-763, August 1983 [doi>10.1109/TC.1983.1676317]
• 11: CacheLogic. 2005. P2P in 2005. http://www.cachelogic.com/research/index.php.
• 12: Byung-Gon Chun , Frank Dabek , Andreas Haeberlen , Emil Sit , Hakim Weatherspoon , M. Frans Kaashoek , John Kubiatowicz , Robert Morris, Efficient replica maintenance for distributed storage systems, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.4-4, May 08-10, 2006, San Jose, CA
• 13: Landon P. Cox , Brian D. Noble, Samsara: honor among thieves in peer-to-peer storage, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 14: Mark E. Crovella , Robert Frangioso , Mor Harchol-Balter, Connection scheduling in web servers, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.22-22, October 11-14, 1999, Boulder, Colorado
• 15: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 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: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 20: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 21: Andreas Haeberlen , Alan Mislove , Peter Druschel, Glacier: highly durable, decentralized storage despite massive correlated failures, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.143-158, May 02-04, 2005
• 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: Mor Harchol-Balter , Bianca Schroeder , Nikhil Bansal , Mukesh Agrawal, Size-based scheduling to improve web performance, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.207-233, May 2003 [doi>10.1145/762483.762486]
• 24: Ryan Huebsch , Joseph M. Hellerstein , Nick Lanham , Boon Thau Loo , Scott Shenker , Ion Stoica, Querying the internet with PIER, Proceedings of the 29th international conference on Very large data bases, p.321-332, September 09-12, 2003, Berlin, Germany
• 25: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 26: Mark Lillibridge , Sameh Elnikety , Andrew Birrell , Mike Burrows , Michael Isard, A cooperative internet backup scheme, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 09-14, 2003, San Antonio, Texas
• 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: Dong Lu , Huanyuan Sheng , Peter Dinda, Size-Based Scheduling Policies with Inaccurate Scheduling Information, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.31-38, October 04-08, 2004
• 29: Dong Lu , Peter Dinda , Yi Qiao , Huanyuan Sheng, Effects and Implications of File Size/Service Time Correlation onWeb Server Scheduling Policies, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.258-270, September 27-29, 2005 [doi>10.1109/MASCOT.2005.30]
• 30: MetaMachine. 2004. eDonkey homepage. http://www.edonkey2000.com.
• 31: Michael J. Freedman , Eric Freudenthal , David Mazières, Democratizing content publication with coral, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.18-18, March 29-31, 2004, San Francisco, California
• 32: James W. Mickens , Brian D. Noble, Exploiting availability prediction in distributed systems, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.6-6, May 08-10, 2006, San Jose, CA
• 33: Mutella. 2004. Mutella homepage. http://mutella.sourceforge.net.
• 34: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 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: Yi Qiao , Dong Lu , Fabián E. Bustamante , Peter A. Dinda, Looking at the server side of peer-to-peer systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-8, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066664]
• 37: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 38: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 39: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 40: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 41: Stefan Saroiu , Krishna P. Gummadi , Richard J. Dunn , Steven D. Gribble , Henry M. Levy, An analysis of internet content delivery systems, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060319]
• 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.
• 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.
• 45: Bianca Schroeder , Mor Harchol-Balter, Web servers under overload: How scheduling can help, ACM Transactions on Internet Technology (TOIT), v.6 n.1, p.20-52, February 2006 [doi>10.1145/1125274.1125276]
• 46: Sharman Networks Ltd. 2004. Kazaa homepage. http://www.kazaa.com.
• 47: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 48: Chunqiang Tang , Sandhya Dwarkadas, Hybrid global-local indexing for effcient peer-to-peer information retrieval, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.16-16, March 29-31, 2004, San Francisco, California
• 49: I. H. Bernstein, Applied multivariate analysis, Springer-Verlag New York, Inc., New York, NY, 1987
• 50: Kevin Walsh , Emin Gün Sirer, Experience with an object reputation system for peer-to-peer filesharing, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.1-1, May 08-10, 2006, San Jose, CA
• 51: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
Peer-to-peer, SRPT, scheduling, server-side, size-based scheduling