Scheduling multisource divisible loads is a challenging task as different sources should cooperate and share their computing power with others to balance their loads and minimize total computational time. In this study, we attempt to address a generalized divisible load scheduling problem for handling loads from multiple sources on arbitrary networks. This problem is all the more challenging as 1) the topology is arbitrary, 2) in such networks, it is difficult to decide from which source and which route a processing node should receive loads, and 3) processing nodes must be allocated to different sources when they become available. We study two distinct cases of interest, static case and dynamic case, and propose two novel strategies, referred to as static scheduling strategy (SSS) and dynamic scheduling strategy (DSS), respectively. Both strategies work in an iterative fashion. In each iteration, they will use a novel graph partitioning (GP) scheme to partition the network such that each source in the network gains a portion of network resources and then these sources cooperate to process their loads. We analyze the performance of DSS using queuing theory and derive upper bounds on a load's average waiting time and a source's average queue length. We use simulation to verify the usefulness and effectiveness of SSS and DSS. Our findings reveal an interesting ¿load insensitive¿ propertyof SSS and also verify the theoretical upper bound of average queue length at each source in the dynamic case.

In this paper, we evaluate and compare the performance of several spanning tree routing strategies for divisible load scheduling on arbitrary graphs and derive recommendations as to which routing strategy provides a better trade-off between complexity and time performance. We consider a network comprising heterogeneous processors interconnected by heterogeneous links in an arbitrary manner. We evaluate the performance over a wide range of arbitrary dense graphs with varying connectivity and processor densities and study the effect of network scalability. In addition, we introduce a novel spanning tree routing strategy, which is referred to as minimum equivalent network spanning tree (EST), and analyze its performance. We apply the resource-aware optimal load distribution with optimal sequencing (RAOLD-OS) scheduling algorithm presented in the literature for obtaining an optimal solution. This study attempts to pool all known and applicable divisible load scheduling algorithms for arbitrary networks and presents a collective and comparative view of their performance.

In this paper, we propose load distribution strategies for divisible loads for networked computing environments where computation and communication resource characteristics are unknown and/or vary with time. The principle on which our strategies are formulated is based on using probing loads to estimate the network characteristics and using them to determine the best possible load distribution. This work extends the adaptive strategies proposed in an earlier work to multilevel general networks. These networks, while being more challenging, also offer several opportunities that can be exploited to make the probing phase more efficient. We propose two strategies, one static, which caters to the presence of unknown parameters, and the other dynamic, which caters to both unknown as well as time-varying network parameters. The proposed strategies are robust, resilient, and easily adaptable to network fluctuations. The algorithms are also shown to have a tracking ability, a property that is important in dynamic environments. Examples are presented to illustrate the salient features of these strategies.