Please use this identifier to cite or link to this item:
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
Static load balancing
Issue Date: 1-May-2004
Citation: 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.
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
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.


checked on May 22, 2018


checked on May 15, 2018

Page view(s)

checked on May 19, 2018

Google ScholarTM



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