Grid capacity planning with negotiation-based advance reservation for optimized QoS

ABSTRACT

Advance reservation of Grid resources can play a key role in enabling Grid middleware to deliver on-demand resource provision with significantly improved Quality-of-Service (QoS). However, in the Grid, advance reservation has been largely ignored due to the dynamic Grid behavior, under-utilization concerns, multi-constrained applications, and lack of support for agreement enforcement. These issues force the Grid middleware to make resource allocations at runtime with reduced QoS. To remedy these, we introduce a new, 3-layered negotiation protocol for advance reservation of the Grid resources. We model resource allocation as an on-line strip packing problem and introduce a new mechanism that optimizes resource utilization and QoS constraints while generating the contention-free solutions. The mechanism supports open reservations to deal with the dynamic Grid and provides a practical solution for agreement enforcement. We have implemented a prototype and performed experiments to demonstrate the effectiveness of our approach.

REFERENCES

• 1: Bill Allcock , Joe Bester , John Bresnahan , Ann L. Chervenak , Ian Foster , Carl Kesselman , Sam Meder , Veronika Nefedova , Darcy Quesnel , Steven Tuecke, Data management and transfer in high-performance computational grid environments, Parallel Computing, v.28 n.5, p.749-771, May 2002 [doi>10.1016/S0167-8191(02)00094-7]
• 2: Altair. Portable batch system (pbs) professional 7.1. http://www.altair.com/software/pbspro.htm.
• 3: Alexander Barmouta , Rajkumar Buyya, GridBank: A Grid Accounting Services Architecture (GASA) for Distributed Systems Sharing and Integration, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.245.1, April 22-26, 2003
• 4: Carter Bays, A comparison of next-fit, first-fit, and best-fit, Communications of the ACM, v.20 n.3, p.191-192, March 1977 [doi>10.1145/359436.359453]
• 5: Buyya, R., and Venugopal, S. 2004. The gridbus toolkit for service oriented grid and utility computing: An overview and status report. In Proceedings of the First IEEE International Workshop on Grid Economics and Business Models, IEEE Press, New Jersey, USA, 1936.
• 6: Cluster Resources, I. Super clusters: Center for hpc cluster resource management and scheduling. http://www.supercluster.org/projects/.
• 7: Consortium, T. A. G. http://www.austriangrid.at.
• 8: Cooper, K., Dasgupta, A., Kennedy, K., Koelbel, C., Mandal, A., Marin, G., Mazina, M., Mellor-Crummey, J., Berman, F., Casanova, H., Chien, A., Dail, H., Liu, X., Olugbile, A., Sievert, O., Xia, H., Johnsson, L., Liu, B., Patel, M., Reed, D., Deng, W., Mendes, C., Shi, Z., Yarkhan, A., and Dongarra, J. 2004. New Grid Scheduling and Rescheduling Methods in the GrADS Project. In International Parallel and Distributed Processing Symposium, Workshop for Next Generation Software, IEEE Computer Society Press.
• 9: János Csirik , Gerhard J. Woeginger, Shelf algorithms for on-line strip packing, Information Processing Letters, v.63 n.4, p.171-175, Aug. 28, 1997 [doi>10.1016/S0020-0190(97)00120-8]
• 10: Karl Czajkowski , Ian T. Foster , Nicholas T. Karonis , Carl Kesselman , Stuart Martin , Warren Smith , Steven Tuecke, A Resource Management Architecture for Metacomputing Systems, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.62-82, March 30, 1998
• 11: Czajkowski, K., Foster, I., Kesselman, C., Sander, V., and Tuecke, S., 2002. Snap: A protocol for negotiating service level agreements and coordinating resource management in distributed systems.
• 12: DUROC-Team G. The dynamically updated request online coallocator. http://www-fp.globus.org/duroc/.
• 13: Elmroth, E., and Tordsson, J. 2005. A Grid Resource Broker Supporting Advance Reservations and Benchmark-based Resource Selection. In State-of-the-art in Scientific Computing., Springer Verlag, vol. 3732 of Lecture Notes in Computer Science, 1077--1085.
• 14: Fahringer, T., Prodan, R., Duan, R., Hofer, J., Nadeem, F., Nerieri, F., Podlipnig, S., Qin, J., Siddiqui, M., Truong, H.-L., Villazon, A., and Wieczorek, M. Askalon: A development and grid computing environment for scientific workflows. Workflows for eScience, Scientific Workflows for Grids.
• 15: Fahringer, T., Prodan, R., Duan, R., Nerieri, F., Podlipnig, S., Qin, J., Siddiqui, M., Truong, H.-L., Villazon, A., and Wieczorek, M. 2005. ASKALON: A Grid Application Development and Computing Environment. In 6th International Workshop on Grid Computing (Grid 2005), IEEE Computer Society Press, Seattle, Washington, USA.
• 16: Foster, I., Kesselman, C., Lee, C., Lindell, R., Nahrstedt, K., and Roy, A. 1999. A distributed resource management architecture that supports advance reservations and co-allocation. In Proceedings of the International Workshop on Quality of Service.
• 17: GLOBUS. The globus alliance. http://www.globus.org/toolkit.
• 18: GRAAP-WG, G. G. F., 2006. Grid resource allocation agreement protocol. https://forge.gridforum.org/projects/graap-wg.
• 19: Abdelhakim Hafid , Gregor von Bochmann , Rachida Dssouli, A quality of service negotiation approach with future reservations (NAFUR): a detailed study, Computer Networks and ISDN Systems, v.30 n.8, p.777-794, May 1, 1998 [doi>10.1016/S0169-7552(97)00109-8]
• 20: David B. Jackson , Quinn Snell , Mark J. Clement, Core Algorithms of the Maui Scheduler, Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, p.87-102, June 16, 2001
• 21: JSDL-Wg, G. G. F. Job submission description language (jsdl). http://www.ggf.org/documents/GFD.56.pdf.
• 22: Andrew Stephen Mcgough , Ali Afzal , John Darlington , Nathalie Furmento , Anthony Mayer , Laurie Young, Making the Grid Predictable through Reservations and Performance Modelling, The Computer Journal, v.48 n.3, p.358-368, May 2005 [doi>10.1093/comjnl/bxh091]
• 23: Netessine, S., and Shumsky(2002), R. Introduction to the theory and practice of yield management. INFORMS Transactions on Education 3, 1.
• 24: Nordugrid-Team. NorduGrid project. http://www.nordugrid.org.
• 25: Platform. Lsf. http://www.platform.com/Products/Platform.LSF.Family.
• 26: T. Röblitz , F. Schintke , A. Reinefeld, Resource reservations with fuzzy requests: Research Articles, Concurrency and Computation: Practice & Experience, v.18 n.13, p.1681-1703, November 2006 [doi>10.1002/cpe.v18:13]
• 27: Yi Shang , Benjamin W. Wah, A Discrete Lagrangian-Based Global-SearchMethod for Solving Satisfiability Problems, Journal of Global Optimization, v.12 n.1, p.61-99, January 1998 [doi>10.1023/A:1008287028851]
• 28: Siddiqui, M., and Fahringer, T. 2005. GridARM: Askalon's Grid Resource Management System. In Advances in Grid Computing - EGC 2005 - Revised Selected Papers, Springer Berlin / Heidelberg, ISBN 3-540-26918-5, vol. 3470 of Lecture Notes in Computer Science, 122--131.
• 29: Siddiqui, M., Fahringer, T., Hofer, J., and Toma, I. 2005. Grid resource ontologies and asymmetric resource-correlation. In 2nd International Conference on Grid Service Engineering and Management (GSEM'05), Lecture Notes in Informatics, Erfurt, Germany, G. S. of Informatics, Ed.
• 30: Mumtaz Siddiqui , Alex Villazon , Jurgen Hofer , Thomas Fahringer, GLARE: A Grid Activity Registration, Deployment and Provisioning Framework, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.52, November 12-18, 2005 [doi>10.1109/SC.2005.30]
• 31: Singh, G., Kesselman, C., and Deelman, E. 2005. Performance impact of resource provisioning on workflows. Technical report 05-850, Information Sciences Institute, University of Southern California. http://www.cs.usc.edu/Research/TechReports/05-850.pdf.
• 32: Scheduling with Advanced Reservations, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.127, May 01-05, 2000
• 33: Sulistio, A., and Buyya, R. 2004. A grid simulation infrastructure supporting advance reservation. In Proceedings of the 16th International Conference on Parallel and Distributed Computing and Systems, ACTA Press, MIT Cambridge, Boston, USA.
• 34: Sun Microsystems, I. Sun grid engine. http://www.sun.com/software/gridware/.
• 35: Christian F. Tschudin, Open Resource Allocation for Mobile Code, Proceedings of the First International Workshop on Mobile Agents, p.186-197, April 07-08, 1997
• 36: Waldspurger, C., and Weihl, W. 1994. Lottery scheduling: Flexible proportionalshare resource management. In First Symposium on Operating System Design and Implementation (OSDI), USENIX.
• 37: Wang, G., Zhang, W., Mailler, R., and Lesser, V. 2003. Analysis of Negotiation Protocols by Distributed Search. Kluwer Academic Publishers, 339--361.
• 38: Lars C. Wolf , Ralf Steinmetz, Concepts for Resource Reservation in Advance, Multimedia Tools and Applications, v.4 n.3, p.255-278, May 1997 [doi>10.1023/A:1009684906050]
• 39: WSRF, G. A. Web services resource framework. http://www.globus.org/wsrf.
• 40: Makoto Yokoo , Edmund H. Durfee , Toru Ishida , Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.673-685, September 1998 [doi>10.1109/69.729707]
• 41: Yu, J., and Buyya, R. 2005. A Taxonomy of Workflow Management Systems for Grid Computing. Technical report grids-tr-2005-1, Grid Computing and Distributed Systems Laboratory, University of Melbourne, Australia, Mar. http://www.gridbus.org/.
• 42: Zhang, W. 2002. Modeling and solving a resource allocation problem with soft constraint techniques. Technical report wucs-2002-13, Department of Computer Science and Engineering, Washington University in St. Louis, May.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Quality assurance

General Terms:
Design, Management, Performance

Keywords:
advance reservation, capacity planning, grid resource allocation, negotiation