| Over the years, numerous scheduling and resource utilization techniques have been proposed for distributed systems that are loosely coupled over local-area interconnection network. However, most of them suffer from significant deficiencies when extended to a distributed heterogeneous systems coupled over wide-area networks like a Grid: some techniques use a centralized approach that renders the algorithm unscalable, while others assume the overhead involved in searching for appropriate resources to be negligible. Furthermore, classical scheduling algorithms do not consider a Grid node to be N-resource (e.g., CPU, memory, I/O-channels, software licenses, etc.) rich and merely work towards maximizing the utilization of one of the resources, thereby leading to wastage of other available resources. In this work, we present a new scheduling and resource utilization algorithm, DONAN (Decentralized Overhead Nullifying Algorithm for N-resource Grid model), for a generalized Grid model of N-resource nodes that not only takes into account the node and network heterogeneity, but also considers the overhead involved in coordinating among the nodes. DONAN is highly scalable, and overlaps the node coordination time with the actual processing time of the ready jobs, thus saving valuable clock cycles needed for making decisions. Comprehensive theoretical study include modeling 2-resource and 3-resource nodes using queueing theory and the runtime complexity analysis of the algorithm. Exhaustive experimental study was done using the Message Passing Interface (MPI) paradigm and the results that canvass various heterogeneous scenarios and several performance metrics were close to the theoretical ideal scenario where a perfect load distribution was assumed with no overhead of any kind. |
