Design and performance analysis of heuristic load-balancing strategies for processing divisible loads on Ethernet clusters

Abstract

We consider the problem of processing divisible loads on Ethernet clusters. In the divisible load theory (DLT) literature, processing of both single large divisible loads and multiple divisible loads is considered in a single Ethernet/bus system. In practice, Ethernet/bus networks are small in size, with only a few processors sharing a common bus as an interconnection medium. In this article, we consider a typical network topology that can be found in any corporate or research/academic environment in which there could be several Ethernet clusters interconnected in some arbitrary fashion. We analyze a scenario where each such cluster receives a single divisible load to process; our objective is to minimize the total processing time of all the loads that arrive at the system. The problem of obtaining minimum processing time within each cluster is well studied in the literature, as individual clusters are autonomous in operation. However, in the above-mentioned scenario, due to the heterogeneity of the cluster systems, there exists an imbalance in the number of loads assigned to each processor in the entire system, and hence resources in the system are underutilized. We use all the available strategies proposed in the literature for obtaining optimal solutions for single- and multi-load processing to carry out efficient load-sharing among the clusters. This is the first attempt in this domain of literature to consider and demonstrate the load-balancing ability of scheduling algorithms for clusters, for processing divisible loads. The contribution of this research is to test the limits of all the available strategies found in the literature while balancing the processing loads among clusters. Rigorous simulation results are presented to quantify the performance of these strategies.