Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jpdc.2006.05.007
Title: Distributed scheduling strategy for divisible loads on arbitrarily configured distributed networks using load balancing via virtual routing
Authors: Zeng, Z. 
Veeravalli, B. 
Keywords: Arbitrary networks
Divisible load theory
Load balancing
Minimum cost spanning tree
Processing time
Routing path
Scheduling
Issue Date: Nov-2006
Source: Zeng, Z., Veeravalli, B. (2006-11). Distributed scheduling strategy for divisible loads on arbitrarily configured distributed networks using load balancing via virtual routing. Journal of Parallel and Distributed Computing 66 (11) : 1404-1418. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jpdc.2006.05.007
Abstract: In this paper, we consider a scheduling problem for divisible loads originating from single or multiple sites on arbitrary networks. We first propose a generalized mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. We derive a number of theoretical results on the solution of the optimization problem. On the basis of these first set of results, we propose an efficient algorithm for scheduling divisible loads using the concept of load balancing via virtual routing for an arbitrary network configuration. The proposed algorithm has three major attractive features. Firstly, the algorithm is simple to realize and can be implemented in a distributed fashion. The second one is in its style of working by avoiding the need for generating a timing diagram explicitly for any complex networks having an arbitrary network topology. The last one is its capability of handling divisible loads originating from both single and multiple sites. When divisible loads originate from a single node, we compare the proposed algorithm with a recently proposed RAOLD algorithm which is based on minimum cost spanning tree [J. Yao, V. Bharadwaj, Design and performance analysis of divisible load scheduling strategies on arbitrary graphs, Cluster Computing 7(2) (2004) 191-207]. When divisible loads originate from multiple sites, we test the performance on sparse, medium and densely connected networks. This is the first time in the divisible load theory (DLT) literature that such a generic approach for handling divisible loads originating from multiple sites on arbitrary networks employing load balancing via virtual routing is attempted. © 2006 Elsevier Inc. All rights reserved.
Source Title: Journal of Parallel and Distributed Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/55685
ISSN: 07437315
DOI: 10.1016/j.jpdc.2006.05.007
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

6
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

6
checked on Nov 17, 2017

Page view(s)

44
checked on Dec 17, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.