Design and analysis of a non-preemptive decentralized load balancing algorithm for multi-class jobs in distributed networks

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.