Please use this identifier to cite or link to this item: https://doi.org/10.1016/S0140-3664(03)00181-6
Title: Divisible load scheduling strategies on distributed multi-level tree networks with communication delays and buffer constraints
Authors: Veeravalli, B. 
Yao, J.
Keywords: Capacity constraints
Communication delays
Divisible loads
Load distribution
Processing time
Tree networks
Issue Date: 1-Jan-2004
Source: Veeravalli, B., Yao, J. (2004-01-01). Divisible load scheduling strategies on distributed multi-level tree networks with communication delays and buffer constraints. Computer Communications 27 (1) : 93-110. ScholarBank@NUS Repository. https://doi.org/10.1016/S0140-3664(03)00181-6
Abstract: In this paper, the problem of scheduling divisible loads on arbitrary tree networks is considered, with the objective to minimize the total processing time of the entire load. We consider an arbitrary tree network comprising heterogeneous processors interconnected via heterogeneous links. The divisible load is assumed to originate at the root processor in the network and the processors in the system are assumed to render only a finite amount of buffer space (capacity constraint) for processing the divisible load. For a special case of the problem instance wherein when all the processor-link pairs in the tree network can be utilized, we design an algorithm referred to as pull-push optimal load distribution algorithm to obtain an optimal solution. For the generic case, when the network has any redundant processor-link pairs (those pairs whose consideration in scheduling the load will penalize the performance) we propose three heuristic strategies to obtain the best possible time performance. These heuristics are based on applying systematic procedures to eliminate any redundant-link pairs and also using the optimal sequencing theorem proposed in the literature for single-level tree networks. We derive the worst and the best case complexities for all the algorithms proposed and present a discussion on the applicability of the algorithms on a wide range of network scenarios. We demonstrate all the above strategies with illustrative examples and evaluate their performance. © 2003 Elsevier B.V. All rights reserved.
Source Title: Computer Communications
URI: http://scholarbank.nus.edu.sg/handle/10635/55688
ISSN: 01403664
DOI: 10.1016/S0140-3664(03)00181-6
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

9
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

6
checked on Nov 18, 2017

Page view(s)

19
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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