Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.comcom.2004.02.002
Title: Design and analysis of a non-preemptive decentralized load balancing algorithm for multi-class jobs in distributed networks
Authors: Zeng, Z. 
Veeravalli, B. 
Keywords: Communication delays
Distributed systems
Mean response time
Non-preemptive scheduling
Routing
Static load balancing
Issue Date: 1-May-2004
Source: Zeng, Z., Veeravalli, B. (2004-05-01). Design and analysis of a non-preemptive decentralized load balancing algorithm for multi-class jobs in distributed networks. Computer Communications 27 (7) : 679-693. ScholarBank@NUS Repository. https://doi.org/10.1016/j.comcom.2004.02.002
Abstract: In this paper, we propose a static, decentralized load balancing algorithm for handling multi-class jobs in distributed network system for minimizing the mean response time of a job, using the concept of virtual routing. We formulate the problem as a constrained non-linear minimization problem with job flow-rate, communication delays, and processing delays, as constraints. We employ a novel approach to transform the formulated problem into an equivalent routing problem and propose an algorithm, referred to as load balancing via virtual routing (LBVR), to seek an optimal solution, whenever it exists. We show that the design of the proposed algorithm subsumes several interesting properties and guarantees to deliver a super-linear rate of convergence in obtaining an optimal solution, whenever it exists. Also, when the variation of mean link delays is assumed to be a convex function, we show that the solution generated by our LBVR algorithm is indeed an optimal solution, whereas, when the above variation is assumed to be non-convex, we derive a necessary condition for an optimal solution. With rigorous experiments we test our algorithm in terms of its rate of convergence and quality of solution to quantify its performance. We demonstrate the complete workings of our algorithm using an illustrative example in a systematic fashion, for ease of understanding. © 2004 Elsevier B.V. All rights reserved.
Source Title: Computer Communications
URI: http://scholarbank.nus.edu.sg/handle/10635/55532
ISSN: 01403664
DOI: 10.1016/j.comcom.2004.02.002
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

16
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

15
checked on Nov 17, 2017

Page view(s)

26
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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