DECENTRALIZED PROPORTIONAL LOAD BALANCING

Abstract. Load balancing is a powerful technique commonly used in communication and com-puter networks to improve system performance, robustness and fairness. In this paper, we consider a general model capturing the performance of communication and computer networks, and on top of it we propose a decentralized algorithm for balancing load among multiple network paths. The proposed algorithm is inspired by the modus operandi of the processor-sharing queue and on each network entry point operates as follows: every time a unit of load completes its service on a path, it increases by one unit the load of that path and decreases by one unit the load of a path selected at random with probability proportional to the amount of load on each of the available paths. We develop a dynamical system to argue that our load-balancer achieves a desirable network-wide utility optimization. Key words. Multipath routing, decentralized load balancer, utility optimization, proportional fairness. AMS subject classifications. 68M10, 68W15, 90B18 1. Introduction. W