Decentralized scheduling on grid environments

Abstract

Resource management is an important field on Grid research. The main contributions in this area are generally carried out under the assumption that there is one primary scheduling system scheduling jobs. However, as environments tend towards larger open "utility" Grids, it becomes increasingly likely that deployments will involve multiple independent schedulers allocating jobs over the same resources. In this work we show that, by using current standard scheduling approaches, such environments with multiple independent scheduling processes working over the same set of resources can potentially exhibit some of the same types of control problems commonly found in today's packet switched IP (Internet Protocol) networks - namely pathological oscillations in resource allocation caused by unintended synchronization of job allocation by independent scheduling instances - leading to significant inefficiencies in performance. Furthermore, in order to overcome these problems caused by the lack of coordination or cooperation among the scheduler-to-resource and scheduler-to-scheduler, we have proposed two novel decentralized scheduling models based on IP networks common techniques - particularly, approaches based on Random Early Detection (RED) buffer management - and mechanisms inspired by the gossip seen in human social networks, which provide an effective way to damp or eliminate such oscillations and thus, improve the throughput and resource utilization in large scale Grids based on RED strategies. The experimental study performed using DSGridSim, a simulation framework designed to support the study of new and different scheduling strategies in such environments, showed that by using RED-based techniques we are able to obtain a reduction of job turn-around times ranging between 19% and 33% and an improvement of the overall resource utilization of up to 15%, when a real workload trace was provided. Furthermore, we have presented a first validation of RED strategies and DSGridSim simulator by comparing their behavior with executions on a real environment and the results obtained suggest that our proposals could be easily implemented in a real Grid.