On Fully Distributed Adaptive Load Balancing

David Breitgand¹, Rami Cohen², Amir Nahir¹, Danny Raz²

¹IBM Haifa Research Lab, Israel
²Technion, Israel

Abstract. Monitoring is an inherent part of the management loop. This paper studies the problem of quantifying utility of monitoring in a fully distributed load balancing setting. We consider a system where job requests arrive to a collection of n identical servers. The goal is to provide the service with the lowest possible average waiting time in a fully distributed manner (to increase scalability and robustness). We present a novel adaptive load balancing heuristic that maximizes utility of information sharing between the servers. The main idea is to forward the job request to a randomly chosen server and to collect load information on the request packet as it moves on. Each server decides, based on that information, whether to forward the job request packet to another server, or to execute it locally. Our results show that in many practical scenarios this self-adaptive scheme, which does not require dedicated resources for propagating of load information and decision making, performs extremely well with respect to best known practice.