On the Design of Online Scheduling Algorithms for Advance Reservations and QoS in Grids
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 1-10
Abstract
We consider the problem of providing QoS guarantees to Grid users through advance reservation of resources. Advance reservation mechanisms provide the ability to allocate resources to users based on agreed-upon QoS requirements and increase the predictability of a Grid system, yet incorporating such mechanisms into current Grid environments has proven to be a challenging task due to the resulting resource fragmentation. We use concepts from computational geometry to present a framework for tackling the resource fragmentation, and for formulating a suite of scheduling strategies. We also develop efficient implementations of the scheduling algorithms that scale to large Grids. We conduct a comprehensive performance evaluation study using simulation, and we present numerical results to demonstrate that our strategies perform well across several metrics that reflect both user-and system-specific goals. Our main contribution is a timely, practical, and efficient solution to the problem of scheduling resources in emerging on-demand computing environments.Keywords
This publication has 10 references indexed in Scilit:
- The Grid EconomyProceedings of the IEEE, 2005
- Nonmigratory Online Deadline Scheduling on MultiprocessorsSIAM Journal on Computing, 2005
- Efficient Burst Scheduling Algorithms in Optical Burst-Switched Networks Using Geometric TechniquesIEEE Journal on Selected Areas in Communications, 2004
- Analysis and Provision of QoS for Distributed Grid ApplicationsJournal of Grid Computing, 2004
- Scheduling with advanced reservations2002
- A taxonomy and survey of grid resource management systems for distributed computingSoftware: Practice and Experience, 2001
- Computational Geometry2000
- Nimrod/G: an architecture for a resource management and scheduling system in a global computational grid2000
- Information power grid: The new frontier in parallel computing?IEEE Concurrency, 1999
- Priority Search TreesSIAM Journal on Computing, 1985