Z. Zeng and B. Veeravalli (Singapore)
Static load balancing, distributed systems, mean responsetime, routing, non-preemptive scheduling
We propose a novel load balancing algorithm for a static load balancing problem that considers processing multi class jobs in distributed networks. Our objective is to min imize the mean response time of the jobs that arrive at the system. We formulate the problem as a constrained non linear minimization problem with job-flow rate, commu nication delays, and processing delays, as constraints. Us ing a systematic methodology, we transform the formulated problem into an equivalent virtual routing problem and pro pose an algorithm, referred to as Load Balancing via Vir tual Routing (LBVR). Thus, we establish a correspondence between the load balancing problem and the routing prob lem. We show that the proposed algorithm has several in teresting properties and guarantees to deliver a super-linear rate of convergence in obtaining an optimal solution, when ever it exists. With rigorous experiments we test the perfor mance of our algorithm in terms of its rate of convergence and quality of solution.
Important Links:
Go Back
