A probabilistic scheduling heuristic for computational grids

Article type: Research Article

Authors: Derbal, Youcef

Affiliations: School of Information Technology Management, Ryerson University, 350 Victoria Street, Toronto, ON, Canada M5B 2K3. Tel.: +1 416 979 5000 x7918; E-mail: yderbal@ryerson.ca

Abstract: Computational grids are large scale distributed networks of peer clusters of computing resources bounded by a decentralized management framework for the purpose of providing computing services, called grid services. The scheduling problem consists in finding the clusters that host the required set of grid services with a sufficient available capacity to handle user service requests in compliance with some specified quality of service. The interplay of intermittent resource participation, resource load dynamics, network latency and processing delay, and random subsystem failures creates a ubiquitous uncertainty on the state of the grid capacity to handle user requests. In addition to the need to account for this uncertainty, the scheduling strategy has to be decentralized since computational grids span distinct management domains. In this paper, we propose a decentralized scheduling strategy that views the dynamics of the grid service capacity as a stochastic process modeled by a Markov chain. The proposed scheduling scheme uses this model to predict the future local availability of resources. This is consolidated by a confidence model that approximates the future ability of peer clusters to successfully handle delegated service requests. The scalability of the proposed scheduling strategy is illustrated through simulation.

Keywords: Probabilistic scheduling, decentralized scheduling, service capacity, computational grid, markov chain

DOI: 10.3233/MGS-2006-2104

Journal: Multiagent and Grid Systems, vol. 2, no. 1, pp. 45-59, 2006