Using content-addressable networks for load balancing in desktop grids

ABSTRACT

Desktop grids have evolved to combine Peer-to-Peer and Grid computing techniques to improve the robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.

REFERENCES

• 1: David P. Anderson , Carl Christensen , Bruce Allen, Designing a runtime system for volunteer computing, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188586]
• 2: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 3: Asad Awan , Ronaldo A. Ferreira , Suresh Jagannathan , Ananth Grama, Unstructured peer-to-peer networks for sharing processor cycles, Parallel Computing, v.32 n.2, p.115-135, February 2006 [doi>10.1016/j.parco.2005.09.002]
• 4: Ali Raza Butt , Xing Fang , Y. Charlie Hu , Samuel Midkiff, Java, peer-to-peer, and accountability: building blocks for distributed cycle sharing, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.13-13, May 06-07, 2004, San Jose, California
• 5: A. S. Cheema , M. Muhammad , I. Gupta, Peer-to-Peer Discovery of Computational Resources for Grid Applications, Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, p.179-185, November 13-14, 2005 [doi>10.1109/GRID.2005.1542740]
• 6: Andrew Chien , Brad Calder , Stephen Elbert , Karan Bhatia, Entropia: architecture and performance of an enterprise desktop grid system, Journal of Parallel and Distributed Computing, v.63 n.5, p.597-610, May 2003 [doi>10.1016/S0743-7315(03)00006-6]
• 7: I. Foster and A. Iamnitchi. On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), Feb. 2003.
• 8: Rohit Gupta , Varun Sekhri , Arun K. Somani, CompuP2P: An Architecture for Internet Computing Using Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, v.17 n.11, p.1306-1320, November 2006 [doi>10.1109/TPDS.2006.149]
• 9: Adriana Iamnitchi , Ian Foster, A peer-to-peer approach to resource location in Grid environments, Grid resource management: state of the art and future trends, Kluwer Academic Publishers, Norwell, MA, 2004
• 10: J.-S. Kim, B. Bhattacharjee, P. J. Keleher, and A. Sussman. Matching Jobs to Resources in Distributed Desktop Grid Environments. Technical Report CS-TR-4791 and UMIACS-TR-2006-15, University of Maryland, Department of Computer Science and UMIACS, Apr. 2006.
• 11: J.-S. Kim, P. Keleher, M. Marsh, B. Bhattacharjee, and A. Sussman. Using Content-Addressable Networks for Load Balancing in Desktop Grids (Extended Version). Technical Report CS-TR-4863 and UMIACS-TR-2007-16, University of Maryland, Department of Computer Science and UMIACS, Mar. 2007.
• 12: J.-S. Kim, B. Nam, P. Keleher, M. Marsh, B. Bhattacharjee, and A. Sussman. Resource Discovery Techniques in Distributed Desktop Grid Environments. In Proceedings of the 7th IEEE/ACM International Conference on Grid Computing (GRID 2006), Sept. 2006.
• 13: J. Ledlie, J. Schneidman, M. Seltzer, and J. Huth. Scooped, Again. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), Feb. 2003.
• 14: M. J. Litzkow, M. Livny, and M. W. Mutka. Condor - A Hunter of Idle Workstations. In Proceedings of the 8th International Conference on Distributed Computing Systems, June 1988.
• 15: V. Lo, D. Zhou, D. Zappala, Y. Lin, and S. Zhao. Cluster Computing on the Fly: P2P Scheduling of Idle Cycles in the Internet. In Proceedings of the 3rd International Workshop on Peer-to-Peer Systems (IPTPS '04), Feb. 2004.
• 16: C. Mastroianni, D. Talia, and O. Verta. A Super-Peer Model for Building Resource Discovery Services in Grids: Design and Simulation Analysis. In Proceedings of the European Grid Conference (EGC2005), Feb. 2005.
• 17: D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat. Design and Implementation Tradeoffs for Wide-Area Resource Discovery. In Proceedings of the 14th IEEE International Symposium on High Performance Distributed Computing (HPDC-14), July 2005.
• 18: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 19: 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
• 20: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 21: D. Zhou , V. Lo, Cluster Computing on the Fly: resource discovery in a cycle sharing peer-to-peer system, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.66-73, April 19-22, 2004
• 22: D. Zhou and V. Lo. WaveGrid: a Scalable Fast-turnaround Heterogeneous Peer-based Desktop Grid System. In Proceedings of the 20th International Parallel & Distributed Processing Symposium, Apr. 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Design

Keywords:
desktop grid, load balancing, peer-to-peer system