A static load balancing algorithm via virtual routing

Abstract

We propose a novel load balancing algorithm for a static load balancing problem that considers processing multiclass jobs in distributed networks. Our objective is to minimize the mean response time of the jobs that arrive at the system. We formulate the problem as a constrained nonlinear minimization problem with job-flow rate, communication delays, and processing delays, as constraints. Using a systematic methodology, we transform the formulated problem into an equivalent virtual routing problem and propose an algorithm, referred to as Load Balancing via Virtual Routing (LBVR). Thus, we establish a correspondence between the load balancing problem and the routing problem. We show that the proposed algorithm has several interesting properties and guarantees to deliver a super-linear rate of convergence in obtaining an optimal solution, whenever it exists. With rigorous experiments we test the performance of our algorithm in terms of its rate of convergence and quality of solution.